1、河北大學(xué)數(shù)學(xué)與計算機學(xué)院河北大學(xué)數(shù)學(xué)與計算機學(xué)院馬潁麗馬潁麗Ma Yingli CMC HBU第五章第五章 圖像編碼與壓縮圖像編碼與壓縮n5.1 概述概述n5.2 統(tǒng)計編碼統(tǒng)計編碼n5.3 預(yù)測編碼預(yù)測編碼n5.4 變換編碼變換編碼n5.5 二值圖像編碼二值圖像編碼n5.6 新型的圖像壓縮編碼方法新型的圖像壓縮編碼方法n5.7 圖像壓縮編碼標(biāo)準(zhǔn)圖像壓縮編碼標(biāo)準(zhǔn)Ma Yingli CMC HBU知識要點n信息論中的有關(guān)概念信息論中的有關(guān)概念n信息，信息量，信息熵，冗余度信息，信息量，信息熵，冗余度n編碼方法編碼方法n統(tǒng)計編碼統(tǒng)計編碼n預(yù)測編碼預(yù)測編碼n變換編碼變換編碼n混合編碼混合編碼n靜態(tài)圖像

2、壓縮標(biāo)準(zhǔn)靜態(tài)圖像壓縮標(biāo)準(zhǔn)nJPEG、JBIG、JPEG2000等等Ma Yingli CMC HBU5.1 概述概述n數(shù)據(jù)編碼的目的各異數(shù)據(jù)編碼的目的各異n信息保密信息保密n信息的壓縮存儲與傳輸?shù)刃畔⒌膲嚎s存儲與傳輸?shù)萵數(shù)碼相機數(shù)碼相機圖像編碼與壓縮技術(shù)成功的范例。圖像編碼與壓縮技術(shù)成功的范例。n本章主要介紹靜態(tài)圖像壓縮編碼的原理、應(yīng)本章主要介紹靜態(tài)圖像壓縮編碼的原理、應(yīng)用及有關(guān)的國際標(biāo)準(zhǔn)。用及有關(guān)的國際標(biāo)準(zhǔn)。Ma Yingli CMC HBUMa Yingli CMC HBU5.1.1 數(shù)據(jù)壓縮的基本概念數(shù)據(jù)壓縮的基本概念n數(shù)據(jù)壓縮數(shù)據(jù)壓縮n以較少的數(shù)據(jù)量表示信源以原始形式所代表的信息以較少

3、的數(shù)據(jù)量表示信源以原始形式所代表的信息n目的在于節(jié)省存儲空間、傳輸時間、信號頻帶或發(fā)送目的在于節(jié)省存儲空間、傳輸時間、信號頻帶或發(fā)送能量等。能量等。Ma Yingli CMC HBU信源編碼的基本概念 圖像數(shù)據(jù)壓縮的是在滿足一定圖像質(zhì)量條件下，用盡可能少的比特數(shù)來表示原始圖像，以提高圖像傳輸?shù)男屎蜏p少圖像存儲的容量，在信息論中稱為。 Ma Yingli CMC HBUMa Yingli CMC HBU圖圖5.1 數(shù)據(jù)壓縮系統(tǒng)組成圖數(shù)據(jù)壓縮系統(tǒng)組成圖 Ma Yingli CMC HBU數(shù)字通信系統(tǒng)模型數(shù)字通信系統(tǒng)模型信源信源信源編碼信源編碼信道編碼信道編碼調(diào)制調(diào)制傳輸信道傳輸信道噪聲噪聲解調(diào)解

4、調(diào)信道解碼信道解碼信源解碼信源解碼信宿信宿Ma Yingli CMC HBU壓縮壓縮檢、糾錯檢、糾錯Ma Yingli CMC HBUu熵（熵（Entropy）n代表信源所含的平均信息量。代表信源所含的平均信息量。n若信源編碼的熵大于信源的實際熵，則信源中的若信源編碼的熵大于信源的實際熵，則信源中的數(shù)據(jù)一定存在冗余度。數(shù)據(jù)一定存在冗余度。n冗余數(shù)據(jù)的去除不會減少信息量。冗余數(shù)據(jù)的去除不會減少信息量。n信息量與數(shù)據(jù)量的關(guān)系可由下式表示信息量與數(shù)據(jù)量的關(guān)系可由下式表示 I I D D dudu （5.15.1）Ma Yingli CMC HBU5.1.2 圖像編碼壓縮的必要性圖像編碼壓縮的必要性n

5、圖像信號的數(shù)據(jù)量圖像信號的數(shù)據(jù)量V (volume) （byte，B） :n V w h d/8 （5.2） nw、h、d 分別表示圖像數(shù)據(jù)量分別表示圖像數(shù)據(jù)量（字節(jié)，（字節(jié)，byte，B） 、圖像寬度圖像寬度width（像素數(shù)，（像素數(shù)，pel）、圖像高度、圖像高度height（像素數(shù)，（像素數(shù)，pel） 、圖像深度、圖像深度depth（位，（位，bit）。）。n圖像的尺寸為：圖像的尺寸為：wh。Ma Yingli CMC HBUMa Yingli CMC HBU典型圖像的數(shù)據(jù)量典型圖像的數(shù)據(jù)量 圖像種類圖像種類圖像參數(shù)圖像參數(shù) 數(shù)據(jù)量數(shù)據(jù)量 二值傳真圖像二值傳真圖像 A4（210 297

