JPEG(1) - JPEG원리

출처 : http://php.chol.com/%7Emrjin

JPEG

JPEG(보통 ‘제이펙’이라고 읽는다.)은 높은 압축 효율 때문에 GIF와 함께 인터넷에서 가장 널리 쓰이는 그래픽 파일 포맷이다. JPEG은 Joint Photographic Experts Group이라는 위원회에서 정한 그래픽 이미지 압축에 관한 표준을 의미한다. JPEG이라는 이름도 이 위원회의 이름에서 유래한 것이다. (이와 비슷하게 동화상 압축에 관한 표준이 만들어졌는데 그것이 바로 MPEG이다. MPEG은 Motion Picture Experts Group에서 만든 표준이다.) JPEG 표준은 ISO(국제표준화기구) 10918-1에 정의되어 있다. JPEG 표준은 그래픽 이미지 압축에 대한 표준만 정해놓았을 뿐 구체적인 구현 방법은 정의하고 있지 않다. 우리가 지금까지 살펴본 BMP, PCX, GIF 그래픽 파일들은 어떤 헤더 구조를 가지고 있으며 그래픽 정보를 어떻게 저장하는지 각 그래픽 파일 규격에 구체적으로 정의되어 있다. 하지만 JPEG 표준은 그래픽 파일 포맷에 대한 규격은 전혀 언급하고 있지 않다. 심지어 어떤 방식의 색상 체계를 쓰는지도 정의되어 있지 않다. 구체적으로 어떤 색상 체계를 사용하며 어떤 파일 포맷으로 그래픽 이미지를 저장하는지에 대한 규격은 JFIF(JPEG File Interchange Format)에 정의되어 있다. JFIF는 C-Cube Microsystems의 Eric Hamilton에 의해 만들어졌으며 누구나 사용할 수 있도록 public domain에 공개되어 있다. 우리가 흔히 접하는 확장자가 JPG인 JPEG 그래픽 파일은 대부분 JFIF로 되어있다. 사실 JFIF는 JPEG 위원회나 어떤 기구에 의해 표준으로 정해진 포맷은 아니다. 하지만 시간이 가면서 널리 쓰이다 보니 표준 아닌 표준이 되어 버렸다. JPEG 위원회에서 뒤늦게 SPIFF(Still Picture Interchange File Format)라는 파일 포맷 표준을 내놓았지만 이미 수 많은 JPEG 이미지 파일들이 JFIF로 되어 있기 때문에 그렇게 각광을 받지는 못하고 있다. 여전히 수 많은 그래픽 소프트웨어들이 JPEG 이미지 파일로 JFIF를 사용하고 있다. 우리가 살펴볼 JPEG 이미지 파일도 JFIF이다.

JPEG의 종류 :

ISO10918-1 표준은 그림 1과 같이 압축 방식, 코딩 방식, 샘플링 크기 등에 따라 JPEG 모드를 여러 개로 나누어 놓았다.

JPEG
Sequential				Progressive				Lossless		Hierarchical
Huffman		Arithmetic		Huffman		Arithmetic		Original Lossless	JPEG-LS
8 bit	12bit	8 bit	12bit	8 bit	12bit	8 bit	12bit

그림 1 여러 가지 JPEG 모드

Sequential 방식은 그래픽 이미지 맨 위부터 아래로 순차적으로 데이터를 저장하는 방식이고 Progressive 방식은 GIF의 Interlaced 모드와 비슷하게 그래픽 이미지를 여러 번 스캔하여 점진적으로 이미지가 뚜렷하게 보이도록 하는 방식이다. GIF의 Interfaced 모드는 몇 줄씩 건너뛰면서 여러 번에 걸쳐 그래픽 이미지를 출력한다. 매번 출력 때마다 그 전에 비어있던 줄을 채워 넣어 그래픽 이미지를 완성한다. JPEG progressive 방식도 여러 번에 걸쳐 그래픽 이미지를 출력하지만 GIF처럼 그림의 일부만 출력하는 것이 아니라 일단 전체 이미지를 모두 출력한다. 단, 마치 포커스가 제대로 맞지 않은 사진처럼 흐릿한 이미지만 출력한다. 그 다음 출력 때 점점 포커스가 맞추어지는 것처럼 보다 더 명확한 이미지를 출력한다. GIF의 경우와 마찬가지로 전체 데이터를 다 전송하지 않고도 어떤 이미지인지 알 수 있게 하기 위해 이런 방식을 사용한다. Hierarchical 방식은 Progressive 방식의 보다 더 진보된 형태이다. 같은 그래픽 이미지를 표현하고 있지만 화질이 서로 다른 이미지를 frame 단위로 여러 개 저장하는 방식이다. 전송 속도가 느린 경우 원하는 화질의 이미지 frame만 전송할 수 있다.

