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

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

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

周三例會(huì)報(bào)告26/11/2023

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

上海大學(xué)

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

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

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

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

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

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

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

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

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

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

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

Hpxilog2pxii0

L1

L1

ninlog2ini0n

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

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

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

1)編碼效率

HLavg

RD1

nnn21121CRn1n1

2)冗余度

RD1100%或CRmLavg

RD1

1CR

3)壓縮比

或

CR

n1n2

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

圖像壓縮_圖像壓縮原理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)的集合稱為碼本。如Aa0,a1,a2,a3,a4,a5,a6碼字：對(duì)每個(gè)碼本的每個(gè)符號(hào)所賦的符號(hào)序列稱為碼字。如a001011碼字長(zhǎng)度：每個(gè)碼字里的符號(hào)個(gè)數(shù)稱為碼字長(zhǎng)度。數(shù)字圖像：碼長(zhǎng)=二進(jìn)制數(shù)長(zhǎng)度。

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

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

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

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

0.16

0.4

0.12

0.04

0.02

0.2

0.06

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

圖像壓縮_無(wú)損壓縮

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ù)字圖像處理,圖像壓縮,圖像編碼,霍夫曼編碼,香濃-費(fèi)諾編碼,游程編碼,預(yù)測(cè)編碼

圖像壓縮_無(wú)損壓縮符號(hào)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

霍弗曼編碼平均碼長(zhǎng)Lavg為：LavgBkPkk0N1

30.1610.430.1250.0450.0230.240.062.380

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

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

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

0.16

0.4

0.12

0.04

0.02

0.2

0.06

pa1n

pak2

并且保證

papai0ijk1j

k

成立或差不多成立；

c)給兩個(gè)子集賦

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

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

圖像壓縮_無(wú)損壓縮計(jì)算香農(nóng)-費(fèi)諾編碼平均碼長(zhǎng)為：LavgBkPkk0N1

10..430.230.1630.1240.0650.0450.022.380

0

0001

10010111011110

0

0111

11110

01

11111

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

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

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

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

算術(shù)編碼具體步驟如下：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ù)編碼的輸入碼。

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

圖像壓縮_無(wú)損壓縮Ab,c,a,d,c

算術(shù)編碼示意圖

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

[0.01011111011,0.01011111101)

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

算數(shù)編碼法：L

avg

91.8比特/字符5

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

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

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

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

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

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

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

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

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

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

圖像壓縮_有損壓縮

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

誤

差信號(hào)：

enfnfn

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

可以推出：

effeeeqfnfnfnfnnnnnnnn

a)當(dāng)qn0時(shí)，無(wú)損預(yù)測(cè)編碼b)當(dāng)qn0時(shí)，有損預(yù)測(cè)編碼。問(wèn)題：如何使誤差盡可能小？最優(yōu)預(yù)測(cè)？

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

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

2

和fn=ifnii1m

b)約束條件：nenfnfnfnenf

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