1、3.1 圖像壓縮編碼的分類圖像壓縮編碼的分類3.2 數據壓縮與信息論基礎數據壓縮與信息論基礎3.3 霍夫曼編碼霍夫曼編碼3.4 游程長度編碼游程長度編碼3.5 算術編碼算術編碼數字圖象通常要求很大的比特數，這給圖象的數字圖象通常要求很大的比特數，這給圖象的傳輸和存儲帶來相當大的困難。要占用很多的傳輸和存儲帶來相當大的困難。要占用很多的資源，花很高的費用。資源，花很高的費用。 如一幅如一幅512x512的黑白圖象的比特數為的黑白圖象的比特數為 512x512x8=。 再如一部再如一部90分鐘的彩色電影，每秒放映分鐘的彩色電影，每秒放映24幀。把它數字化，每幀幀。把它數字化，每幀512x512象素

2、，象素，每象素的每象素的 、 三分量分別占三分量分別占8 bit，總比，總比特數為特數為 90 x60 x24x3x512x512x8bit=。 如一張如一張CD光盤可存光盤可存600兆字節數據，這部兆字節數據，這部電影光圖象（還有聲音）就需要電影光圖象（還有聲音）就需要張張CD光光盤用來存儲。盤用來存儲。 對圖象數據進行對圖象數據進行壓縮顯得非常必要壓縮顯得非常必要。 本章討論的問題：在滿足一定條件下，能否本章討論的問題：在滿足一定條件下，能否減小圖象減小圖象bitbit數，以及用什么樣的編碼方法使之數，以及用什么樣的編碼方法使之減少。減少。圖像壓縮編碼限失真編碼無失真編碼行程編碼LZW編碼

3、哈夫曼編碼算術編碼無損預測編碼位平面編碼有損預測編碼分形編碼模型編碼子帶編碼神經網絡編碼變換編碼K.L變換Haar變換Walsh.Hadamard變換離散余弦變換離散傅立葉變換斜變換小波變換1. 1.圖象壓縮是可能的圖象壓縮是可能的：n一般原始圖象中存在很大的冗余度。一般原始圖象中存在很大的冗余度。n用戶通常允許圖象失真。用戶通常允許圖象失真。n當信道的分辨率不及原始圖象的分辨率當信道的分辨率不及原始圖象的分辨率時，降低輸入的原始圖象的分辨率對輸出時，降低輸入的原始圖象的分辨率對輸出圖象分辨率影響不大。圖象分辨率影響不大。n用戶對原始圖象的信號不全都感興趣，用戶對原始圖象的信號不全都感興趣，可

4、用特征提取和圖象識別的方法，丟掉大可用特征提取和圖象識別的方法，丟掉大量無用的信息。提取有用的信息，使必須量無用的信息。提取有用的信息，使必須傳輸和存儲的圖象數據大大減少。傳輸和存儲的圖象數據大大減少。 n原始圖象越有規則，各象素之間的相關性越原始圖象越有規則，各象素之間的相關性越強，它可能壓縮的數據就越多。強，它可能壓縮的數據就越多。 值得指出的是：當前采用的編碼方法得到值得指出的是：當前采用的編碼方法得到的結果，離可能壓縮的極限還相差很遠，這的結果，離可能壓縮的極限還相差很遠，這說明圖象數據壓縮的潛力是很大的，直到目說明圖象數據壓縮的潛力是很大的，直到目前為止，它還是個正在繼續研究的領域。

5、前為止，它還是個正在繼續研究的領域。33K15K 圖象數據壓縮的圖象數據壓縮的目的目的是在滿足一定圖象質量是在滿足一定圖象質量條件下，用盡可能少的比特數來表示原始圖條件下，用盡可能少的比特數來表示原始圖象，以提高圖象傳輸的效率和減少圖象存儲象，以提高圖象傳輸的效率和減少圖象存儲的容量，在信息論中稱為的容量，在信息論中稱為信源編碼信源編碼。 信源編碼可分為兩大類，一類是信源編碼可分為兩大類，一類是無失真編無失真編碼碼，另一類是，另一類是有失真編碼有失真編碼或稱或稱限失真編碼限失真編碼。從從N個數選定一個數個數選定一個數s的概率為的概率為p(s)，且等概率，且等概率，p(s)=1/N。設信源符號表