Lossless 방식은 말 그대로 화질 저하가 없는 방식이다. 뒤에 설명하겠지만 JPEG은 높은 압축률을 구현하기 위해 사람 눈이 구분하지 못할 정도로 미세하게 데이터를 생략하는 방식을 사용한다. 그래서 BMP 또는 GIF 그래픽 이미지에서 JPEG 이미지로 변환을 하면 약간의 화질 저하가 있다. BMP --> PCX --> BMP 변환을 아무리 여러 번 수행해도 화질의 변화가 없지만 BMP --> JPEG --> BMP 변환을 수행하면 할수록 점점 화질 저하가 누적된다. Lossless 방식은 전혀 압축을 하지 않는 대신 화질의 변화를 주지 않는 방식이다. JPEG-LS 역시 화질의 변화 없이 저장하는 방식인데 원래 Lossless 방식과는 구현 방법이 다르다.

GIF 그래픽 파일에서 LZW 코딩 방식으로 데이터를 압축 저장하듯이 JPEG도 그래픽 데이터를 압축해서 저장하기 위해 Huffman 코딩이라는 압축 방식을 사용한다. Arithmetic 방식은 구현 방법만 다를 뿐 Huffman 코딩 방식과 똑같은 코딩 방식이다. Arithmetic 방식은 특허로 보호 받기 때문에 함부로 사용할 수 없다.

또한 JPEG 그래픽 이미지는 각 픽셀의 색상을 8비트 또는 12비트로 표현할 수 있다. 우리가 흔히 접하는 JPG 파일은 8비트로 색상을 표현한다.

이렇게 많은 종류의 JPEG 모드 가운데 가장 널리 사용되는 방식은 Sequential – Huffman – 8비트 방식이며 Progressive - Huffman - 8비트 방식의 JPEG 파일도 많이 쓰인다.

JPEG 파일의 원리 :

JPEG 파일, 엄밀하게는 JFIF 포맷의 원리와 구조에 대해 간단하게 알아보자. JPEG 파일은 그림 2와 같은 과정을 거쳐 압축이 된다.

그림 2 JPEG 압축 과정

Sampling은 RGB 색상 체계를 Y-Cb-Cr 색상 체계로 변환하는 과정이다. 이때 Cb, Cr 성분을 구할 때 일부 성분들은 생략되므로 압축의 효과를 가져온다. DCT는 샘플링된 데이터를 코사인 함수의 합으로 변환하는 과정이다. 이렇게 변환된 데이터에서 원래 데이터를 크게 변화시키지 않을 만큼 불필요한 성분들을 제거한다. 이 과정을 양자화(quantization)이라고 한다. 양자화를 거처 압축된 데이터는 Huffman 코딩이라는 압축 알고리즘을 통해 압축이 된다. 양자화 과정에서 한번 압축이 일어나고 Huffman 코딩에서 또 한번 더 압축이 일어나 압축 효율이 극대화되는 것이다. 양자화에 의한 압축은 원래 데이터를 일부 제거하기 때문에 JPEG 이미지의 화질 저하의 원인이 된다. Huffman 코딩은 Lossless 압축 방식이므로 JPEG 이미지 화질 저하와는 관련이 없다.

이렇게 압축된 JPEG 이미지를 복원하려면 위의 과정을 역순으로 행하면 된다. 먼저 Huffman 디코딩을 통해 압축을 풀어 양자화된 데이터를 얻어낸다. 양자화된 데이터는 역 양자화(de-quantization)을 통해 원래 DCT 성분으로 복원된다. 물론 양자화 때문에 완벽하게 100% 원래 성분들을 모두 복원할 수는 없으나 사람의 눈에는 거의 뜨이지 않을 정도로 복원이 가능하다. 복원된 DCT 성분들은 IDCT 변환을 통해 Y-Cb-Cr 데이터로 변환된다. 이렇게 해서 얻은 Y-Cb-Cr 데이터는 Up-sampling 과정을 통해 다시 R,G,B 색상 체계로 변환되어 원래 모습을 찾게 된다. 물론 100% 똑같은 이미지는 아니지만.

