[영상처리] Compression

이미지는 기본적으로 용량이 크다. 예를 들어, 흑백 이미지가 1024 x 1024이고, 픽셀당 8 bit이라면, 1024 x 1024 x 8bits 정도의 데이터가 필요하다. 컬러 이미지라면 RGB 3채널이므로 3배의 크기가 필요하다. 그래서 이미지를 저장하거나 전송할 때 압축이 필요하다. 압축에는 두 가지의 종류가 있다.

• 무손실 압축(Lossless compression) : Huffman, Run-length
• 손실 압축(Lossy compression) : JPEG

무손실 압축과 손실 압축의 차이는 말 그대로 압축하는 과정에서 정보의 손실이 있느냐 없느냐로 구분할 수 있다. 

---

Lossless compression

Huffman coding

Huffman coding의 핵심은 간단하다. 자주 나오는 값에는 짧은 비트열을 주고, 드물게 나오는 값에는 긴 비트열을 준다. 예를 들어, 어떤 이미지에서 gray value가 다음 확률로 나온다고 가정하자.

Fixed code라면 값이 4개니까 각각 2bit가 필요하다. 반면, Variable code를 사용한다면, 자주 나올 확률이 높은 gray value에 대하여 짧은 비트열인 1을 할당함으로써 평균 bit 수를 줄일 수 있다.

이렇게 bit 수를 줄임으로써 얼마나 압축이 가능할까? 이를 확인하기 위해 Entropy 라는 개념이 나온다. Entropy는 쉽게 말해 무손실로 압축할 때 이론적으로 필요한 최소 평균 bit 수를 의미한다.

여기서 p_i는 값 gray value가 등장할 확률을 의미한다. 각 gray value의 확률이 0.2, 0.4, 0.3, 0.1이라고 가정했을 때, Entropy는 다음과 같이 계산된다.

즉, 아무리 압축을 잘해도 평균적으로 약 1.8464 bit/pixel 보다 더 낮추기는 어렵다는 의미이다.

그래서 huffman coding은 어떻게 진행되는가 알아보자. 우선 무작정 자주 나오는 값에 짧은 코드를 아무렇게나 주면 안된다. 왜냐하면 복원이 안될 수 있기 때문이다. A라는 값에 대해 코드 1을 주고 B라는 값에 대해 코드 10을 주고, C라는 값에 대해 코드 11을 주었다고 가정하자. 이 경우 압축된 비트열이 11이면 이 코드가 C인지 AA인지 알아보기 어렵다. 따라서 짧은 code를 주되, 복원할 때 헷갈리지 않은 code 체계를 만들어야 한다. 그래서 필요한 조건이 prefix-free code이다.

Prefix-free code란, 어떤 code도 다른 code의 앞부분이 되지 않는 코드 체계를 의미한다. 그럼 짧은 code와 긴 code를 적절히 배치하면서, 동시에 복원 가능한 prefix-free code를 어떻게 만들까? 이에 대한 답이 바로 Huffman tree이다.

Huffman tree는 다음 두 가지를 동시에 만족시키기 위해 등장한다.

1. 자주 나오는 값은 짧은 code를 갖게 한다.
2. 전체 code가 prefix-free가 되도록 만든다.

Huffman tree를 만드는 과정은 다음과 같다.

1. 이미지의 각 gray value 확률을 구한다.
2. 확률이 가장 작은 두 개를 묶는다.
3. 묶은 값을 다시 하나의 노드로 보고 또 가장 작은 두 개를 묶는다.
4. 전체 확률이 1이 될 때까지 위 과정(3)을 반복한다.
5. 트리의 가지에 0과 1을 붙인다.
6. root에서 leaf까지 내려가며 codeword를 읽는다.

---

Run-length Encoding, RLE

Run-length Encoding은 같은 값이 연속되는 구간을 반복 횟수로 표현한다. 예를 들어, 0000011111000 이 있으면, 이는 "5,5,3" 처럼 표현할 수 있다. 이 방식은 특히 값이 0과 1뿐인 binary image에서 좋다. 그러나 일반적인 이미지에서는 사용하기 어렵다. 예시로, 128 129 130 128 131 128 130 ... 이런식으로 사람 눈으로 구분하기 어려운 픽셀값에 대해서 RLE로 표현하면 "(128, 1), (129, 1), (130, 1), (128, 1), (131, 1), (128, 1), (130, 1)" 이런 식으로 오히려 데이터가 더 커질 수 있기 때문이다.

---

Lossy compression

JPEG

무손실 압축으로는 충분히 줄이기 어렵다. 따라서 손실 압축을 사용하게 되는데, 손실 압축의 배경은 다음과 같다. 우선 사람의 눈은 모든 정보를 똑같이 민감하게 보지 않는다. 예를 들어 전체적인 밝기 변화나 큰 구조는 잘 느끼지만, 아주 미세한 고주파 질감 변화에는 상대적으로 둔감하다.