6、mm）大小、）大小、1728 2376 2色分色分辨率辨率501 KB 灰度圖像灰度圖像 512 512，8 bit灰度等級灰度等級 256 KB VGA圖像圖像 640 480 256色色 300 KB CIF視頻圖像視頻圖像 352 288 256色，亮度取樣率為色，亮度取樣率為3 MHz，亮度，亮度和兩色差按和兩色差按4 1 1取樣，亮色量化位數(shù)共取樣，亮色量化位數(shù)共12 bit，幀頻幀頻29.97，按，按1 s計算計算 4.3 MB HDTV亮度信號亮度信號 1280 720，量化位數(shù)為，量化位數(shù)為8 bit，幀頻，幀頻30 Hz，按，按1 s計算計算 52.7MBMa Yingli

7、CMC HBU5.1.3 圖像編碼壓縮的可能性圖像編碼壓縮的可能性一般圖像中存在著以下數(shù)據(jù)冗余因素一般圖像中存在著以下數(shù)據(jù)冗余因素: : 編碼冗余編碼冗余 像素間的相關(guān)性形成的冗余像素間的相關(guān)性形成的冗余 視覺特性和顯示設(shè)備引起的冗余視覺特性和顯示設(shè)備引起的冗余Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.1.4 圖像編碼壓縮的技術(shù)指標(biāo)圖像編碼壓縮的技術(shù)指標(biāo)常用的圖像壓縮技術(shù)指標(biāo)常用的圖像壓縮技術(shù)指標(biāo): 圖像熵與平均碼長（圖像熵與平均碼長（ Entropy and a