지금까지 설명한 과정들이 아마도 쉽게 들어오지 않을 것이다. 보다 더 자세하게 각 과정들을 설명하도록 하겠다.

색상 체계 : JPEG 파일이 사용하는 색상 체계는 Y-Cb-Cr 색상 체계로 앞에서 살펴본 YIQ 색상 체계와 비슷한 방식이다. Y는 밝기를 나타내고 Cb, Cr이 색상을 나타낸다. 원래 Y는 0에서 1사이, Cb, Cr은 –0.5에서 0.5 사이의 값을 가지지만 JPEG 파일은 Y, Cb, Cr 모두 0에서 255의 범위를 가진다. 다음은 RGB에서 YCbCr, YCbCr에서 RGB로 변환하는 공식이다.

Y = 0.299 R + 0.587 G + 0.114 B
Cb = - 0.1687 R - 0.3313 G + 0.5 B + 128
Cr = 0.5 R - 0.4187 G - 0.0813 B + 128

R = Y + 1.402 (Cr-128)
G = Y - 0.34414 (Cb-128) - 0.71414 (Cr-128)
B = Y + 1.772 (Cb-128)

JPEG 파일은 YCbCr 세 개의 성분 가운데 어느 한 성분(보통 Y성분)만 저장하거나 세 성분 모두를 저장할 수 있다. Y성분만 저장하는 것은 256 level gray 색상으로 저장하는 것을 의미한다. 실제 JPEG 파일에 Y,Cb,Cr 데이터가 저장될 때는 128씩 뺀 값이 저장된다.

Sampling : 지금까지 살펴본 BMP, PCX, GIF와 같은 그래픽 파일들은 한 픽셀의 색을 나타내기 위해 R, G, B 색상 체계를 사용하였으며 3가지 성분 모두 같은 비율로 저장되었다. 하지만 JPEG 파일에서는 Y, Cb, Cr이 서로 다른 비율로 저장될 수 있다. 예를 들어 매 픽셀의 Y 성분을 모두 저장하는 반면 Cb, Cr은 한 픽셀씩 건너 뛰면서 저장할 수도 있다. 이와 같이 전체 픽셀 가운데 일부 픽셀의 데이터만 선별하여 저장하는 방식을 sampling이라고 한다.

JPEG 파일은 샘플링하는 간격을 샘플링 주기(sampling frequency)로 나타내는데 샘플링 주기는 각 성분의 샘플링 간격의 역수비로 나타낸다. Y 성분은 매 픽셀 마다 샘플링하고 Cb 성분은 두 번째 픽셀마다 샘플링하고 Cr 성분은 네 번째 픽셀마다 샘플링한다면 YCbCr의 샘플링 주기는 4:2:1 이 된다. 사람의 눈은 밝기(Y) 성분에 더 민감하기 때문에 보통 Y 성분의 샘플링 주기가 더 크다. 물론 꼭 Y 성분의 샘플링 주기가 커야 되는 것은 아니다. 필요하다면 Cb, Cr의 샘플링 주기가 더 클 수 있지만 그런 경우는 거의 없다.

또한 가로 방향의 샘플링 주기와 세로 방향의 샘플링 주기가 틀릴 수도 있다. 즉, 가로 방향으로는 모든 픽셀의 데이터를 다 저장하고 세로 방향으로는 한 픽셀 씩 건너 뛰면서 데이터를 저장할 수도 있다. JPEG 파일이 허용하는 최대 샘플링 주기는 4이다.

