Chap10圖象壓縮與編碼課件

1、Chap 10 圖象壓縮與編碼要點(diǎn)：信息量，熵，聯(lián)合熵，率失真函數(shù)編碼效率，冗余度，壓縮比無(wú)失真編碼，有失真編碼霍夫曼編碼行程編碼預(yù)測(cè)編碼DCT編碼混合編碼圖象壓縮與編碼 數(shù)字圖象通常要求很大的比特?cái)?shù)，這給圖象的傳輸和存儲(chǔ)帶來(lái)相當(dāng)大的困難。要占用很多的資源，花很高的費(fèi)用。 如一幅512x512的黑白圖象的比特?cái)?shù)為 512x512x8=2,097,152 bit=256k。 再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8 bit，總比特?cái)?shù)為圖象壓縮與編碼 90 x60 x24x3x512x512x8bit=97,200M。 如一張

2、CD光盤(pán)可存600兆字節(jié)數(shù)據(jù)，這部電影光圖象（還有聲音）就需要160張CD光盤(pán)用來(lái)存儲(chǔ)。 對(duì)圖象數(shù)據(jù)進(jìn)行壓縮顯得非常必要。 本章討論的問(wèn)題：在滿足一定條件下，能否減小圖象bit數(shù)，以及用什么樣的編碼方法使之減少。英文字母出現(xiàn)相對(duì)頻率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出現(xiàn)相對(duì)頻率圖象編碼密碼點(diǎn)擊圖片播放視頻某個(gè)圖形或物品也可以作為密碼。 圖象編碼密碼虹膜與指紋。 圖象壓縮與編碼1圖象數(shù)據(jù)壓縮是可

3、能的：一般原始圖象中存在很大的冗余度。用戶通常允許圖象失真。當(dāng)信道的分辨率不及原始圖象的分辨率時(shí)，降低輸入的原始圖象的分辨率對(duì)輸出圖象分辨率影響不大。用戶對(duì)原始圖象的信號(hào)不全都感興趣，可用特征提取和圖象識(shí)別的方法，丟掉大量無(wú)用的信息。提取有用的信息，使必須傳輸和存儲(chǔ)的圖象數(shù)據(jù)大大減少。 圖象壓縮與編碼2原始圖象越有規(guī)則，各象素之間的相關(guān)性越強(qiáng)，它可能壓縮的數(shù)據(jù)就越多。 值得指出的是：當(dāng)前采用的編碼方法得到的結(jié)果，離可能壓縮的極限還相差很遠(yuǎn)，這說(shuō)明圖象數(shù)據(jù)壓縮的潛力是很大的，直到目前為止，它還是個(gè)正在繼續(xù)研究的領(lǐng)域。圖象壓縮與編碼3圖象結(jié)構(gòu)的性質(zhì)，大體上可分為兩大類，一類是具有一定圖形特征的結(jié)構(gòu)

4、，另一類是具有一定概率統(tǒng)計(jì)特性的結(jié)構(gòu)。 基于不同的圖象結(jié)構(gòu)特性，應(yīng)采用不同的壓縮編碼方法。圖象壓縮與編碼4全面評(píng)價(jià)一種編碼方法的優(yōu)劣，除了看它的編碼效率、實(shí)時(shí)性和失真度以外，還要看它的設(shè)備復(fù)雜程度，是否經(jīng)濟(jì)與實(shí)用。 常采用混合編碼的方案，以求在性能和經(jīng)濟(jì)上取得折衷。 隨著計(jì)算方法及VLSI的發(fā)展，使許多高效而又比較復(fù)雜的編碼方法在工程上有實(shí)現(xiàn)的可能。信源編碼的基本概念 圖象數(shù)據(jù)壓縮的目的是在滿足一定圖象質(zhì)量條件下，用盡可能少的比特?cái)?shù)來(lái)表示原始圖象，以提高圖象傳輸?shù)男屎蜏p少圖象存儲(chǔ)的容量，在信息論中稱為信源編碼。 信源編碼可分為兩大類，一類是無(wú)失真編碼，另一類是有失真編碼或稱限失真編碼。無(wú)失真

5、編碼 無(wú)失真編碼又稱信息保持編碼或可逆的無(wú)誤差編碼。 信息量：從N個(gè)相等可能發(fā)生的事件中，選出其中一個(gè)事件所需的信息度量，稱為信息量。 無(wú)失真編碼 要辨識(shí)1到32中選定的某一個(gè)數(shù)，可先提問(wèn)：“是否大于16？”，得到回答就消去半數(shù)可能事件。每提問(wèn)一次得到回答，可以得到1bit信息量（二進(jìn)制位）。這里共需5次，因此所需的信息量為 。例無(wú)失真編碼 定義信息量：從N個(gè)數(shù)選定一個(gè)數(shù)s的概率為p(s)，且等概率，p(s)=1/N。 熵：設(shè)信源符號(hào)表為 s=s1, s2, , sq，其概率分布為P(s)=p(s1), p(s2), , p(sq)，則信源的熵為無(wú)失真編碼 s作為灰度，共q級(jí)，出現(xiàn)概率均等時(shí)，

