第五章 圖像壓縮(第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 背景知識(shí)5.2 基本概念5.3 Huffman編碼5.4 算術(shù)編碼5.5 行程編碼5.6 本章小結(jié)5.1 背景知識(shí) 在一幅圖像中規(guī)則的物體和規(guī)則的背景具有很強(qiáng)的相關(guān)性。 人眼的視覺系統(tǒng)對(duì)于圖像的感知是非均勻和非線性的，對(duì)圖像的變化并不都能察覺出來。 電視圖像序列中相鄰兩幅圖像之間有較大的相關(guān)性。 圖像從大面積上看，常存在有紋理結(jié)

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

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

4、碼具有最優(yōu)性解釋：在給定信源符號(hào)的概率分布和碼字母表的前提下，沒有其他編碼可以獲得比Huffman編碼更短的平均碼長(zhǎng)。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編碼的平均碼長(zhǎng)編碼的平均碼長(zhǎng)5.3 Huffman編碼例例1 1：第一次重排編碼編碼結(jié)果結(jié)果輸入輸入數(shù)據(jù)數(shù)據(jù)對(duì)應(yīng)對(duì)應(yīng)概率概率W10

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

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

8、12wP計(jì)算其Huffman編碼和碼長(zhǎng)。問題：沒有達(dá)到“高頻短碼，低頻長(zhǎng)碼”的要求！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編碼、碼長(zhǎng)和編碼效率。問題：信源符號(hào)的概率嚴(yán)重不對(duì)稱的情況下， 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 從另一種角度對(duì)很長(zhǎng)的信源符號(hào)序列進(jìn)行有效編碼n 對(duì)整個(gè)序列信源符號(hào)串產(chǎn)生一個(gè)唯一的標(biāo)識(shí)（ tag ）n 不用對(duì)該長(zhǎng)度所有可能的序列編碼n 標(biāo)識(shí)是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ū)間的長(zhǎng)度為前子區(qū)間的長(zhǎng)度為當(dāng)前符號(hào)所在區(qū)間的左端為當(dāng)前符號(hào)所在區(qū)間的左端為當(dāng)前符號(hào)所在區(qū)間的右端為當(dāng)前符號(hào)所在區(qū)間的右端sNeNsFLlCrC5.5 行程編碼基本原理 在給定的圖像數(shù)據(jù)中尋找連續(xù)重復(fù)的數(shù)值，然后用兩個(gè)字符值取代這些連續(xù)值。例子： 計(jì)算 aabbbb