數(shù)字圖像處理——圖像壓縮

1、 周三例會(huì)報(bào)告周三例會(huì)報(bào)告 26/11 /2014 上海大學(xué)上海大學(xué) 數(shù)字圖像處理數(shù)字圖像處理圖像壓縮圖像壓縮 OUTLINE:OUTLINE: 圖像壓縮圖像壓縮 1.香農(nóng)信息論香農(nóng)信息論 2.數(shù)據(jù)壓縮原理數(shù)據(jù)壓縮原理 3.數(shù)據(jù)冗余數(shù)據(jù)冗余 4.無(wú)損壓縮無(wú)損壓縮 5.有損壓縮有損壓縮 3圖像壓縮圖像壓縮_ _香農(nóng)信息論香農(nóng)信息論1 1、香農(nóng)信息論、香農(nóng)信息論 說(shuō)明：一個(gè)消息若能傳達(dá)給我們?cè)S多原來(lái)未知的內(nèi)容，我們就認(rèn)為這個(gè)信息很有意義，信息量大；反之，一個(gè)消息傳達(dá)給我們的是已知確定的東西，則這個(gè)傳達(dá)就失去了意義。 生活實(shí)例生活實(shí)例 第一句話：我有一個(gè)師兄叫“*”。 第二句話：我有一個(gè)舍友叫“*”

2、。直觀的感受一下這兩句話所攜帶的未知信息量。 例例 信息量信息量 在信息論中：信息使用不確定的度量來(lái)確定的，一個(gè)消息的可能性越小，其信息含量越大；消息的可能性越大，其信息含量越小。設(shè)某消息 發(fā)生的概率為 ，則該消息攜載的信息量為： 1）當(dāng) 時(shí)，則單位為比特（bit）； 2）當(dāng) 時(shí)，則單位為奈特（nat）； 3）當(dāng) 時(shí)，則單位為哈特（hat）。一般以2為底取對(duì)數(shù)，由此定義的信息量等于描述該信息所用的最少比特?cái)?shù)。 logiiaI xp xix ip x2a ae10a 信息熵信息熵 若信源有 個(gè)字符，對(duì)應(yīng)字符 的概率為 ，則該信源的平均信息量就稱為信息熵，既： 具體到數(shù)字圖像中，稱 為圖像信息熵。

3、它給出了描述一幅圖像攜載信息量的最少比特?cái)?shù)。圖像壓縮圖像壓縮_ _香農(nóng)信息論香農(nóng)信息論 112200loglogiLLiiiiinnHp xp xnnnixip xH Shannon Shannon無(wú)失真編碼定理無(wú)失真編碼定理 基于圖像信息熵，存在一種無(wú)失真的編碼方法，使編碼的平均碼長(zhǎng)與信息熵?zé)o限的接近。既：但以 為下限，既 。這就是Shannon的無(wú)失真編碼定理。 無(wú)失真編碼性能的幾個(gè)指標(biāo)： 1 1）編碼效率）編碼效率 2 2）冗余度）冗余度 或 3 3）壓縮比）壓縮比 或,0avgLHHavgLHa v gHL1100%DRRavgmCL12RnCn11DRRC 212111100%111

4、1avgDavgavgDRLHHRLLnnnRCnn 5圖像壓縮圖像壓縮_ _圖像壓縮原理圖像壓縮原理2 2、圖像壓縮原理圖像壓縮原理 1）數(shù)據(jù)壓縮的對(duì)象是數(shù)據(jù)，大的數(shù)據(jù)量并不代表含有大的信息量。 2）圖像壓縮就是除去圖像中多余的數(shù)據(jù)而對(duì)信息沒(méi)有本質(zhì)的影響。 3）圖像壓縮是以圖像編碼的形式實(shí)現(xiàn)的，用較少的比特?cái)?shù)表示出現(xiàn)概率較大的灰度級(jí)，用較多的比特?cái)?shù)表示出現(xiàn)概率較小的灰度級(jí)，從而使平均碼長(zhǎng)更接近于信息熵。 圖像編碼圖像編碼 碼本：碼本：編碼所用符號(hào)的集合稱為碼本。 如 碼字：碼字：對(duì)每個(gè)碼本的每個(gè)符號(hào)所賦的符號(hào)序列稱為碼字。如 碼字長(zhǎng)度：碼字長(zhǎng)度：每個(gè)碼字里的符號(hào)個(gè)數(shù)稱為碼字長(zhǎng)度。數(shù)字圖像：碼

