數(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ù)。 log i ia I xp x i x i p x 2a ae 10a 信息熵信息熵 若信源有 個(gè)字符，對(duì)應(yīng)字符 的概率為 ，則該信源的平均信息量就稱(chēng)為信息熵，既： 具體

3、到數(shù)字圖像中，稱(chēng) 為圖像信息熵。它給出了描述一幅圖像攜載信息量的最少比特?cái)?shù)。 圖像壓縮圖像壓縮_ _香農(nóng)信息論香農(nóng)信息論 11 22 00 loglog i LL ii i ii nn Hp xp x nn n i x i p x H Shannon Shannon無(wú)失真編碼定理無(wú)失真編碼定理 基于圖像信息熵，存在一種無(wú)失真的編碼方法，使編碼的平均碼長(zhǎng)與信息熵?zé)o限的接 近。既： 但以 為下限，既 。這就是Shannon的無(wú)失真編碼定理。 無(wú)失真編碼性能的幾個(gè)指標(biāo)： 1 1）編碼效率）編碼效率 2 2）冗余度）冗余度 或 3 3）壓縮比）壓縮比 或 ,0 avg LH H avg LH a v

4、g H L 1100% D R R avg m C L 1 2 R n C n 1 1 D R R C 212 11 1100%1 1 11 avg D avgavg D R LH H R LL nnn R Cnn 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)更接近于信息熵。 圖像編碼圖像編碼 碼本

5、：碼本：編碼所用符號(hào)的集合稱(chēng)為碼本。 如 碼字：碼字：對(duì)每個(gè)碼本的每個(gè)符號(hào)所賦的符號(hào)序列稱(chēng)為碼字。如 碼字長(zhǎng)度：碼字長(zhǎng)度：每個(gè)碼字里的符號(hào)個(gè)數(shù)稱(chēng)為碼字長(zhǎng)度。數(shù)字圖像：碼長(zhǎng) = 二進(jìn)制數(shù)長(zhǎng)度。 0123456 A,aa aa aa a 0 01011a 6 圖像壓縮圖像壓縮_ _數(shù)據(jù)冗余數(shù)據(jù)冗余 3 3、數(shù)據(jù)冗余、數(shù)據(jù)冗余 1)1)信息熵冗余：信息熵冗余：也稱(chēng)編碼冗余，如果圖像中平均比特?cái)?shù)大于該圖像的信息熵，則圖像中存 在冗余，這種冗余稱(chēng)為信息熵冗余。 2)2)空間冗余：空間冗余：也稱(chēng)為像素間冗余或幾何冗余，是圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性 所造成的冗余。 3)3)時(shí)間冗余：時(shí)間冗余：視頻

6、圖像序列中的不同幀之間的相關(guān)性所造成的冗余。 4)4)視覺(jué)冗余：視覺(jué)冗余：是指人眼不能感知或不敏感的那部分圖像信息。 5)5)結(jié)構(gòu)冗余：結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。 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è)信源為 ，其概率分布為： 01234

7、56 A,a a a a a a a 符號(hào) 概率0.160.40.120.040.020.20.06 0 a 1 a 2 a 3 a 4 a 5 a 6 a 圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 0.4 0.2 0.16 0.12 0.06 0.06 0.4 0.2 0.16 0.12 0.12 0.4 0.24 0.2 0.16 0.4 0.36 0.24 0.6 0.4 0 1 0 0 1 0 1 1 01 00 001 0 001 010 0110 01110 000000 11 000 001001 010 010 0110110 0111 1 01111 霍弗曼編碼示意圖 9 圖像

8、壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 符號(hào) 概率0.160.40.120.040.020.20.06 0 a 1 a 2 a 3 a 4 a 5 a 6 a 霍弗曼編碼 （碼字） 001101001110011110000110 二進(jìn)制編碼 （碼字） 000001010011100101110 二進(jìn)制編碼效率為： 2.325 100%100%77.5% 3 H m Huffman Huffman編碼效率編碼效率 信源信息熵為： 霍弗曼編碼平均碼長(zhǎng) 為： 霍夫曼編碼效率為 ： avg L 7 1 2 0 log2.325 kk k HP ap a 2.325 100%100%97.7% 2.380

9、 avg H L 1 0 3 0.161 0.43 0.125 0.045 0.023 0.24 0.06 2.380 N avgkk k LB P 壓縮比： 3 1.26 2.380 R avg m C L 圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 2）香農(nóng)）香農(nóng)- -費(fèi)諾編碼費(fèi)諾編碼 由于霍夫曼編碼法中的信源縮減過(guò)程復(fù)雜，當(dāng)信源符號(hào)個(gè)數(shù)較多時(shí)十分不便。為此Shannon和 Fano提出了一種類(lèi)似的變長(zhǎng)編碼方法，相對(duì)于霍夫曼編碼法更方便、快捷。 假設(shè)有一個(gè)信源為 ，其概率分布為： 0123456 A,a a a a a a a 符號(hào) 概率0.160.40.120.040.020.20.06 0

10、 a 1 a 2 a 3 a 4 a 5 a 6 a 具體步驟如下： a）將信源符號(hào)按出現(xiàn)的概率 由大到小排列； b）將信源A分成兩個(gè)子集 并且保證 成立或差不多成立； c）給兩個(gè)子集賦不同的碼元值； d）重復(fù)（2）、（3），既對(duì)每個(gè)子集再一分為二，并賦予不同的碼元值，直到每個(gè)子集僅含一 個(gè)符號(hào)為止。 01k 12 12 0112 AA kkn kkkn aaaaaa p ap ap ap ap ap a 和 01 kn ij ij k p ap a i p a 圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 0 1 0 1 0 1 1 1 1 0 0 0 0 100 101 110 1110 111

11、10 11111 香農(nóng)-費(fèi)諾編碼示意圖 計(jì)算香農(nóng)-費(fèi)諾編碼平均碼長(zhǎng)為： 1 0 1 0.430.230.1630.1240.0650.0450.02 2.380 N avgkk k LB 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ù)編碼具體步驟如下： a）“當(dāng)前區(qū)間”

12、初始化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ù)編碼的輸 入碼。 2 log1.732 ii I xp x 例如： 圖像壓縮圖像壓縮_ _無(wú)損壓縮無(wú)損壓縮 算術(shù)編碼示意圖 輸出區(qū)間0.3728,0.37376） 0.01011111011,0.01011111101） 取位數(shù)最少的一個(gè)數(shù): 0.010111111 不考慮“0.”，則編碼輸出為:010111111 算數(shù)編碼法： 霍夫

13、曼編碼法： 9 1.8/ 5 avg L比特字符 1.9/ avg L比特 字符 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

14、）（1,7） 游程編碼適合于二值圖像編碼，只有黑白出現(xiàn)。規(guī)定“0”游程開(kāi)始。 例如：對(duì)于一個(gè)二元序列：00000011111000110010000001111100011001，對(duì)應(yīng)的又稱(chē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 P

15、ulse Code 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è)？ nnn eff nnn qe e nnn ffe nnnnnnnnnnn ffffeffeeeq 0 n q 0 n q 圖像壓縮圖像壓縮_ _有損壓縮有損壓縮 最佳預(yù)測(cè)器最佳預(yù)測(cè)器 預(yù)測(cè)器選擇要滿足兩個(gè)要求： a)使均方預(yù)測(cè)誤差最小，既： b)約束條

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