第九章 圖像編碼

第九章圖像編碼1北京大學(xué)遙感所第九章 圖像編碼■概述■信息量和信息熵■圖像信息熵值和信息剩余度■編碼技術(shù)■預(yù)測(cè)編碼JPEG與MPEG簡(jiǎn)介2北京大學(xué)遙感所§9.1概述■什么是圖像編碼？Q 數(shù)字圖像作為數(shù)字存儲(chǔ)時(shí)數(shù)據(jù)量特別大，并且傳輸時(shí)占用頻帶寬，因而需要事先對(duì)圖像進(jìn)行壓縮編碼。圖像的壓縮編碼，依據(jù)圖像信號(hào)固有的統(tǒng)計(jì)特征和人類的視覺(jué)特征進(jìn)行。Q 圖像信號(hào)固有的統(tǒng)計(jì)特征表明：圖像相鄰象素之間，相鄰行之間，或者相鄰幀之間，存在較強(qiáng)的相關(guān)性。利用某種編碼方法在一定程度上消除這些相關(guān)性，就可以實(shí)現(xiàn)圖像信息的數(shù)據(jù)壓縮。3北京大學(xué)遙感所§9.1概述■無(wú)損壓縮編碼：（也叫信息保持壓縮編碼）Q無(wú)損壓縮編碼方法是基于圖像信息的統(tǒng)計(jì)特性，其表現(xiàn)特點(diǎn)是圖像信息在一行的相鄰象素間、或相鄰行列之間、相鄰幀之間具有較強(qiáng)的相關(guān)性，去掉這些相關(guān)性，即可去掉圖像信息中許多冗余信息，而保持那些有用信息。Q 信息論理論證明，只要編碼后的圖像的每個(gè)象素的平均碼元長(zhǎng)度大于圖像的熵值，則總能保持圖像中的有用信息，在解碼重建圖像時(shí)不致于造成失真。4北京大學(xué)遙感所§9.1概述■有損壓縮編碼：Q經(jīng)采用某種方法對(duì)圖像數(shù)據(jù)壓縮雖然會(huì)造成一定程度的失真，但在重建時(shí)，這種失真人眼難以察覺(jué)，能被人眼視覺(jué)所忽略，或從主觀感覺(jué)上覺(jué)察不出它與原圖像之間的差別。Q這種壓縮編碼屬于信息非保持編碼，與信息保持編碼相比具有更高的壓縮效率5北京大學(xué)遙感所§9.1概述■研究圖像編碼技術(shù)的目的：在保證圖像觀察質(zhì)量的前提下，盡可能最大限度地降低碼率（單位時(shí)間內(nèi)所傳輸圖像數(shù)據(jù)的比特-bit數(shù)），以利于節(jié)省圖像數(shù)據(jù)的存儲(chǔ)空間，減少傳輸時(shí)間、傳輸通道，降低成本。流程圖如下：原始圖像數(shù)據(jù)編碼器被壓縮的圖像數(shù)據(jù)傳輸傳輸解碼器重建圖像數(shù)據(jù)被壓縮的圖像數(shù)據(jù)6北京大學(xué)遙感所§9.2信息量和信息熵■“信息”是指對(duì)消息接收者來(lái)說(shuō)預(yù)先不知道的報(bào)導(dǎo)。從概率統(tǒng)計(jì)的角度來(lái)看，由信息源發(fā)出一系列消息{ak}，出現(xiàn)概率率p(ak),k

0,1,2,...,K

1■其中，K為消息源的總數(shù)量。■假定接收者接收到符號(hào)為ak的概率為p(ak)，則信息量定義為I

log[p(ak)]7北京大學(xué)遙感所§9.2信息量和信息熵■其中信息源發(fā)出的各個(gè)是獨(dú)立無(wú)關(guān)的，稱為無(wú)記憶信息源。當(dāng)無(wú)記憶信息源發(fā)出的各個(gè)消息是等概率的，信息量為最大。消息源的熵定義為K

1H

E{I(ak)}

p(ak)log[p(ak)]k