JPEG 파일에서 주로 쓰이는 샘플링 주기는 2:1:1 또는 1:1:1이다. 이와 같이 각 성분의 샘플링 주기를 다르게 하는 이유는 화질의 크게 떨어뜨리지 않고 데이터의 양을 줄이기 위해서 이다. 가로, 세로 방향의 YCbCr 샘플링 주기를 각각 2:1:1로 하면 1:1:1로 하는 것보다 화질의 저하는 다소 있을 수 있으나 데이터 양을 반으로 줄일 수 있다. 이와 같이 일부 픽셀 데이터만 샘플링하는 것을 Down-sampling이라고 하고 반대로 down sampling된 데이터를 원래 픽셀 개수로 늘이는 것을 Up-sampling이라고 한다. 다운 샘플링하는 방법은 여러 가지가 있을 수 있다. 단순하게 일정 간격마다 건너 뛰면서 픽셀 데이터를 저장할 수도 있고 일정 간격 내의 모든 픽셀 데이터들의 평균을 저장할 수도 있다. 후자가 좀 더 나은 방식인데 어떤 방식으로 샘플링하느냐는 그래픽 소프트웨어와 같은 어플리케이션 프로그램에 의해 결정된다. 그림 3은 샘플링의 예이다. 첫번째 경우는 픽셀 모두를 샘플링하는 경우이고 두 번째는 한 픽셀씩 건너 뛰면서 데이터를 샘플링하는 것이고 세 번째의 경우는 4 픽셀의 평균을 샘플링하는 것이다. 이 세가지 경우 샘플링 주기는 2:1:1이다. 두 번째와 세 번째는 샘플링 주기는 같다. 샘플링 방식만 다를 뿐이다.

그림 3 샘플링의 예

DCT와 양자화 : DCT란 Discrete Cosine Transform(이산 코사인 변환)의 약자로 JPEG 압축 기술의 핵심이라 할 수 있다. DCT는 임의의 데이터 배열을 코사인 함수의 합으로 표현할 수 있다는 성질을 이용한 것이다. 예를 들어 임의의 데이터 배열 f를 코사인 함수의 합으로 표현하면 다음과 같다.

이때 코사인 함수의 진폭 F를 DCT 계수(DCT coefficient)라고 하고 새로운 배열 F를 구하는 것을 DCT라고 한다. DCT 계수는 다음과 같이 구할 수 있다.

DCT 계수를 이용해 원래 데이터 f를 구하는 것을 IDCT(Inverse Discrete Cosine Transform)라고 한다. N개의 데이터 f를 DCT로 변환하면 N개의 DCT 계수 F를 구할 수 있다. 예를 들어 표 1의 f와 같이 8개의 원소로 이루어진 배열이 있다고 해보자. DCT 변환을 하면 8개의 DCT 계수 F를 구할 수 있다. DCT 계수들 중 0차 계수는 다른 계수들과 달리 코사인의 함수가 아니기 때문에 DC 계수라고 하고 다른 계수들은 AC 계수라고 부른다. 보통 DC 계수 값이 AC 계수 값에 비해 크기 때문에 JPEG 파일은 DC 계수와 AC 계수를 서로 다른 방법으로 저장한다. 구체적인 것은 뒤에 다시 설명하겠다.

n	0	1	2	3	4	5	6	7
f(n)	10	9.59	8.07	8.15	11.02	14.04	13.51	9.28
F(n)	29.58	-3.22	0.24	4.40	-2.39	0.35	-0.44	0.08

표 1 DCT 변환의 예

DCT 계수 F를 이용해 IDCT를 수행하면 다시 원래 데이터 f를 구할 수 있다. IDCT를 수행할 때 높은 차수의 DCT 계수(n이 큰 DCT 계수)를 생략할 수도 있는데 이 경우 원래 데이터와 100% 똑같지 않지만 상당히 비슷한 값으로 복원해 낼 수 있다. 그림 4는 DCT 계수를 1개에서부터 8개까지 사용해 IDCT를 수행한 경우 복원된 값을 그래프로 보여주고 있다.

점선이 IDCT로 복원된 값이고 실선이 원래 데이터이다. DCT 계수를 많이 쓸수록 원래 데이터에 근접한 결과를 얻을 수 있음을 알 수 있다. 하지만 N=5, 즉 5차 DCT 계수까지만 사용해 IDCT를 해도 원래 데이터와 상당히 유사한 결과를 얻을 수 있다. 여기에 JPEG 압축의 비밀이 들어 있는 것이다. DCT 계수를 모두 다 저장하지 않고 일부만 저장하여도 나중에 복원할 때 원래 데이터와 상당히 유사한 형태로 복원을 할 수 있는 것이다. 이와 같이 DCT 변환된 데이터 중 일부를 버리는 작업을 양자화(Quantization)라고 한다. JPEG 이미지로 변환할 때 약간의 화질 저하가 생기는 이유도 바로 양자화 때문이다.

