[JPEG] Huffman Table Decoding

JPEG image를 decoding할 때 VLD의 경우 standard Huffman table을 사용하는 경우가 대부분이지만
간혹 image에 optimized되어 있는 Huffman table을 사용하여 encoding된 image가 있다.
이러한 image는 Huffman table이 JPEG image의 header에 명시되어 있는데
이 또한 압축된 형태로 들어있으므로 이를 풀어주어야만 한다.
압축을 푸는 과정을 예를 통해 알아보도록 하자

여기서 예로 사용하는 테스트 이미지는 다음과 같다.
(직접 다운받아 16진수로 열어보면 아래 내용을 더욱 쉽게 이해할 수 있다)

먼저 Huffman table의 위치는 0xFFC4의 marker로 시작된다.
이를 위의 테스트 이미지에서 찾아보면

빨간색 부분과 같다.
위의 내용을 간략하게 정리하면 다음과 같다

빨간색: Marker
주황색: 해당 데이터의 크기 (in byte)
초록색: Huffman Table의 종류
           (00: Luminance-DC, 10: Luminance-AC, 01: Chrominance-DC, 11: Chrominance AC)
파란색: Code 길이 별 Huffman table 데이터의 개수
보라색: Huffman table 데이터

위에서 네번째 Huffman table인 Chrominance AC table을 가지고 이를 decoding해보도록 하겠다.
전체 데이터를 적으면 다음과 같다.

FFC4 0033 1100 0202 0202 0104 0201 0304 0301 0002 0300 0102 1103 2112 3141 0413 2251 3261 7105 1442 2333 8191 15A1 B152 62F0 C1D1 E1

일단 빨간색 부분은 이후의 내용이 Huffman table이라는 marker이다.
주황색은 유효한 데이터의 크기가 0x33 (51) byte라는 것을 의미한다. (주황색+초록색+파란색+보라색의 데이터의 크기가 총 51byte인 것을 확인할 수 있ㄷ)
초록색은 이 내용이 Chrominance AC의 Huffman table인 것을 의미한다)
파란색은 code 길이 별 Huffman table의 element의 개수를 의미한다. 앞에서부터 1byte씩 1bit, 2bit, 3bit, ..., 16bit길이의 code의 element 개수를 의미하는데 이를 정리하면 다음과 같다.

Length	개수
1bit	0개
2bit	2개
3bit	2개
4bit	2개
5bit	2개
6bit	1개
7bit	4개
8bit	2개
9bit	1개
10bit	3개
11bit	4개
12bit	3개
13bit	1개
14bit	0개
15bit	2개
16bit	3개

이를 통해 보라색 부분인 실제 Huffman table 데이터를 element를 알 수 있는데,
위의 파란색 부분을 통해 얻은 표를 보며 각각의 element를 채울 수 있다.
일단 length 1bit의 element의 개수는 0이므로 넘어가고,
length 2bit의 element가 총 2개인 것으로 나타났으므로
보라색 데이터 중 처음 2byte는 length 2bit의 element에 속한다.
즉, 0x00, 0x01은 length 2bit의 element가 된다.
마찬가지로 3bit의 element의 개수는 2개이고, 이는 그 다음 2bit인 0x02, 0x11이 된다.
이와 같은 방법으로 위의 보라색 부분을 해석하여 정리하면 다음과 같다.

Length of code	Code element
1bit
2bit	0x00, 0x01
3bit	0x02, 0x11
4bit	0x03, 0x21
5bit	0x12, 0x31
6bit	0x41
7bit	0x04, 0x13, 0x22, 0x51
8bit	0x32, 0x61
9bit	0x71
10bit	0x05, 0x14, 0x42
11bit	0x23, 0x33, 0x81, 0x91
12bit	0x15, 0xA1, 0xB1
13bit	0x52
14bit
15bit	0x62, 0xF0
16bit	0xC1, 0xD1, 0xE1

위의 표를 JPEG image로부터 얻으면 Huffman table을 작성할 준비가 끝난 것이다.

이제 본격적으로 Huffman table을 구해보도록 하자.

위의 그림은 앞서 구했던 표<Length of code-Code element>를 통해 얻어진 binary tree이다.
위의 binary tree를 구하는 방법은 예를 통해 알아보도록 하자.
먼저 paranet node를 기준으로 왼쪽 node는 0, 오른쪽 node는 1을 나타낸다.

Length 1에 해당하는 code element는 없으므로 두 개의 non-leaf node를 그린다.

그리고 row 1의 non-leaf node를 span하면 row 2에 해당하는 node 총 4개가 나온다.
Length 2에 해당하는 code element는 표에서 보면 0x00과 0x01, 두 개가 존재한다.
이들을 row 2의 왼쪽 node부터 값이 0x00, 0x01인 leaf node로 지정한다.

마찬가지로 row2의 non-leaf node를 span하면 row 3에는 총 4개의 node가 나온다.
Length 3에 해당하는 code element는 0x02, 0x11 두 개이므로
4개의 node 중 왼쪽 두 개를 각각 값이 0x02, 0x11인 leaf node로 지정하고
나머지는 non-leaf node로 지정하고 span한다.

위와 같은 방법으로 계속해서 binary tree를 만들어가면 그림과 같은 binary tree를 얻을 수 있다.

이를 구한 후에 각각의 node의 binary 값과 지정된 값을 표로 정리하면 다음과 같은 Huffman table이 구해진다.

Binary (Code)	Value  (Extracted value)
00	0x00 (EOB)
01	0x01
100	0x02
101	0x11
1100	0x03
1101	0x21
11100	0x12
11101	0x31
111100	0x41
...	...

위의 표가 우리가 구하고자 하는 위 테스트 이미지의
Chrominance component의 AC성분 Huffman table이다.