0■上式稱為信息熵或信源熵，熵值的單位是：“比特/符號(hào)”。8北京大學(xué)遙感所§9.2信息量和信息熵■如果一幅亮度分辨率為8bit的黑白圖像，從其亮度直方圖的分布看是等概率的，它的熵值為：255H

pilog2pi11256256*log ??i

0

256*2????

8比特/象素■對(duì)于一個(gè)8bit的圖像來(lái)說(shuō)，如果其直方圖分布是等概率的，它的熵值就是8比特/象素。9北京大學(xué)遙感所§9.3圖像信息熵值和信息剩余度■編碼效率：■一幅圖像在一般情況下各亮度值總是非等概率的，因此其熵值總是小于等概率的熵值。去掉這些冗余的信息，便壓縮編碼后的圖像熵值不低于圖像信息源熵值，就不會(huì)丟失圖像的有用信息?！鱿鄬?duì)熵和剩余度：一個(gè)信息源實(shí)際輸出的熵與該信息源的最大可能熵之比稱為相對(duì)熵h,信源的剩余度定義為r

1

haNlog nH(X)

10北京大學(xué)遙感所§9.4編碼技術(shù)哈夫曼編碼(Huffmancoding)■

鏈碼■

拓?fù)鋽?shù)據(jù)結(jié)構(gòu)■

關(guān)系結(jié)構(gòu)金字塔編碼（pyramids）四叉樹（Quad-trees）11北京大學(xué)遙感所§9.4.1哈夫曼編碼哈夫曼編碼(Huffmancoding)Q

最早于50年代提出，它是一種無(wú)損的統(tǒng)計(jì)編碼方法。哈夫曼方法用變長(zhǎng)的碼來(lái)使冗余量達(dá)到最小。其基本思想是：對(duì)于出現(xiàn)概率大的信息符號(hào)編以短字長(zhǎng)的碼字，對(duì)于出現(xiàn)概率小的信息符號(hào)編以長(zhǎng)字長(zhǎng)的碼字。Q

它屬于信息保持編碼，又叫做熵保存編碼，或者叫熵編碼。12北京大學(xué)遙感所§9.4.1哈夫曼編碼具體算法：Q將各消息按照概率由大到小排成一個(gè)序列；Q將其中兩個(gè)最小概率所對(duì)應(yīng)的符號(hào)為子結(jié)點(diǎn)，（概率較小者為左結(jié)點(diǎn)，概率較大者為右結(jié)點(diǎn)）由此構(gòu)造其父結(jié)點(diǎn)，其概率等于二者概率之和；Q將新生成的結(jié)點(diǎn)與未經(jīng)處理的消息按照概率大小重新排列，形成一個(gè)新的概率序列；重復(fù)上述步驟，直到所有結(jié)點(diǎn)全部插入到結(jié)點(diǎn)表中；Q設(shè)所有的結(jié)點(diǎn)左結(jié)點(diǎn)為1，右結(jié)點(diǎn)為0，從根結(jié)點(diǎn)開(kāi)始經(jīng)中間結(jié)點(diǎn)到達(dá)葉結(jié)點(diǎn)，其路徑代碼即是該結(jié)點(diǎn)的Huffman編碼。13北京大學(xué)遙感所§9.4.1哈夫曼編碼互換，此時(shí)平均碼長(zhǎng)為 ，則 為，可見(jiàn)，N'

N

[np(l)

n p(l)]

[n p(l)

np(l)]b a a b a a b b

N

nb[p(la)

p(lb)]

na[p(la)

p(lb)]

N

(nb

na)[p(la)

p(lb)]Q證明：設(shè)最佳排列方式的碼字平均長(zhǎng)度為N，則mN

niP(li)i

1Q其中p(li)為信源符號(hào)li出現(xiàn)的概率，ni為編碼后符號(hào)的碼字長(zhǎng)度，a b a b當(dāng) p(l)

時(shí)p(l，)有n

n,a,b

1,2,

mQ將abl 與l' 'N NQ因?yàn)閚b