그림 4 IDT로 복원할 때 사용한 계수의 개수에 따라 복원 정도가 달라진다.

그러나 양자화가 만능은 아니다. 그림 5는 서로 다른 유형의 데이터를 DCT하고 N=5로 양자화한 것을 다시 IDCT로 복원한 것이다. 왼쪽 그림의 경우 거의 완벽하게 복원이 되었으나 오른쪽 그림의 경우는 제대로 복원이 되지 않았다.

그림 5 양자화가 적합한 경우와 그렇지 않은 경우.

양자화가 힘을 발휘하려면 데이터들의 변화가 되도록이면 적어야 한다. 그래서 색의 변화가 극단적으로 일어나는 도형 이미지를 JPEG 이미지로 만들면 자연스럽지 못한 것도 양자화 때문이다. 그림 6을 보자. 왼쪽 그림은 원래 이미지이고 오른쪽 그림은 JPEG으로 저장한 이미지이다. 도형의 모양과 색이 왜곡된 것을 볼 수 있다.

그림 6 JPEG 이미지로 저장할 때 데이터 손실이 생긴다.

그러나 사진의 경우 색의 변화가 심한 부분이 적기 때문에 양자화를 해도 화질의 저하가 그리 크지 않다. 그래서 JPEG은 사진 이미지에 보다 더 적합한 포맷이다.

앞에서 살펴본 DCT, IDCT는 1차원인데 실제 JPEG 이미지에서는 2차원 DCT, IDCT를 사용한다. 샘플링한 픽셀 데이터를 8x8 블록으로 나누어 각 블록마다 2차원 DCT를 수행한 뒤 양자화를 거쳐 데이터 양을 줄인다. 2차원 DCT, IDCT는 다음과 같이 정의된다.

위의 식을 간단하게 행렬로 표시하면 다음과 같다.

JPEG에서는 N은 항상 8이며 f, F는 8x8 행렬이다. 변환 행렬 M은 다음과 같이 정의된다.

M^T 는 행렬 M의 Transpose 행렬로 행렬 의 행과 열을 서로 뒤 바꾼 것이다. 즉, M^T (i,j)=M(j,i)이다.

JPEG 파일 안에는 8x8 크기의 Quantization table이라는 것이 보관되어 있는데 이 테이블을 이용해 8x8 DCT 계수를 양자화한다. DCT 계수를 1대1로 대응되는 quantization table 값으로 나눈 뒤 반올림 해주면 양자화된 DCT 행렬을 얻을 수 있다. 이렇게 양자화된 DCT 행렬은 대부분의 값이 0이 된다. 양자화된 DCT 행렬을 다시 원래 상태로 돌리려면 단순히 quantization table 값을 곱해주면 된다.

Interleave와 non-interleave 방식 : JPEG 파일은 DCT를 수행하기 위해 샘플링 데이터들을 8x8 크기의 블록으로 나누어야 한다. 이렇게 나뉘어진 8x8 크기의 데이터 블록을 Data Unit이라고 부른다. 가로 세로 샘플링 간격이 1 x 1 픽셀이라면 8 x 8 픽셀 블록이 하나의 데이터 유닛이 되고 가로 세로 샘플링 간격이 2 x 2 픽셀이라면 16 x 16 픽셀 블록이 하나의 데이터 유닛이 된다. 한 데이터 유닛의 픽셀 데이터를 샘플링하여 DCT 계수를 구하고 양자화를 한 뒤 저장을 한다. 그림 이미지의 위에서부터 아래로, 왼쪽부터 오른쪽으로 가면서 샘플링-DCT-양자화를 반복한다.

