Huffman decoding of DC coefficients

由於以下兩個原因:

1) DCT 的 DC 係數就是代表 8*8 區塊的像素平均值,
2) 影像中相鄰區塊的像素平均值有很大的機率是相近的

因此 JPEG 的 Huffman encoding procedure 並不是直接對 DC coefficients 編碼, 而是對兩個相鄰區塊的 DC difference 編碼。由於 difference 可能的值涵蓋太廣了, 對每一個可能值採取直接編碼的方式並不可行 (decoding tree 太大了), 因此 JPEG 採用的作法是先對所有可能值分成12個類別(category), 然後統計每一類別的機率, 有了機率後, 再依機率做 Huffman 編碼。JPEG 規格書 P.89 的 Table F.1 列出了 DC difference 是如何分類的

Table F.1 Difference magnitude categories for DC coding
SSSS 　　DIFF values
0 　 　　　　　　 0
1 　　　　　　　-1, 1
2 　 　　　　 -3,-2, 2, 3
3 　 　　　　 -7..-4, 4..7
4 　　　　　 -15..-8, 8..15
5 　　　　　 -31..-16, 16..31
6 　　　　　 -63..-32, 32..63
7 　　　　　-127..-64, 64..127
8 　　　　　-255..-128, 128..255
9 　　　　　-511..-256, 256..511
10 　　　　-1023..-512, 512..1023
11 　　　　-2047..-1024, 1024..2047

除了第 0 類 (SSSS=0) 之外, 每一類中, difference 的可能值並不只有一個, 因此還另外需要一些額外的位元(appended additional bits) 來標示出確切的 difference 值。所需要的額外位元總數就剛好是 SSSS 值, 原因很簡單, 第 1 類 (SSSS=1) 中有 -1, 1 兩個可能值, 因此只需要 1 個額外位元來指出真正的 difference 值是哪一個。同理, 第 2 類 (SSSS=2) 中有 -3, -2, 2, 3 共 4 個可能值, 因此需要 2 個額外位元來指出真正的 difference 值是哪一個。其餘類別的個數剛好就是 2^SSSS 個, 因此共需要 SSSS 個額外位元才夠指出真正的 difference 值為何。

如果 DIFF > 0, 額外位元就是 DIFF 的二進位表示法中的 SSSS 個低位元(low order bits), 如果 DIFF < 0, 則是用 (DIFF-1) 的 SSSS 個低位元。 我們舉例說明: a) 假設 DIFF 值為 -9, SSSS=4, 因為DIFF < 0, 因此 (DIFF-1) = -10, 用 2-complement 來表示 -10, 為 11110110, 那麼 4 個低位元就是 0110。 JPEG 解壓縮時, Huffman decoding procedure 如果使用 decoding tree 解碼得到 SSSS=4, 就會繼續取得 4 個額外位元 0110, 根據第 1 個位元判斷 DIFF<0, 然後使用後面 3 個位元計算得到 6, SSSS=4 這個類別負數區間的最小值為 -15, 將 -15 + 6 = -9 , 就可以得到 DIFF = -9。 b) 假設 DIFF 值為 6, SSSS=3, 因為 DIFF > 0, 因此用 2-complement 來表示 6 為 00000110, 那麼 3 個低位元就是 110。

使用 decoding tree 得到 SSSS=3 後, 繼續取得 3 個位元 110, 由於第 1 個位元為 1, 因此判斷 DIFF 屬於正數區間, 後面兩個位元為 10, 值為 2, 正數區間的最小值為 4, 4 + 2 =6 因此得到 DIFF=6。