Chap10圖象壓縮與編碼課件

Chap10圖象壓縮與編碼要點：信息量，熵，聯(lián)合熵，率失真函數(shù)編碼效率，冗余度，壓縮比無失真編碼，有失真編碼霍夫曼編碼行程編碼預(yù)測編碼DCT編碼混合編碼Chap10圖象壓縮與編碼要點：信息量，熵，聯(lián)合熵，率1圖象壓縮與編碼數(shù)字圖象通常要求很大的比特數(shù)，這給圖象的傳輸和存儲帶來相當(dāng)大的困難。要占用很多的資源，花很高的費用。如一幅512x512的黑白圖象的比特數(shù)為512x512x8=2,097,152bit=256k。再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8bit，總比特數(shù)為圖象壓縮與編碼數(shù)字圖象通常要求很大的比特數(shù)，這給圖象2圖象壓縮與編碼90x60x24x3x512x512x8bit=97,200M。如一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影光圖象（還有聲音）就需要160張CD光盤用來存儲。

對圖象數(shù)據(jù)進行壓縮顯得非常必要。本章討論的問題：在滿足一定條件下，能否減小圖象bit數(shù)，以及用什么樣的編碼方法使之減少。圖象壓縮與編碼90x60x24x3x512x3英文字母出現(xiàn)相對頻率字母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)相對頻率字母百分比字母百分比4英文字母出現(xiàn)相對頻率英文字母出現(xiàn)相對頻率5圖象編碼—密碼點擊圖片播放視頻某個圖形或物品也可以作為密碼。圖象編碼—密碼點擊圖片某個圖形或物品也可以作為密碼。6圖象編碼—密碼虹膜與指紋。圖象編碼—密碼虹膜與指紋。7圖象壓縮與編碼1．圖象數(shù)據(jù)壓縮是可能的：一般原始圖象中存在很大的冗余度。用戶通常允許圖象失真。當(dāng)信道的分辨率不及原始圖象的分辨率時，降低輸入的原始圖象的分辨率對輸出圖象分辨率影響不大。用戶對原始圖象的信號不全都感興趣，可用特征提取和圖象識別的方法，丟掉大量無用的信息。提取有用的信息，使必須傳輸和存儲的圖象數(shù)據(jù)大大減少。圖象壓縮與編碼1．圖象數(shù)據(jù)壓縮是可能的：8圖象壓縮與編碼2．原始圖象越有規(guī)則，各象素之間的相關(guān)性越強，它可能壓縮的數(shù)據(jù)就越多。值得指出的是：當(dāng)前采用的編碼方法得到的結(jié)果，離可能壓縮的極限還相差很遠，這說明圖象數(shù)據(jù)壓縮的潛力是很大的，直到目前為止，它還是個正在繼續(xù)研究的領(lǐng)域。圖象壓縮與編碼2．原始圖象越有規(guī)則，各象素之間的相關(guān)性越強，9圖象壓縮與編碼3．圖象結(jié)構(gòu)的性質(zhì)，大體上可分為兩大類，一類是具有一定圖形特征的結(jié)構(gòu)，另一類是具有一定概率統(tǒng)計特性的結(jié)構(gòu)?；诓煌膱D象結(jié)構(gòu)特性，應(yīng)采用不同的壓縮編碼方法。圖象壓縮與編碼3．圖象結(jié)構(gòu)的性質(zhì)，大體上可分為兩大類，一類是10圖象壓縮與編碼4．全面評價一種編碼方法的優(yōu)劣，除了看它的編碼效率、實時性和失真度以外，還要看它的設(shè)備復(fù)雜程度，是否經(jīng)濟與實用。常采用混合編碼的方案，以求在性能和經(jīng)濟上取得折衷。