Y,Cb,Cr 중 한 가지 성분만 저장할 때는 단순하게 (8 * 가로 샘플링 간격) x (8 * 세로 샘플링 간격) 픽셀 씩 나누어 DCT를 수행해 맨 오른쪽 윗부분부터 순차적으로 저장하면 된다. 하나 이상의 성분을 저장할 때는 조금 복잡해 진다. Y, Cb, Cr 각 성분의 샘플링 주기가 모두 같을 때는 하나의 8 x 8 블록 내에 있는 Y, Cb, Cr 데이터를 순차적으로 저장하고 그 다음 8 x 8 블록의 Y, Cb, Cr 데이터를 순차적으로 저장한다. 샘플링 주기가 다를 때는 샘플링 주기가 가장 작은 성분을 기준 블록으로 삼고 이 블록 안의 Y, Cb, Cr 데이터를 순차적으로 모두 저장한 뒤 그 다음 기준 블록의 Y, Cb, Cr 데이터를 저장한다. 이 기준 블록을 MCU(Minimum Coded Unit)이라고 한다. 이와 같이 여러 개의 성분을 번갈아 가면서 저장하기 때문에 하나 이상의 성분을 저장할 때를 Interleaved 방식이라고 한다. 반면에 하나의 성분만 저장할 때는 Non-interleaved 방식이라고 한다. 그림 7은 Non-interleaved 방식으로 저장하는 예이다.

그림 7 Non-interleave 방식

그림 8은 Y, Cb, Cr의 샘플링 주기가 2:1:1인 경우 interleaved 방식으로 저장하는 예이다. Y성분은 모든 픽셀에서 샘플링하고 Cb, Cr 성분은 한 픽셀씩 건너 뛰면서 샘플링한다. 따라서 Y의 8 x 8 블록은 8 x 8 픽셀로 이루어져 있지만 Cb, Cr의 8 x 8 블록은 16 x 16 픽셀로 이루어져 있다. 즉, MCU는 16 x 16 픽셀로 되어 있으며 각 MCU 별로 Y, Cb, Cr 성분을 저장하게 된다.

그림 8 Interleave 방식

첫번째 MCU 블록에서 Y1, Y2, Y3, Y4 블록의 순으로 Y 데이터를 저장하는데 각 데이터 유닛의 크기는 8 x 8 픽셀이다. 다음 16 x 16 픽셀의 Cb, Cr 데이터(Cb1, Cr1)를 순차적으로 저장하면 첫번째 MUC 블록의 저장이 끝이 난다. 그 다음 두 번째 MCU 블록에서 Y5, Y6, Y7, Y8 블록 순으로 Y 데이터를 저장하고 Cb2, Cr2 데이터를 저장한다. 이런 방식으로 맨 마지막 8번째 MCU 블록까지 저장한다.

Interleaved 방식이던 Non-interleaved 방식이던 항상 MCU 의 배수 크기로 저장을 해야 한다. 따라서 그림 이미지 크기가 정확하게 MCU의 배수 크기가 아니면 실제 크기보다 더 크게 저장이 된다. 물론 복원할 때 원래 그림 이미지 크기에 맞게 불필요한 부분을 잘라낸다. MCU 크기에 맞지 않는 블록에서는 비어있는 부분은 보통 마지막 픽셀을 중복해서 채워넣는다.

JPEG 파일에는 각 성분의 샘플링 주기에 대한 정보와 그림 이미지의 크기에 대한 정보만 있을 뿐 MCU의 크기, 개수에 대한 정보는 저장되어 있지 않다. 따라서 다음과 같은 공식으로 MCU의 크기와 개수를 계산해 낼 수 있다.

MCU 폭 = 최대 샘플링 주기 * 데이터 유닛 폭(항상 8)
MCU 높이 = 최대 샘플링 주기 * 데이터 유닛 높이(항상 8)
가로 방향 MCU 개수 = (이미지 폭 + MCU폭 – 1) / MCU 폭
세로 방향 MCU 개수 = (이미지 높이 + MCU높이 – 1) / MCU 높이

Huffman Coding : 샘플링-DCT-양자화를 거친 데이터를 바로 그냥 저장하는 것이 아니고 한번 더 압축을 해서 저장을 한다. GIF 파일에서 LZW 코딩을 했듯이 JPEG 파일에서는 Huffman 코딩이라는 방법을 써서 압축을 한다. Huffman 코딩의 원리는 간단하다. 보통 한 픽셀 데이터의 길이는 8비트로 고정이 되어 있는데 Huffman 코드는 데이터의 빈도수에 따라 그 길이가 다르다. 빈도수가 많은 코드일수록 길이가 짧기 때문에 길이가 고정된 경우보다 전체 데이터의 크기가 작은 것이다.