5、長(zhǎng) = 二進(jìn)制數(shù)長(zhǎng)度。0123456A,aa aaaaa001011a 6圖像壓縮圖像壓縮_ _數(shù)據(jù)冗余數(shù)據(jù)冗余3 3、數(shù)據(jù)冗余、數(shù)據(jù)冗余 1)1)信息熵冗余：信息熵冗余：也稱編碼冗余，如果圖像中平均比特?cái)?shù)大于該圖像的信息熵，則圖像中存在冗余，這種冗余稱為信息熵冗余。 2)2)空間冗余：空間冗余：也稱為像素間冗余或幾何冗余，是圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性所造成的冗余。 3)3)時(shí)間冗余：時(shí)間冗余：視頻圖像序列中的不同幀之間的相關(guān)性所造成的冗余。 4)4)視覺(jué)冗余：視覺(jué)冗余：是指人眼不能感知或不敏感的那部分圖像信息。 5)5)結(jié)構(gòu)冗余：結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。

6、6) 6)知識(shí)冗余：知識(shí)冗余：是指有些圖像還包含與某些先驗(yàn)知識(shí)有關(guān)的信息。圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮4 4、無(wú)損編碼、無(wú)損編碼 常用的無(wú)損編碼方法有霍夫曼編碼霍夫曼編碼、香農(nóng)香農(nóng)費(fèi)諾編碼費(fèi)諾編碼、算術(shù)編碼算術(shù)編碼、游程編碼游程編碼和無(wú)損預(yù)測(cè)編碼無(wú)損預(yù)測(cè)編碼等。 1 1）HuffmanHuffman編碼編碼 霍夫曼編碼法是消除編碼冗余最常用的方法。 假設(shè)有一個(gè)信源為 ，其概率分布為：0123456A,a a a a a a a符號(hào)概率0.160.40.120.040.020.20.060a1a2a3a4a5a6a圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮0.40.20.160.120.0

7、60.060.40.20.160.120.120.40.240.20.160.40.360.240.60.401001011010000100010100110011100000001100000100101001001101100111101111霍弗曼編碼示意圖9圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮符號(hào)概率0.160.40.120.040.020.20.060a1a2a3a4a5a6a霍弗曼編碼 （碼字）001101001110011110000110二進(jìn)制編碼（碼字）000001010011100101110二進(jìn)制編碼效率為：2.325100%100%77.5%3Hm Huffman

8、Huffman編碼效率編碼效率 信源信息熵為： 霍弗曼編碼平均碼長(zhǎng) 為： 霍夫曼編碼效率為 ： avgL7 120log2.325kkkHP ap a 2.325100%100%97.7%2.380avgHL103 0.161 0.43 0.125 0.045 0.023 0.24 0.062.380NavgkkkLB P 壓縮比：31.262.380RavgmCL圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 2）香農(nóng)）香農(nóng)- -費(fèi)諾編碼費(fèi)諾編碼 由于霍夫曼編碼法中的信源縮減過(guò)程復(fù)雜，當(dāng)信源符號(hào)個(gè)數(shù)較多時(shí)十分不便。為此Shannon和Fano提出了一種類似的變長(zhǎng)編碼方法，相對(duì)于霍夫曼編碼法更方便、快

9、捷。 假設(shè)有一個(gè)信源為 ，其概率分布為：0123456A,a a a a a a a符號(hào)概率0.160.40.120.040.020.20.060a1a2a3a4a5a6a 具體步驟如下： a）將信源符號(hào)按出現(xiàn)的概率 由大到小排列； b）將信源A分成兩個(gè)子集并且保證 成立或差不多成立； c）給兩個(gè)子集賦不同的碼元值； d）重復(fù)（2）、（3），既對(duì)每個(gè)子集再一分為二，并賦予不同的碼元值，直到每個(gè)子集僅含一個(gè)符號(hào)為止。 01k 12120112AAkknkkknaaaaaap ap ap ap ap ap a和01knijij kp ap a ip a圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮0101

10、01111000010010111011101111011111香農(nóng)-費(fèi)諾編碼示意圖計(jì)算香農(nóng)-費(fèi)諾編碼平均碼長(zhǎng)為：101 0.430.230.1630.1240.0650.0450.022.380NavgkkkLB P 圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 3）算術(shù)編碼）算術(shù)編碼 算術(shù)編碼法和霍夫曼編碼法都是一種變長(zhǎng)編碼。但霍夫曼編碼必須分配整數(shù)位碼字，而算數(shù)編碼可以分配帶有小數(shù)的比特?cái)?shù)目信符，并且算術(shù)編碼給整個(gè)信源符號(hào)序列分配一個(gè)單一的算術(shù)碼字。 假設(shè)有一信源為 ，信源中各符號(hào)出現(xiàn)的概率分別為： Ab,c,a,d,c(a)0.2(b)0.3(c)0.4(d)0.1pppp 算術(shù)編碼具體步驟