6、p(si)=1/q， 當(dāng)灰度只有兩級(jí)時(shí)，即si = 0, 1，且0出現(xiàn)概率為p1，1出現(xiàn)概率為p2=1- p1 ，其熵?zé)o失真編碼 當(dāng)p1=1/2， p2=1- p1 =1/2時(shí)， H(s)=1為最大值。如圖所示。無(wú)失真編碼熵的性質(zhì)：（1）熵是一個(gè)非負(fù)數(shù)，即總有H(s)0。（2）當(dāng)其中一個(gè)符號(hào)sj的出現(xiàn)概率p(sj)=1時(shí)，其余符號(hào)si(ij)的出現(xiàn)概率p(si) =0，H(s)=0。（3）當(dāng)各個(gè)si出現(xiàn)的概率相同時(shí)，則最大平均信息量為log2 q。（4）熵值總有H(s) log2 q。無(wú)失真編碼(一) 無(wú)失真編碼定理 可以證明，在無(wú)干擾的條件下，存在一種無(wú)失真的編碼方法，使編碼的平均長(zhǎng)度 L與

7、信源的熵H(s)任意地接近，即L=H(s)+，其中為任意小的正數(shù)，但以H(s)為其下限，即LH(s)，這就是香農(nóng)(Shannon)無(wú)干擾編碼定理。無(wú)失真編碼(二) 熵與相關(guān)性、冗余度的關(guān)系 對(duì)于無(wú)失真圖象的編碼，原始圖象數(shù)據(jù)的壓縮存在一個(gè)下限，即平均碼組長(zhǎng)度不能小于原始圖象的熵，而理論上的最佳編碼的平均碼長(zhǎng)無(wú)限接近原始圖象的熵。 原始圖象冗余度定義為：無(wú)失真編碼 將編碼效率定義為： 冗余度接近于0，或編碼效率接近于1的編碼稱為高效碼。無(wú)失真編碼 若原始圖象的平均比特率為n，編碼后的平均比特率為nd，則壓縮比C定義為： 由Shannon定理，無(wú)失真編碼最大可能的數(shù)據(jù)壓縮比為：無(wú)失真編碼 獨(dú)立信源

8、的熵與馬爾可夫信源的熵 令q=2L，其中L等于自然二進(jìn)制碼的長(zhǎng)度?？梢宰C明，對(duì)于獨(dú)立信源，等概率分布時(shí)，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能壓縮。討論（1）獨(dú)立信源，又稱無(wú)記憶信源，符號(hào)si 的出現(xiàn)，與其他的符號(hào)無(wú)關(guān)。無(wú)失真編碼 非等概率分布時(shí)的熵，一般有H1(s) 0，還有可能壓縮。（2）有限馬爾可夫(Markov)信源的熵 又稱有限記憶信源，它的統(tǒng)計(jì)特性要用轉(zhuǎn)移概率或條件概率來(lái)描述。 m階Markov信源，是指某個(gè)符號(hào)si出現(xiàn)的概率只與前面m個(gè)符號(hào)有關(guān)。無(wú)失真編碼 設(shè)s=s1, s2, sq，則轉(zhuǎn)移概率 p(si/si1, si2, sim)乃是前m個(gè)

9、符號(hào)為si1, si2, sim時(shí)，第 m+1個(gè)符號(hào)為si的概率。 信息量 I(si/si1, si2, sim)=-log2 p(si/si1, si2, sim) 無(wú)失真編碼 對(duì)符號(hào)表取平均的信息量 這是在給定序列si1, si2, sim的條件下，信源的條件熵。 無(wú)失真編碼 再考慮序列si1, si2, sim發(fā)生的概率， 可將m階Markov信源的熵定義為：無(wú)失真編碼 （四）高效的編碼方法 無(wú)干擾編碼定理只指出存在一種無(wú)失真的編碼，可使 。它并沒(méi)有指出具體的編碼方法。下面介紹幾種具體的編碼方法。（1）Huffman碼 它是長(zhǎng)度不均勻的，其平均長(zhǎng)度最短的即時(shí)可譯碼。其要點(diǎn)是對(duì)經(jīng)常出現(xiàn)的符

