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

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

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

周三例會報告26/11/2023

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

上海大學(xué)

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

OUTLINE:圖像壓縮1.香農(nóng)信息論2.數(shù)據(jù)壓縮原理3.數(shù)據(jù)冗余4.無損壓縮5.有損壓縮

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_香農(nóng)信息論1、香農(nóng)信息論例生活實例第一句話：我有一個師兄叫“**”。第二句話：我有一個舍友叫“**”。直觀的感受一下這兩句話所攜帶的未知信息量。說明：一個消息若能傳達(dá)給我們許多原來未知的內(nèi)容，我們就認(rèn)為這個信息很有意義，

信息量大；反之，一個消息傳達(dá)給我們的是已知確定的東西，則這個傳達(dá)就失去了意義。

信息量在信息論中：信息使用不確定的度量來確定的，一個消息的可能性越小，其信息含量越大；消息

的可能性越大，其信息含量越小。設(shè)某消息xi發(fā)生的概率為pxi,則該消息攜載的信息量為：Ixilogapxi1)當(dāng)a2時，則單位為比特(bit);

2)當(dāng)ae時，則單位為奈特(nat);

3)當(dāng)a10時，則單位為哈特(hat)。一般以2為底取對數(shù)，由此定義的信息量等于描述該信息所用的最少比特數(shù)。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_香農(nóng)信息論信息熵若信源有n個字符，對應(yīng)字符xi的概率為pxi,則該信源的平均信息量就稱為信息熵，既：

Hpxilog2pxii0

L1

L1

ninlog2ini0n

具體到數(shù)字圖像中，稱H為圖像信息熵。它給出了描述一幅圖像攜載信息量的最少比特數(shù)。

Shannon無失真編碼定理基于圖像信息熵，存在一種無失真的編碼方法，使編碼的平均碼長與信息熵?zé)o限的接近。既：

LavgH,0但以H為下限，既LavgH。這就是Shannon的無失真編碼定理。R1100%1HLavgHDLavgLavg無失真編碼性能的幾個指標(biāo)：

1)編碼效率

HLavg

RD1

nnn21121CRn1n1

2)冗余度

RD1100%或CRmLavg

RD1

1CR

3)壓縮比

或

CR

n1n2

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_圖像壓縮原理2、圖像壓縮原理1)數(shù)據(jù)壓縮的對象是數(shù)據(jù)，大的數(shù)據(jù)量并不代表含有大的信息量。2)圖像壓縮就是除去圖像中多余的數(shù)據(jù)而對信息沒有本質(zhì)的影響。3)圖像壓縮是以圖像編碼的形式實現(xiàn)的，用較少的比特數(shù)表示出現(xiàn)概率較大的灰度級，用較多的比特數(shù)表示出現(xiàn)概率較小的灰度級，從而使平均碼長更接近于信息熵。

圖像編碼碼本：編碼所用符號的集合稱為碼本。如Aa0,a1,a2,a3,a4,a5,a6碼字：對每個碼本的每個符號所賦的符號序列稱為碼字。如a001011碼字長度：每個碼字里的符號個數(shù)稱為碼字長度。數(shù)字圖像：碼長=二進(jìn)制數(shù)長度。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_數(shù)據(jù)冗余3、數(shù)據(jù)冗余1)信息熵冗余：也稱編碼冗余，如果圖像中平均比特數(shù)大于該圖像的信息熵，則圖像中存在冗余，這種冗余稱為信息熵冗余。2)空間冗余：也稱為像素間冗余或幾何冗余，是圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性所造成的冗余。3)時間冗余：視頻圖像序列中的不同幀之間的相關(guān)性所造成的冗余。4)視覺冗余：是指人眼不能感知或不敏感的那部分圖像信息。5)結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。6)知識冗余：是指有些圖像還包含與某些先驗知識有關(guān)的信息。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮4、無損編碼常用的無損編碼方法有霍夫曼編碼、香農(nóng)—費諾編碼、算術(shù)編碼、游程編碼和無損預(yù)測編碼等。1)Huffman編碼霍夫曼編碼法是消除編碼冗余最常用的方法。假設(shè)有一個信源為Aa0,a1,a2,a3,a4,a5,a6,其概率分布為：符號概率a0a1a2a3a4a5a6

0.16

0.4

0.12

0.04

0.02

0.2

0.06

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮

1

0.410.20000.160010.120100.0601100.060111

0.410.20000.160010.120100.12011

0.41

0.41

0.60

000001

0.24010.20000.16001

0.36000.2401

0.4

1

010

01100111001111

霍弗曼編碼示意圖

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮符號a0a1a2a3a4a5a6

概率霍弗曼編碼(碼字)二進(jìn)制編碼(碼字)

0.16001000

0.41001

0.12023010

0.0401110011

0.0202311100

0.2000101

0.06011011031.262.380

Huffman編碼效率信源信息熵為：HPaklog2pak2.325k071

壓縮比：CRmLavg

二進(jìn)制編碼效率為：H2.325100%100%77.5%m3

霍弗曼編碼平均碼長Lavg為：LavgBkPkk0N1

30.1610.430.1250.0450.0230.240.062.380

