비디오 코덱을 작성해 봅시다 - 3부: 스틸 이미지

이 시리즈의 이전 부분에서 우리는 이산 코사인 변환(Discrete Cosine Transform)에 대해 수학적 정의부터 실제 예에서의 구현까지 배웠습니다. 또한 주파수 영역에서 데이터를 표현하는 DCT의 기능이 어떻게 손실이 있는 데이터 압축을 가능하게 하는지 살펴보았습니다.

이제 우리는 다음 단계를 밟고 있습니다. 우리는 마침내 우리가 논의해온 추상적인 숫자 배열과 그것이 나타낼 수 있는 실제 이미지를 연결하는 선을 그릴 것입니다.

이 기사가 끝날 때쯤이면 실제 JPEG 이미지 압축 프로세스의 약 80%를 재발견하게 될 것입니다.

매트릭스

이전 기사에서는 2D-DCT에 대해 소개했습니다. 이제 해당 공식을 약간 조정한 버전을 살펴보겠습니다.

변수 u 와 v DCT로 인코딩된 2D 배열 값의 수평 및 수직 오프셋을 나타냅니다. 함수 α(x) 는 x == 0 이면 1/sqrt(2) 와 같고 그렇지 않으면 1 입니다. 마지막으로 x 와 y 소스 이미지의 픽셀 위치를 나타냅니다.

이는 명백해 보이지 않을 수도 있지만 동일한 계산을 다음 형식의 행렬 곱셈으로 표현할 수 있습니다.

이 공식에서 DCT 는 DCT 행렬이고 T 행렬 전치를 나타내며 IMG 는 소스 이미지입니다.

이 작업의 복잡성은 소스 이미지의 크기에 비례한다는 점을 명심하세요. 모든 크기의 이미지를 관리하고 작업을 줄이기 위해 계산을 8x8픽셀 이미지 블록으로 제한하겠습니다.

실제 이미지는 해상도가 더 높은 경향이 있지만, 우리는 이를 여러 개의 독립적인 8x8 블록으로 구성되어 있다고 생각할 수 있습니다.

원하는 효과를 생성하는 DCT 행렬을 계산하는 방법은 다음과 같습니다.

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

dctMatrix 의 값은 다음과 같습니다.

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

보시다시피 그것은 단지 숫자의 배열일 뿐입니다. 변환을 적용할 때마다 행렬 값을 다시 계산할 필요가 없으므로 코드에서 상수 배열로 유지할 수 있습니다.

이 코드는 8x8 행렬 곱셈을 수행합니다.

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

8x8 DCT는 다음과 같이 계산됩니다.

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

역 DCT는 일반 및 전치 DCT 행렬을 교체하여 간단히 얻을 수 있습니다.

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

큰 그림

이제 우리가 알고 있는 지식을 실제 이미지에 적용할 준비가 되었습니다. 이것으로 작업해 봅시다:

이 이미지를 각각 해당 위치의 픽셀 밝기를 나타내는 숫자 배열로 로드하는 코드가 있다고 가정해 보겠습니다.

 func loadImage(width: Int, height: Int) -> [Float] { ... }

이미지가 256x256픽셀이라고 가정하면 다음 값은 왼쪽 상단 모서리에 해당합니다.

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

수학적 편의를 위해 픽셀 밝기를 0.0 에서 255.0 사이의 숫자로 표현하는 대신 128.0 뺍니다. 즉, 128.0 이 아닌 0.0 중심으로 값을 지정합니다.

그런 다음 이미지의 모든 8x8 블록에 dct 함수를 적용합니다.

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

결과는 다음 이미지입니다.

사진으로는 거의 인식이 안 되더라도 일부 패턴(모자 등)은 여전히 눈에 띕니다. 흥미롭게도 검은색 픽셀이 많이 있습니다. 실제로 대부분의 픽셀은 검은색입니다. 8x8 블록 중 하나를 확대해 보겠습니다.

