영상 압축

<영상부호화 및 압축>

- 무손실 및 손실 압축

  - 손실 압축 : VQ(Vector Quantization), JPEG

  - 무손실 압축 : Huffman, DPCM(Differential Pulse Coded Modulation), RLE(Run Length Encoding)

 

 

 

 

 

 

<허프만(Huffman) 부호화>

- 영상에서 그레이 값들을 표현하는데 고정길이코드(8비트)를 사용하지 않고 가변길이코드를 사용하는데,

  영상 내에서 그레이 값들이 확률적으로 자주 나오는 값일수록 보다 짧은 코드를 사용하는 것이다

- 즉, 발생빈도가 많이 나오는 코드는 짧게 표현하고 발생빈도가 적게 나오는 코드는 길게 표현 -> 가변길이(Variable Length Coding)

 

 

Gray value  Probability  Fixed code  Variable code

    0               0.2          00             000  

    1               0.4          01                1

    2               0.3          10               01

- 화소 당 평균 비트수 : 0*0.2 + 1*0.4 + 2*0.3 = 1

 

 

 

 

 

<엔트로피(Entropy)>

- 정보의 양을 측정

- 엔트로피 H는 정보의 손실이 없이 영상을 부호하하는데 요구하는 화소 당 이론적 최소의 비트수

- H = -{시그마 i=0~(L-1)p(i)*log2(pi)}

 

- 주어진 영상에 대하여 허프만부호를 구하기 위해 아래와 같은 과정으로 진행

  1. 영상에서 각 그레이 값의 확률을 구한다

  2. 이진 트리로부터 가장 낮은 확률을 취하여 더한다

  3. 그 꼭지 점에서 트리의 각 가지에 임의로 0과 1을 할당한다

  4. 위에서 아래로 부호(코드)로 읽는다

 

 

 

 

 

<호프만 복호화>

- 허프만부호화는 유일하게 복호될 수 있고, 일발통행으로 문자열이 복호될 수 있다

- 어떤 코드도 다른 코드의 접두사가 될 수 없다

- 무손실 압축이다

 

 

 

 

 

<줄길이 부호화(Run-length coding)>

- 각 수열에서 반복되는 0과 1을 부호화하는 것

- RLE는 팩스전송에서 표준으로 사용되고 있다

- 그레이 부호(Gray codes) : 그레이 값들을 보호화 할 수 있다

  - 그레이 부호는 하나의 수열과 다음 수열 사이에 단지 하나의 비트만 변화하도록 주어진 길이의 모든 2진 수열을 순서화하는 것

  - 그레이부호평면은 하나의 비트평면을 제외하고는 높은 상관을 가지며, 여기서 모든 이진비트평면은 무상관을 가진다

 

 

 

 

 

<JPEG 알고리즘>

- 손실압축은 압축률을 높이기 위해 데이터 일부의 손실을 허용한다

  가능한 많은 방법 중에서 Joint Photographic Expert Goup(JPEG)에서 알고리즘이 가장 널리 사용되고 있다

- 영상이 화소 그 자체가 부호화되지 않고 변환부호화(transform coding)를 이용한다

- 이 알고리즘의 핵심은 'Discrete Cosine Transform(DCT)' 이다

- 어떤 사이즈의 배열도 적용할 수 있지만, JPEG 알고리즘은 오로지 8x8 블록(64개의 데이터)을 적용한다

- 이 알고리즘은 저주파영역에서 정밀하게 처리되며, 이 경우에 원래 블록이 매우 적은 오차범위 내에서 복원될 수 있다

- JPEG 압축을 blkpro 함수(block processing)를 이용하여 실험할 수 있고,

  이 함수는 영상에서 각 블록 단위로 함수를 적용하며 blkpro 함수는 파라메터로서 주어지는 블록사이즈로 처리된다

- jpg_in : 8x8 블록으로 압축, jpg_out : 복원

- 각 함수에 대하여 구체적인 파라메터 n을 포함하는데 이것은 정규화 매트릭스를 스케일링하는데 사용된다

 

- DCT는 특히 압축에 적합한 여러 가지 성질을 가지는데 이는 아래와 같다

  1. 복잡한 복소수를 필요로하지 않고 실수의 값을 가진다

  2. 이는 작은 수의 계수로 많은 정보량을 묶을 수 있기 대문에 높은 정보의 묶음을 가진다

  3. 하드웨어 구현에 매우 효과적이다

  4. FFT와 같이 최대의 효율을 가지는 변환이 가능하다

  5. 기저값(basis values)은 데이터와 무관하다

 

- High Energy compaction property : 저주파에 영상정보의 대부분이 모여 있다

 

- JPEG의 기본적 압축구조는 다음과 같이 적용된다

  1. 영상을 8x8 블록으로 나누고 각 블록을 변환하며 압축은 블록 단위로 이루어진다

  2. 주어진 블록에 대하여, 해당 값들은 각 값에서 128을 빼서(8x8의 중간값) 시프트된다

  3. DCT는 이 시프트된 블록에서 적용된다

  4. DCT 값들은 정규화 매트릭스 Q로 나누어서 정규화된다. 이 정규화 값들은 해당 블록 내 대부분의 요소들이 0이 되어서 압축이 된다

  5. 이 매트릭스는 아래와 같이 그림과 같이 지그재그 순서로 왼쪽 위에서 모두 0이 아닌 값들을 벡터로 간주한다

  6. 각 벡터의 첫째 계수는 벡터에서 가장 큰 값이고, 이는 DC 계수이며, 각 값과 이전 블록에서의 값의 차이를 리스트에 의해 부호화된다

  7. 이들 값들은 RLE를 이용하여 다시 압축된다

  8. 모든 나머지 값들(AC 계수들)은 허프만부호화를 이용하여 압축된다

 

- 압축을 풀기 위해 위의 단계들을 역으로 적용하는데, 허프만부호화와 RLE는 정보의 손실 없이 복원될 수 있다

  복원하는 과정

  1. 벡터는 8x8 매트릭스로 돌아가서 읽혀진다

  2. 이 매트릭스는 정규화 매트릭스와 곱해진다

  3. 이 결과에 역 DCT가 적용된다

  4. 이 결과는 원래 영상을 얻기 위해 128까지 되돌려서 시프트된다

 

- 2차원 DCAT와 역 DCT는 각각 함수 dct2와 idc2로 구현될 수 있다