10、英文字母出現(xiàn)相對(duì)頻率字母ABCDEFGHIJKLM百分比8.21.52.84.312.72.22.06.17.00.20.84.02.4字母NOPQRSTUVWXYZ百分比6.77.51.90.16.06.39.12.81.02.40.22.00.1英文字母出現(xiàn)相對(duì)頻率國(guó)際莫爾斯電碼符號(hào)SymbolABCDEFGHIJKLMCode.-.-.-.-.-.-.-.-.-SymbolNOPQRSTUVWXYZCode-.-.-.-.-.-.-.-.-.-.-.Symbol0123456789Code-.-.-.-.-.-.-.-.Symbol.,?:;-/“Code.-.-.-.-.-.-.-.-

11、.-.-.-.-.無(wú)失真編碼號(hào)賦予最短的碼字，然后按出現(xiàn)概率減少的次序，逐個(gè)賦予較長(zhǎng)的碼字，這樣可使碼的平均長(zhǎng)度具有最小值，pi-si出現(xiàn)概率，li-對(duì)si編碼的長(zhǎng)度。無(wú)失真編碼 信號(hào)源 s=s1, s2, s3, s4, s5, s6，其概率分布為p1=0.4 p2=0.3 p3=0.1 p4=0.1 p5=0.06 p6=0.04，求最佳Huffman碼。例方法：將信源符號(hào)按出現(xiàn)概率從大到小排成一列，然后把最末兩個(gè)符號(hào)的概率相加，合成一個(gè)概率。無(wú)失真編碼方法：把這個(gè)符號(hào)的概率與其余符號(hào)的概率按從大到小排列，然后再把最末兩個(gè)符號(hào)的概率加起來(lái)，合成一個(gè)概率。 重復(fù)上述做法，直到最后剩下兩個(gè)概率

12、為止。從最后一步剩下的兩個(gè)概率開(kāi)始逐步向前進(jìn)行編碼。每步只需對(duì)兩個(gè)分支各賦予一個(gè)二進(jìn)制碼，如對(duì)概率大的賦予碼元0，對(duì)概率小的賦予碼元1。Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.1

13、0.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.

14、40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0

15、.60.40101010101S3=011Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.1

16、0.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011無(wú)失真編碼（2）B碼 在某些應(yīng)用中，編碼器輸入符號(hào)集合的概率分布服從乘冪律：pk=k-r, k=1,2,q。r為正常數(shù)，則用B碼，它接近于最佳編碼。B碼是一種非等長(zhǎng)碼，由兩部分組成，一部分叫“延續(xù)比特”，一部分叫“信息比特”。延續(xù)比特的作用是標(biāo)注一個(gè)碼字究竟延續(xù)多長(zhǎng)，信息比特的作用是表示不同的信息符號(hào)。無(wú)失真編碼方法： 將信源符號(hào)按出現(xiàn)概率從大到小排序，然后按B1碼的前后順序分別賦予相應(yīng)符號(hào)，便得到各符號(hào)的B1碼。其中信息碼是按二進(jìn)制的

17、長(zhǎng)度及數(shù)的順序排列的，即0，1，00，01，10，11，000，001，。延續(xù)碼C是在編碼過(guò)程中確定的，可將C=0賦予前一個(gè)碼字，將C=1賦予后一個(gè)碼字，再將C=0賦予下一個(gè)碼字。無(wú)失真編碼方法： 例如，編碼器輸入符號(hào)序列為s4s1s5s2, 則B1碼為： 0001，10，0100，11 ，或者 1011 ， 00，1110，01， 延續(xù)碼改變，表示前一個(gè)碼字結(jié)束，后一個(gè)碼字開(kāi)始。 B1碼優(yōu)點(diǎn)：編碼方法簡(jiǎn)單，容易實(shí)現(xiàn)。無(wú)失真編碼（3）移位碼S2 對(duì)具有單調(diào)減小概率的輸入信號(hào)相當(dāng)有效的非等長(zhǎng)碼。 S2碼由2bit長(zhǎng)的碼字組成，總共包含四個(gè)不同的碼字：C1=00，C2=01，C3=10，C4=11

18、， C4的個(gè)數(shù)用來(lái)表示該符號(hào)的序數(shù)超過(guò)3的次數(shù)。符號(hào)編碼：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3， 這種編碼方法更簡(jiǎn)單。幾種編碼比較輸入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04幾種編碼比較輸入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14幾種編碼比較輸入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼碼1000110100010100101

19、12.20.9750.0251.362.14B1碼C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14幾種編碼比較輸入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14B1碼C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2碼0001101100110111102.40.8950.1151.252.14幾種編碼比較輸入S1S2S3S4S5S6 rCH(s)概率0.40.30.10.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14B1碼C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14S2碼0001101100110111102.40.8950.1151.252.14自然碼00000101001110010130.7130.40212.14限失真編碼 嚴(yán)格的無(wú)失真編碼的壓縮比一般是不大的。編碼效率的提高往往要以采用較復(fù)雜的編碼方法為代價(jià)；另一方面，用戶通