11、如下： a）“當(dāng)前區(qū)間”初始化0,1）； b）對(duì)于輸入信源中的每個(gè)符號(hào)，依次執(zhí)行如下兩個(gè)步驟：將“當(dāng)前區(qū)間”分成子區(qū)間，該子區(qū)間的長(zhǎng)度正比于符號(hào)的概率；選擇下一個(gè)信符對(duì)應(yīng)的子區(qū)間，并使它成為新的“當(dāng)前區(qū)間”； c）將整個(gè)信源的所有符號(hào)處理完后，在最后一個(gè)“當(dāng)前區(qū)間”中任找一個(gè)數(shù)作為算數(shù)編碼的輸入碼。2log1.732iiI xp x 例如：圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮算術(shù)編碼示意圖 輸出區(qū)間0.3728,0.37376） 0.01011111011,0.01011111101） 取位數(shù)最少的一個(gè)數(shù): 0.010111111 不考慮“0.”，則編碼輸出為:010111111 算數(shù)編碼法

12、： 霍夫曼編碼法： 91.8/5avgL比特字符1.9/avgL比特 字符Ab,c,a,d,c圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 4）游程編碼）游程編碼 游程：游程：是指字符序列中各個(gè)字符連續(xù)重復(fù)出現(xiàn)而形成字符串的長(zhǎng)度。 游程編碼（行程編碼）：游程編碼（行程編碼）：就是將字符串序列映射成字符串的長(zhǎng)度和串的位子的標(biāo)志序列。 例如：一個(gè)字符串5 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 15 5 5 5 5 5 7 7 7 7 7 3 3 3 2 2 2 2 1 1 1 1 1 1 1 游程編碼：（5,6）（7,5）（3,3）（2,4）（1,7

13、） 游程編碼適合于二值圖像編碼，只有黑白出現(xiàn)。規(guī)定“0”游程開(kāi)始。 例如：對(duì)于一個(gè)二元序列：00000011111000110010000001111100011001，對(duì)應(yīng)的又稱序列為：653221。然后根據(jù)不同長(zhǎng)度段發(fā)生的概率來(lái)分配不同長(zhǎng)度的碼字。 5）無(wú)損預(yù)測(cè)編碼）無(wú)損預(yù)測(cè)編碼 無(wú)損預(yù)測(cè)編碼跟有損預(yù)測(cè)編碼一起講解。圖像壓縮圖像壓縮_ _有損壓縮有損壓縮 1 1）預(yù)測(cè)編碼）預(yù)測(cè)編碼 預(yù)測(cè)編碼是通過(guò)消除緊鄰像素在空間和時(shí)間上的冗余來(lái)實(shí)現(xiàn)的，它僅對(duì)每個(gè)像素中的新信息進(jìn)行提取并代替原圖像進(jìn)行編碼。新信息=實(shí)際值-預(yù)測(cè)值,既預(yù)測(cè)誤差。 差分脈沖編碼調(diào)制（Differential Pulse Cod

14、e Modulation，DPCM）。5 5、有損編碼、有損編碼 常用的有損編碼方法有預(yù)測(cè)編碼預(yù)測(cè)編碼、變換編碼變換編碼 圖像壓縮圖像壓縮_ _有損壓縮有損壓縮DPCM系統(tǒng)原理框圖 誤差信號(hào)： 量化器誤差： 接收端輸出： 可以推出： a）當(dāng) 時(shí)，無(wú)損預(yù)測(cè)編碼 b）當(dāng) 時(shí)，有損預(yù)測(cè)編碼。 問(wèn)題：如何使誤差盡可能?。?最優(yōu)預(yù)測(cè)？ nnneffnnnqeennnffe nnnnnnnnnnnffffeffeeeq0nq 0nq 圖像壓縮圖像壓縮_ _有損壓縮有損壓縮 最佳預(yù)測(cè)器最佳預(yù)測(cè)器 預(yù)測(cè)器選擇要滿足兩個(gè)要求： a)使均方預(yù)測(cè)誤差最小，既： b)約束條件： 22E enEf nf n 1=mii

15、fne nf ne nf nf nfnf ni和 常用的幾種線性預(yù)測(cè)方案 前值預(yù)測(cè)： 一維預(yù)測(cè)： 二維預(yù)測(cè)： 三位預(yù)測(cè)：也叫幀間預(yù)測(cè)，主要用于視頻壓縮。 1,mnmnf xyaf xy10,mmniinif xya f x y11100,mMmniinjjnijf xya f x yb f xy圖像壓縮圖像壓縮_ _有損壓縮有損壓縮 2 2）變換編碼）變換編碼 變換編碼是采用一種可逆線性變換（正交變換），把圖像從空間域映射到變換域的系數(shù)集合，然后對(duì)這些變換系數(shù)進(jìn)行量化和編碼。 區(qū)別：變換編碼是在變換域內(nèi)進(jìn)行編碼。變換編碼方法編碼、解碼示意圖圖像壓縮圖像壓縮_ _有損壓縮有損壓縮 第一步：子圖像分解第一步：子圖像分解 將一副大小為 的輸入圖像分解成大小為 的子圖像。 88 1