隨著計算方法及VLSI的發(fā)展，使許多高效而又比較復(fù)雜的編碼方法在工程上有實現(xiàn)的可能。圖象壓縮與編碼4．全面評價一種編碼方法的優(yōu)劣，除了看它的編碼11信源編碼的基本概念圖象數(shù)據(jù)壓縮的目的是在滿足一定圖象質(zhì)量條件下，用盡可能少的比特數(shù)來表示原始圖象，以提高圖象傳輸?shù)男屎蜏p少圖象存儲的容量，在信息論中稱為信源編碼。信源編碼可分為兩大類，一類是無失真編碼，另一類是有失真編碼或稱限失真編碼。信源編碼的基本概念圖象數(shù)據(jù)壓縮的目的是在滿足一定圖象12無失真編碼

無失真編碼又稱信息保持編碼或可逆的無誤差編碼。

信息量：從N個相等可能發(fā)生的事件中，選出其中一個事件所需的信息度量，稱為信息量。無失真編碼無失真編碼又稱信息保持編碼或可逆的無誤差編13無失真編碼

要辨識1到32中選定的某一個數(shù)，可先提問：“是否大于16？”，得到回答就消去半數(shù)可能事件。每提問一次得到回答，可以得到1bit信息量（二進制位）。這里共需5次，因此所需的信息量為。例無失真編碼要辨識1到32中選定的某一個數(shù)，可先提問14無失真編碼定義信息量：從N個數(shù)選定一個數(shù)s的概率為p(s)，且等概率，p(s)=1/N。熵：設(shè)信源符號表為s={s1,s2,…,

sq}，其概率分布為P(s)={p(s1),p(s2),…,p(sq)}，則信源的熵為無失真編碼定義信息量：從N個數(shù)選定一個數(shù)s的概率為p15無失真編碼s作為灰度，共q級，出現(xiàn)概率均等時，p(si)=1/q，當(dāng)灰度只有兩級時，即si=0,1，且0出現(xiàn)概率為p1，1出現(xiàn)概率為p2=1-p1

