第九章 影像壓縮
內容 9.1 前言 9.2 霍夫曼編碼 9.3 向量量化法 9.4 靜態影像壓縮 9.5 作業
9.1 前言 JPEG內含數種壓縮技巧混合而成的系統。我們將針對其中的霍夫曼編碼(Huffman Coding)，向量量化法(Vector Quantization)，和JPEG基本架構做介紹。
9.2 霍夫曼編碼 霍夫曼樹 圖9.2.1 霍夫曼樹
範例9.2.1： 在影像處理中，霍夫曼編碼可用於不失真壓縮上，現有一44灰階影像如下所示，假設符號集S為灰階值，而頻率集W為每個灰階值所對應的出現頻率，利用霍夫曼編碼，請實作出本張影像所代表的霍夫曼樹，並寫出灰階值為50的像素之霍夫曼碼長。 60 102 80 95 40 155 50
解答： 符號集S=<40, 50, 60, 80, 95, 102, 155>對應的頻率集為W=<1, 1, 2, 2, 3, 3, 4>，建出的霍夫曼樹如下所示: 灰階值50的霍夫曼碼長為4，而其對應的碼為0001。
單邊成長(Single-side Growing)霍夫曼樹 圖9.2.2 單邊成長霍夫曼樹
9.3 向量量化法 令碼表中的碼為 而待搜尋的區塊向量為X，找到 使得 這裡 而
金字塔式向量搜尋法 若每四個元素縮成一個平均值 使用的資料結構為金字塔，q可被看成為金字塔的高度。在上面的不等式中， 為 X 縮小 1/4 後的上一層之向量，而 為 的上一層之向量，這裡X和 皆可視為最底層的向量。 若 的值比目前暫時的最小值都來的大時，則 就不必再往金字塔的下層考慮了。
9.4 靜態影像壓縮 JPEG首先將輸入的影像切割成 8 8 的子影像集。將輸入全彩影像中每一像素的R、G和B值轉換為Y、Cb和Cr值。 每一像素皆先減去128，以下列的計算完成DCT 圖9.4.1 經DCT 作用後的結果 (a) 8 8子影像 (b) 8 8係數矩陣
圖9.4.2(b)的DCT係數矩陣經IDCT(Inverse DCT) 量化表與量化後的結果 (a) 8 8量化表 (b) 8 8量化後DCT係數矩陣 圖9.4.2(b)的DCT係數矩陣經IDCT(Inverse DCT) 作用後，可得解壓後的影像，如圖9.4.3所示。 圖9.4.3 8 8解壓後影像
依據Zig-Zag的掃描次序，得到圖9.4.2(b)的向量型式 (39,-3,2,1,-1,1,0,0,0,0,0,-1,0,0,0, … ,0,0,0)。 進行Run-length編碼 可編碼為(0,-3)(0,2)(0,1) (0,-1)(0,1)(5,-1)EOB 圖9.4.4 Zig-Zag掃描次序 在Run-Length編碼的格式(x,y)中，x通常採用固定長度編碼，而y則依照事先建好的圖9.4.5表進行變動長度編碼。上述的向量型式進一步編成(0,2)(00)(0,2)(10)(0,1)(1)(0,1)(0)(0,1)(1)(5,1)(0) 1 -1,1 2 -3,-2,2,3 3 -7,…,-4,4,…,7 4 -15,…,-8,8,…,15 : 位元數 y 的範圍 圖9.4.5 y 的編碼對照表 進行DPCM(Differential Pulse Code Modulation)和霍夫曼編碼(Huffman Encoding)
範例9.4.1： 試問如何對y的範圍編碼？ 解答： 根據圖9.4.5中位元數的機率分佈，若DCT係數掉在位元數 i 所對應的y範圍內，則該DCT係數可編碼為0…01 。 例如：某一DCT係數為-5，則很容易找到其對應的位元數為3，我們可將DCT係數-5編碼成0001。 i+1
範例9.4.2： 給予下面AC值所編的Run-Length編碼: (0,3)(011)(0,2)(11)(0,1)(1)(0,2)(10)(0,2)(01)(0,1)(1)(1,1)(0)(0,1)(1)(8,1)(1)配合下圖的y編碼對照表 求出影像經量化後的DCT係數矩陣。（假設DC值為34，區塊大小為8） 位元組 y的範圍 1 -1,1 2 -3,-2,2,3 3 -7,…,-4,4,…,7 4 -15,…,-8,8,…,15 …
解答： 可得出AC值在矩陣中的位置及大小，所得出的值如下：(0,-4)(0,3)(0,1)(0,2)(0,-2)(0,1)(1,-1)(0,1)(8,1)根據上面的向量，最後所得到的矩陣如下： 34 -4 -2 1 3 2 -1
9.5 作業 作業一：寫一C程式以完成霍夫曼編碼的實作。 作業二：依本章介紹的JPEG系統架構，實作出簡易版的JPEG系統。