--- # System prepended metadata title: JPEG Decoder (2/3) tags: [DataCompression] --- --- ###### tags: `DataCompression` --- # JPEG Decoder (2/3) 在上一部份處理完MCU的DCT及量化，這篇要介紹如何進行對係數進行編碼。 一個8x8 MCU經過量化後可分為 - 1個在左上角雙向上頻率為0的**DC coefficient** - 63個**AC coefficient** 從2-D DCT可發現DC coefficient代表區塊內像素平均值，由於鄰近區塊的DC coefficient有相似性，以DPCM方式編碼使值縮小，可以在之後的壓縮取得不錯成效。 - $DiffDC(i) = DC(i) - DC(i-1), i=1,2,...$ - $DC(0)=0$ 例如 - DC(1)=-512 - DC(2)=1024 代表 - MCU 1: DC Coef=-512 - MCU 2: DC Coef=512。 AC coefficient藉由zig-zag順序來將低頻率的係數放在前面，有助於entropy coding。又因區塊小，跨區塊變化也小，高頻部份趨近於0，適合以RLE方式編碼。 接者編碼AC/DC coefficient成Bit-stream。 # 1. Huffman Coding DC/AC coefficient在檔案中的存放方式 ``` | MCU 1 | | Y | Cb | Cr | | DC | AC | DC | AC | DC | AC | ... ``` DC/AC coefficient需經過Huffman encoding才寫入。 下表範例是經過Huffman encoding的資料集以及其codeword Symbol|a|b|c|d|e -|-|-|-|-|- weights|0.10|0.15|0.30|0.16|0.29 codeword|0b010|0b011|0b11|0b00|0b10 ### 1.1 Huffman Table JPEG分兩部份存Huffman table，第一個部份存codeword length，第二個存decoded value，[實作](https://www.impulseadventure.com/photo/jpeg-decoder.html)上可使用兩個迴圈建出Huffman tree。[Expansion of DHT Table into binary bit strings](https://www.impulseadventure.com/photo/jpeg-huffman-coding.html)敘述如何利用codeword length及decoded value重建code word： ``` Class = 1 (AC Table) Destination ID = 0 Codes of length 01 bits (000 total): Codes of length 02 bits (002 total): 01 02 Codes of length 03 bits (001 total): 03 Codes of length 04 bits (003 total): 11 04 00 Codes of length 05 bits (003 total): 05 21 12 ... ``` ![](https://www.impulseadventure.com/photo/images/huffman/huff_tree1.gif) 步驟如下： 1. 0 bit (root)沒有value，生成左右node 2. 1 bit 沒有value，同樣生成左右node 3. 2 bit 有 0x01, 0x02，從左至右填上分支出來的位置，成為leaf node。剩下的node繼續分支。 4. 3 bit 有 0x03，填上剛生成的node，以此類推。 了解上述流程才能理解Huffman table在JPEG內所佔空間為何是`16+n` bytes > In JPEG all Huffman code tables are defined in the image header. Each table requires 16 + n bytes, where n is the number of codewords in the table. **The first 16 bytes list the number of codewords of each length from 1 to 16 bits (codewords longer than 16 bits are forbidden).** The remaining n bytes list the decoded output values of the n codewords in ascending codeword order (n < 256). 以下方HEX Code為例，嘗試解出Huffman table： ``` 01 05 01 01 01 01 01 01 00 00 00 00 00 00 00 | 01 02 03 04 05 06 07 08 09 0A 0B codeword length | decoded value ``` Codeword length (bits)|1|2|3|4|5|6|7|8|9|...|16 -|-|-|-|-|-|-|-|-|-|-|- Decoded value| - | 0x00 | 0x01, 0x02, 0x03, 0x04, 0x05 | 0x06 | 0x07 | 0x08 | 0x09 | 0x0A | 0x0B | - | - Symbol|Codeword|Bit-length -|-|- 0x00|00|2 0x01|010|3 0x02|011|3 0x03|100|3 0x04|101|3 0x05|110|3 0x06|1110|4 0x07|11110|5 0x08|111110|6 0x09|1111110|7 0x0A|11111110|8 0x0B|111111110|9 :::info 當採用Optimized Luminance/Chrominance的DC/AC coefficient分別個一張表，共4張表 ::: ### 1.2 Optimized JPEG 一般來說，JPEG不會對各種係數各建一張表，除非儲存時選擇`Optimized`。 Optimized JPEG指的是對Y(Luminance), CbCr(Chrominance)不同DC/AC係數各算一張Huffman table，雖然在檔案中需額外定義，但整體空間省下[2.4~6.8%](https://www.impulseadventure.com/photo/optimized-jpeg.html)。現代高階相機具有輸出Optimized JPEG的能力，但考慮到耗時與節省的空間不成比例，多採用[JPEG ITU-T81D standard, 149-157](https://www.w3.org/Graphics/JPEG/itu-t81.pdf)提供的Huffman table。 計算Optimized JPEG的Huffman table方式不只一種，最簡單的方式是採用先前提到的作法：將係數化成`Size`和`Additional bits`，再對`Size`進行編碼。也有的軟體有自家處理的方法，例如Photoshop CS2限制DC chrominance table不得有`0xA-0xB`、`EOB`為在DC luminance table內為5位元長度的codeword。 ### 1.3 Standard Huffman Tables 由於JPEG對於Huffman table的限制，DC table的`Size`為`0x0-0xB`，也就是最多12個code word；AC table的`Run`與`Size`分別為`0x0-0xF`、`0x1-0xA`，再加上`EOB (0x00)`與`ZRL (0xF0)`共162個code word。Standard huffman tables必須涵蓋所有code word。 使用方式如下，拿Table K3的category對應到Luminance的DC係數的Size。例如Size = 3, 對應的code word就是`0b100`。 ![](https://i.imgur.com/E3pgEON.png) 但即使存儲影像時選擇`Standard`也未必採用Standard huffman table，例如Photoshop CS2輸出的檔案，其Huffman table會依據quaility而定。 # 2. DC coefficient Encoding DC coeffiecient並非直接經過Huffman encoding直接寫入檔案，先前提過由於相鄰的區塊DC coefficient有所關係，使用DPCM可降低entropy。 ![](https://i.imgur.com/WIxYdbV.png) 但經過DPCM轉換有著Difference過大的問題，想像一下原始圖片數值介於`[0,255]`，假設經過DCT放大8倍，Difference同樣擴大8倍，這會造成code table非常巨大。因此進一步採用floating-point representation。 ### 2.1 Floating-point representation **Decode** Huffman table解碼出的值，對應到下方表格的`Size`、。`Size=5`代表要讀取5 bits的`Additional bits`，再對應到實際的值。在給定`Size`下，每個`Additional bits`出現的機率相近，使得entropy coding效率高。 DC Value (Size) | Additional bits | Value (DC Coef Difference) -|-|- 0x05|0b00101|-26 - `Size = 0` 具有特殊意義，代表該MCU結束(End of block) ![](https://i.imgur.com/5uo3nnx.png) ```python3= # https://github.com/yasoob/Baseline-JPEG-Decoder/blob/master/decoder.py def DecodeNumber(code, bits): l = 2 ** (code - 1) if bits >= l: return bits else: return bits - (2 * l - 1) DecodeNumber(0x05,0b00101) # -26 DecodeNumber(0x04,0b0101) # -10 ``` **Encode** ```python3= import math def EncodeNumber(value): code = int(math.log(abs(value))/math.log(2)) + 1 if value > 0: return code, value else: return code, value+2**code-1 EncodeNumber(15) # 0x4, 0b1111 EncodeNumber(-26) # 0x5, 0b00101 ``` **Example** 以一小段hex作為[範例](https://www.impulseadventure.com/photo/jpeg-huffman-coding.html)，MCU 1, 2的DC Coef分別是 -512、+508 ![](https://i.imgur.com/HFcc6NH.png) --- # 3. AC coefficient Encoding Run-length encoding(RLE)具有以下特性： - 容易實作 - 無損壓縮 - 對資料內有連續出現的數值壓縮率佳 影像經過DCT及Quantization，數值集中在左上角，AC coefficient以zig-zag順序排成一維陣列，進行 (RLE)可以得到不錯的效果。 ### 3.1 Zig-zag sequence ![](https://i.imgur.com/Ag1pmP1.png) 觀察zig-zag matrix - 每條斜線上的點座標x+y均同，左上到右下x+y是遞增的 - 在同一條斜線上，x+y是奇數方向為右上至左下，反之亦然 我們可以拿[zigzag matrix](https://rosettacode.org/wiki/Zig-zag_matrix#Python)生成函式的一部份，窮舉所有座標對應的值，依照這些值進行遞增排序即為zig-zag order。 預先生成8x8 zig-zag matrix： ```python= zigzag = [ [0, 1, 5, 6, 14, 15, 27, 28], [2, 4, 7, 13, 16, 26, 29, 42], [3, 8, 12, 17, 25, 30, 41, 43], [9, 11, 18, 24, 31, 40, 44, 53], [10, 19, 23, 32, 39, 45, 52, 54], [20, 22, 33, 38, 46, 51, 55, 60], [21, 34, 37, 47, 50, 56, 59, 61], [35, 36, 48, 49, 57, 58, 62, 63], ] ``` ### 3.2 Run-length encoding [JPEG Entropy Coding](http://www.mee.tcd.ie/~sigmedia/pmwiki/uploads/Teaching.4S1b/handout6_4s1.pdf): > The codeword represents the **run-length of zeros before a non-zero coef and the Size of that coef.** This is then followed by the Additional Bits which define the coef amplitude and sign precisely. Size and Additional Bits are defined just as for DC coefs. 編碼方式： ``` (Run, Size) codeword + coefficient additional bits ``` - Run: run-length of zeros - Size & Additional bits: 剛才提到的Floating-point representation 步驟如下： 1. 拿 `(Run, Size)` 組合而成的位元組進行Huffman encoding得到codeword，例如 `Run=0x0A, Size=0x03, (Run, Size)=0xA3` 2. 後面放上`Additional bit` 之所以將`Run`和`Size`放在一起進行編碼，是因為`Run`和`Size`關聯性高（較小的係數通常前面0多，較大的係數前面0較少）。 :::info 有些特殊的組合： - `EOB=(0,0)` - `ZRL=(15,0)` > The procedure “Append EHUFSI(X’F0’) bits of EHUFCO(X’F0’)” codes a run of 16 zero coefficients (ZRL code of Figure F.1). The procedure “Code EHUFSI(0) bits of EHUFCO(0)” codes the end-of-block (EOB code). If the last coefficient (K = 63) is not zero, the EOB code is bypassed. - [ISO/IEC 10918-1:19, 90-91](https://www.w3.org/Graphics/JPEG/itu-t81.pdf) `EOB`代表後續無係數，`ZRL`用來與其他`(Run, Size)`使用表示更長的run，例如： ``` (ZRL) (4,3) 010 ``` 等同 ``` |----- x16-----| |- 4 -| AC 0 0 0 .... 0 0 0 0 0 0 0 -5 ``` ::: 如果不想對`(Run, Size)`進行Huffman encoding，可以使用上方的Table K.3。 **Example** ![](https://i.imgur.com/u3HYSac.png) # 4. Conclusion ![](https://i.imgur.com/M8PEMAq.png) 這篇弄清了係數如何進行編碼AC/DC coeffieient，下篇介紹如何將這些東西塞進檔案。此外，我們並未進行down-sampling，但後續仍需處理這部份的JPEG header。 # 5. Reference - :star: [Understanding and Decoding a JPEG Image using Python ](https://yasoob.me/posts/understanding-and-writing-jpeg-decoder-in-python/) - [JPEG Huffman Coding Tutorial](https://www.impulseadventure.com/photo/jpeg-huffman-coding.html)