，其熵?zé)o失真編碼s作為灰度，共q級，出現(xiàn)概率均等時，p(s16無失真編碼當(dāng)p1=1/2，p2=1-p1=1/2時，H(s)=1為最大值。如圖所示。無失真編碼當(dāng)p1=1/2，p2=1-p1=1/17無失真編碼熵的性質(zhì)：（1）熵是一個非負數(shù)，即總有H(s)≥0。（2）當(dāng)其中一個符號sj的出現(xiàn)概率p(sj)=1時，其余符號si(i≠j)的出現(xiàn)概率p(si)

=0，H(s)=0。（3）當(dāng)各個si出現(xiàn)的概率相同時，則最大平均信息量為log2

q。（4）熵值總有H(s)≤log2

q。無失真編碼熵的性質(zhì)：18無失真編碼(一)無失真編碼定理

可以證明，在無干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度

L與信源的熵H(s)任意地接近，即L=H(s)+ε，其中ε為任意小的正數(shù)，但以H(s)為其下限，即L≥H(s)，這就是香農(nóng)(Shannon)無干擾編碼定理。

無失真編碼(一)無失真編碼定理19無失真編碼(二)熵與相關(guān)性、冗余度的關(guān)系對于無失真圖象的編碼，原始圖象數(shù)據(jù)的壓縮存在一個下限，即平均碼組長度不能小于原始圖象的熵，而理論上的最佳編碼的平均碼長無限接近原始圖象的熵。

原始圖象冗余度定義為：無失真編碼(二)熵與相關(guān)性、冗余度的關(guān)系20無失真編碼

將編碼效率定義為：

冗余度接近于0，或編碼效率接近于1的編碼稱為高效碼。無失真編碼將編碼效率定義為：冗余度接近于0，21無失真編碼若原始圖象的平均比特率為n，編碼后的平均比特率為nd，則壓縮比C定義為：由Shannon定理，無失真編碼最大可能的數(shù)據(jù)壓縮比為：無失真編碼若原始圖象的平均比特率為n，編碼后的平均比22無失真編碼

獨立信源的熵與馬爾可夫信源的熵令q=2L，其中L等于自然二進制碼的長度?？梢宰C明，對于獨立信源，等概率分布時，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能壓縮。討論（1）獨立信源，又稱無記憶信源，符號si的出現(xiàn)，與其他的符號無關(guān)。無失真編碼獨立信源的熵與馬爾可夫信源的23無失真編碼非等概率分布時的熵，一般有H1(s)<HM(s)=L，因而冗余度r=L/H1(s)-1>0，還有可能壓縮。（2）有限馬爾可夫(Markov)信源的熵又稱有限記憶信源，它的統(tǒng)計特性要用轉(zhuǎn)移概率或條件概率來描述。

m階Markov信源，是指某個符號si出現(xiàn)的概率只與前面m個符號有關(guān)。無失真編碼非等概率分布時的熵，一般有H1(s)<H24無失真編碼

設(shè)s={s1,s2,…,sq}，則轉(zhuǎn)移概率

p(si/si1,si2,…,sim)乃是前m個符號為si1,si2,…,sim時，第m+1個符號為si的概率。

信息量

I(si/si1,si2,…,sim)=-log2p(si/si1,si2,…,sim)無失真編碼設(shè)s={s1,s2,…,sq}，則轉(zhuǎn)移25無失真編碼對符號表取平均的信息量

這是在給定序列si1,si2,…,sim的條件下，信源的條件熵。

無失真編碼對符號表取平均的信息量這是在給定序26無失真編碼

再考慮序列si1,si2,…,sim發(fā)生的概率，可將m階Markov信源的熵定義為：無失真編碼再考慮序列si1,si2,…,sim發(fā)27無失真編碼

（四）高效的編碼方法無干擾編碼定理只指出存在一種無失真的編碼，可使。它并沒有指出具體的編碼方法。下面介紹幾種具體的編碼方法。（1）Huffman碼它是長度不均勻的，其平均長度最短的即時可譯碼。其要點是對經(jīng)常出現(xiàn)的符無失真編碼（四）高效的編碼方法28英文字母出現(xiàn)相對頻率字母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)相對頻率字母百分比字母百分比29英文字母出現(xiàn)相對頻率英文字母出現(xiàn)相對頻率30國際莫爾斯電碼符號SymbolABCDEFGHIJKLMCode.--…-.-.-.....-.--.…....----.-.-..--SymbolNOPQRSTUVWXYZCode-.---.--.--.-.-.…-..-…-.---..--.----..Symbol0123456789Code-----.----..---…--….-…..-….--...---..----.Symbol.,?:;-/“Code.-.-.---..--..--..---…-.-.-.-…--..-..-..-.國際莫爾斯電碼符號SymbolCodeSymbolCodeS31無失真編碼號賦予最短的碼字，然后按出現(xiàn)概率減少的次序，逐個賦予較長的碼字，這樣可使碼的平均長度具有最小值，pi--si出現(xiàn)概率，li--對si編碼的長度。無失真編碼號賦予最短的碼字，然后按出現(xiàn)概率減少的次序，逐個賦32無失真編碼

