Huffman Table Generating Procedures

在了解 JPEG 影像檔如何儲存 Huffman tables 之後, 接下來就是要將儲存在檔頭 (header) 的參數(paremeters) 轉換成解壓縮時能用的 Huffman tables。
JPEG 規格書 的 Annex C , 提供了一套完整的作法。

整個演算法包含三個程序:

1. Figure C.1 : generates a table of Huffman code sizes.

Goal: 讀取儲存在 JPEG 檔頭中的 BITS list, 將其轉換成儲存每個 Huffman code 的長度。

input: BITS list
output: HUFFSIZE table

以 Rex.jpg 的第 1 個 Huffman table 為例,
BITS 為 0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
HUFFSIZE 應該為 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8

Figure C.1 的對應程式碼如下:

k=0;
for (i=1 ; i<17 ; i++)
{
for (j=0 ; j<iBITS[iTc][iTh][i]; j++)
{
iHUFFSIZE[iTc][iTh][k] = i;
k++;　　
}
}
iHUFFSIZE[iTc][iTh][k] = 0;
iLASTK[iTc][iTh] = k;

//由於一共有 4 個 tables 需要處理, 因此我宣告三維陣列來分別儲存這些資料

2. Figure C.2 : generates the Huffman codes from the table built in the Figure C.1.

Goal: 根據 HUFFSIZE 所記錄的長度, 產生相對應的 HUFFCODE

input: table HUFFSIZE
output: table HUFFCODE

同樣以 Rex.jpg 的第 1 個 Huffman table 為例,
HUFFSIZE 為 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8
HUFFCODE 應該為 0, 1, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254

Figure C.2 的對應程式碼如下:

k=0;
iCODE = 0;
iSI = iHUFFSIZE[iTc][iTh][0];
do {
do {
iHUFFCODE[iTc][iTh][k] = iCODE;
iCODE++;
k++;
}
while (iHUFFSIZE[iTc][iTh][k] == iSI);
if (iHUFFSIZE[iTc][iTh][k]!=0)
{
do {
iCODE = iCODE << 1;
iSI++;
}
while (iHUFFSIZE[iTc][iTh][k]! = iSI);
}
}
while (iHUFFSIZE[iTc][iTh][k] != 0);

3. Figure C.3 : generates the Huffman codes in symbol value order.

Goal: 將 C.2 Procedure 所產生的 HUFFCODE 依照 HUFFVAL 的次序排列。

input: HUFFCODE, HUFFSIZE, HUFFVAL
output: ordered HUFFCODE, ordered HUFFSIZE

Rex.jpg 的第 1 個 Huffman table,
HUFFCODE 為 0, 1, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254
HUFFVAL 為 04, 05, 03, 02, 06, 01, 00, 07, 08, 09, 0A, 0B
因此, 排序過的 HUFFCODE 為 6, 5, 3, 2, 0, 1, 4, 14, 30, 62, 126, 254

Figure C.3 的對應程式碼如下:

for (k=0;k<iLASTK[iTc][iTh];k++)　
{
i = ucHUFFVAL[k];
iEHUFCO[iTc][iTh][i]=iHUFFCODE[iTc][iTh][k];
iEHUFSI[iTc][iTh][i]=iHUFFSIZE[iTc][iTh][k];
}


除此之外, 由於在解壓縮時, 我們所接收的 input 是 binary data,
因此, 光有 HUFFCODE 是無法進行解碼的,
必須配合 HUFFSIZE 進一步將 HUFFCODE 變成二進位模式,
如同規格書 K.3.1 (P.149) 的 Code word一般。

將 HUFFCODE 轉換成二進位形式之對應程式碼如下:

for (k=0;k<256;k++)
{
iCodeLength = iEHUFSI[iTc][iTh][k];
iCodeValue = iEHUFCO[iTc][iTh][k];
for (i=iCodeLength-1;i>=0;i--)
{
iEHUFCOB[iTc][iTh][k][i] = iCodeValue % 2;
iCodeValue = iCodeValue / 2;
}
}

Rex.jpg 的第 1 個 Huffman table 為

Category　Length　HUFFCODE　Code word
0　　　　　3　　　　6　　　　110
1　　　　　3　　　　5　　　　101
2　　　　　3　　　　3　　　　011
3　　　　　3　　　　2　　　　010
4　　　　　3　　　　0　　　　000
5　　　　　3　　　　1　　　　001
6　　　　　3　　　　4　　　　100
7　　　　　4　　　　14　　 　 1110
8　　　　　5　　　　30　　　 11110
9　　　　　6　　　　62　 　　111110
10　　　　 7　　　　126　　　1111110
11　　　　 8　　　　254　　　11111110