압축의 원리에 대해서 알아보자! (허프만 코딩 알고리즘)

● 압축

​

​  기본적으로 압축의 원리는 공간적으로 중복 성격의 데이터가 존재한다는 '공간적 상관관계'와 영상에서 시간이 지나도 화면에 큰 차이가 없는 경우가 있다는 '시간적 상관관계'라는 특성을 바탕으로 합니다. 즉, 유사한 데이터의 반복을 압축함으로써 용량을 줄일 수 있다는 원리에 입각하는 것입니다. 압축의 종류는 손실 압축과 무손실 압축으로 나눌 수 있습니다. 먼저 손실 압축은 중복되고 필요하지 않은 정보가 손실되는 것을 허용하는 것을 말합니다. 인간의 시각으로는 감지할 수 없는 자료를 제거하는 것이 그 예시입니다. 그 다음으로 무손실 압축은 처리상에서 자료의 손실이 없으며 입출력 영상이 완전히 동일하도록 압축하는 것을 의미합니다. 의료영상, 설계도면 등에서 활용됩니다.

​

  인간의 최소 가청 한계에 의하면 인간은 약 1KHz에서 2KHz 정도의 소리를 듣는데 수월하게 설계되어있습니다. 마스킹 효과란 '특정 주파수가 가지는 에너지가 다른 주파수의 에너지보다 훨씬 클 때 이를 마스커 주파수라고 말하며 마스커 주파수만 유독 잘 들리게 되는 효과'를 말합니다. 결과적으로 마스커 주파수를 위주로 필터링을 하면 듣기에는 비슷하지만 용량은 훨씬 줄일 수 있게 됩니다. MP3 또는 MPEG Layer 3는 이러한 마스킹 효과를 이용합니다. MP3는 오디오 데이터의 압축기술로서 MPEG-1 기능 사양 중 일부입니다. MPEG-1의 오디오 부분의 Layer 3를 MP3라는 이름으로 사용합니다. Layer 3의 경우 압축률이 10 ~ 12정도 되기 때문에 상당히 효율적입니다. 곡 전체의 정보를 담는 헤더 뒤에 데이터가 프레임이라는 단위로 저장되며 프레임의 크기는 고정되어 있어 압축률이 높은 부분에서도 쓸모 없는 용량을 차지한다는 단점을 가지고 있습니다.

​

​  압축과 관련하여 가장 유명한 두 방식이 바로 Run Length Coding 방식과 허프만 코딩(Huffman Coding) 방식입니다.

​

​ - Run Length Coding

​

  AAAAAAABBCCCDEEEEFFFFFFG라는 텍스트가 있을 때 이것을 각각 '문자 X 반복 횟수'로 표현하는 방법입니다. 저 텍스트는 원래 24개의 문자를 가져 24바이트의 용량이지만 A7B2C3D1E4F6G1으로 표현이 가능하기 때문에 결과적으로 14바이트로 줄어들게 됩니다. 따라서 압축에 성공한 것입니다. 하지만 이러한 방식에 문제점이 많아 나중에 '전치문자'라는 것을 사용하게 됩니다. 반복되는 문자는 '전치문자 X 반복된 횟수 X 반복 문자'와 같은 방식으로 적용이 됩니다. 이러한 방식으로 위 텍스트를 다시 표현해보면 *7A*2B*3CD*4E*6FG가 됩니다. 반복되지 않는 문자는 그대로 쓰는 것입니다.

​

 - 허프만 코딩(Huffman Coding)

​

​  대부분의 압축 프로그램에서 사용하는 방법입니다. 자주 사용되는 문자는 적은 비트로 된 코드로 변환해서 표현하고, 별로 사용되지 않는 문자는 많은 비트로 된 코드로 변환하여 표현함으로써 전체 데이터를 표현하는 데 필요한 비트의 양을 줄이는 방법입니다. 허프만 코딩에서는 압축 대상이 되는 데이터마다 최대한 효율적으로 압축될 수 있게끔 코드를 생성하고 그 체계에 따라 압축합니다. 그렇게 되려면 데이터마다 각 문자에 대한 특정 코드가 정해져야만 하는데 이 때 필요한 것이 허프만 트리입니다.

​

  아래는 허프만 코딩에 관한 문제입니다.

 

< 문제 >

다음 데이터는 R, G, B, C, M, Y, K를 사용하여 나타낸 이미지입니다. 픽셀의 깊이는 16비트라고 가정했을 때 각각의 문항에 답하세요.

 

R	G	Y	G
B	B	R	R
C	R	K	C
K	B	G	R
C	B	C	K
G	M	B	G
C	G	G	C
B	B	G	R

​

1) 원본 이미지의 용량을 계산하세요.

 

이미지의 가로 픽셀 수는 4개, 세로 픽셀 수는 8개, 각 픽셀 당 16비트를 할당하므로 원본 이미지의 총 용량은 4 X 8 X 16 = 32 x 16 = 512 bit입니다.

 

2) 허프만 코딩을 했을 때 각 색상의 코드 값을 설명하세요.

 

데이터에서 사용되는 각 문자에 대한 출현 빈도수를 구하면 아래와 같습니다.

 

문자	R	G	B	C	M	Y	K
출현빈도	6	8	7	6	1	1	3

​

빈도수를 기준으로 내림차순으로 정렬하면 아래와 같습니다.

​

 

이후에 가장 작은 문자의 집합을 2개씩 계속해서 합치는 과정을 반복해 허프만 코드를 작성하면 아래와 같은 과정을 거치게 됩니다.

 

 

 

위와 같이 최종 호프만 코드가 완성되었습니다. 왼쪽의 경로는 0, 오른쪽의 경로는 1의 코드를 붙여서 코드를 정리하면 아래와 같이 표로 정리가 가능합니다.

색상	비트
G	01
B	10
R	11
C	000
K	0010
M	00110
Y	00111

 

3) 허프만 코딩 후 이미지의 용량을 계산하세요.

 

허프만 코드표에는 각각의 색상에 대한 비트 수가 붙어있습니다. 이것을 이용해 빈도수와 각각 곱해서 계산하면 다음과 같이 계산할 수 있습니다.

 

2 X 8 + 2 X 7 + 2 X 6 + 3 X 6 + 4 X 3 + 5 X 1 + 5 X 1 = 82 bit

 

4) 압축률을 계산하세요.

 

압축률은 ‘원시 자료 : 압축된 자료’로 계산할 수 있습니다. 이 경우에는 512bit에서 82bit로 압축이 이루어졌기 때문에 압축률은 256 : 41로서 약 6입니다.