信號源s={s1,s2,s3,s4,s5,s6}，其概率分布為p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman碼。例方法：將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。無失真編碼信號源s={s1,s2,s3,s433無失真編碼方法：把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。重復(fù)上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。無失真編碼方法：34Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Huffman編碼例輸入輸入概率35Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman編碼例輸入輸入概率第一步36Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼例輸入輸入概率第一步第二步37Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼例輸入輸入概率第一步第二步第三步38Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步39Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步0040Huffman編碼例輸入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.40101010101S1=1Huffman編碼例輸入輸入概率第一步第二步第三步第四步0041Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步0042Huffman編碼例輸入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.40101010101S3=011Huffman編碼例輸入輸入概率第一步第二步第三步第四步0043Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步0044Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步0045Huffman編碼例輸入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.40101010101S6=01011Huffman編碼例輸入輸入概率第一步第二步第三步第四步0046無失真編碼（2）B碼

在某些應(yīng)用中，編碼器輸入符號集合的概率分布服從乘冪律：pk=k-r,k=1,2,…,q。r為正常數(shù)，則用B碼，它接近于最佳編碼。B碼是一種非等長碼，由兩部分組成，一部分叫“延續(xù)比特”，一部分叫“信息比特”。延續(xù)比特的作用是標(biāo)注一個碼字究竟延續(xù)多長，信息比特的作用是表示不同的信息符號。無失真編碼（2）B碼47無失真編碼方法：將信源符號按出現(xiàn)概率從大到小排序，然后按B1碼的前后順序分別賦予相應(yīng)符號，便得到各符號的B1碼。其中信息碼是按二進制的長度及數(shù)的順序排列的，即0，1，00，01，10，11，000，001，…。延續(xù)碼C是在編碼過程中確定的，可將C=0賦予前一個碼字，將C=1賦予后一個碼字，再將C=0賦予下一個碼字。無失真編碼方法：48無失真編碼方法：例如，編碼器輸入符號序列為s4s1s5s2…,則B1碼為：

0001，10，0100，11，…或者1011，00，1110，01，…延續(xù)碼改變，表示前一個碼字結(jié)束，后一個碼字開始。

B1碼優(yōu)點：編碼方法簡單，容易實現(xiàn)。無失真編碼方法：49無失真編碼（3）移位碼S2對具有單調(diào)減小概率的輸入信號相當(dāng)有效的非等長碼。

S2碼由2bit長的碼字組成，總共包含四個不同的碼字：C1=00，C2=01，C3=10，C4=11，C4的個數(shù)用來表示該符號的序數(shù)超過3的次數(shù)。符號編碼：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，…這種編碼方法更簡單。無失真編碼（3）移位碼S250幾種編碼比較輸入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04幾種編碼比較輸入概率51幾種編碼比較輸入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14幾種編碼比較輸入概率霍夫曼碼52幾種編碼比較輸入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.060.04霍夫曼碼100011010001010010112.20.9750.0251.362.14B1碼C0C1C0C0C0C1C1C0C1C12.60.8250.211.152.14幾種編碼比較輸入概率霍夫曼碼B1碼53幾種編碼比較輸入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幾種編碼比較輸入概率霍夫曼碼B1碼S2碼54幾種編碼比較輸入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幾種編碼比較輸入概率霍夫曼碼B1碼S2碼自然碼55限失真編碼嚴(yán)格的無失真編碼的壓縮比一般是不大的。編碼效率的提高往往要以采用較復(fù)雜的編碼方法為代價；另一方面，用戶通常允許圖象有一定的失真，這為圖象數(shù)據(jù)壓縮提供了較大的可能性，因此人們非常注意限失真編碼問題。在給定失真條件下，信源編碼所能達到的壓縮率的極限碼率，稱為率失真函數(shù)，R(D)

，

D為失真上限。限失真編碼嚴(yán)格的無失真編碼的壓縮比一般是不大的。編碼56限失真編碼

R(0)≤H(Y)，收到的信號序列不存在相關(guān)性時，等號成立。D↑，R(D)↓。允許失真度D越小，則所需率失真函數(shù)值R(D)就越大，要求信源編碼效率也越高。限失真編碼R(0)≤H(Y)，收到的信號序列不存在57p.436p.43658圖象編碼模型映射變換器量化器編碼器原始圖象碼字圖象壓縮編碼的一般框圖圖象編碼模型映射量化器編碼器原始圖象碼字圖象壓縮編碼的一般框59圖象編碼模型

映射變換：將輸入數(shù)據(jù)從象素域變換到另一個域，在變換域中則能以較少的比特數(shù)對圖象進行量化編碼。對映射變換器的要求，要從數(shù)據(jù)壓縮的有效性、保真度和經(jīng)濟實用方面考慮，應(yīng)該是高度去相關(guān)的、可逆的、重現(xiàn)的均方誤差最小、易于實現(xiàn)的。圖象編碼模型映射變換：將輸入數(shù)據(jù)從象素域變換到另一個60圖象編碼模型（1）行程編碼把沿著掃描行的象素序列x1,x2,…,xN映射為行程序列(g1,l1),

(g2,l2),…,(gk,lk)。

gi—灰度級li—gi的行程長度因為象素序列可以根據(jù)行程序列來重建，故行程映射變換是可逆的。因它包含灰度鑒別和行程計數(shù)，故它是非線性的。例圖象編碼模型（1）行程編碼例61圖象編碼模型（2）差分映射編碼矩陣形式：例圖象編碼模型（2）差分映射編碼例62圖象編碼模型或矩陣A是非奇異的，因而這種映射變換是可逆的。差分編碼是一種最簡單的線性預(yù)測編碼。圖象編碼模型或矩陣A是非奇異的，因而這種映射63圖象編碼模型（3）正交變換編碼各種正交變換都是可逆的線性變換。應(yīng)用正交變換的圖象編碼常稱為變換編碼。正交變換有傅立葉變換(FFT)、余弦變換(DCT)、沃爾什-哈達瑪變換(WHT)、小波變換(DWT)等。例圖象編碼模型（3）正交變換編碼例64Chap10圖象壓縮與編碼要點：信息量，熵，聯(lián)合熵，率失真函數(shù)編碼效率，冗余度，壓縮比無失真編碼，有失真編碼霍夫曼編碼行程編碼預(yù)測編碼DCT編碼混合編碼Chap10圖象壓縮與編碼要點：信息量，熵，聯(lián)合熵，率65圖象壓縮與編碼數(shù)字圖象通常要求很大的比特數(shù)，這給圖象的傳輸和存儲帶來相當(dāng)大的困難。要占用很多的資源，花很高的費用。如一幅512x512的黑白圖象的比特數(shù)為512x512x8=2,097,152bit=256k。再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8bit，總比特數(shù)為圖象壓縮與編碼數(shù)字圖象通常要求很大的比特數(shù)，這給圖象66圖象壓縮與編碼90x60x24x3x512x512x8bit=97,200M。如一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影光圖象（還有聲音）就需要160張CD光盤用來存儲。

對圖象數(shù)據(jù)進行壓縮顯得非常必要。本章討論的問題：在滿足一定條件下，能否減小圖象bit數(shù)，以及用什么樣的編碼方法使之減少。圖象壓縮與編碼90x60x24x3x512x67英文字母出現(xiàn)相對頻率字母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)相對頻率字母百分比字母百分比68英文字母出現(xiàn)相對頻率英文字母出現(xiàn)相對頻率69圖象編碼—密碼點擊圖片播放視頻某個圖形或物品也可以作為密碼。圖象編碼—密碼點擊圖片某個圖形或物品也可以作為密碼。70圖象編碼—密碼虹膜與指紋。圖象編碼—密碼虹膜與指紋。71圖象壓縮與編碼1．圖象數(shù)據(jù)壓縮是可能的：一般原始圖象中存在很大的冗余度。用戶通常允許圖象失真。當(dāng)信道的分辨率不及原始圖象的分辨率時，降低輸入的原始圖象的分辨率對輸出圖象分辨率影響不大。用戶對原始圖象的信號不全都感興趣，可用特征提取和圖象識別的方法，丟掉大量無用的信息。提取有用的信息，使必須傳輸和存儲的圖象數(shù)據(jù)大大減少。圖象壓縮與編碼1．圖象數(shù)據(jù)壓縮是可能的：72圖象壓縮與編碼2．原始圖象越有規(guī)則，各象素之間的相關(guān)性越強，它可能壓縮的數(shù)據(jù)就越多。值得指出的是：當(dāng)前采用的編碼方法得到的結(jié)果，離可能壓縮的極限還相差很遠，這說明圖象數(shù)據(jù)壓縮的潛力是很大的，直到目前為止，它還是個正在繼續(xù)研究的領(lǐng)域。圖象壓縮與編碼2．原始圖象越有規(guī)則，各象素之間的相關(guān)性越強，73圖象壓縮與編碼3．圖象結(jié)構(gòu)的性質(zhì)，大體上可分為兩大類，一類是具有一定圖形特征的結(jié)構(gòu)，另一類是具有一定概率統(tǒng)計特性的結(jié)構(gòu)?；诓煌膱D象結(jié)構(gòu)特性，應(yīng)采用不同的壓縮編碼方法。圖象壓縮與編碼3．圖象結(jié)構(gòu)的性質(zhì)，大體上可分為兩大類，一類是74圖象壓縮與編碼4．全面評價一種編碼方法的優(yōu)劣，除了看它的編碼效率、實時性和失真度以外，還要看它的設(shè)備復(fù)雜程度，是否經(jīng)濟與實用。常采用混合編碼的方案，以求在性能和經(jīng)濟上取得折衷。