8、verage code lenthgh ） 圖像冗余度與編碼效率（圖像冗余度與編碼效率（Coding efficiency） 壓縮比（壓縮比（Compression ratio） 客觀評價客觀評價 SNR 主觀評價主觀評價Ma Yingli CMC HBU 1、 熵：信源的平均信息量 qiiiqiiispIspspspH112)()()(log)() s ( 設(shè)圖像像素灰度級表為設(shè)圖像像素灰度級表為 s=s1, s2, , sq，其概率，其概率分布為分布為P(s)=p(s1), p(s2), , p(sq)，則信源的，則信源的為為Ma Yingli CMC HBU s作為灰度，共作為灰度，共q

9、級，出現(xiàn)概率均等時，級，出現(xiàn)概率均等時，p(si)=1/q， 當(dāng)灰度只有兩級時，即當(dāng)灰度只有兩級時，即si = 0, 1，且，且0出現(xiàn)概出現(xiàn)概率為率為p1，1出現(xiàn)概率為出現(xiàn)概率為p2=1- p1 ，其熵，其熵qqqHqi212log1log1) s ( 12112111log)1(1log) s (ppppH Ma Yingli CMC HBU 當(dāng)p1=1/2， p2=1- p1 =1/2時， H(s)=1為最大值。如圖所示。Ma Yingli CMC HBU熵的性質(zhì)：熵的性質(zhì)：（1）熵是一個非負(fù)數(shù)，即總有）熵是一個非負(fù)數(shù)，即總有H(s)0。（2）當(dāng)其中一個符號）當(dāng)其中一個符號sj的出現(xiàn)概率的

10、出現(xiàn)概率p(sj)=1時，其時，其余符號余符號si(ij)的出現(xiàn)概率的出現(xiàn)概率p(si) =0，H(s)=0。（3）當(dāng)各個）當(dāng)各個si出現(xiàn)的概率相同時，則有最大平均出現(xiàn)的概率相同時，則有最大平均信息量為信息量為log2 q。（4）熵值總有）熵值總有H(s) log2 q。Ma Yingli CMC HBU 2、 平均碼長：平均碼長：碼字長度的數(shù)學(xué)期望碼字長度的數(shù)學(xué)期望 qiiiLspR1)()s(3、冗余度、冗余度定義為：定義為：)()(11sRsHr 原始圖像的平均碼長原始圖像的平均碼長原始圖像的熵原始圖像的熵Ma Yingli CMC HBU 4、編碼效率、編碼效率定義為：定義為：rsRs

11、H 1)()( 冗余度接近于冗余度接近于0 0，或編碼效率接近于，或編碼效率接近于1 1的編碼的編碼稱為稱為高效碼高效碼。Ma Yingli CMC HBU 5、壓縮比：、壓縮比：若原始圖象的平均比特率為若原始圖象的平均比特率為n，編，編碼后的平均比特率為碼后的平均比特率為nd，則，則壓縮比壓縮比C定義為：定義為：dnnC 壓縮后平均碼長壓縮后平均碼長壓縮前平均碼長壓縮前平均碼長Ma Yingli CMC HBU 6、客觀評價、客觀評價信噪比信噪比SNR定義為：定義為：Ma Yingli CMC HBU表表5.1 圖像質(zhì)量的主觀評價等級圖像質(zhì)量的主觀評價等級Score評價評價Notes5優(yōu)秀優(yōu)

12、秀圖像質(zhì)量非常好圖像質(zhì)量非常好4良好良好圖像質(zhì)量高圖像質(zhì)量高,有很小的干擾但不影響觀看有很小的干擾但不影響觀看3中等中等圖像質(zhì)量可接受圖像質(zhì)量可接受,但有一些干擾但有一些干擾,對觀看稍對觀看稍有妨礙有妨礙2差差圖像質(zhì)量差圖像質(zhì)量差,對觀看有妨礙對觀看有妨礙1很差很差,劣劣 圖像質(zhì)量很差圖像質(zhì)量很差,無法觀看無法觀看7、主觀評價、主觀評價：Ma Yingli CMC HBU圖像編碼主、客觀評價的內(nèi)在關(guān)系圖像編碼主、客觀評價的內(nèi)在關(guān)系圖像類型圖像類型高分辨率廣播電視高分辨率廣播電視普通數(shù)字廣播電視普通數(shù)字廣播電視數(shù)據(jù)庫圖像數(shù)據(jù)庫圖像會議電視會議電視傳輸數(shù)碼率傳輸數(shù)碼率客觀評價客觀評價SNR主觀評價

13、主觀評價74 Mb/s48dB4.5分分34 Mb/s43dB4.0分分識別圖像識別圖像36dB.0分分64kb/s30dB2.5分分壓縮后圖像壓縮后圖像Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa

14、 Yingli CMC HBUMa Yingli CMC HBU5.1.5 數(shù)據(jù)壓縮方法的分類數(shù)據(jù)壓縮方法的分類1 .1 .無損壓縮無損壓縮（Lossless Compression）:nHuffman編碼編碼 nShannon編碼編碼n游程編碼游程編碼n算術(shù)編碼算術(shù)編碼n輪廓編碼輪廓編碼Ma Yingli CMC HBU2、有損壓縮（、有損壓縮（Lossy Compression）n預(yù)測編碼預(yù)測編碼 n變換編碼變換編碼 n混合編碼混合編碼現(xiàn)代壓縮編碼方法：現(xiàn)代壓縮編碼方法：n分形編碼分形編碼n模型基（模型基（Model-based）編碼）編碼Ma Yingli CMC HBU 圖像編碼圖像編

15、碼/ /壓縮主要分無損圖像壓縮和有損圖像壓縮主要分無損圖像壓縮和有損圖像壓縮兩大塊，按其發(fā)展歷程可分為：壓縮兩大塊，按其發(fā)展歷程可分為：l第一代壓縮編碼第一代壓縮編碼 八十年代以前，主要是根據(jù)傳統(tǒng)的信源編碼方法。八十年代以前，主要是根據(jù)傳統(tǒng)的信源編碼方法。l第二代壓縮編碼第二代壓縮編碼 八十年代以后，突破信源編碼理論，結(jié)合分形、模型基、八十年代以后，突破信源編碼理論，結(jié)合分形、模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分利用視覺系統(tǒng)生理心神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分利用視覺系統(tǒng)生理心理特性和圖像信源的各種特性。理特性和圖像信源的各種特性。圖像壓縮方法的分類圖像壓縮方法的分類Ma Yingl

16、i CMC HBU像素編碼像素編碼變換編碼變換編碼預(yù)測編碼預(yù)測編碼位平面編碼位平面編碼增量調(diào)制增量調(diào)制熵編碼熵編碼算術(shù)編碼算術(shù)編碼DCTDCT變換變換DPCMDPCM調(diào)制調(diào)制 第一代壓縮編碼第一代壓縮編碼其他編碼其他編碼行程編碼行程編碼Ma Yingli CMC HBU子帶編碼子帶編碼模型編碼模型編碼分層編碼分層編碼分型編碼分型編碼第二代壓縮編碼第二代壓縮編碼Ma Yingli CMC HBU預(yù)測編碼預(yù)測編碼混合編碼混合編碼變換編碼變換編碼DFT、DCT變換變換ADPCMDPCM調(diào)制調(diào)制 數(shù)數(shù) 據(jù)據(jù) 壓壓 縮縮其他編碼其他編碼增量調(diào)制增量調(diào)制 無損壓縮無損壓縮 有損壓縮有損壓縮統(tǒng)計編碼統(tǒng)計編碼

17、Huffman、Shannon編碼編碼算術(shù)編碼算術(shù)編碼行程編碼行程編碼輪廓編碼輪廓編碼Ma Yingli CMC HBU5.2 統(tǒng)計編碼統(tǒng)計編碼n統(tǒng)計編碼統(tǒng)計編碼n根據(jù)信源的概率分布特性，分配具有惟一可譯性的根據(jù)信源的概率分布特性，分配具有惟一可譯性的可變長碼字，降低平均碼字長度，以提高信息的傳可變長碼字，降低平均碼字長度，以提高信息的傳輸速度，節(jié)省存儲空間。輸速度，節(jié)省存儲空間。n基本原理基本原理n在信號概率分布情況已知的基礎(chǔ)上，概率大的信號在信號概率分布情況已知的基礎(chǔ)上，概率大的信號對應(yīng)的碼字短，概率小的信號對應(yīng)的碼字長，這樣對應(yīng)的碼字短，概率小的信號對應(yīng)的碼字長，這樣就降低了平均碼字長度

18、。就降低了平均碼字長度。Ma Yingli CMC HBU可變碼長最佳編碼定理可變碼長最佳編碼定理n 在變長編碼中，如果碼字長度嚴(yán)格按照信在變長編碼中，如果碼字長度嚴(yán)格按照信號中符號出現(xiàn)概率大小的相反順序排列，則平號中符號出現(xiàn)概率大小的相反順序排列，則平均碼字長度一定小于其他符號順序排列方式的均碼字長度一定小于其他符號順序排列方式的平均碼字長度。平均碼字長度。Ma Yingli CMC HBU英文字母出現(xiàn)相對頻率英文字母出現(xiàn)相對頻率Ma Yingli CMC HBU英文字母出現(xiàn)相對頻率Ma Yingli CMC HBU國際莫爾斯電碼符號國際莫爾斯電碼符號Ma Yingli CMC HBU5.2

19、.1 Huffman編碼編碼n1前綴碼（前綴碼（Prefix Code）n一組唯一可譯碼的任一個碼字都只與一種信號一組唯一可譯碼的任一個碼字都只與一種信號存在對應(yīng)關(guān)系。存在對應(yīng)關(guān)系。n為保證唯一可譯碼，任一碼字都不能是其他碼為保證唯一可譯碼，任一碼字都不能是其他碼字的前綴。字的前綴。n例：例：f(i)=0,10,110,111Ma Yingli CMC HBU5.2.1 Huffman編碼編碼n1前綴碼（前綴碼（Prefix Code） 4 4層樹形結(jié)構(gòu)的編碼情況層樹形結(jié)構(gòu)的編碼情況Ma Yingli CMC HBUf(i)=0,10,110,111為其子樹。為其子樹。Ma Yingli CM

20、C HBU2Huffman編碼編碼算法：算法： 將圖像的灰度等級按概率大小進行將圖像的灰度等級按概率大小進行升升/ /降降序排序。序排序。 在灰度級集合中取兩個最小概率相加，合成一個概率。在灰度級集合中取兩個最小概率相加，合成一個概率。 新合成的概率與其他的概率成員組成新的概率集合。新合成的概率與其他的概率成員組成新的概率集合。 在新的概率集合中，仍然按照步驟的規(guī)則，直至新在新的概率集合中，仍然按照步驟的規(guī)則，直至新的概率集合中只有一個概率為的概率集合中只有一個概率為1 1的成員。這樣的歸并過程可的成員。這樣的歸并過程可以用二叉樹描述。以用二叉樹描述。 從根節(jié)點按前綴碼的編碼規(guī)則進行二進制編碼

21、。從根節(jié)點按前綴碼的編碼規(guī)則進行二進制編碼。Ma Yingli CMC HBUMa Yingli CMC HBU 信號源 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碼。方法：I.將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。Ma Yingli CMC HBUii.把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。 iii.重復(fù)上述做法，直到最后剩下兩個概率為止。iv.從最后一步剩下的兩個

22、概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。Ma Yingli CMC HBUHuffman編碼輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Ma Yingli CMC HBUHuffman編碼輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Ma Yingli CMC HBU輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼Ma

23、 Yingli CMC HBU輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼Ma Yingli CMC HBU輸入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編碼Ma Yingli CMC HBU輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二

24、步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman編碼Ma Yingli CMC HBU輸入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編碼Ma Yingli CMC HBU輸入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.4010101

25、0101S2=00Huffman編碼Ma Yingli CMC HBU輸入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編碼Ma Yingli CMC HBU輸入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編碼Ma Yingli CMC

26、 HBU輸入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編碼Ma Yingli CMC HBU輸入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編碼Ma Yingli CMC HBU編碼結(jié)果輸入S1S2S3S4S5S6輸入概率0.

27、40.30.10.10.060.04代碼10001101000101001011碼長123455Ma Yingli CMC HBU1 10 00 01 1S1S21 11 11 10 00 00 0S5S4S3S6編碼效率：6161log2.14/2.2/2.14/2.297.3%iiii iiHppbit symbolLplH L 信源熵：平均碼長：編碼效率：Ma Yingli CMC HBU【例5.1】n第第1行和第行和第2行列舉了一個信源的統(tǒng)計特性行列舉了一個信源的統(tǒng)計特性n結(jié)果如第三行所示結(jié)果如第三行所示符號集符號集xi x1 x2 x3 x4 x5 x6 概率分布概率分布pi 0.4

28、00.200.120.110.090.08Huffman編碼編碼 101000000101100111Ma Yingli CMC HBUHuffman編碼示意圖編碼示意圖n上圖所示為建立碼的過程上圖所示為建立碼的過程n下圖所示為從根開始，經(jīng)各下圖所示為從根開始，經(jīng)各中間節(jié)點到葉節(jié)點的路徑采用中間節(jié)點到葉節(jié)點的路徑采用二進制編碼的情況二進制編碼的情況Ma Yingli CMC HBU【例】Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU3Huffman編碼的性能編碼的性能n優(yōu)

29、點：優(yōu)點：n實現(xiàn)實現(xiàn)Huffman編碼的基礎(chǔ)是統(tǒng)計源數(shù)據(jù)集中各信號的概率編碼的基礎(chǔ)是統(tǒng)計源數(shù)據(jù)集中各信號的概率分布。分布。nHuffman編碼在無失真的編碼方法中效率優(yōu)于其他編碼方編碼在無失真的編碼方法中效率優(yōu)于其他編碼方法，是一種最佳變長碼，其平均碼長接近于熵值。法，是一種最佳變長碼，其平均碼長接近于熵值。n缺點：缺點：n當(dāng)信源數(shù)據(jù)成分復(fù)雜時，龐大的信源集致使當(dāng)信源數(shù)據(jù)成分復(fù)雜時，龐大的信源集致使Huffman碼表碼表較大，碼表生成的計算量增加，編譯碼速度相應(yīng)變慢較大，碼表生成的計算量增加，編譯碼速度相應(yīng)變慢n不等長編碼致使硬件譯碼電路實現(xiàn)困難。上述原因致使不等長編碼致使硬件譯碼電路實現(xiàn)困難

30、。上述原因致使Huffman編碼的實際應(yīng)用受到限制。編碼的實際應(yīng)用受到限制。Ma Yingli CMC HBU4圖像的圖像的Huffman編譯碼系統(tǒng)編譯碼系統(tǒng)Ma Yingli CMC HBUClaude Elwood Shannon (19162001)Claude Elwood Shannon (April 30, 1916 February 24, 2001) was an American mathematician, electronic engineer, and cryptographer known as The father of Information Theory.Ma

31、Yingli CMC HBU5.2.2 Shannon編碼與編碼與Fano編碼編碼5.2.2 Shannon編碼與編碼與Fano編碼編碼n1. Shannon提出了將信源符號依其概率降序排列，用提出了將信源符號依其概率降序排列，用符號序列累積概率的二進制表示作為對信源的唯一可符號序列累積概率的二進制表示作為對信源的唯一可譯編碼。其應(yīng)用于圖像編碼的步驟如下：譯編碼。其應(yīng)用于圖像編碼的步驟如下：（1 1）將）將N N個灰度級個灰度級x xi i按其概率遞減進行排列。按其概率遞減進行排列。（2 2）求概率分布）求概率分布p pi i的第的第i i個灰度級的二進制位數(shù)個灰度級的二進制位數(shù)n ni i。

32、 (5.10)(5.10) （3 3）計算與）計算與p pi i相對應(yīng)的累積概率相對應(yīng)的累積概率P Pi i, , 把與把與P Pi i相對應(yīng)的二相對應(yīng)的二進碼和接下去與進碼和接下去與p pk k（k k i i）相應(yīng)的碼相比較，前面的）相應(yīng)的碼相比較，前面的n ni i位至少有一位以上的數(shù)字是不同的。位至少有一位以上的數(shù)字是不同的。1loglog22iiipnpMa Yingli CMC HBU【例5.2】由表5.3計算該信源的Shannon編碼n平均碼字長度為平均碼字長度為2.92，較，較Huffman編碼為長。編碼為長。Ma Yingli CMC HBU2.Fano編碼編碼步驟步驟（1）

33、將圖像灰度級）將圖像灰度級xi其概率大小按遞減順序進行排序。其概率大小按遞減順序進行排序。（2）將）將xi分成兩組，使每組的概率和盡量接近。分成兩組，使每組的概率和盡量接近。給第一組灰度級分配代碼給第一組灰度級分配代碼“0”，第二組分配代碼，第二組分配代碼“1”。（3）若每組還是由兩個或以上的灰度級組成，重復(fù)上述）若每組還是由兩個或以上的灰度級組成，重復(fù)上述步驟，直至每組只有一個灰度級為止。步驟，直至每組只有一個灰度級為止。 Ma Yingli CMC HBU【例5.3】圖5.6以表5.3的信源為例說明Fano編碼。Ma Yingli CMC HBU5.2.3 算術(shù)編碼算術(shù)編碼Ma Yingl

34、i CMC HBUMa Yingli CMC HBU5.2.3 算術(shù)編碼算術(shù)編碼n在信源各符號概率接近的條件下，算術(shù)編碼是一種優(yōu)于在信源各符號概率接近的條件下，算術(shù)編碼是一種優(yōu)于Huffman編碼的方法。編碼的方法。n【例例】根據(jù)信源的概率分布進行算術(shù)編碼。已知信源的概根據(jù)信源的概率分布進行算術(shù)編碼。已知信源的概率分布為率分布為n求二進制序列求二進制序列01011的編碼。的編碼。535210XMa Yingli CMC HBUn解：步驟如下：解：步驟如下：n（1）二進制信源只有）二進制信源只有x1 = 0和和x2 = 1兩種符號，相兩種符號，相應(yīng)的概率為應(yīng)的概率為pc = 2/5, pe =

35、1- pc =3/5 n（2）設(shè)）設(shè)s為區(qū)域左端起始位置，為區(qū)域左端起始位置，e為區(qū)域右端終止為區(qū)域右端終止位置，位置，l為子區(qū)的長度，則為子區(qū)的長度，則 n符號符號“0”的子區(qū)為的子區(qū)為0，2/5），子區(qū)長度為），子區(qū)長度為2/5 ;n符號符號“1”的子區(qū)為的子區(qū)為2/5 ，1，子區(qū)長度為，子區(qū)長度為3/5 。舉例舉例2 2Ma Yingli CMC HBU（3）隨著序列符號的出現(xiàn)，子區(qū)按下列公式減少長度）隨著序列符號的出現(xiàn)，子區(qū)按下列公式減少長度:n新子區(qū)左端新子區(qū)左端 = 前子區(qū)左端前子區(qū)左端 + 當(dāng)前子區(qū)左端當(dāng)前子區(qū)左端前子區(qū)長度前子區(qū)長度n新子區(qū)長度新子區(qū)長度 = 前子區(qū)長度前子區(qū)長

36、度當(dāng)前子區(qū)長度當(dāng)前子區(qū)長度n設(shè)初始子區(qū)為設(shè)初始子區(qū)為0，1，步序為，步序為step，則編碼過程參見，則編碼過程參見實例實例。n可見，最后子區(qū)左端起始位置可見，最后子區(qū)左端起始位置 二進十進（）（)001110. 03125692sMa Yingli CMC HBUn最后子區(qū)長度n最后子區(qū)右端終止位置 n編碼結(jié)果為子區(qū)起始位置與終止位置之中點 = 0.0011。n所以，二進序列的算術(shù)編碼為0011。二進十進十進（）（）（)01000. 0125326251083125692e二進十進十進（）（）（)01000. 0125326251083125692e20.010000.001110Ma Yin