6、為設信源符號表為 s=s1, s2, , sq ，其概率分布為其概率分布為P(s)=p(s1), p(s2), , p(sq) ，則信源的，則信源的為為)()(log1loglog)(222spIspNNsIqiiiqiiispIspspspH112)()()(log)()(ss作為灰度，共作為灰度，共q級級，出現概率均等時，出現概率均等時，p(si)=1/q， 當灰度只有兩級時，即當灰度只有兩級時，即si = = 0, 1，且，且0出現出現概率為概率為p1，1出現概率為出現概率為p2=1- p1 ，其熵，其熵qqqHqi212log1log1)(s12112111log)1 (1log)(p

7、pppHs當當p1=1/2， p2=1- p1 =1/2時，時， H(s)=1為最大值。如圖所示。為最大值。如圖所示。（1 1）熵是一個非負數，即總有）熵是一個非負數，即總有H(s)0。（2 2）當其中一個符號）當其中一個符號sj的出現概率的出現概率p(sj)=1時，時，其余符號其余符號si(ij)的出現概率的出現概率p(si) =0，H(s)=0。（3 3）當各個）當各個si出現的概率相同出現的概率相同時時，則最大平，則最大平均信息量為均信息量為log2 q。（4 4）熵值總有）熵值總有H(s) log2 q。無失真編碼定理無失真編碼定理 可以證明，在無干擾的條件下，存在一種無可以證明，在無

8、干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度失真的編碼方法，使編碼的平均長度 與與信源信源的熵的熵H(s)任意地接近，即任意地接近，即L=H(s)+，其中，其中為任意小的正數，但以為任意小的正數，但以H(s)為其下限，即為其下限，即LH(s)，這就是，這就是香農香農(Shannon)無干擾編無干擾編碼定理碼定理。L)(sHL)(sHL 熵與相關性、冗余度的關系熵與相關性、冗余度的關系 對于無失真圖象的編碼，原始圖象數據的壓對于無失真圖象的編碼，原始圖象數據的壓縮存在一個下限，即平均碼組長度不能小于原縮存在一個下限，即平均碼組長度不能小于原始圖象的熵，而理論上的最佳編碼的平均碼長始圖

9、象的熵，而理論上的最佳編碼的平均碼長無限接近原始圖象的熵。無限接近原始圖象的熵。 原始圖象原始圖象定義為：定義為：1)(1sHLr原始圖象的熵原始圖象平均碼長將將定義為：定義為：rLsH11)( 冗余度接近于冗余度接近于0，或編碼效率接近于，或編碼效率接近于1的編的編碼稱為碼稱為。 數字圖像通信系統的組成數字圖像通信系統的組成：其中，其中，信源編碼器：完成原數據的壓縮。信源編碼器：完成原數據的壓縮。信道信道 編編 碼：為了抗干擾，增加一些容錯、校驗碼：為了抗干擾，增加一些容錯、校驗位、版權保護，實際上是增加冗余。位、版權保護，實際上是增加冗余。信信 道：如道：如Internet、廣播、通訊、可

10、移動介質、廣播、通訊、可移動介質符號符號解碼器解碼器反向反向映射器映射器映射器映射器量化器量化器符號符號編碼器編碼器等字長編碼等字長編碼 每個抽樣值都以相同長度的二進制碼表示。每個抽樣值都以相同長度的二進制碼表示。 編碼簡單，但編碼效率低編碼簡單，但編碼效率低 PCM變字長編碼變字長編碼n每個抽樣值用不同長度的二進制碼表示。每個抽樣值用不同長度的二進制碼表示。n每個符號的平均碼長：每個符號的平均碼長：設圖像信源有設圖像信源有K種符號（例如種符號（例如K種灰度等種灰度等級），級）， ,且它們出現的概率為且它們出現的概率為 ,那么，不考那么，不考慮信源符號的相關性，對每個符號編碼時，慮信源符號的相

11、關性，對每個符號編碼時，其平均碼長為：其平均碼長為：其中其中li為為ai的碼字長度，的碼字長度，L為平均碼長為平均碼長若編碼時，對概率大的符號用短碼，概率小若編碼時，對概率大的符號用短碼，概率小的符號用長碼，則的符號用長碼，則L L會比等長編碼所需的碼會比等長編碼所需的碼字短。字短。 較等長編碼效率高。較等長編碼效率高。i1(a )kiiLpl構成不等長編碼的方法有許多，構成不等長編碼的方法有許多，Huffman于于1952年提出一種最佳不等長編碼，是圖像編年提出一種最佳不等長編碼，是圖像編碼中常用的無損壓縮編碼。碼中常用的無損壓縮編碼。 1、定理、定理 如果碼字長度嚴格按照符號出現概率大小如

12、果碼字長度嚴格按照符號出現概率大小逆序排列，則平均碼字長度最小。逆序排列，則平均碼字長度最小。概率大概率大的用短碼，概率小的用長碼。的用短碼，概率小的用長碼。2、編碼方法、編碼方法 （1）對信源符號按其出現的概率進行遞減排）對信源符號按其出現的概率進行遞減排序。序。 （2）將兩個最小的概率相加，其和作為新符）將兩個最小的概率相加，其和作為新符號的概率，并按（號的概率，并按（1）重新排序。）重新排序。 （3）重復（）重復（1）（）（2），直到概率之和達到），直到概率之和達到1為止。為止。 （4）每次合并符號時，將被合并的符號賦予）每次合并符號時，將被合并的符號賦予1和和0或或0和和1。 （5）尋

13、找從概率）尋找從概率1處到每個信源符號的路徑，處到每個信源符號的路徑，記錄下路徑上的記錄下路徑上的0，1序列，該序列即為信源符序列，該序列即為信源符號的碼字（編碼）。號的碼字（編碼）。 舉例：舉例：信號源信號源 s=ss=s1 1, s, s2 2, s, s3 3, s, s4 4, s, s5 5, s, s6 6 ，其概率，其概率分布為分布為p p1 1=0.4 p=0.4 p2 2=0.3 p=0.3 p3 3=0.1 p=0.1 p4 4=0.1 =0.1 p p5 5=0.06 p=0.06 p6 6=0.04=0.04，求最佳，求最佳HuffmanHuffman碼。碼。i. i.

14、 將信源符號按出現概率從大到小排成一列將信源符號按出現概率從大到小排成一列，然后把最末兩個符號的概率相加，合成，然后把最末兩個符號的概率相加，合成一個概率。一個概率。ii. ii. 把這個符號的概率與其余符號的概率按從把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。率加起來，合成一個概率。 ii. ii. 重復上述做法，直到最后剩下兩個概率為重復上述做法，直到最后剩下兩個概率為止。止。iii.iii.從最后一步剩下的兩個概率開始逐步向前從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一進行

15、編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元對概率小的賦予碼元1。輸入輸入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=1S2=00S3=011S4=0100S5=01010S6=01011壓縮前，等長編碼：每個符號壓縮前，等長編碼：每個符號3bit壓縮后，壓縮后， =1*0.4+2*0.3+3*0.1+4*0.1+5*0.06+5

16、*0.04=2.2bit壓縮比：壓縮比：3/2.21.36靜態編碼靜態編碼：在壓縮之前就建立好一個概率統計：在壓縮之前就建立好一個概率統計表和編碼樹。算法速度快，但壓縮效果不是最表和編碼樹。算法速度快，但壓縮效果不是最好；好；動態編碼動態編碼：對每一個圖像，臨時建立概率統計：對每一個圖像，臨時建立概率統計表和編碼樹。算法速度慢，但壓縮效果最好。表和編碼樹。算法速度慢，但壓縮效果最好?；舴蚵獯a霍夫曼解碼設接收端收到的碼流是設接收端收到的碼流是101001000，如何，如何判斷應判斷應“斷斷”在何處，即哪幾個比特應對應在何處，即哪幾個比特應對應一個碼字？也就是說如何解碼？下面介紹兩一個碼字？也就

17、是說如何解碼？下面介紹兩種方法。種方法。1）樹形解碼。樹形解碼。解碼器先進高位，并根據該位是解碼器先進高位，并根據該位是1還是還是0判斷判斷由根向下走向，若走到樹葉，說明至此為止由根向下走向，若走到樹葉，說明至此為止的碼串部分對應一個碼字，從而解出對應的的碼串部分對應一個碼字，從而解出對應的符號；符號；重新從樹根開始解碼，若未走到樹葉，則繼重新從樹根開始解碼，若未走到樹葉，則繼續進一位，至到走到樹葉。續進一位，至到走到樹葉。 2）并行解碼。）并行解碼。 用樹形解碼時需一位一位讀入和判斷，當碼用樹形解碼時需一位一位讀入和判斷，當碼表較長時，速度太慢。特別是對活動圖像解表較長時，速度太慢。特別是對

18、活動圖像解碼時，難以用硬件實現。而并行解碼，可一碼時，難以用硬件實現。而并行解碼，可一次解出一個碼字，易于硬件實現，解碼速度次解出一個碼字，易于硬件實現，解碼速度快?？?。游程編碼游程編碼是一種簡單的無損壓縮的方法。是一種簡單的無損壓縮的方法。概念：概念：行程行程：具有相同灰度值的像素序列。：具有相同灰度值的像素序列。編碼思想：編碼思想：去除像素冗余。去除像素冗余。用行程的灰度和行程的長度代替行程本身。用行程的灰度和行程的長度代替行程本身。例：設重復次數為例：設重復次數為 iC, 重復像素值為重復像素值為 iP編碼為：編碼為：iCiP iCiP iCiP 編碼前：編碼前：aaaaaaabbbbb

19、bcccccccc 編碼后：編碼后：7a6b8c基本方法：基本方法： 使用一新字符序列代取原始數據中相同的字使用一新字符序列代取原始數據中相同的字 符序列，來實現數據壓縮。（壓縮原始符序列，來實現數據壓縮。（壓縮原始數據數據中相同的字符序列）中相同的字符序列）把沿著掃描行的象素序列把沿著掃描行的象素序列x1, x2, xN映射映射為行程序列為行程序列(g1, l1), (g2, l2), (gk, lk) gi灰度級灰度級 ligi的行程長度的行程長度因為象素序列可以根據行程序列來重建，故行因為象素序列可以根據行程序列來重建，故行程映射變換是可逆的。因它包含灰度鑒別和行程映射變換是可逆的。因它

20、包含灰度鑒別和行程計數，故它是非線性的。程計數，故它是非線性的。分析：分析：對于有大面積色塊的圖像，壓縮效果很對于有大面積色塊的圖像，壓縮效果很好好對于紛雜的圖像，壓縮效果不好，最壞對于紛雜的圖像，壓縮效果不好，最壞情況下，會加倍圖像情況下，會加倍圖像例如一個數據字符串為例如一個數據字符串為RTTTTTTTTABBC KGHJK用一新的字符串：用一新的字符串：#8T，代替，代替8個個T。#為特殊標識符，表示行程編碼。為特殊標識符，表示行程編碼。8代表其后字符重復的次數代表其后字符重復的次數；T為重復的字符。為重復的字符。則行程編碼后的字符串為：則行程編碼后的字符串為：R8TABBC K GHJ

21、K壓縮前總字符數壓縮前總字符數 18壓縮后總字符數壓縮后總字符數 13其壓縮比：其壓縮比：= 18/13 = 1.38幾點說明幾點說明： 1、如果原始數據字符串包含了、如果原始數據字符串包含了“#”符符號，則用兩個號，則用兩個“#”符號替換原始數據字符串符號替換原始數據字符串中的中的“#”符號。符號。2、原始數據字符串中重復字符數少于、原始數據字符串中重復字符數少于4個，個，則行程編碼無效。則行程編碼無效。3、壓縮對象可以是重復的單個字符序列，也、壓縮對象可以是重復的單個字符序列，也可以是重復的多個字符序列。對于后者，必可以是重復的多個字符序列。對于后者，必須標識一個字符序列的長度或者結束標志

22、。須標識一個字符序列的長度或者結束標志。算術編碼：越來越流行（在很多標準中被算術編碼：越來越流行（在很多標準中被采用）采用）適合的場合：適合的場合：小字母表：如二進制信源小字母表：如二進制信源概率分布不均衡概率分布不均衡建模與編碼分開建模與編碼分開算術編碼算術編碼：對整個序列信源符號串產生一個唯一的對整個序列信源符號串產生一個唯一的標識（標識（ tag ）直接對序列進行編碼（不是碼字的串直接對序列進行編碼（不是碼字的串聯）：非分組碼聯）：非分組碼不用對該長度所有可能的序列編碼不用對該長度所有可能的序列編碼標識是標識是0,1)之間的一個數（二進制小之間的一個數（二進制小數，可作為序列的二進制編碼