隨著計算方法及VLSI的發(fā)展，使許多高效而又比較復(fù)雜的編碼方法在工程上有實現(xiàn)的可能。圖象壓縮與編碼4．全面評價一種編碼方法的優(yōu)劣，除了看它的編碼75信源編碼的基本概念圖象數(shù)據(jù)壓縮的目的是在滿足一定圖象質(zhì)量條件下，用盡可能少的比特數(shù)來表示原始圖象，以提高圖象傳輸?shù)男屎蜏p少圖象存儲的容量，在信息論中稱為信源編碼。信源編碼可分為兩大類，一類是無失真編碼，另一類是有失真編碼或稱限失真編碼。信源編碼的基本概念圖象數(shù)據(jù)壓縮的目的是在滿足一定圖象76無失真編碼

無失真編碼又稱信息保持編碼或可逆的無誤差編碼。

信息量：從N個相等可能發(fā)生的事件中，選出其中一個事件所需的信息度量，稱為信息量。無失真編碼無失真編碼又稱信息保持編碼或可逆的無誤差編77無失真編碼

要辨識1到32中選定的某一個數(shù)，可先提問：“是否大于16？”，得到回答就消去半數(shù)可能事件。每提問一次得到回答，可以得到1bit信息量（二進制位）。這里共需5次，因此所需的信息量為。例無失真編碼要辨識1到32中選定的某一個數(shù)，可先提問78無失真編碼定義信息量：從N個數(shù)選定一個數(shù)s的概率為p(s)，且等概率，p(s)=1/N。熵：設(shè)信源符號表為s={s1,s2,…,

sq}，其概率分布為P(s)={p(s1),p(s2),…,p(sq)}，則信源的熵為無失真編碼定義信息量：從N個數(shù)選定一個數(shù)s的概率為p79無失真編碼s作為灰度，共q級，出現(xiàn)概率均等時，p(si)=1/q，當(dāng)灰度只有兩級時，即si=0,1，且0出現(xiàn)概率為p1，1出現(xiàn)概率為p2=1-p1

