Huffman Tables in JPEG Files

在 JPEG 影像壓縮標準中, DCT係數經過量化( quantization )後, 會使用熵編碼( entropy coding )來做更進一步的資料壓縮處理。在JPEG壓縮中, 熵編碼最常使用的技術就是霍夫曼編碼技術(Huffman coding)。因此, 在每一個 JPEG 影像壓縮檔 ( *.jpg ) 的檔頭中, 都會定義 Huffman table, 而 X'FFC4' 就是 Define Huffman table(s) - DHT 的 marker。當我們在 JPEG 影像檔頭中搜尋到 X'FFC4', 這表示接下來的資料就是在解壓縮時, 會用到的 Huffman table。

Huffman Table 的儲存語法在規格書 B.2.4.2 有完整說明, 這邊我們則再進一步解釋, 讓大家更容易看懂規格書。

Lh: Huffman table definition length.
　用 16 bits 來記錄整個規格書中, 所有 Huffman table 的總長度。

Tc: Table class - 0 = DC table or lossless table, 1 = AC table.
　有些 table 是給 DC 係數壓縮用的, 有些則是用來壓縮 AC 係數, 因此用 4 bits 來區分。

Th: Huffman table destination identifier
　影像中不同的 component 通常會使用不同的 table 來處理, 因此這邊用 4 bits 來讓這些 tables 有所區分。

Li: Number of Huffman codes of length i - Specifies the number of Huffman codes for each of the 16 possible lengths allowed by this Specification. Li’s are the elements of the list BITS.
　由於 Huffman coding 所編出來的碼, 並不是固定長度的(fixed-length), JPEG 壓縮標準所使用的最長編碼為 16, 因此, L1 就是紀錄長度為 1 的碼有幾個, L2 就是紀錄長度為 2 的碼有幾個,... 每個 Li 使用 8 bits 來記錄, 一共有 16 bytes。在規格書 Annex C 中, 用一個 list BITS 來儲存 Li。將 16 個 Li 值加總起來, 就是所有 Huffman codes 的總數。

Vi,j: Value associated with each Huffman code – Specifies, for each i, the value associated with each Huffman code of length i. The meaning of each value is determined by the Huffman coding model. The Vi,j’s are the elements of the list HUFFVAL.
　每一個 Huffman code 都有一個 Symbol Value 相對應, 利用這些 Value 就可以將所產生 Huffman Codes 用 Figure C.3 的演算法 做正確的排序。在 Annex C 中, 用一個 list HUFFVAL 來儲存這些 Symbol Value。

實例:



上圖是一張大小為 120*120 的 JPEG 影像, Rex.pdf 是將檔案內容以16進位的方式列印出來的結果。

我們如果在 Rex.pdf 中搜尋 "FF C4" 字串, 會分別在 address 00000215h (Page 1), 0000153ah (Page 9), 0000358ch (Page 23) 等三處找到 "FF C4" 字串。根據規格書中的 Table B.1 Marker Code Assignment 所列出來的 Marker 研判, 前面二個 FFC4 是屬於 Application Segments 的範圍, 只有第三個 "FFAC" 才是用來壓縮影像本身的 Huffman table。在這個例子中, Lh = 01A2, 一共有 418 bytes, 一共包含 4 個 Huffman tables, 前 2 個 tables 的 Tc = 0, 屬於 DC tables, 後 2 個 tables 的 Tc = 1, 屬於 AC tables。

第 1 個 table 的 Tc = 0, Th = 0,
L1 = 0, L2 = 0, L3 = 7, L4 = 1, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 0, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 7 + 1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 04, 05, 03, 02, 06, 01, 00, 07, 08, 09, 0A, 0B。

第 2 個 table 的 Tc = 0, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 3, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 1, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 2 + 2 + 3 +1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 01, 00, 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B。

第 3 個 table 的 Tc = 1, Th = 0,
L1 = 0, L2 = 2, L3 = 1, L4 = 3, L5 = 3, L6 = 2, L7 = 4, L8 = 2,
L9 = 6, L10 = 7, L11 = 3, L12 = 4, L13 = 2, L14 = 6, L15 = 2, L16 = 73。
注意: L16 = 73, 是 16 進位值, 所以實際應該為 7 * 16 + 3 = 115
一共有 2 + 1 + 3 + 3 + 2 + 4 + 2 + 6 + 7 + 3 + 4 + 2 + 6 + 2 + 115 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 02, 03, 11, 04, 00, 05, 21, 12, 31, 41, 51, 06, 13, 61, 22,
71, 81, 14, 32, 91, A1, 07, 15, B1, 42, 23, C1, 52, D1, E1, 33,
16, 62, F0, 24, 72, 82, F1, 25, 43, 34, 53, 92, A2, B2, 63, 73,
C2, 35, 44, 27, 93, A3, B3, 36, 17, 54, 64, 74, C3, D2, E2, 08,
26, 83, 09, 0A, 18, 19, 84, 94, 45, 46, A4, B4, 56, D3, 55, 28,
1A, F2, E3, F3, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 37, 47, 57, 67,
77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88, 98,
A8, B8, C8, D8, E8, F8, 29, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。

第 4 個 table 的 Tc = 1, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 1, L5 = 2, L6 = 3, L7 = 5, L8 = 5,
L9 = 4, L10 = 5, L11 = 6, L12 = 4, L13 = 8, L14 = 3, L15 = 3, L16 = 6D。
注意: L16 = 6D, 是 16 進位值, 所以實際應該為 6 * 16 + 13 = 109
一共有 2 + 2 + 1 + 2 + 3 + 4 + 5 + 4 + 5 + 6 + 4 + 8 + 3 + 3 + 109 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 00, 02, 11, 03, 04, 21, 12, 31, 41, 05, 51, 13, 61, 22, 06,
71, 81, 91, 32, A1, B1, F0, 14, C1, D1, E1, 23, 42, 15, 52, 62,
72, F1, 33, 24, 34, 43, 82, 16, 92, 53, 25, A2, 63, B2, C2, 07,
73, D2, 35, E2, 44, 83, 17, 54, 93, 08, 09, 0A, 18, 19, 26, 36,
45, 1A, 27, 64, 74, 55, 37, F2, A3, B3, C3, 28, 29, D3, E3, F3,
84, 94, A4, B4, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 46, 56, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 47, 57,
67, 77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88,
98, A8, B8, C8, D8, E8, F8, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。

延伸閱讀:
1. Huffman Table Generating Procedures
2. Huffman Tables in the Rex.jpg