第五章 圖像壓縮(第14-16講)

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

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

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

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

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

6、止；Step5：對最后兩個(gè)分配以“0”和“15.3 Huffman編碼Step5 : 用線將符號連接起來，從而得到一個(gè)碼樹，樹的N個(gè)端點(diǎn)對應(yīng)N個(gè)信源符號；Step6：從最后一個(gè)概率為1的節(jié)點(diǎn)開始，沿著到達(dá)信源的每個(gè)符號，將一路遇到的二進(jìn)制碼“0”或“1”順序排列起來，就是端點(diǎn)所對應(yīng)的信源符號的碼字。5.3 Huffman編碼例例1 1（續(xù)）：（續(xù)）：輸入數(shù)據(jù)輸入數(shù)據(jù)W1W2W3W4W5W6概率概率0.10.060.04編碼結(jié)果編碼結(jié)果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編碼性質(zhì)性質(zhì)2：Huffman方法構(gòu)造出來的碼不是惟一的性質(zhì)3：Huffman編碼中，沒有一個(gè)碼字是另一個(gè)碼 字的前綴，因此，每個(gè)碼字惟一可譯。性質(zhì)4：Huffman編碼對不同的信源，其編碼效率是 不同的。性質(zhì)1：Huffman編碼具有最優(yōu)性5.3 Huffman編碼例2：設(shè)有編碼輸入 ，其頻率分別為：21,wwW ,321wP,3

8、12wP計(jì)算其Huffman編碼和碼長。問題：沒有達(dá)到“高頻短碼，低頻長碼”的要求！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計(jì)算其Huffman編碼、碼長和編碼效率。問題：信源符號的概率嚴(yán)重不對稱的情況下， 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 算術(shù)編碼（Arithmetic Coding）基本原理基本原理 將待壓縮的整段數(shù)據(jù)映射到實(shí)數(shù)半開區(qū)間0，1）內(nèi)，以某一區(qū)段的任一個(gè)數(shù)值作為數(shù)據(jù)段的唯一可譯代碼。013421aaaa3112aaaa5.4 算術(shù)編碼（Arithmetic Coding）n 從另一種角度對很長的信源符號序列進(jìn)行有效編碼n 對整個(gè)序列信源符號串產(chǎn)生一個(gè)唯一的標(biāo)識（ tag ）n 不用對該長度所有可能的序列編碼n 標(biāo)識是0,1)之間的一個(gè)數(shù)（二進(jìn)制小數(shù)，可作為序列的二進(jìn)制編碼）5.4 算術(shù)編碼（Arithmetic Coding）編碼函數(shù)編碼函數(shù)LCFNLCFNrselss為新子區(qū)間的起始位置為新子區(qū)間的起始位置為新子區(qū)間的結(jié)束位置為新子區(qū)間的結(jié)束位置為前子區(qū)間的起始位置為前子區(qū)間的起始位置為前子區(qū)間的長度為前子區(qū)間的長度為當(dāng)前符號所在區(qū)間的左端為當(dāng)前符號所在區(qū)間的左端為當(dāng)前符號所在區(qū)間的右端為當(dāng)前符號所在區(qū)間的右端sNeNsFLlCrC5.5 行程編碼基本原理 在給定的圖像數(shù)據(jù)中尋找連續(xù)重復(fù)的數(shù)值，然后用兩個(gè)字符值取代這些連續(xù)值。例子： 計(jì)算 aabbbb