37、gli CMC HBU算術(shù)編碼算法的計算步驟實例算術(shù)編碼算法的計算步驟實例step x s l 1002/5 210 +（2/5）（2/5）= 4/25 （2/5）（3/5）= 6/25 302/5 + 0 6/25 = 4/25 （6/25）（2/5）= 12/125 414/25 +（2/5）（12/125）= 124/625 （12/125）（3/5）= 36/625 51124/625 +（2/5）（36/625）= 692/3125 （36/625）（3/5）= 108/625 Ma Yingli CMC HBU舉例舉例2 2Ma Yingli CMC HBUMa Yingli CM

38、C HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU算術(shù)編碼的過程：Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU算術(shù)編碼與Huffman編碼的比較：Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU5.3 預(yù)測編碼預(yù)測編碼預(yù)測編碼的基本思想：預(yù)測編碼的基本思想：在某種模型的指導(dǎo)下，根據(jù)過去的樣本序列在某種模型的指導(dǎo)下，根據(jù)過去的樣本序列推測當(dāng)前的信號樣本值，然后用實際值與預(yù)推測當(dāng)前的信號樣本值

39、，然后用實際值與預(yù)測值之間的誤差值進行編碼。測值之間的誤差值進行編碼。如果模型與實際情況符合得比較好且信號序如果模型與實際情況符合得比較好且信號序列的相關(guān)性較強，則誤差信號的幅度將遠(yuǎn)遠(yuǎn)列的相關(guān)性較強，則誤差信號的幅度將遠(yuǎn)遠(yuǎn)小于樣本信號。小于樣本信號。Ma Yingli CMC HBUMa Yingli CMC HBU圖像差值幅度的概率分布Ma Yingli CMC HBU5.3.1 預(yù)測編碼基本原理預(yù)測編碼基本原理n對實際值與預(yù)測值之間的誤差值進行編碼n差分脈沖編碼調(diào)制nDifferential Pulse Code ModulationnDPCMMa Yingli CMC HBU圖圖5.8

