Huffman Tree in the JPEG Decoder

當我們在 JPEG 影像檔的檔頭遭遇 X'FFC4' marker, 並且將 Huffman Table 產生出來後, 必須進一步建立 Huffman Tree, 如此就可以對 MCU 中的資料進行解碼。

(宣告部份)

　// 遞迴的結構體宣告, 包含一個資料與兩個指向下一個節點的指標
　struct stHuffmanDecodingTreeNode
　　{
　　int iCategory;
　　struct stHuffmanDecodingTreeNode *ZeroSubtree;
　　struct stHuffmanDecodingTreeNode *OneSubtree;
　　};
　stHuffmanDecodingTreeNode *hdtnCurrentNode, *hdtnRoot[2][2];
　stHuffmanDecodingTreeNode *hdtnNewNode;

(程式碼)

　for ( iTc = 0 ; i Tc< 2 ; iTc++)
　　for ( iTh = 0 ; iTh< 2 ; iTh++)
　　　{
　　　hdtnCurrentNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
　　　hdtnCurrentNode->iCategory = -1;
　　　hdtnCurrentNode->ZeroSubtree = NULL;
　　　hdtnCurrentNode->OneSubtree = NULL;
　　　hdtnRoot[iTc][iTh] = hdtnCurrentNode;
　　　for ( k = 0; k< iLASTK[iTc][iTh] ; k++)
　　　　{
　　　　hdtnCurrentNode = hdtnRoot[iTc][iTh];
　　　　iCodeLength = iEHUFSI[iTc][iTh][k];
　　　　for ( i = 0; i < iCodeLength ; i++)
　　　　　{
　　　　　if ( iEHUFCOB[iTc][iTh][k][i] == 0 )
　　　　　　{　　　　
　　　　　　if ( hdtnCurrentNode->ZeroSubtree != NULL )
　　　　　　　hdtnCurrentNode = hdtnCurrentNode->ZeroSubtree;
　　　　　　else
　　　　　　　{
　　　　　　　hdtnNewNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
　　　　　　　hdtnNewNode->iCategory = -1;
　　　　　　　hdtnNewNode->ZeroSubtree = NULL;
　　　　　　　hdtnNewNode->OneSubtree = NULL;
　　　　　　　hdtnCurrentNode->ZeroSubtree = hdtnNewNode;
　　　　　　　hdtnCurrentNode = hdtnNewNode;
　　　　　　　}
　　　　　　}
　　　　　else // iEHUFCOB[iTc][iTh][k][i] == 1
　　　　　　{
　　　　　　if ( hdtnCurrentNode->OneSubtree != NULL )
　　　　　　　hdtnCurrentNode = hdtnCurrentNode->OneSubtree;
　　　　　　else
　　　　　　　{
　　　　　　　hdtnNewNode = (stHuffmanTreeDecodingNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
　　　　　　　hdtnNewNode->iCategory = -1;
　　　　　　　hdtnNewNode->ZeroSubtree = NULL;
　　　　　　　hdtnNewNode->OneSubtree = NULL;
　　　　　　　hdtnCurrentNode->OneSubtree = hdtnNewNode;
　　　　　　　hdtnCurrentNode = hdtnNewNode;
　　　　　　　}
　　　　　　}
　　　　　}
　　　　hdtnCurrentNode->iCategory = k;
　　　　}
　　}



在 Rex.jpg 這張影像中, DC 係數的第 1 個 Huffman table (for luminance component) 為

　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

經過上述的程式所產生的 Decoding Tree 顯示在下圖, leaf node 中的紅色數字代表 category。



下圖每一個 node 中的籃色數字則是代表各個節點的產生順序。



注意: 上述程式為了程式的可讀性, 用了全型的空白"　"來控制部落格文章的內縮顯示。因此, 如果你要直接複製上述程式到 C++ Builder 執行, 請務必將全型空白"　"改成半型空白" ", 否則, 編譯時發出現以下的錯誤訊息:
[C++ Error] Unit1.cpp(40): E2206 Illegal character '　' (0xa140)