第十一章 影像與視訊壓縮
內容 11.1 前言 11.2 消息理論 11.3 不失真壓縮 11.4 向量量化法 11.5 靜態影像壓縮 11.6 動態影像壓縮 11.3.1 霍夫曼編碼 11.3.2 算術碼
11.2 消息理論 定理11.2.1 給任意 n 個事件，其熵 。 證明： n 個事件且機率分別為 、 、…和 。
圖11.2.1 的示意圖
Kraft不等式 。 長度為 ， 假設完成了 後，為避免發生 為 的前置碼(Prefix Code)，則必須滿足條件 ，這裡 為不合法的碼數。 同理，考慮時 ，則需滿足 。不等式兩邊同除以 ，可得 。依此類推，可得下列Kraft不等式 Kraft不等式將幫助證明熵可視為平均碼長的下限。 編碼 :
定理11.2.2 令 且 已被編成長度為 的碼， 則熵 ，這裡L代表平均碼長。 已知 證明： 又
巨集符號(Macro Symbol)集的平均碼長 n個符號形成一個巨集符號(Macro Symbol)。 字母集 假設兩兩符號為彼此獨立 表一個巨集符號所需的位元長度。 推得 若n趨近於無窮大，則 。
11.3 不失真壓縮 11.3.1 霍夫曼編碼 霍夫曼樹 符號集 對應頻率 符號集 對應頻率 Key: 將頻率最小的二個符號編碼，可建構出圖11.3.1.1的霍夫曼樹。 碼可編成 = 碼長度為 圖11.3.1.1 霍夫曼樹
範例1:給一4×4灰階影像，請建出霍夫曼樹並寫出灰階值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 解答完畢
單邊成長(Single-side Growing)霍夫曼樹 首先令 且 。 。單邊成長霍夫曼樹往左成長，所以 。可建出圖11.3.1.2的單邊成長霍夫曼樹且 令 代表第i層的葉子樹。 令 代表第i層的內部節點數。 給 ， ， 需跳過 中的兩個樹葉 ， 解碼只需 的時間，d指的是單邊成長霍夫曼樹的深度。 圖11.3.1.2 單邊成長霍夫曼樹
速度最快的霍夫曼解碼器 圖11.3.1.3 霍夫曼樹 在霍夫曼樹上進行廣先搜尋，在內部節點旁存上 的值，r代表位於同一層但在該內部節點左邊的內部節點數；l 代表在同一層上，內部節點右邊的節點數。第0層到第2層形成了一個完全子樹，可利用 變數記錄這特性。儲存 令輸入 ， ， ， 霍夫曼解碼可在 的時間內完成。
11.3.2 算術碼 字母集 且字母的機率為 、 、 和 。我們要編碼的訊息為 我們可用標簽的中間值0.2844表示原始之訊息。 字母集 且字母的機率為 、 、 和 。我們要編碼的訊息為 我們可用標簽的中間值0.2844表示原始之訊息。 收方收到的值是0.2844該如何解碼呢？因為0.2 ，可知第一個字母為 ；從0.28 可知第二個字母亦為 。最終可推得原訊息為 。
11.4 向量量化法 令碼表中的碼為 而待搜尋的區塊向量為 X，找到 使得 這裏 ， 。
再令 ， ， 金字塔式向量搜尋法 給二非負整數x和y 對任意向量 ，令
回到VQ的方法上，令 若每四個元素縮成一個平均值 其中q表示金字塔的高度。 不等式中， 為 X 縮小 1/4 後的上一層之向量，而 為 的上一層之向量，這裡 X 和 Ci 皆為最底層的向量。 每一個 Ci 皆事先建好自己的金字塔。X也建出屬於自己的金字塔。計算兩金字塔的頂端的相關值，即 。若計算得到的值比目前暫時的最小值都來的大時，則 就不必再往金字塔的下層考慮了。
11.5 靜態影像壓縮 JPEG一直是彩色影像和高灰階影像的壓縮標準。JPEG首先將輸入的影像切割成 8 8 的子影像集。將輸入全彩影像中每一像素的R、G和B值轉換為Y、Cb和Cr值。 (1) 將DCT作用在 8 8 的子影像上：每一像素皆先減去128，以下列的計算完成DCT 圖11.5.1 經DCT 作用後的結果 (a) 8 8子影像 (b) 8 8係數矩陣
(2)將第(1)步驟所得的頻率域值除以8 8量化表(Quantization Table) 圖11.5.2 量化表與量化後的結果 (a) 8 8量化表 (b) 8 8量化後DCT係數矩陣 (3)將第(2)步驟所得的結果四捨五入以取整數 圖11.5.2(b)的DCT係數矩陣經IDCT(Inverse DCT) 作用後，可得解壓後的影像，如圖11.5.3所示。 圖11.5.3 8 8解壓後影像
(5)針對AC進行Run-Length編碼 (4)依據Zig-Zag的掃描次序，將第(3)步驟所得的結果依低頻為先的原則，圖11.5.2(b)的向量型式為(39,-3,2,1,-1,1,0,0,0,0,0,-1,0,0,0, … ,0,0,0)。 圖11.5.4 Zig-Zag掃描次序 (5)針對AC進行Run-Length編碼 (6)進行DPCM(Differential Pulse Code Modulation)和霍夫曼編碼(Huffman Encoding) 可編碼為(0,-3)(0,2)(0,1) (0,-1)(0,1)(5,-1)EOB 在Run-Length編碼的格式(x,y)中，x通常採用固定長度編碼，而y則依照事先建好的圖11.5.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 的範圍 圖11.5.5 y 的編碼對照表
11.6 動態影像壓縮 視訊壓縮 (Video Compression) 中，例如MPEG或H.264/AVC，我們先將視訊影像分成三類，分別為 I 、 P 和 B 影像。 I 影像用Intra Mode壓縮即可。 P 影像可利用前面的 I 影像，透過區塊匹配 (Block Matching) 和補償 (Compensation) 來壓縮。 夾在 I 和 P 之間的 B 影像之區塊就由 I 和 P 所匹配到 的區塊內插而成。 I P B
區塊匹配 在MPEG或H.264/AVC中，區塊匹配是核心的工作。 區塊匹配是在前一張參考影像中找到某一區塊，使得找到的區塊和目前區塊最匹配。通常是採用在前張影像中先訂出一個搜尋視窗，在這搜尋視窗內包含許多與目前區塊相同大小的正方形區塊。因此進行區塊匹配前得先決定搜尋的範圍和區域。
Feng等人[22]。 假設目前區塊為 Bc，西邊鄰近區塊、西北邊鄰近區塊和北邊鄰近區塊會用來產生 Bc 的初始移動向量。接著，利用初始移動向量所得的區塊 B’r，計算兩者的絕對差平均值(Mean Absolute Difference, MAD): 若得到的值很大，則 Bc 屬於高移動區塊，搜尋視窗為原始搜尋範圍。若是中等的值，則屬於中移動區塊，搜尋範圍為原始搜尋範圍的一半。否則屬於低移動區塊，搜尋範圍則為1/4的原始搜尋範圍。 應用到全搜尋(Full Search)演算法後，有60%以上的時間改良率。估計精確度和全搜尋演算法則是差不多。
[24]實際分析圖11.6.1所示的五種視訊檔中的機率，給出類型配對和搜尋範圍間更合理的建議。而為了節省乘法和除法的計算，以累計絕對差 (Accumulated Absolute Difference, AAD) 當作區塊間的相似量度。定義如下： 由式子可知，對每個目前區塊算出參考影像中最匹配的區塊，然後紀錄 。
根據實驗，發現D=4時，幾乎涵蓋大多數的最大絕對值位移。圖11.6.2為五種視訊檔的不同絕對位移分佈圖。 銷售員 花園 月曆車 蘇西 足球 圖11.6.2 五種視訊檔的不同D分佈圖 百分比
令 代表在視訊檔l中的第i張影像中隨機變數D的機率值。D的平均機率可表示為 令 ，這個值在決定最低搜尋範圍時會用到。
(0,0) D=0 (1,1) D=1 (1,0) (3,2) D=3 (2,0) D=2 (3,1) (5,3) D=5 (6,2) D=6 (2,1) (2,2) 圖11.6.4 一個例子 (3,2) (5,3) (4,1) (4,2) (a)參考影像 (b)目前影像 假設在視訊檔 l 中的第i張影像已被分割成5×5個區塊，見圖11.6.4(a) ，圖中的(x,y)代表該區域的移動向量(Motion Vector)值。圖11.6.4(b) 這四個鄰近區塊的移動向量之平均值可用來預測Bc 的初始移動後的Bc 。 由圖11.6.4(a)可算得 ， ， ， ， ， ， 。利用式子 可得到 。
完全搜尋(Full Search) 我們假定在搜尋範圍中的某一搜尋正方形，如圖11.6.5所示的中間較小框框 。若Bc在 內找到最匹配的區塊，則完成匹配。否則在 的邊緣上找一暫時最匹配的區塊所在處定一3×3的視窗如圖11.6.5中以A點為中心的視窗。接著在這小視窗中找Bc的最佳匹配區塊。直到找到最佳的匹配區塊為止。 圖11.6.5 區塊匹配
贏家修正策略(Winner-update Starategy) 沿用11.4節中的符號 X 和 ， ，但 X 為目前影像中的待匹配區塊，而 為前一張參考影像中在搜尋範圍內的所有區塊，這裡假設十六維的向量 。為方便說明，假設 ，且各個向量只有三維。 首先，我們檢查 、 、 和 的第一個元素，假如四個元素如下所示
因為 為最小者，就繼續看 並且計算出 ，假定目前的前置和如下所示 這時因為 為前置和中最小值，所以計算 =3+6+9。目前的前置和如下所示
重複同樣的方式，假設最終的前置和如下所示 則由 可知 和 最匹配。