40、DPCM系統(tǒng)的組成系統(tǒng)的組成 Ma Yingli CMC HBU5.3.2 線性自適應(yīng)預(yù)測編碼線性自適應(yīng)預(yù)測編碼n假設(shè)經(jīng)掃描后的圖像信號假設(shè)經(jīng)掃描后的圖像信號x（t）是一個均值為零、方）是一個均值為零、方差為的平穩(wěn)隨機過程。線性預(yù)測就是選擇差為的平穩(wěn)隨機過程。線性預(yù)測就是選擇ai（i 1，2，N 1）使預(yù)測值）使預(yù)測值 n并且使差值并且使差值en的均方值為最小。的均方值為最小。n預(yù)測信號的均方誤差（預(yù)測信號的均方誤差（MSE）定義為）定義為 Een = E(xn - xn) 211nNiiixaxMa Yingli CMC HBU設(shè)計最佳預(yù)測的系數(shù)設(shè)計最佳預(yù)測的系數(shù)ai，采用，采用MMSEn最

41、小均方誤差準(zhǔn)則。可以令最小均方誤差準(zhǔn)則?？梢粤頽定義定義xi和和xj的自相關(guān)函數(shù)的自相關(guān)函數(shù) R（i，j）= Exi，xjn寫成矩陣形式為寫成矩陣形式為Yule-Walker方程組方程組 02niaeE) 1()2() 1 ()0()3(2()3()0() 1 ()2() 1 ()0(1n21NRRRaaaRNRNRNRRRNRRR）)()(11ikRaiRNkk若若R（i）已知，該方程組可以用遞推算法來求解）已知，該方程組可以用遞推算法來求解ai。Ma Yingli CMC HBU通過分析可以得出以下結(jié)論：通過分析可以得出以下結(jié)論：n圖像的相關(guān)性越強，壓縮效果越好。圖像的相關(guān)性越強，壓縮效果

42、越好。n當(dāng)某個階數(shù)已使當(dāng)某個階數(shù)已使EeN, eN 1 0時，即使再增加預(yù)時，即使再增加預(yù)測點數(shù)，壓縮效果也不可能繼續(xù)提高。測點數(shù)，壓縮效果也不可能繼續(xù)提高。n若若xi是平穩(wěn)是平穩(wěn)m階階Markov過程序列，則過程序列，則m階線性預(yù)階線性預(yù)測器就是在測器就是在MMSE意義下的最佳預(yù)測器。意義下的最佳預(yù)測器。Ma Yingli CMC HBU圖圖5.9 當(dāng)前像素與鄰近像素的位置關(guān)系當(dāng)前像素與鄰近像素的位置關(guān)系Ma Yingli CMC HBU常用預(yù)測器方案常用預(yù)測器方案n前值預(yù)測：用前值預(yù)測：用x0同一行的最近鄰近像素來預(yù)測同一行的最近鄰近像素來預(yù)測 =x0 n一維預(yù)測：如一維預(yù)測：如上圖上圖中

43、的中的x1、x5。n二維預(yù)測：如二維預(yù)測：如上圖上圖中的中的 x1、x2、x3、x4、x5、x6、x7等。等。n三維預(yù)測三維預(yù)測x Ma Yingli CMC HBU5.3.3 自適應(yīng)預(yù)測編碼自適應(yīng)預(yù)測編碼n自適應(yīng)預(yù)測自適應(yīng)預(yù)測n預(yù)測參數(shù)根據(jù)信號的統(tǒng)計特性來確定，以達到最預(yù)測參數(shù)根據(jù)信號的統(tǒng)計特性來確定，以達到最佳預(yù)測佳預(yù)測n預(yù)測編碼的優(yōu)點預(yù)測編碼的優(yōu)點n直觀快捷、便于實現(xiàn)直觀快捷、便于實現(xiàn)n預(yù)測編碼的缺點預(yù)測編碼的缺點n壓縮比不夠高壓縮比不夠高Ma Yingli CMC HBU5.4 變換編碼變換編碼5.4.1 變換編碼的基本原理變換編碼的基本原理n 通過數(shù)學(xué)變換可以改變信號能量的分布，從而

44、壓通過數(shù)學(xué)變換可以改變信號能量的分布，從而壓縮信息量?？s信息量。n以傅里葉變換的概念說明合理的變換可以改變信以傅里葉變換的概念說明合理的變換可以改變信號能量分布的基本原理。號能量分布的基本原理。Ma Yingli CMC HBU變換可以改變信號能量的分布（Ma Yingli CMC HBU5.4.2 變換編碼的系統(tǒng)結(jié)構(gòu)變換編碼的系統(tǒng)結(jié)構(gòu)圖圖5.10 變換編碼系統(tǒng)變換編碼系統(tǒng)正正交交變變換換量量化化編編碼碼傳傳輸輸/儲儲存存解解碼碼反反交交換換圖圖像像輸輸入入圖圖像像輸輸出出Ma Yingli CMC HBU5.4.3 變換編碼的實現(xiàn)變換編碼的實現(xiàn)在變換編碼中有以下幾個問題值得注意：在變換編碼中

45、有以下幾個問題值得注意：n圖像變換方法的選取圖像變換方法的選取n子圖像大小的選取子圖像大小的選取n常用的圖像編碼方法常用的圖像編碼方法n區(qū)域編碼區(qū)域編碼n閾值編碼閾值編碼n混合編碼混合編碼Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBU變換編碼Ma Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUMa Yingli CMC H

46、BU幀內(nèi)混合編碼原理圖幀內(nèi)混合編碼原理圖變換編碼變換編碼變換編碼變換編碼變換編碼變換編碼預(yù)預(yù)測測編編碼碼信信道道傳傳輸輸/存存儲儲預(yù)預(yù)測測編編碼碼反反變變換換 f(1,n)F(1,n)e(1,n)e(1,n)f(2,n)F(2,n)e(2,n)e(2,n)f(M,n)F(M,n)e(M,n)e(M,n)f(1,n)f(2,n)f(M,n).Ma Yingli CMC HBUI傅 立 葉 變 換 FF頻 譜 中 心 化去 除 高 頻 F1F反 變 換 AF1反 變 換 BMa Yingli CMC HBU原 圖 IDCT變 換 D去 除 高 頻 D1D反 變 換 C1D1反 變 換 C2Ma Y

47、ingli CMC HBUMa Yingli CMC HBUMa Yingli CMC HBUDCTDCT變換：變換：1010222) 12(cos) 12(cos),()()(),(MxNyMNMNcyxyxfccF正變換：正變換：1010222) 12(cos) 12(cos),()()(),(MNMNcMNyxFccyxf1)(21xc0 x1,.,2 , 1Nx逆變換：逆變換：其中：其中：Ma Yingli CMC HBUMa Yingli CMC HBUHuffman:42bits； 編碼效率編碼效率32.8%Huffman:16bits;編碼效率：編碼效率：12.5%2922171

48、4241613141914121216111116C例：例：56606159586059625759596157586059F原圖像為：原圖像為：DCTDCT變換變換除以量化系數(shù)，取整除以量化系數(shù)，取整236.254.51692.47491.56361.05920.17681.17130.78031.76780.43872.251.71251.00310.28030.86780.1768D15000000000000000DMa Yingli CMC HBUMa Yingli CMC HBUDCT變換編碼實例原圖原圖解壓圖解壓圖Ma Yingli CMC HBUMa Yingli CMC HB

49、UMa Yingli CMC HBU5.4.4 整數(shù)小波變換與圖像壓縮整數(shù)小波變換與圖像壓縮n量化器的設(shè)計是決定圖像保真度的關(guān)鍵環(huán)節(jié)，而傳統(tǒng)的DCT和經(jīng)典小波變換在圖像變換后會產(chǎn)生浮點數(shù)，因而必須對變換后的數(shù)據(jù)進行量化處理，這樣就產(chǎn)生不同程度的失真。n新一代的整數(shù)小波變換（又叫第二代小波變換）采用提升方法能夠?qū)崿F(xiàn)整數(shù)變換，因而能夠?qū)崿F(xiàn)圖像的無損壓縮，顯然它是一種很適合于醫(yī)學(xué)等圖像的壓縮方法。 n新的靜態(tài)圖像壓縮標(biāo)準(zhǔn)JPEG2000中采用了基于提升方法的整數(shù)小波變換。Ma Yingli CMC HBU提升方法構(gòu)造小波分為分裂、預(yù)測和更新提升方法構(gòu)造小波分為分裂、預(yù)測和更新3 3個步驟。個步驟。n