霍夫曼編碼效率為：H2.325100%100%97.7%Lavg2.3809

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮2)香農(nóng)-費諾編碼由于霍夫曼編碼法中的信源縮減過程復(fù)雜，當(dāng)信源符號個數(shù)較多時十分不便。為此Shannon和Fano提出了一種類似的變長編碼方法，相對于霍夫曼編碼法更方便、快捷。假設(shè)有一個信源為Aa0,a1,a2,a3,a4,a5,a6,其概率分布為：符號概率具體步驟如下：a)將信源符號按出現(xiàn)的概率pai由大到小排列；b)將信源A分成兩個子集a0A1pa0a1akak1和A2pakpak1ak2anpana0a1a2a3a4a5a6

0.16

0.4

0.12

0.04

0.02

0.2

0.06

pa1n

pak2

并且保證

papai0ijk1j

k

成立或差不多成立；

c)給兩個子集賦

不同的碼元值；d)重復(fù)(2)、(3),既對每個子集再一分為二，并賦予不同的碼元值，直到每個子集僅含一個符號為止。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮計算香農(nóng)-費諾編碼平均碼長為：LavgBkPkk0N1

10..430.230.1630.1240.0650.0450.022.380

0

0001

10010111011110

0

0111

11110

01

11111

香農(nóng)-費諾編碼示意圖

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮3)算術(shù)編碼例如：Ixilog2pxi1.732

算術(shù)編碼法和霍夫曼編碼法都是一種變長編碼。但霍夫曼編碼必須分配整數(shù)位碼字，而算數(shù)編碼可以分配帶有小數(shù)的比特數(shù)目信符，并且算術(shù)編碼給整個信源符號序列分配一個單一的算術(shù)碼字。假設(shè)有一信源為Ab,c,a,d,c,信源中各符號出現(xiàn)的概率分別為：p(a)0.2p(b)0.3p(c)0.4p(d)0.1

算術(shù)編碼具體步驟如下：a)“當(dāng)前區(qū)間”初始化[0,1);

b)對于輸入信源中的每個符號，依次執(zhí)行如下兩個步驟：①將“當(dāng)前區(qū)間”分成子區(qū)間，該子區(qū)間的長度正比于符號的概率；②選擇下一個信符對應(yīng)的子區(qū)間，并使它成為新的“當(dāng)前區(qū)間”;c)將整個信源的所有符號處理完后，在最后一個“當(dāng)前區(qū)間”中任找一個數(shù)作為算數(shù)編碼的輸入碼。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮Ab,c,a,d,c

算術(shù)編碼示意圖

輸出區(qū)間[0.3728,0.37376)

[0.01011111011,0.01011111101)

取位數(shù)最少的一個數(shù):0.010111111不考慮“0.”,則編碼輸出為:010111111

算數(shù)編碼法：L

avg

91.8比特/字符5

霍夫曼編碼法：Lavg1.9比特/字符

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_無損壓縮4)游程編碼游程：是指字符序列中各個字符連續(xù)重復(fù)出現(xiàn)而形成字符串的長度。游程編碼(行程編碼):就是將字符串序列映射成字符串的長度和串的位子的標(biāo)志序列。例如：一個字符串5555557777733322221111111

游程編碼：(5,6)(7,5)(3,3)(2,4)(1,7)游程編碼適合于二值圖像編碼，只有黑白出現(xiàn)。規(guī)定“0”游程開始。例如：對于一個二元序列：0000001111100011001,對應(yīng)的又稱序列為：653221。然后根據(jù)不同長度段發(fā)生的概率來分配不同長度的碼字。

5)無損預(yù)測編碼無損預(yù)測編碼跟有損預(yù)測編碼一起講解。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_有損壓縮5、有損編碼常用的有損編碼方法有預(yù)測編碼、變換編碼

1)預(yù)測編碼預(yù)測編碼是通過消除緊鄰像素在空間和時間上的冗余來實現(xiàn)的，它僅對每個像素中的新信息進(jìn)行提取并代替原圖像進(jìn)行編碼。新信息=實際值-預(yù)測值,既預(yù)測誤差。

差分脈沖編碼調(diào)制(DifferentialPulseCodeModulation,DPCM)。

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_有損壓縮

DPCM系統(tǒng)原理框圖

誤

差信號：

enfnfn

量化器誤差：qnenen接收端輸出：ffennn

可以推出：

effeeeqfnfnfnfnnnnnnnn

a)當(dāng)qn0時，無損預(yù)測編碼b)當(dāng)qn0時，有損預(yù)測編碼。問題：如何使誤差盡可能?。孔顑?yōu)預(yù)測？

數(shù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費諾編碼,游程編碼,預(yù)測編碼

圖像壓縮_有損壓縮最佳預(yù)測器預(yù)測器選擇要滿足兩個要求：a)使均方預(yù)測誤差最小，既：nEe2nEfnf

2

和fn=ifnii1m

b)約束條件：nenfnfnfnenf

常用的幾種線性預(yù)測方案①前值預(yù)測：fxm,ynafxm1,yn②一維預(yù)測：fxm,ynaifxi,yni0