Thursday, October 25, 2007

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)

No comments:

Post a Comment