Huffman 코드를 만드는 방법은 여러 가지가 있는데 JPEG 파일은 코드 길이(Code length)를 이용한 방법을 쓰고 있다. 알고리즘은 다음과 같다.

1. 데이터 배열에서 각 데이터들의 빈도수를 구한다.
2. 데이터들의 빈도수를 이용해 코드의 길이를 구한다.
3. 코드 길이를 이용해 Huffman 코드를 구한다.

예를 들어 다음과 같은 데이터 배열의 Huffman 코드를 구해보자.

BABDAGBFBDBDBABGGBCDBGBDBGBEFGFFGBFG

데이터의 종류는 A에서 G까지 7가지 이고 각 데이터들의 빈도수는 다음과 같다.

데이터	빈도수	데이터	빈도수
A	3	B	13
C	1	D	5
E	1	F	5
G	8

이를 이용해 코드의 길이를 구한다. 먼저 각 데이터들의 코드 길이를 나타내는 변수를 하나씩 할당해주고 모두 0으로 초기화한다. 다음 가장 빈도수가 작은 데이터 두 개를 골라 합친다. 그리고 각 데이터의 빈도수의 합을 새로운 빈도수로 넣어주고 코드 길이를 1씩 증가시킨다. 아래의 예에서는 빈도수가 1인 C와 E를 합쳐주고 코드 길이를 1씩 더했다. 새로운 테이블에서 다시 가장 빈도수가 작은 데이터 두 개를 골라 합치고 코드 길이를 1씩 증가시킨다.

이 작업을 모든 데이터가 다 합쳐질 때까지 반복한다.

이제 최종적으로 남은 코드 길이가 Huffman 코드의 길이가 된다. 빈도수가 높은 데이터일수록 코드 길이는 작다는 것을 알 수 있다. 다음 알고리즘을 이용해 Huffman 코드를 구할 수 있다.

HuffCodeCount = 0
CurrCodeLength = CodeLength(0)
i = 0
Do While i < NoOfCodes
  Do While CodeLength(i) = CurrCodeLength
    Code(i) = HuffCodeCount
    HuffCodeCount = HuffCodeCount + 1
    i = i + 1
  Loop
  HuffCodeCount = ShiftLeft(HuffCodeCount)
  CurrCodeLength = CurrCodeLength + 1
Loop

이 알고리즘을 한 스텝씩 따라가보면 그림 9와 같은 결과를 얻을 수 있다. 아래 첨자 2는 2진수임을 나타낸다.

그림 9 Huffman code 만들기

마지막 테이블이 최종적으로 구한 Huffman 코드 테이블이다. 이 코드 테이블을 이용해 데이터 배열의 각 데이터들을 Huffman 코드로 바꾸어 주면 압축이 된다. Huffman 코드는 코드마다 길이다 다르기 때문에 한 바이트 안에 여러 개의 코드가 들어갈 수도 있고 두 바이트에 걸쳐 하나의 코드가 들어갈 수도 있다.

얼마나 압축을 할 수 있는지 한번 살펴보자. 원래 데이터들은 A부터 G까지 7가지 이므로 3비트로 표현한다고 해보자. 총 데이터 개수가 36개이므로 전체 데이터 배열의 크기는 3 x 36 = 108 비트이다. 데이터 배열을 Huffman 코드로 표현하면 B는 1비트 코드로 표현할 수 있으며 B의 개수는 13개이므로 13비트가 필요하다. G의 개수는 8개이며 3비트로 표현할 수 있으므로 24비트가 필요하다. 이런 식으로 필요한 모든 비트 수를 계산하면 표 2와 같이 총 89비트가 필요하다. 따라서 압축 효율은 89/108 = 89.8%가 된다.

데이터	코드 길이	개수	필요한 비트 수
B	1	13	13
D	3	5	15
G	3	8	24
F	3	5	15
A	4	3	12
C	5	1	5
E	5	1	5
합		36	89

표 2 압축 효율