na，p(la)

p(lb)，所以QN是最短的。N'

N14北京大學(xué)遙感所§9.4.1哈夫曼編碼舉例：某信源發(fā)出的8個(gè)消息及其相應(yīng)出現(xiàn)的概率為：P(A)=0.1;P(B)=0.18;P(C)=0.4;P(D)=0.05;P(E)=0.06;P(F)=0.1;P(G)=0.07;P(H)=0.04C：1；B：001；A：011；F：0000G：0100；E：0101；D：00010；H：000111m平均碼長(zhǎng)為：L

nip(i)

2.61比特/消息i

18信源實(shí)際輸出的熵：H

p(i)log2p(i)

2.55比特/消息編碼效率為：

2.55/2.61

97.8%15北京大學(xué)遙感所§9.4.2行程編碼■行程編碼：指在一行掃描的象素中，比較相鄰象素的幅度。當(dāng)幅度有顯著變化時(shí)，就說(shuō)明有一個(gè)行程存在。■通常用于圖像矩陣中符號(hào)串的表示。例如，傳真機(jī)就使用這種方式。在二值圖像中，行程編碼僅記錄圖像中屬于物體的區(qū)域，該區(qū)域表示成以表為元素的表。圖像的每行表示成一個(gè)子表，它的第一個(gè)元素為行號(hào)，然后是兩個(gè)縱坐標(biāo)構(gòu)成的項(xiàng)，第一個(gè)為行程的開(kāi)始的縱坐標(biāo)（列號(hào)），第二個(gè)為行程的結(jié)束的縱坐標(biāo)。一行中可以有若干個(gè)這樣的序列項(xiàng)。16北京大學(xué)遙感所§9.4.2行程編碼0 123 4 5 60123456行程編碼;編碼為((11144)(214)(52355)).17北京大學(xué)遙感所§9.4.3鏈碼■鏈碼：描述物體的邊界，鏈碼中的符號(hào)一般對(duì)應(yīng)于圖像基元的鄰接關(guān)系。如下圖所示。鏈碼可以用靜態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)表示，如1維數(shù)組，取其大小為鏈碼的最大可能長(zhǎng)度；也可以用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)表示，且這樣在節(jié)省存儲(chǔ)空間方面更合適。18北京大學(xué)遙感所§9.4.3鏈碼76504123鏈碼示例：00007766555555660000000644444444222111111223444565221119北京大學(xué)遙感所§9.4.4拓?fù)鋽?shù)據(jù)結(jié)構(gòu)■拓?fù)鋽?shù)據(jù)結(jié)構(gòu)：圖像描述成一組元素及其相互關(guān)系的圖結(jié)構(gòu)。例如，賦值的屬性圖，區(qū)域鄰接圖。區(qū)域鄰接圖例子如下：13245013