23、）數，可作為序列的二進制編碼） 算術編碼中，信源符號與碼字之間不存在一一算術編碼中，信源符號與碼字之間不存在一一對應的關系。一個碼字不是賦給某個信源符對應的關系。一個碼字不是賦給某個信源符號，而是賦給整個消息序列。這個碼字本身號，而是賦給整個消息序列。這個碼字本身定義一個介于定義一個介于0和和1之間的實數區間，該區間之間的實數區間，該區間中的任何一個實數就代表要編碼的消息序列中的任何一個實數就代表要編碼的消息序列。當消息中的符號數目增加時，用于描述消。當消息中的符號數目增加時，用于描述消息的間隔變得更小，而表示間隔所需要的信息的間隔變得更小，而表示間隔所需要的信息單元（如編碼位數）變得更多了。

24、息單元（如編碼位數）變得更多了。定義一一映射：定義一一映射：ak FX(k-1), FX(k), k = 1.m, FX(0) = 0FX(k-1), FX(k)區間內的任何數字表示區間內的任何數字表示 ak對對2字母序列字母序列ak aj編碼編碼對對ak ，選擇，選擇FX(k-1), FX(k)然后將該區間按比例分割并選取第然后將該區間按比例分割并選取第j個區間：個區間： 11,111XXXXXXXXFjFjFkFkFkFkFkFk算術編碼方法：算術編碼方法：1.產生標識將0, 1)分為m個區間： 00,.1,1XXXFmiiFiF考慮對考慮對a1a2a3編碼編碼：A = a1, a2, a