고주파 얘기가 나와서 주파수 영역에 대해 간단하게 소개하자면, 이미지를 바라보는 관점이 공간 영역에서 픽셀값의 변화량의 영역으로 바꾼 것이다. 즉, 이미지를 바라볼 때 픽셀값으로 이미지를 바라보는 것이 아닌 인접한 픽셀값들 사이의 차이, 즉 변화량으로 이미지를 바라보는 것이며, "미세한 고주파 질감 변화" 는 인접한 두 픽셀 사이의 변화량이 큰 픽셀의 관계를 말한다.

아무튼 다시 본론으로 돌아와서 사람이 잘 못 느끼는 세부 정보는 줄이고, 중요한 구조는 보존하면 용량을 훨씬 줄일 수 있지 않을까? 가 손실 압축인 JPEG의 출발점이다. 

그런데 어떤 정보가 중요하고 덜 중요한지 어떻게 알 수 있을까? 

이미지는 픽셀 값으로 저장되어 있다. 픽셀 값 그대로 보면 어떤 값이 중요한지 판단하기 어렵다. 따라서 이미지를 바라보는 관점을 주파수 영역으로 바꾼다. 이때 사용하는 변환이 바로 DCT이다. 

DCT로 변환한 이후에는 Quantization을 해준다. 압축 과정을 대략적으로 표현하면 다음과 같다.

1. 이미지를 작은 block으로 나눈다.
2. 각 block에 DCT를 적용한다.
3. Quantization을 한다.
4. Zigzag scanning을 한다.
5. Entropy coding을 한다.

복원 과정은 다음과 같다.

1. Entropy decoding
2. Inverse quantization
3. Inverse DCT
4. Block들을 다시 합침

DCT

DCT는 이미지를 여러 주파수 서분으로 나누는 역할을 한다. 쉽게 말하면 8x8 block 하나를 다음과 같은 성분들의 조합으로 표현하는 것이다.

• 전체적으로 밝은 정도
• 천천히 변하는 성분
• 빠르게 변하는 성분
• 세밀한 경계나 질감

같은 성분들의 조합으로 표현된다. 수식은 다음과 같다. 참고로, DCT는 이미지 block을 여러 cosine basis 패턴의 조합으로 표현하는 변환이다. JPEG에서는 0~255 범위의 픽셀값을 그대로 DCT에 넣기보다, 각 값에서 128을 빼서 -128~127 정도의 0 중심 데이터로 이동시킨 뒤 DCT를 적용한다. 이렇게 하면 block의 평균 밝기 성분이 한쪽으로 크게 치우치는 것을 줄이고, 밝기 변화 성분을 더 다루기 좋은 형태로 변환할 수 있다.

 4x4 block을 주파수 영역으로 변환했다고 하자. 각 자리는 다음과 같이 해석할 수 있다.

• F(0, 0) : 전체 평균 밝기 성분
• F(1, 0) : x방향으로 천천히 변하는 성분
• F(0, 1) : y방향으로 천천히 변하는 성분
• F(3, 3) : x, y 방향으로 빠르게 변하는 고주파 성분

일반적으로 DCT의 결과에서 왼쪽 위는 저주파 성분, 오른쪽 아래는 고주파 성분으로 해석한다. 즉, F(0, 0) 근처는 이미지의 큰 구조를 담고 F(3, 3) 근처는 세밀한 변화나 질감을 담는다.

DCT만 한다고 압축이 되는 것은 아니다. 실제로 용량을 줄이는 과정은 Quantization을 진행해야 한다.

8x8 block에 대해 각 pixel값 - 128

DCT 변환

Quantization

DCT의 결과를 해석하면 다음과 같다. 사람의 눈이 민감하게 반응하는 정보는 왼쪽 위에 저주파 성분으로 몰려 있고, 덜 민감하게 인식하는 정보는 오른쪽 아래인 고주파 성분으로 몰려있다. 

따라서 오른쪽 아래인 고주파 성분을 대충 저장하거나 0으로 만들면 되지 않을까? 라는 생각에서 출발한 것이 바로 Quantization이다. 각 자리에 대응하는 matrix로 나누고 반올림을 해준다. 

왼쪽 위 저주파 영역은 값을 비교적 많이 반영해야하므로 작은 값으로 나누고 반올림을 해주는 반면, 오른쪽 아래 고주파 영역은 0이 되도 상관없기 때문에 큰 값으로 나누고 반올림을 해준다. 결과는 다음과 같다.

이런식으로 Quantization을 진행하면 된다. 그렇다면 손실은 어디서 발생할까? 바로 올림을 하는 부분에서 발생한다. (0, 0) 위치의 -415에 대해서 16으로 나눈 후 반올림을 한 결과가 -26이다. 이 -26을 다시 16으로 곱하여 복원을 하면 -416이 된다. 처음 -415와 1이 차이가 나게 된다. 정리하자면 Quantization에서 나누고 반올림하면서 원래 DCT coefficient의 정확한 값이 사라지는 현상이 발생하여 손실이 생기는 것이다.

Zigzag scanning

Quantization 이후에는 값을 지그재그로 읽어준다. EOB는 End Of Block이라는 의미로, 이 뒤는 모두 0이 되기 때문에 더 이상 저장하지 않겠다는 의미이다.