50、1分裂（分裂（split）n 將一原始信號序列sj按偶數(shù)和奇數(shù)序號分成兩個較小的、互不相交的小波子集sj-1和dj-1：n2.預(yù)測（預(yù)測（predict）n 由于數(shù)據(jù)間存在相關(guān)性，因而可以定義一個預(yù)測算子P，用P(sj-1)來預(yù)測 dj-1.。n這樣可用相鄰的偶數(shù)序列來預(yù)測奇數(shù)序列。n用dj-1與P(sj-1)的差值代替d j-1，則數(shù)據(jù)量要比原始d j-1要小得多。n3更新（更新（update）n 上述兩個過程一般不能保持原圖像中的某些整體性質(zhì)（如亮度）,為此我們要構(gòu)造一個U算子去更新s,使之保持原有數(shù)據(jù)集的某些特性。Ma Yingli CMC HBU5.5 二值圖像編碼二值圖像編碼n只有只

51、有“白白”（用（用“0”表示）和表示）和“黑黑”（用（用“1”表示）表示）兩個灰度級稱之為二值圖像（兩個灰度級稱之為二值圖像（binary image）。）。n二值圖像通常是由人為產(chǎn)生的，如由文字組成的文檔文二值圖像通常是由人為產(chǎn)生的，如由文字組成的文檔文件、表格、工程圖紙、地圖等。件、表格、工程圖紙、地圖等。n一幅二維圖像按位平面進行分解可以得到若干個二值圖一幅二維圖像按位平面進行分解可以得到若干個二值圖像，因而二值圖像的編碼方法為逐進編碼模式奠定了基像，因而二值圖像的編碼方法為逐進編碼模式奠定了基礎(chǔ)。礎(chǔ)。 Ma Yingli CMC HBU5.5.1 跳躍空白編碼跳躍空白編碼 (skip

52、blank coding ) n將圖像的每一條掃描線分成若干等長的段，每段有將圖像的每一條掃描線分成若干等長的段，每段有m個像個像素，一般素，一般m=812。n這些掃描線段的組成可能出現(xiàn)二類情況：（1 1）全是）全是“0”0”像素。像素。n這種線段稱為這種線段稱為“空白塊（空白塊（blankblank）”，常表示二值圖像的背景成分。，常表示二值圖像的背景成分。n編碼時編碼時“空白塊空白塊”用碼字用碼字“0 0”表示。表示。（2 2）全是）全是“1”1”像素或由像素或由“0”0”、“1”1”像素混合而成。像素混合而成。n編碼時，這種線段用編碼時，這種線段用“1”1”加加直接編碼直接編碼表示。表示

