JPEG에 사용된 압축 알고리즘

JPEG은 국제 표준으로 정식 명칭은 ‘Digital Compression and Coding of Continuous Tone Still Image’이다.  이는 ISO/IEC 10918-1(ITU권고 T.81)로 표준화되어 있다.

JPEG에서는 DC성분과 AC성분을 따로 압축한다.  DC성분은 DCT를 행한 첫째 값이고 AC성분은 이 나머지 값을 말한다.

JPEG은 데이터를 8x8의 블록 단위로 읽어서 처리한다. 

DC성분은 12가지의 값을 가질 수 있다.  그리고 한 화면에서 DC값들은 비슷한 경우가 많기 때문에 새로운 블록을 처리할 때 이전 블록의 DC값과 비교해서 이 차이를 이용해 압축을 수행한다.

AC성분은 ‘지그재그 스캔’한 데이터를 가지고 압축한다.  기본적인 JPEG에서는 AC값이 모두 10가지 값을 가질 수 있다.  AC값은 한 바이트를 4비트씩 나눠 앞쪽에는 연속된 데이터의 개수가 들어가고 뒤에는 코드값이 들어간다( Run Length Coding). 또한 0이 16개 이상 연속으로 나오면 이를 한 블록의 끝(EOB)이라고 인식한다.

이와 같은 식으로 우선 한번의 작업을 거친 후에 이 데이터를 가지고 엔트로피 코딩에 들어간다.

 

허프만 코딩(Huffman coding)

JPEG에서 사용하는 엔트로피 코딩은 Huffman coding과 Arithmetic coding의 두 가지이다.  이 두 가지를 모두 사용하는 것은 아니고 파일에 따라서 어떤 파일은 Huffman coding을, 어떤 파일은 Arithmetic coding을 사용하는 것이다.  Huffman coding은 허프만이란 사람이 개발한 코드로 구현하기 쉽고 사용료가 없기 때문에 가장 많이 사용되는 코드이다. Arithmetic coding은 IBM에서 개발한 코드로, 압축률은 Huffman coding보다 약간 좋다고 알려져 있지만, 실수연산을 하기 때문에 코드가 복잡하고 IBM에 사용료를 지불해야 하기 때문에 잘 사용하지 않는다.

 

파라미터	크기(bits)	값	설    명
DHT	16	FFC4(h)	허프만 테이블임을 나타내는 마커 코드
Lh	16		허프만 테이블의 길이
Tc	4	0,1	table class(0=DC, 1=AC)
Th	4	0,1	Identifier
Li	8	0-255	코드길이가 i인 허프만 코드의 개수
Vi,j	8	0-255	허프만 코드에 해당하는 값

표 1 허프만 테이블 구문 Discrete Cosine Transform(DCT)

1차원 DCT           : C(u) = alpha (u)  sum from {x=0} to {N-1} f(x) cos [ { (2x+1) u pi } over { 2 N } ]

1차원 IDCT          :f(x) = sum from {u=0} to {N-1} alpha (u) C(u) cos[ { (2x+1) u pi } over { 2 N } ]

u, x는 0에서 N-1까지이고, alpha 는 다음과 같이 정의된다.

alpha (u) &= root { 1 over N } ~~~~~for~ u=0# &=root { 2 over N } ~~~~~for~u!=1

2차원 DCT              :C(u,v) = alpha (u) alpha (v) sum from { x=0 } to { n-1 } sum from {y=0} to {n-1} f(u,v) cos [ {2x+1) u pi } over { 2N } ] cos [ { (2y+1) u pi } over {2N} ]

2차원 IDCT          :f(u,v) = sum from { x=0 } to { n-1 } sum from {y=0} to {n-1} alpha (u) alpha(v) C(u, v) cos [ {2x+1) u pi } over { 2N } ] cos [ { (2y+1) u pi } over {2N} ]

 

JPEG Encoding, Decoding 방법

① 입력 영상을 8x8블럭으로 나눈다.

② 각각의 블록에 대해 DCT를 행한다.

③ 양자화를 행한다.

④ 계수값을 코딩한다.

⑤ 헤더를 붙이고 형식에 맞춰서 저장한다.

⑥ 파일을 읽는다.

⑦ 값을 디코딩한다.

⑧ 역양자화를 행한다.

⑨ 각각의 블록에 대하여 IDCT를 행한다.

⑩ 원영상을 재구성한다.





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을 인코딩하는 것이다. 이렇게 하면 서로 똑같은 값들이 많아지기 때문에 값 자체를 인코딩할 때 보다 훨씬 더 압축 효율이 높아진다. 이런 이유 때문에 인접한 픽셀들끼리의 변화가 적은 사진 이미지가  도형 이미지보다 압축 효율이 좋다.