Huffman 코드로 압축된 데이터를 원래 데이터로 복원하는 것은 더 간단하다. 압축된 파일 안에는 Huffman 코드 테이블을 함께 저장한다. Huffman 코드 테이블을 참조하여 원래 데이터로 바꾸기만 하면 된다. 예를 들어 앞에서 살펴본 데이터 배열의 첫 4개의 데이터를 Huffman 코드로 표현하면 다음과 같다.

BABD ... -->  011₂ 100₂ 100₂ ...

그 런데 Huffman 코드는 길이가 가변이기 때문에 어디에서부터 어디까지가 하나의 코드인지 쉽게 구분이 가지 않는다. 하지만 Huffman 코드를 잘 살펴보면 해답을 찾을 수 있다. 서로 다른 코드는 코드의 맨 앞부분이 서로 중복되지 않는다는 특징을 가지고 있다. 예를 들어 B를 가리키는 코드는 0₂인데 0₂로 시작되는 코드는 하나도 없다. 마찬가지로 100₂로 시작하는 코드는 D밖에 없다. 따라서 코드 길이 순서대로 코드 테이블을 검색하여 최초로 일치하는 코드가 나오면 그 코드가 바로 찾으려는 코드가 된다. 위의 예에서 첫번째 비트 데이터는 0₂인데 Huffman 코드 테이블에서 0₂으로 시작하는 코드는 B 밖에 없으므로 첫번째 비트가 B를 가리키는 Huffman 코드임을 알 수 있다. 그 다음 비트는 1₂인데 코드 길이가 1인 코드는 0₂밖에 없으므로 그 다음 비트를 읽어봐야 한다. 그 다음 비트는 1₂인데 코드 길이가 2인 코드는 없으므로 또 다음 비트를 읽어야 한다. 그 다음 비트까지 읽으면 지금까지 읽은 코드는 111₂이 된다. 하지만 Huffman 코드 테이블에는 111₂코드는 존재하지 않는다. 따라서 또 다음 비트를 더 읽어와야 한다. 그 다음 비트까지 읽으면 1110₂이 되는데 1110₂은 Huffman 코드 테이블에 존재하며 A를 가리킨다. 두 번째 코드를 찾은 것이다. 그 다음 비트는 0₂인데 0₂은 B를 가리킨다. 세 번째 코드도 찾았다. 마찬가지로 Huffman 코드 테이블에 존재하는 코드가 나올 때까지 다음 비트들을 읽는다. 그러면 그 다음 코드는 100₂가 됨을 알 수 있고 100₂는 D를 가리킨다.

JPEG 파일에서 Huffman 코딩 : JPEG 파일에서는 DCT-양자화를 거친 데이터를 Huffman 코딩 방식으로 압축을 한다. Huffman 코드의 최대 길이는 16비트로 제한되어 있다. DCT 계수 가운데 DC 계수와 AC 계수를 따로 분리하여 코딩하고 필요에 따라 YCbCr 성분 별로도 따로 코딩을 한다. Huffman 코딩은 서로 같은 데이터가 많을수록 압축 효율이 좋기 때문에 이렇게 서로 비슷한 성분들끼리 분리하여 코딩을 하는 것이다.

보통 DC 계수의 크기는 AC 계수의 크기보다 크며 양자화된 AC 계수는 대부분이 0이다. AC 계수끼리 묶으면 대부분의 데이터가 0인데 보다 압축 효율을 높이기 위해 0으로 된 데이터들은 PCX 파일에서 사용한 Run-length encoding 방식으로 압축을 한다. 즉, 데이터 자체를 저장하는 것이 아니라 0의 개수를 저장하는 것이다. 0이 아닌 AC 계수와 DC 계수는 Huffman 인코딩을 하는데 값 자체를 인코딩하는 것이 아니고 인접한 값과의 차이를 인코딩한다. 예를 들어 DC 계수 배열이 122, 123, 124, 125, 126 이런 식이라면 실제 값이 아닌 인접한 값과의 차이인 122, 1, 1, 1, 1을 인코딩하는 것이다. 이렇게 하면 서로 똑같은 값들이 많아지기 때문에 값 자체를 인코딩할 때보다 훨씬 더 압축 효율이 높아진다. 이런 이유 때문에 인접한 픽셀들끼리의 변화가 적은 사진 이미지가 도형 이미지보다 압축 효율이 좋다.

[출처] JPEG(1) - JPEG원리|작성자 절광