25、3, P = 0.7, 0.1, 0.2)映射：映射：a1 1, a2 2, a3 3cdf: FX(1) = 0.7, FX(2) = 0.8, FX(3) = 1.0A = a1, a2, , am對公平擲骰子的例子：1, 2, 3, 4, 5, 66.161kforkXP iXPiFiXPkXPaTXikiX2112111 25. 022112XPXPTX 75. 0521541XPkXPTkX映射成數字映射成數字字符串的詞典順序：字符串的詞典順序：其中其中 表示表示“在字母順序中，在字母順序中，y在在x的前面的前面”n 為序列的長度為序列的長度 ( ):12inXiiTPPy y xx

26、yxxy 考慮兩輪連續的骰子：考慮兩輪連續的骰子：輸出輸出 = 11, 12, , 16, 21, 22, , 26, , 61, 62, , 66 469. 07251321121113xPxPxPTXv注意：注意：為了產生為了產生13的標識，我們不必對產生其他標識的標識，我們不必對產生其他標識=但是，為了產生長度為但是，為了產生長度為n的字符串的標識，我的字符串的標識，我們必須知道比其短的字符串的概率們必須知道比其短的字符串的概率這與產生所有的碼字一樣繁重！這與產生所有的碼字一樣繁重！應該想辦法來避免此事應該想辦法來避免此事區間構造區間構造包含某個標識的區間與所有其他標識的區間不相交包含某