，其熵?zé)o失真編碼s作為灰度，共q級，出現(xiàn)概率均等時，p(s80無失真編碼當(dāng)p1=1/2，p2=1-p1=1/2時，H(s)=1為最大值。如圖所示。無失真編碼當(dāng)p1=1/2，p2=1-p1=1/81無失真編碼熵的性質(zhì)：（1）熵是一個非負數(shù)，即總有H(s)≥0。（2）當(dāng)其中一個符號sj的出現(xiàn)概率p(sj)=1時，其余符號si(i≠j)的出現(xiàn)概率p(si)

=0，H(s)=0。（3）當(dāng)各個si出現(xiàn)的概率相同時，則最大平均信息量為log2

q。（4）熵值總有H(s)≤log2

q。無失真編碼熵的性質(zhì)：82無失真編碼(一)無失真編碼定理

可以證明，在無干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度

L與信源的熵H(s)任意地接近，即L=H(s)+ε，其中ε為任意小的正數(shù)，但以H(s)為其下限，即L≥H(s)，這就是香農(nóng)(Shannon)無干擾編碼定理。

無失真編碼(一)無失真編碼定理83無失真編碼(二)熵與相關(guān)性、冗余度的關(guān)系對于無失真圖象的編碼，原始圖象數(shù)據(jù)的壓縮存在一個下限，即平均碼組長度不能小于原始圖象的熵，而理論上的最佳編碼的平均碼長無限接近原始圖象的熵。

原始圖象冗余度定義為：無失真編碼(二)熵與相關(guān)性、冗余度的關(guān)系84無失真編碼

將編碼效率定義為：

冗余度接近于0，或編碼效率接近于1的編碼稱為高效碼。無失真編碼將編碼效率定義為：冗余度接近于0，85無失真編碼若原始圖象的平均比特率為n，編碼后的平均比特率為nd，則壓縮比C定義為：由Shannon定理，無失真編碼最大可能的數(shù)據(jù)壓縮比為：無失真編碼若原始圖象的平均比特率為n，編碼后的平均比86無失真編碼

獨立信源的熵與馬爾可夫信源的熵令q=2L，其中L等于自然二進制碼的長度?？梢宰C明，對于獨立信源，等概率分布時，具有最大熵HM(s)=L比特，因而冗余度r=L/HM(s)-1=0，不可能壓縮。討論（1）獨立信源，又稱無記憶信源，符號si的出現(xiàn)，與其他的符號無關(guān)。無失真編碼獨立信源的熵與馬爾可夫信源的87無失真編碼非等概率分布時的熵，一般有H1(s)<HM(s)=L，因而冗余度r=L/H1(s)-1>0，還有可能壓縮。（2）有限馬爾可夫(Markov)信源的熵又稱有限記憶信源，它的統(tǒng)計特性要用轉(zhuǎn)移概率或條件概率來描述。

m階Markov信源，是指某個符號si出現(xiàn)的概率只與前面m個符號有關(guān)。無失真編碼非等概率分布時的熵，一般有H1(s)<H88無失真編碼

設(shè)s={s1,s2,…,sq}，則轉(zhuǎn)移概率

p(si/si1,si2,…,sim)乃是前m個符號為si1,si2,…,sim時，第m+1個符號為si的概率。

信息量

I(si/si1,si2,…,sim)=-log2p(si/si1,si2,…,sim)無失真編碼設(shè)s={s1,s2,…,sq}，則轉(zhuǎn)移89無失真編碼對符號表取平均的信息量

這是在給定序列si1,si2,…,sim的條件下，信源的條件熵。

無失真編碼對符號表取平均的信息量這是在給定序90無失真編碼

再考慮序列si1,si2,…,sim發(fā)生的概率，可將m階Markov信源的熵定義為：無失真編碼再考慮序列si1,si2,…,sim發(fā)91無失真編碼

（四）高效的編碼方法無干擾編碼定理只指出存在一種無失真的編碼，可使。它并沒有指出具體的編碼方法。下面介紹幾種具體的編碼方法。（1）Huffman碼它是長度不均勻的，其平均長度最短的即時可譯碼。其要點是對經(jīng)常出現(xiàn)的符無失真編碼（四）高效的編碼方法92英文字母出現(xiàn)相對頻率字母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)相對頻率字母百分比字母百分比93英文字母出現(xiàn)相對頻率英文字母出現(xiàn)相對頻率94國際莫爾斯電碼符號SymbolABCDEFGHIJKLMCode.--…-.-.-.....-.--.…....----.-.-..--SymbolNOPQRSTUVWXYZCode-.---.--.--.-.-.…-..-…-.---..--.----..Symbol0123456789Code-----.----..---…--….-…..-….--...---..----.Symbol.,?:;-/“Code.-.-.---..--..--..---…-.-.-.-…--..-..-..-.國際莫爾斯電碼符號SymbolCodeSymbolCodeS95無失真編碼號賦予最短的碼字，然后按出現(xiàn)概率減少的次序，逐個賦予較長的碼字，這樣可使碼的平均長度具有最小值，pi--si出現(xiàn)概率，li--對si編碼的長度。無失真編碼號賦予最短的碼字，然后按出現(xiàn)概率減少的次序，逐個賦96無失真編碼

