Download presentation
Presentation is loading. Please wait.
1
第十一章 影像與視訊壓縮
2
內容 11.1 前言 11.2 消息理論 11.3 不失真壓縮 11.4 向量量化法 11.5 靜態影像壓縮 11.6 動態影像壓縮
霍夫曼編碼 算術碼
3
11.2 消息理論 定理11.2.1 給任意 n 個事件，其熵 。 證明： n 個事件且機率分別為 、 、…和 。
4
圖 的示意圖
5
Kraft不等式 。 長度為 ， 假設完成了 後，為避免發生 為 的前置碼(Prefix Code)，則必須滿足條件 ，這裡 為不合法的碼數。 同理，考慮時 ，則需滿足 。不等式兩邊同除以 ，可得 。依此類推，可得下列Kraft不等式 Kraft不等式將幫助證明熵可視為平均碼長的下限。 編碼 :
6
定理11.2.2 令 且 已被編成長度為 的碼， 則熵 ，這裡L代表平均碼長。
已知 證明： 又
7
巨集符號(Macro Symbol)集的平均碼長
n個符號形成一個巨集符號(Macro Symbol)。 字母集 假設兩兩符號為彼此獨立 表一個巨集符號所需的位元長度。 推得 若n趨近於無窮大，則 。
8
11.3 不失真壓縮 11.3.1 霍夫曼編碼 霍夫曼樹 符號集 對應頻率
符號集 對應頻率 Key: 將頻率最小的二個符號編碼，可建構出圖 的霍夫曼樹。 碼可編成 = 碼長度為 圖 霍夫曼樹
9
範例1:給一4×4灰階影像，請建出霍夫曼樹並寫出灰階值50的霍夫曼碼長。
60 102 80 95 40 155 50
10
解答:S=<40,50,60,80,95,102,155>，而W=<1,1,2,2,3,3,4>，霍夫曼樹如下:
灰階值50的霍夫曼碼長為4 解答完畢
11
單邊成長(Single-side Growing)霍夫曼樹
首先令 且 。 。單邊成長霍夫曼樹往左成長，所以 。可建出圖 的單邊成長霍夫曼樹且 令 代表第i層的葉子樹。 令 代表第i層的內部節點數。 給 ， ， 需跳過 中的兩個樹葉 ， 解碼只需 的時間，d指的是單邊成長霍夫曼樹的深度。 圖 單邊成長霍夫曼樹
12
速度最快的霍夫曼解碼器 圖 霍夫曼樹 在霍夫曼樹上進行廣先搜尋，在內部節點旁存上 的值，r代表位於同一層但在該內部節點左邊的內部節點數；l 代表在同一層上，內部節點右邊的節點數。第0層到第2層形成了一個完全子樹，可利用 變數記錄這特性。儲存 令輸入 ， ， ， 霍夫曼解碼可在 的時間內完成。
13
11.3.2 算術碼 字母集 且字母的機率為 、 、 和 。我們要編碼的訊息為 我們可用標簽的中間值0.2844表示原始之訊息。
字母集 且字母的機率為 、 、 和 。我們要編碼的訊息為 我們可用標簽的中間值0.2844表示原始之訊息。 收方收到的值是0.2844該如何解碼呢？因為0.2 ，可知第一個字母為 ；從0.28 可知第二個字母亦為 。最終可推得原訊息為 。
14
11.4 向量量化法 令碼表中的碼為 而待搜尋的區塊向量為 X，找到 使得 這裏 ， 。
15
再令 ， ， 金字塔式向量搜尋法 給二非負整數x和y 對任意向量 ，令
16
回到VQ的方法上，令 若每四個元素縮成一個平均值 其中q表示金字塔的高度。 不等式中， 為 X 縮小 1/4 後的上一層之向量，而 為 的上一層之向量，這裡 X 和 Ci 皆為最底層的向量。 每一個 Ci 皆事先建好自己的金字塔。X也建出屬於自己的金字塔。計算兩金字塔的頂端的相關值，即 。若計算得到的值比目前暫時的最小值都來的大時，則 就不必再往金字塔的下層考慮了。
17
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係數矩陣
18
(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所示。 圖 8解壓後影像
19
(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)。 圖 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 的範圍 圖 y 的編碼對照表
20
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
21
區塊匹配 在MPEG或H.264/AVC中，區塊匹配是核心的工作。
區塊匹配是在前一張參考影像中找到某一區塊，使得找到的區塊和目前區塊最匹配。通常是採用在前張影像中先訂出一個搜尋視窗，在這搜尋視窗內包含許多與目前區塊相同大小的正方形區塊。因此進行區塊匹配前得先決定搜尋的範圍和區域。
22
Feng等人[22]。 假設目前區塊為 Bc，西邊鄰近區塊、西北邊鄰近區塊和北邊鄰近區塊會用來產生 Bc 的初始移動向量。接著，利用初始移動向量所得的區塊 B’r，計算兩者的絕對差平均值(Mean Absolute Difference, MAD): 若得到的值很大，則 Bc 屬於高移動區塊，搜尋視窗為原始搜尋範圍。若是中等的值，則屬於中移動區塊，搜尋範圍為原始搜尋範圍的一半。否則屬於低移動區塊，搜尋範圍則為1/4的原始搜尋範圍。 應用到全搜尋(Full Search)演算法後，有60%以上的時間改良率。估計精確度和全搜尋演算法則是差不多。
![Feng等人[22]。 假設目前區塊為 Bc，西邊鄰近區塊、西北邊鄰近區塊和北邊鄰近區塊會用來產生 Bc 的初始移動向量。接著，利用初始移動向量所得的區塊 B’r，計算兩者的絕對差平均值(Mean Absolute Difference, MAD):](http://slidesplayer.com/slide/14330931/89/images/22/Feng%E7%AD%89%E4%BA%BA%5B22%5D%E3%80%82+%E5%81%87%E8%A8%AD%E7%9B%AE%E5%89%8D%E5%8D%80%E5%A1%8A%E7%82%BA+Bc%EF%BC%8C%E8%A5%BF%E9%82%8A%E9%84%B0%E8%BF%91%E5%8D%80%E5%A1%8A%E3%80%81%E8%A5%BF%E5%8C%97%E9%82%8A%E9%84%B0%E8%BF%91%E5%8D%80%E5%A1%8A%E5%92%8C%E5%8C%97%E9%82%8A%E9%84%B0%E8%BF%91%E5%8D%80%E5%A1%8A%E6%9C%83%E7%94%A8%E4%BE%86%E7%94%A2%E7%94%9F+Bc+%E7%9A%84%E5%88%9D%E5%A7%8B%E7%A7%BB%E5%8B%95%E5%90%91%E9%87%8F%E3%80%82%E6%8E%A5%E8%91%97%EF%BC%8C%E5%88%A9%E7%94%A8%E5%88%9D%E5%A7%8B%E7%A7%BB%E5%8B%95%E5%90%91%E9%87%8F%E6%89%80%E5%BE%97%E7%9A%84%E5%8D%80%E5%A1%8A+B%E2%80%99r%EF%BC%8C%E8%A8%88%E7%AE%97%E5%85%A9%E8%80%85%E7%9A%84%E7%B5%95%E5%B0%8D%E5%B7%AE%E5%B9%B3%E5%9D%87%E5%80%BC%28Mean+Absolute+Difference%2C+MAD%29%3A.jpg "若得到的值很大，則 Bc 屬於高移動區塊，搜尋視窗為原始搜尋範圍。若是中等的值，則屬於中移動區塊，搜尋範圍為原始搜尋範圍的一半。否則屬於低移動區塊，搜尋範圍則為1/4的原始搜尋範圍。 應用到全搜尋(Full Search)演算法後，有60%以上的時間改良率。估計精確度和全搜尋演算法則是差不多。")
23
[24]實際分析圖11.6.1所示的五種視訊檔中的機率，給出類型配對和搜尋範圍間更合理的建議。而為了節省乘法和除法的計算，以累計絕對差 (Accumulated Absolute Difference, AAD) 當作區塊間的相似量度。定義如下： 由式子可知，對每個目前區塊算出參考影像中最匹配的區塊，然後紀錄 。
![[24]實際分析圖11.6.1所示的五種視訊檔中的機率，給出類型配對和搜尋範圍間更合理的建議。而為了節省乘法和除法的計算，以累計絕對差 (Accumulated Absolute Difference, AAD) 當作區塊間的相似量度。定義如下：](http://slidesplayer.com/slide/14330931/89/images/23/%5B24%5D%E5%AF%A6%E9%9A%9B%E5%88%86%E6%9E%90%E5%9C%9611.6.1%E6%89%80%E7%A4%BA%E7%9A%84%E4%BA%94%E7%A8%AE%E8%A6%96%E8%A8%8A%E6%AA%94%E4%B8%AD%E7%9A%84%E6%A9%9F%E7%8E%87%EF%BC%8C%E7%B5%A6%E5%87%BA%E9%A1%9E%E5%9E%8B%E9%85%8D%E5%B0%8D%E5%92%8C%E6%90%9C%E5%B0%8B%E7%AF%84%E5%9C%8D%E9%96%93%E6%9B%B4%E5%90%88%E7%90%86%E7%9A%84%E5%BB%BA%E8%AD%B0%E3%80%82%E8%80%8C%E7%82%BA%E4%BA%86%E7%AF%80%E7%9C%81%E4%B9%98%E6%B3%95%E5%92%8C%E9%99%A4%E6%B3%95%E7%9A%84%E8%A8%88%E7%AE%97%EF%BC%8C%E4%BB%A5%E7%B4%AF%E8%A8%88%E7%B5%95%E5%B0%8D%E5%B7%AE+%28Accumulated+Absolute+Difference%2C+AAD%29+%E7%95%B6%E4%BD%9C%E5%8D%80%E5%A1%8A%E9%96%93%E7%9A%84%E7%9B%B8%E4%BC%BC%E9%87%8F%E5%BA%A6%E3%80%82%E5%AE%9A%E7%BE%A9%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "由式子可知，對每個目前區塊算出參考影像中最匹配的區塊，然後紀錄 。")
24
根據實驗，發現D=4時，幾乎涵蓋大多數的最大絕對值位移。圖11.6.2為五種視訊檔的不同絕對位移分佈圖。
銷售員 花園 月曆車 蘇西 足球 圖 五種視訊檔的不同D分佈圖 百分比
25
令 代表在視訊檔l中的第i張影像中隨機變數D的機率值。D的平均機率可表示為
令 ，這個值在決定最低搜尋範圍時會用到。
26
(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) 圖 一個例子 (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)可算得 ， ， ， ， ， ， 。利用式子 可得到 。
27
完全搜尋(Full Search) 我們假定在搜尋範圍中的某一搜尋正方形，如圖11.6.5所示的中間較小框框 。若Bc在 內找到最匹配的區塊，則完成匹配。否則在 的邊緣上找一暫時最匹配的區塊所在處定一3×3的視窗如圖11.6.5中以A點為中心的視窗。接著在這小視窗中找Bc的最佳匹配區塊。直到找到最佳的匹配區塊為止。 圖 區塊匹配
28
贏家修正策略(Winner-update Starategy)
沿用11.4節中的符號 X 和 ， ，但 X 為目前影像中的待匹配區塊，而 為前一張參考影像中在搜尋範圍內的所有區塊，這裡假設十六維的向量 。為方便說明，假設 ，且各個向量只有三維。 首先，我們檢查 、 、 和 的第一個元素，假如四個元素如下所示
29
因為 為最小者，就繼續看 並且計算出 ，假定目前的前置和如下所示
這時因為 為前置和中最小值，所以計算 =3+6+9。目前的前置和如下所示
30
重複同樣的方式，假設最終的前置和如下所示
則由 可知 和 最匹配。
Similar presentations
