1、第5章 圖像壓縮 Chapter5 Image Compression 第14周周三34節2016年05月30日第15周周二34節2016年06月06日第16周周二34節2016年06月13日 JMU 2009 All Right Reserved本章的主要內容5.1 背景知識5.2 基本概念5.3 Huffman編碼5.4 算術編碼5.5 行程編碼5.6 本章小結5.1 背景知識 在一幅圖像中規則的物體和規則的背景具有很強的相關性。 人眼的視覺系統對于圖像的感知是非均勻和非線性的，對圖像的變化并不都能察覺出來。 電視圖像序列中相鄰兩幅圖像之間有較大的相關性。 圖像從大面積上看，常存在有紋理結

2、構，稱之為結構冗余。5.1 背景知識通用的圖像壓縮與解壓系統框圖5.2 基本概念信源中每個符號的平均信息量，稱為信息的熵，可表示為H102logLiiiPPH式中 為灰度級 出現的概率。iPi5.2 基本概念 全部信息所占用的碼子的平均長度 ，即B10LiiiPB式中 為灰度級 對應的碼長， 為灰度級 出現的概率。iiiiP5.2 基本概念 若對原始圖像數據的信息進行信源的無失真圖像編碼，壓縮后平均碼長 存在一個下限，這個下限就是信息源信息熵 ，BH10210logLiiiLiiiPPHPB式中 為灰度級 對應的碼長， 為灰度級 出現的概率。iiiiP5.2 基本概念 圖像壓縮后的冗余度r1H

3、Br式中 為信息熵， 為平均碼長HB5.2 基本概念 圖像的編碼效率BH式中 為信息熵， 為平均碼長HB5.2 基本概念解壓后的圖像與原始圖像不存在誤差，稱為無損壓縮；解壓后的圖像與原始圖像存在誤差，稱為有損壓縮。其它編碼變換編碼預測編碼有損壓縮行程編碼算術編碼編碼無損壓縮圖像壓縮技術Huffman5.3 Huffman編碼 Huffman于1952年提出 基本思想：頻率高的，賦給短碼； 頻率低的，賦給長碼；5.3 Huffman編碼 Huffman編碼是最優的。換言之，若C*是Huffman編碼，另有一個唯一可譯碼C，不等式 L(C*) L(C)恒成立。提高：課后請同學證明，Huffman編

4、碼具有最優性解釋：在給定信源符號的概率分布和碼字母表的前提下，沒有其他編碼可以獲得比Huffman編碼更短的平均碼長。5.3 Huffman編碼例例1 1：設有編碼輸入設有編碼輸入 ，其頻率分別為：，其頻率分別為：654321,wwwwwwW , 4 . 01wP, 3 . 02wP, 1 . 03wP, 1 . 04wP,06. 05wP,04. 06wP求：求：1 1）、）、HuffmanHuffman編碼編碼 2 2）、計算）、計算HuffmanHuffman編碼的平均碼長編碼的平均碼長5.3 Huffman編碼例例1 1：第一次重排編碼編碼結果結果輸入輸入數據數據對應對應概率概率W10

5、.4W20.3W30.1W40.1W50.06W60.00.60.4第二次重排第三次重排第四次重排01111110001000000000100110110100010101000101001011010110101001101101005.3 Huffman編碼例1（續）：Huffman編碼步驟Step1 : 把信源符號 按出現概率的值由大到小的順序排列；iWStep2：然后把這兩個概率相加作為一個新的輔助符號的概率；Step3：將新的輔助符號與其他符號一起重新按概率大小順序排列；Step4：跳到第2步，直到出現2個為

6、止；Step5：對最后兩個分配以“0”和“15.3 Huffman編碼Step5 : 用線將符號連接起來，從而得到一個碼樹，樹的N個端點對應N個信源符號；Step6：從最后一個概率為1的節點開始，沿著到達信源的每個符號，將一路遇到的二進制碼“0”或“1”順序排列起來，就是端點所對應的信源符號的碼字。5.3 Huffman編碼例例1 1（續）：（續）：輸入數據輸入數據W1W2W3W4W5W6概率概率0.10.060.04編碼結果編碼結果10001101000101001011碼長碼長1234552 . 204. 0506. 051 . 041 . 033 . 024 . 011

7、0LiiiPB1436. 2)04. 0log04. 006. 0log06. 01 . 0log1 . 01 . 0log1 . 03 . 0log3 . 04 . 0log4 . 0(log222222102LiiiPPH5.3 Huffman編碼Huffman編碼性質性質2：Huffman方法構造出來的碼不是惟一的性質3：Huffman編碼中，沒有一個碼字是另一個碼 字的前綴，因此，每個碼字惟一可譯。性質4：Huffman編碼對不同的信源，其編碼效率是 不同的。性質1：Huffman編碼具有最優性5.3 Huffman編碼例2：設有編碼輸入 ，其頻率分別為：21,wwW ,321wP,3

8、12wP計算其Huffman編碼和碼長。問題：沒有達到“高頻短碼，低頻長碼”的要求！bitH91829. 052832. 038997. 0)31(log31)32(log32221311321B08898. 0191829. 011HBr5.3 Huffman編碼例3：A = a, b, c, P(a) = 0.95, P(b) = 0.02, P(c) = 0.03計算其Huffman編碼、碼長和編碼效率。問題：信源符號的概率嚴重不對稱的情況下， Huffman編碼惡化。335. 01518. 01129. 00703. 0)03. 0(log03. 0)02. 0(log02. 0)95

9、. 0(log95. 0222H05. 103. 0202. 0295. 01B1343. 21335. 005. 11HBrHuffman編碼：a0b11c105.4 算術編碼（Arithmetic Coding）基本原理基本原理 將待壓縮的整段數據映射到實數半開區間0，1）內，以某一區段的任一個數值作為數據段的唯一可譯代碼。013421aaaa3112aaaa5.4 算術編碼（Arithmetic Coding）n 從另一種角度對很長的信源符號序列進行有效編碼n 對整個序列信源符號串產生一個唯一的標識（ tag ）n 不用對該長度所有可能的序列編碼n 標識是0,1)之間的一個數（二進制小數，可作為序列的二進制編碼）5.4 算術編碼（Arithmetic Coding）編碼函數編碼函數LCFNLCFNrselss為新子區間的起始位置為新子區間的起始位置為新子區間的結束位置為新子區間的結束位置為前子區間的起始位置為前子區間的起始位置為前子區間的長度為前子區間的長度為當前符號所在區間的左端為當前符號所在區間的左端為當前符號所在區間的右端為當前符號所在區間的右端sNeNsFLlCrC5.5 行程編碼基本原理 在給定的圖像數據中尋找連續重復的數值，然后用兩個字符值取代這些連續值。例子： 計算 aabbbb