[JPEG] JPEG Decoding - VLD (Veriable Length Decoding)

JPEG decoding의 process 중 가장 먼저 거치는 과정인 VLD(Variable Length Decoding)에 대해서 알아보도록 하자

VLD의 과정을 설명하는데 사용되는 예제는 아래 그림과 같은 16x8 의 test image를 사용한다.



VLD를 수행할 실제 Image 데이터 찾기

일단, JPEG image 파일에서 실제로 image data가 들어가 있는 부분은 standard에서 정해진 marker로 찾아낼 수 있다.
Image data(보통 scan data라고 불린다)는 전체 JPEG image 파일에서 FF DA에서 FF D9사이에 존재한다.
FF DA와 FF D9 사이에 있는 image data는 부가데이터와 실제 VLD를 수행해야할 데이터로 나누어지는데
이 부가데이터의 크기는 FF DA 바로 뒤에 있는 2 byte에 명시되어 있다.
여기에서 유의해야 할 점은 부가데이터의 크기는 FF DA 바로 뒤에 있는 2 byte의 크기를 나타내는 데이터를 포함한 것이라는 점이다.



즉, 위에서 FF DA ~ FF D9 사이에 있는
00 0C 03 01 00 02 11 03 11 00 3F 00 FC FF 00 E2 AF EF F3 15 7F
이 데이터가 image data에 해당하는데,
이중 00 0C(12 byte)에 해당하는 노란색과 연두색 부부이 부가적인 데이터고
그 이외의 파란색 부분이 실제 VLD를 수행할 image data에 해당한다.

일단 VLD를 수행할 image data를 찾았다가면 그 데이터에서 FF 00이 있는지 확인해야 한다.
그 이유는 JPEG image file에서 FF는 marker에 사용되는 특별한 의미를 가지고 있기 때문에
JPEG encoding을 할때 FF가 나온다면 이 뒤에 00을 붙여 이 FF가 marker가 아님을 알려주도록 되어있다.
그렇다면 위의 예에서 실제로 우리가 VLD를 수행할 데이터는
FC FF E2 AF EF F3 15 7F
가 되게 된다.


VLD를 수행하여 얻을 결과

이제 input을 알아 냈다면 우리가 VLD를 수행한 후 얻어야 할 output의 구조에 대해서 알아보도록 하자
VLD를 수행하여 얻을 데이터는 nomalize된 frequency domain의 데이터이다.
이 nomalized frequency domain의 데이터는 MCU(minimum coded unit; JPEG에서는 8x8의 image 조각) 단위로 나누어져 있는데
각각의 MCU는 Y, Cb, Cr 세 개의 channel로 구성되어 있고
이들은 또 각각 DC component(1개)와 AC component(63개) 나누어져 있다.
즉, VLD를 수행해서 얻어낼 데이터의 총 개수는
MCU의 개수 * 3 (3 channels) * 64 (1 for DC component, 63 for AC components)
이다.

위에서 제시한 예의 image는 16x8(2개의 MCU)로 되어 있기 때문에 우리가 알아내야 할 데이터는 아래와 같다
MCU1 - Y   - 1 DC

                 - 63 AC
            Cb - 1 DC
                 - 63 AC
            Cr  - 1 DC
                 - 63 AC

MCU2 - Y   - 1 DC

                 - 63 AC
            Cb - 1 DC
                 - 63 AC
            Cr  - 1 DC
                 - 63 AC


VLD 수행과정

그러면 이제 예로 제시한 데이터를 통해 VLD를 수행하는 과정을 살펴보도록 하자
FC FF E2 AF EF F3 15 7F
위의 데이터를 2진수로 나타내면
1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
이다

이 데이터를 가지고 VLD를 수행하기 위해서는 Huffman table이 있어야 한다.
이는 JPEG image file의 header부분에 명시되어 있는데,
이 데이터 또한 상당히 압축되어 제시되어 있기 때문에 이를 해석하는 것은 다른 포스팅(링크)에서 자세하게 설명하도록 하겠다.

일단 예에서 제시한 이미지의 Huffman table이 다음과 같다고 가정하자

Table 1 - Huffman - Luminance (Y) - DC

Length	Bits	Code
3 bits	000 001 010 011 100 101 110	04 05 03 02 06 01 00 (End of Block)
4 bits	1110	07
5 bits	1111 0	08
6 bits	1111 10	09
7 bits	1111 110	0A
8 bits	1111 1110	0B

Table 2 - Huffman - Luminance (Y) - AC

Length	Bits	Code
2 bits	00 01	01 02
3 bits	100	03
4 bits	1010 1011 1100	11 04 00 (End of Block)
5 bits	1101 0 1101 1 1110 0	05 21 12
6 bits	1110 10 1110 11	31 41
...	...	...
12 bits	... 1111 1111 0011 ...	... F0 (ZRL) ...
...	...	...
16 bits	... 1111 1111 1111 1110	... FA

Table 3 - Huffman - Chrominance (Cb & Cr) - DC

Length	Bits	Code
2 bits	00 01	01 00 (End of Block)
3 bits	100 101	02 03
4 bits	1100 1101 1110	04 05 06
5 bits	1111 0	07
6 bits	1111 10	08
7 bits	1111 110	09
8 bits	1111 1110	0A
9 bits	1111 1111 0	0B

Table 4 - Huffman - Chrominance (Cb & Cr) - AC

Length	Bits	Code
2 bits	00 01	01 00 (End of Block)
3 bits	100 101	02 11
4 bits	1100	03
5 bits	1101 0 1101 1	04 21
6 bits	1110 00 1110 01 1110 10	12 31 41
...	...	...
9 bits	... 1111 1100 0 ...	... F0 (ZRL) ...
...	...	...
16 bits	... 1111 1111 1111 1110	... FA