이 8x8 블록은 주파수 영역 표현이 무엇인지 보여줍니다. 0이 아닌 값은 블록의 왼쪽 상단에 모이는 경향이 있습니다. 오른쪽 하단 모서리로 갈수록 큰 값이 나올 가능성은 크게 감소합니다.

이는 왼쪽 상단 값이 이미지에 더 중요하다는 것을 나타냅니다.

오른쪽 하단 값 중 일부를 0.0 으로 설정하여 제거하는 "압축" 함수를 작성하여 이를 입증할 수 있습니다.

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

처리 루프를 조정한 후:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

우리는 다음 이미지를 얻습니다.

무슨 일이 일어났는지 잠시 생각해 보세요. 각 이미지 블록의 64개 값 중 39개를 제거했지만 여전히 원본과 매우 유사한 이미지를 생성했습니다. 이는 행렬을 곱하고 결정론적으로 데이터를 삭제함으로써 달성된 60% 압축률입니다!

DCT 계수의 86%를 버리면 다음과 같은 일이 발생합니다.

양자화

일반적으로 4바이트의 저장 공간이 필요한 DCT 계수를 부동 소수점 숫자로 저장하는 것은 엄청나게 낭비입니다. 대신 가장 가까운 정수로 반올림해야 합니다. 8x8 블록의 경우 각 값은 2바이트 정수로 표시될 수 있습니다.

앞서 살펴본 블록을 다시 살펴보겠습니다. (반올림된) 숫자 표현은 다음과 같습니다.

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

이전에 시각적으로 확인한 것처럼 왼쪽 상단에 가까울수록 더 큰 값이 발생할 가능성이 높습니다. 그러나 모든 블록이 이 패턴을 따르는 것은 아닙니다. 다음은 이미지의 또 다른 블록입니다.

이 블록은 DCT 값의 공통 분포를 따르지 않습니다. 오른쪽 하단 값을 계속해서 무시하면 이미지의 일부 부분에 더 많은 압축 아티팩트가 표시될 수 있습니다. 이를 방지하려면 어떤 블록이 다른 블록보다 더 많은 데이터를 필요로 하는지 결정해야 합니다.

간단하면서도 우아한 솔루션은 앞서 발견한 클러스터링 속성을 활용합니다. 이를 "양자화"라고 합니다. DCT 값을 다양한 계수로 나눕니다. 편의를 위해 각 DCT 계수에 대한 값이 포함된 테이블을 사용하겠습니다.

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

더 중요한 위치는 더 낮은 약수에 해당하며 그 반대도 마찬가지입니다. 양자화된 데이터에 테이블의 계수를 곱하여 역양자화 단계를 수행합니다.

이러한 함수는 각각 양자화 및 역양자화 단계를 수행합니다.

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

양자화와 역양자화를 코드에 통합해 보겠습니다.

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

양자화되었을 때 첫 번째 블록의 모습은 다음과 같습니다.

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

그리고 이것은 두 번째 블록입니다.

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

두 번째 블록에는 0이 아닌 값이 더 많이 있다는 것을 알 수 있습니다. 따라서 양자화 단계를 통해 더 유용한 데이터를 저장하고 나머지는 버릴 수 있습니다.

결론과 다음은 무엇입니까?

기본적인 수학부터 실제 이미지를 인코딩하고 디코딩하는 방법을 알아냈습니다. 우리는 DCT가 임의의 데이터를 주파수 세트로 변환하는 방법과 일부 주파수가 다른 주파수보다 얼마나 중요한지 시각적으로 확인했습니다.

기본 압축에 익숙해진 후에는 양자화 개념을 도입하여 스토리지 요구 사항을 더욱 줄였습니다.

다음 부분에서는 RGB 이미지로 이동하여 결과 데이터를 더욱 압축하는 방법을 살펴보겠습니다.

이 기사의 코드는 https://github.com/petertechstories/image-dct 에서 찾을 수 있습니다.