245區(qū)域鄰接圖例子20北京大學(xué)遙感所§9.4.5關(guān)系結(jié)構(gòu)■關(guān)系結(jié)構(gòu)：信息集中在語(yǔ)義上重要的圖像組成部分（它們是圖像分割的結(jié)果）即物體之間的關(guān)系上，適合用于高層次的圖像理解工作。例如，使用關(guān)系結(jié)構(gòu)描述自然場(chǎng)景的示意圖（物體及其關(guān)系屬性表）如下：21北京大學(xué)遙感所§9.4.5關(guān)系結(jié)構(gòu)1234567示例關(guān)系表No.ObjectnameColorMin.rowMin.col.Inside1SunWhite54022SkyBlue00-3CloudGrey2018024TreetrunkBrown957565TreecrownGreen5363-6HillLightgreen970-7PondBlue100160622北京大學(xué)遙感所§9.4.6金字塔編碼Level0Level2Level1金字塔編碼23北京大學(xué)遙感所§9.4.7四叉樹（Quad-trees）023101112120121 122 123四叉樹編碼01011120121131221232324北京大學(xué)遙感所§9.5預(yù)測(cè)編碼?預(yù)測(cè)編碼（DifferentialPulseCodeModula-tion）是統(tǒng)計(jì)冗余數(shù)據(jù)壓縮理論的三個(gè)重要分支之一。?預(yù)測(cè)編碼的理論基礎(chǔ)是現(xiàn)代統(tǒng)計(jì)學(xué)和控制論，它主要減少了數(shù)據(jù)在時(shí)間和空間上的相關(guān)性。?對(duì)于靜止圖像來(lái)說(shuō)，預(yù)測(cè)編碼將被圖像變換編碼所取代。?而預(yù)測(cè)編碼對(duì)于視頻圖像來(lái)說(shuō)，它充分利用了連續(xù)幀之間的統(tǒng)計(jì)冗余性，是當(dāng)今主流技術(shù)并且還會(huì)流行于未來(lái)。25北京大學(xué)遙感所§9.5預(yù)測(cè)編碼№.1預(yù)測(cè)編碼的基本原理?預(yù)測(cè)編碼是根據(jù)圖像數(shù)學(xué)模型利用以往的樣本值對(duì)于新樣本值進(jìn)行預(yù)測(cè)，然后將樣本的實(shí)際值與其預(yù)測(cè)值相減得到一個(gè)誤差值，對(duì)這一誤差值進(jìn)行編碼,是有損壓縮編碼。?如果模型足夠好且樣本序列在時(shí)間上相關(guān)性較強(qiáng)，那么誤差信號(hào)的幅度將遠(yuǎn)遠(yuǎn)小于原始信號(hào)，從而可以用較少的數(shù)據(jù)對(duì)其差值量化得到較好的數(shù)據(jù)壓縮效果。26北京大學(xué)遙感所§9.5預(yù)測(cè)編碼№.1預(yù)測(cè)編碼的基本原理?如果能精確地預(yù)測(cè)數(shù)據(jù)源輸出，那就不存在關(guān)于數(shù)據(jù)源的不確定性，也就不存在要傳輸?shù)男畔ⅰ?通常預(yù)測(cè)器的設(shè)計(jì)不是利用數(shù)據(jù)源的實(shí)際數(shù)學(xué)模型，而是根據(jù)經(jīng)驗(yàn)事先準(zhǔn)備一個(gè)經(jīng)驗(yàn)數(shù)學(xué)模型，因?yàn)閿?shù)據(jù)源的實(shí)際數(shù)學(xué)模型是非常復(fù)雜，而且是時(shí)變的。?實(shí)驗(yàn)結(jié)果表明：以最小均方預(yù)測(cè)誤差設(shè)計(jì)的預(yù)測(cè)器不但能獲得最小均方預(yù)測(cè)誤差，容易實(shí)現(xiàn)，同時(shí)在視覺(jué)效果上也是比較好的。27北京大學(xué)遙感所§9.5預(yù)測(cè)編碼＋＋＋＋－№.2預(yù)測(cè)編碼的流程圖＋編碼傳輸濾波預(yù)測(cè)輸出量化預(yù)測(cè)抽樣輸入預(yù)測(cè)編碼原理圖28北京大學(xué)遙感所§9.5預(yù)測(cè)編碼№.3預(yù)測(cè)編碼的統(tǒng)計(jì)特性?一般情況下，相鄰兩象素灰度值突變的概率較小。如果取一幅圖像第i行的第j列象素的亮度離散值為f(i,j)，則△1=f(i,j)-f(i,j-1)△2=f(i,j)-f(i-1,j)其中△稱為差值信號(hào)。?幅度差值愈大的差值信號(hào)出現(xiàn)的概率愈小，而零值或接近零值的差值信號(hào)出現(xiàn)的概率最大。29北京大學(xué)遙感所§9.5預(yù)測(cè)編碼№.3預(yù)測(cè)編碼的統(tǒng)計(jì)特性?圖像差值信號(hào)的概率分布如圖所示：概率差值信號(hào)-2-101230北京大學(xué)遙感所§9.5預(yù)測(cè)編碼№.4預(yù)測(cè)編碼的編碼