가장 먼저 우리가 구해야 할 데이터는 MCU1의 Y channel, DC component의 데이터이다.
그러므로 적용해야할 table은 Table 1이 된다.
1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
그럼 위의 데이터 중 Table 1과 매치가 되는 부분은 빨간색으로 칠해진 부분이 된다.
그리고 이것이 의미하느 code는 0A가 된다.
여기서 구한 0A는 그 다음 10(0A)bit이 우리가 구해야할 MCU1의 Y channel, DC component의 값이라는 것을 의마한다.
그렇다면 위의 데이터중 녹색 부분은 아래의 표를 통해 해석할 수 있다.

DC Code	Size	Additional Bits		DC Value
00	0			0
01	1	0	1	-1	1
02	2	00,01	10,11	-3,-2	2,3
03	3	000,001,010,011	100,101,110,111	-7,-6,-5,-4	4,5,6,7
04	4	0000,...,0111	1000,...,1111	-15,...,-8	8,...,15
05	5	0 0000,...	...,1 1111	-31,...,-16	16,...,31
06	6	00 0000,...	...,11 1111	-63,...,-32	32,...,63
07	7	000 0000,...	...,111 1111	-127,...,-64	64,...,127
08	8	0000 0000,...	...,1111 1111	-255,...,-128	128,...,255
09	9	0 0000 0000,...	...,1 1111 1111	-511,...,-256	256,...,511
0A	10	00 0000 0000,...	...,11 1111 1111	-1023,...,-512	512,...,1023
0B	11	000 0000 0000,...	...,111 1111 1111	-2047,...,-1024	1024,...,2047

위 표는 위에서 제시한 JPEG image file header에서 제공되는 Huffman table과 다르게 모든 JPEG image file에서 공통으로 사용하는 table이다.
즉, standard에서 제시한 table이며 JPEG image file에는 제시되어 있지 않다.
그렇다면 위 표의 빨간색 부분에서 녹색 부분을 데이터를 찾아보면 그 값이 -512가 됨을 알 수 있다.
그러므로 MCU1의 Y channel, DC component의 데이터는 -512가 된다.

MCU1, Y, DC값을 구했으니 이제 MCU1, Y, AC값을 구할 차례다
AC값은 DC값과 달리 63개의 AC값을 구해야한다.
1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
그럼 DC값을 구하고 남은 나머지 scan data 에서 Table 2와 match가 되는 data를 찾아보면
위의 빨간색 부분이 될 것이다.
이 빨간색 부분은 code가 EOB(End of Block)인데 이는 이후의 값이 모두 0이고,
지금 값을 구하고 있는 MCU의 해당 channel의 해당 component VLD가 다 끝났음을 나타낸다.
MCU1, Y, AC의 63개의 값은 모두 0이 된다.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
그 다음은
MCU1, Cb, DC값을 구할 차례다
Table 3에서 남은 scan data와 일치하는 항목을 찾아보면 빨간색 부분임을 알 수 있다.
그러므로 MCU1, Cb, DC값은 0이고
MCU1, Cb, AC값의 경우 파란색 부분과 일치하는데 이 또한 모두 0임을 확인할 수 있다.
마찬가지 방법으로 MCU1, Cr, DC값, AC값들을 구해보면
각각 녹색과 보라색의 scan data에 해당하는데 이 모두 0이다.

그러므로 MCU1의 값은 다음과 같다.
MCU1 - Y   - 1 DC     : -512

                 - 63 AC   : 0, 0, 0, 0, ... , 0
            Cb - 1 DC     : 0
                 - 63 AC   : 0, 0, 0, 0, ... , 0
            Cr  - 1 DC     : 0
                 - 63 AC   : 0, 0, 0, 0, ... , 0

위에서 구한 방법과 마찬가지로 MCU2의 값을 구하면
1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
MCU2, Y, DC 성분은 빨간색 부분을 Table 1에서 찾아 위의 표에서 code값을 대입하여 파란색 부분의 값을 찾아내면 1020,
MCU2, Y, AC 성분은 녹색 부분을 Table 2에서 찾아 보면 EOB,
MCU2, Cb/Cr, DC/AC 성분은 보라색 부분을 Table 3/4에서 찾아보면 또한 EOB이므로
전체 값은
MCU2 - Y   - 1 DC     : 1020 -> 508

                 - 63 AC   : 0, 0, 0, 0, ... , 0
            Cb - 1 DC     : 0
                 - 63 AC   : 0, 0, 0, 0, ... , 0
            Cr  - 1 DC     : 0
                 - 63 AC   : 0, 0, 0, 0, ... , 0
인데, 여기서 주의해야 할 것이 항상 DC성분은 이전 MCU의 DC성분과의 차이값을 나타낸다는 것이다. (제일 첫 MCU의 경우 그 전 DC값이 0이라고 가정한다)
그러므로 MCU2, Y, DC성분의 실제 값은 빨간색인 508이 될 것이다.

이로써 VLD 과정을 통해 두 개의 MCU의 Y/Cb/Cr, DC/AC성분 값을 모두 구하였다.
여기서는 예로 상당히 간단한 이미지를 사용하였기 때문에 Cb,Cr과 Y의 AC성분이 모두 0으로 나왔지만
0이 아니라면, 위에서 DC성분을 구한것과 마찬가지로 Table 2또는 Table 4를 참고하여 code를 구한 후,
AC성분의 code-value를 나타내는 표에서 그 값을 찾아 넣으면 된다.


Reference
1. JPEG Huffma Coding Tutorial, http://www.impulseadventure.com/photo/jpeg-huffman-coding.html