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，實作上可使用兩個迴圈建出Huffman tree。Expansion of DHT Table into binary bit strings敘述如何利用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 
    ...

步驟如下：

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

當採用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%。現代高階相機具有輸出Optimized JPEG的能力，但考慮到耗時與節省的空間不成比例，多採用JPEG ITU-T81D standard, 149-157提供的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。

但即使存儲影像時選擇Standard也未必採用Standard huffman table，例如Photoshop CS2輸出的檔案，其Huffman table會依據quaility而定。

2. DC coefficient Encoding

DC coeffiecient並非直接經過Huffman encoding直接寫入檔案，先前提過由於相鄰的區塊DC coefficient有所關係，使用DPCM可降低entropy。

但經過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://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

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作為範例，MCU 1, 2的DC Coef分別是 -512、+508

---

3. AC coefficient Encoding

Run-length encoding(RLE)具有以下特性：

• 容易實作
• 無損壓縮
• 對資料內有連續出現的數值壓縮率佳

影像經過DCT及Quantization，數值集中在左上角，AC coefficient以zig-zag順序排成一維陣列，進行 (RLE)可以得到不錯的效果。

3.1 Zig-zag sequence

觀察zig-zag matrix

• 每條斜線上的點座標x+y均同，左上到右下x+y是遞增的
• 在同一條斜線上，x+y是奇數方向為右上至左下，反之亦然

我們可以拿zigzag matrix生成函式的一部份，窮舉所有座標對應的值，依照這些值進行遞增排序即為zig-zag order。

預先生成8x8 zig-zag matrix：

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:

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較少）。

有些特殊的組合：

• 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

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

4. Conclusion

這篇弄清了係數如何進行編碼AC/DC coeffieient，下篇介紹如何將這些東西塞進檔案。此外，我們並未進行down-sampling，但後續仍需處理這部份的JPEG header。

5. Reference

• Understanding and Decoding a JPEG Image using Python
• JPEG Huffman Coding Tutorial