27、個標識的區間與所有其他標識的區間不相交基本思想基本思想遞歸：將序列的下遞歸：將序列的下/上界視為更短序列的界的上界視為更短序列的界的函數函數上述骰子的例子：上述骰子的例子：考慮序列：考慮序列：3 2 2 令令u(n), l(n) 為長度為為長度為n序列的上界和下界，則序列的上界和下界，則 u(1) = FX(3), l(1) = FX(2)u(2) = FX(2)(32), l(2) = FX(2)(31) (2)32(11).(16)(21).(26)(31)(32)XFPPPPPPxxxxxx6661212112111,iiiPkiP xk xiP xkP xiP xkwherex xxx

28、(2)1132(1)(2)(31)(32)(2)(31)(32)XXFP xP xPPFPPxxxx1221(31)(32)(3)(1)(2)(3)(2)XPPP xP xP xP xFxx)2()3()3(1XXFFxP)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu ) 1 ()2()3()2(31)2(XXXXXFFFFF) 1 ()1()1()1()2(XFlull()()(3)( )(3)( )322 ,32133XXuFlF=()()(3)(2)(2)(2)322(31)(32)(31)(2)XXXXXFFFFF=+-()()(3)(

29、2)(2)(2)321(31)(32)(31)(1)XXXXXFFFFF=+-)2()2()2()2()3(XFlulu) 1 ()2()2()2()3(XFlull)2()2()3()2(32)2(XXXXXFFFFF)2()1()1()1()2(XFlulu產生標識：產生標識：通常，對任意序列通常，對任意序列x = x1x2xn ( )( )2nnXulTx( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl只需知道信源的只需知道信源的cdfcdf，即信源的概率模型，即信源的概率模型算術編碼：編碼和解碼過程都只涉及算術運算（加、算術編碼

30、：編碼和解碼過程都只涉及算術運算（加、減、乘、除）減、乘、除）考慮隨機變量考慮隨機變量X(ai) = i 對序列對序列1 3 2 1編碼：編碼：3, 1)(, 1)3(,82. 0)2(, 8 . 0) 1 (, 0, 0)(kkFFFFkkFXXXXX1, 0)0()0(ul8 . 0) 1 (0)0()0()0()0()1()0()0()0()1(XXFluluFlull18 . 0)3(656. 0)2()1()1()1()2()1()1()1()2(XXFluluFlull1377408. 0)2(7712. 0) 1 ()2()2()2()3()2()2()2()3(XXFluluFlull132()()(4)(1)(3)(3)(4)(3)(3)(3)( )0.7712(1)0.7735040XXllulFululF=+-=+-=1321(4)(4)13210.7723522XulT( )(1)(1)(1)( )(1)(1)(1)()(1)kkkkkkXkXkkkulullluFxFxl算術編碼的唯一性和有效性算術編碼的唯一性和有效性上述產生的標識可以唯一表示一個序列，上述產生的標識可以唯一表示一個序列，這意味著該標識的二進制表示為序列的唯這意味著該標識的二進制