信號源s={s1,s2,s3,s4,s5,s6}，其概率分布為p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman碼。例方法：將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。無失真編碼信號源s={s1,s2,s3,s497無失真編碼方法：把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。重復(fù)上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。無失真編碼方法：98Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Huffman編碼例輸入輸入概率99Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman編碼例輸入輸入概率第一步100Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼例輸入輸入概率第一步第二步101Huffman編碼例輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼例輸入輸入概率第一步第二步第三步102Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步103Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步00104Huffman編碼例輸入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.40101010101S1=1Huffman編碼例輸入輸入概率第一步第二步第三步第四步00105Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步00106Huffman編碼例輸入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.40101010101S3=011Huffman編碼例輸入輸入概率第一步第二步第三步第四步00107Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步00108Huffman編碼例輸入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編碼例輸入輸入概率第一步第二步第三步第四步00109Huffman編碼例輸入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.40101010101S6=01011Huffman編碼例輸入輸入概率第一步第二步第三步第四步00110無失真編碼（2）B碼

在某些應(yīng)用中，編碼器輸入符號集合的概率分布服從乘冪律：pk=k-r,k=1,2,…,q。r為正常數(shù)，則用B碼，它接近于最佳編碼。B碼是一種非等長碼，由兩部分組成，一部分叫“延續(xù)比特”，一部分叫“信息比特”。延續(xù)比特的作用是標(biāo)注一個碼字究竟延續(xù)多長，信息比特的作用是表示不同的信息符號。無失真編碼（2）B碼111無失真編碼方法：將信源符號按出現(xiàn)概率從大到小排序，然后按B1碼的前后順序分別賦予相應(yīng)符號，便得到各符號的B1碼。其中信息碼是按二進制的長度及數(shù)的順序排列的，即0，1，00，01，10，11，000，001，…。延續(xù)碼C是在編碼過程中確定的，可將C=0賦予前一個碼字，將C=1賦予后一個碼字，再將C=0賦予下一個碼字。無失真編碼方法：112無失真編碼方法：例如，編碼器輸入符號序列為s4s1s5s2…,則B1碼為：

0001，10，0100，11，…或者1011，00，1110，01，…延續(xù)碼改變，表示前一個碼字結(jié)束，后一個碼字開始。

B1碼優(yōu)點：編碼方法簡單，容易實現(xiàn)。無失真編碼方法：113無失真編碼（3）移位碼S2對具有單調(diào)減小概率的輸入信號相當(dāng)有效的非等長碼。

S2碼由2bit長的碼字組成，總共包含四個不同的碼字：C1=00，C2=01，C3=10，C4=11，C4的個數(shù)用來表示該符號的序數(shù)超過3的次數(shù)。符號編碼：C1，C2，C3，C4C1，C4C2，C4C3，C4C4C1，C4C4C2，C4C4C3，…這種編碼方法更簡單。無失真編碼（3）移位碼S2114幾種編碼比較輸入S1S2S3S4S5S6

rCH(s)概率0.40.30.10.10.06