53、。Ma Yingli CMC HBUn上述方法很容易推廣的在二維情形中。上述方法很容易推廣的在二維情形中。n將圖像劃分為若干個子圖像。當(dāng)將圖像劃分為若干個子圖像。當(dāng)子圖像像素全為子圖像像素全為0 0時，時，編碼為編碼為“0”0”; ;否則，子圖像的否則，子圖像的編碼首位為編碼首位為“1”1”， 其其余碼位余碼位（code position）采用像素的直接編碼采用像素的直接編碼表示表示。Ma Yingli CMC HBU5.5.2 游程長度編碼游程長度編碼RLC (Run Length Coding ) n一種簡單的無損編碼技術(shù)，它改變連續(xù)出現(xiàn)相同字符的表一種簡單的無損編碼技術(shù)，它改變連續(xù)出現(xiàn)相

54、同字符的表達方式，以降低碼長。達方式，以降低碼長。n傳真的二值圖像中，連傳真的二值圖像中，連“0”0”或連或連“1”1”總是成串出現(xiàn)，總是成串出現(xiàn)，稱為稱為“白游程白游程”和和“黑游程黑游程”。n非二值的相同連續(xù)數(shù)據(jù)串，同樣簡化為兩個符號：一非二值的相同連續(xù)數(shù)據(jù)串，同樣簡化為兩個符號：一個符號代表個符號代表數(shù)據(jù)數(shù)據(jù)，第二個代表，第二個代表串串長長。n游程長度編碼一般不直接單獨使用，通常配合其他編碼方游程長度編碼一般不直接單獨使用，通常配合其他編碼方式使用來提高壓縮效果。式使用來提高壓縮效果。 Ma Yingli CMC HBU二維行程編碼要解決的核心問題是: 將二維排列的像素，采用某種方式轉(zhuǎn)化

55、成一維排列的方式。之后按照一維行程編碼方式進行編碼。(a) (b) 兩種典型的二維行程編碼的排列方式兩種典型的二維行程編碼的排列方式Ma Yingli CMC HBU如果按照行掃描的順序排如果按照行掃描的順序排列的話，數(shù)據(jù)分布為：列的話，數(shù)據(jù)分布為：行程編碼為行程編碼為: :（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），），（1，129），（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），），（2，130），（），（1，129），（），（2，130），（）

56、，（1，129），（），（2，130），（），（2，129），），（1，127），（），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，129），），（1，131），（），（1，130），（），（1，127），（），（1，128），（），（1，127），（），（1，128），），（1，127），（），（1，128），（），（2，132），（），（1，125），（），（1，126），（），（2，129），），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，127），（），（1，125），），（2，128）

57、，（），（1，126），（），（1，130），（），（2，131）數(shù)據(jù)量為數(shù)據(jù)量為:46:46* *（3+83+8）=506(bit) (98.83%)=506(bit) (98.83%)130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f數(shù)據(jù)量：數(shù)據(jù)量：64*

58、8=512(bit)【例例】Ma Yingli CMC HBU如果按照列掃描的順如果按照列掃描的順序排列的話，數(shù)據(jù)分序排列的話，數(shù)據(jù)分布為：布為：行程編碼為行程編碼為: :數(shù)據(jù)量為數(shù)據(jù)量為:42:42* *（3+83+8）=462(bit) (92.03%)=462(bit) (92.03%)（3，130），（），（1，129），（），（2，127），（），（1，125），（），（1，127），（），（4， 130），），（2，128），（），（1，126），（），（1，125），（），（4，130），（），（2，127），（），（1，129），），（1，128），（），（5，129），（），

59、（1，128），（），（1，129），（），（1，128），（），（2， 134），），（1，132），（），（1，130），（），（1，131），（），（2，127），（），（1，126），（），（2，133），），（1，132），（），（1，130），（），（1，129），（），（1，128），（），（1，129），（），（1，130），）， （1，129），（），（2，130），（），（1，129），（），（1，131），（），（1，132），（），（1，133），），（1，131），（），（3，130），（），（1，129），（），（1，130），（），（2，132），（），（1，13

60、1）130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131fMa Yingli CMC HBU如果按照方式如果按照方式(a)(a)掃掃描的順序排列的話，描的順序排列的話，數(shù)據(jù)分布為：數(shù)據(jù)分布為：行程編碼為行程編碼為: :數(shù)據(jù)量為數(shù)據(jù)量為:43:43* *（3+83+