第7章 圖像編碼與壓縮

1、 7.1 概述 7.2 圖像保真度準則 7.3 圖像的統(tǒng)計編碼方法 7.4 預測編碼 7.5 變換編碼第七章 圖像編碼與壓縮7 7.1 .1 概述概述一、圖像數(shù)據(jù)壓縮的必要性與可能性一、圖像數(shù)據(jù)壓縮的必要性與可能性 數(shù)據(jù)壓縮的研究內(nèi)容包括數(shù)據(jù)的表示、傳輸、變換和編碼方法，目的是減少存儲數(shù)據(jù)所需的空間和傳輸所用的時間。 圖像編碼與壓縮就是對圖像數(shù)據(jù)按一定的規(guī)則進行變換和組合，達到以盡可能少的代碼（符號）來表示盡可能多的圖像信息。為什么要對圖像進行壓縮？圖像數(shù)據(jù)的特點之一：數(shù)據(jù)量大為什么能對圖像進行壓縮？圖像中存在著冗余數(shù)據(jù)二、數(shù)據(jù)冗余類別二、數(shù)據(jù)冗余類別(1) 編碼冗余 與灰度分布的概率特性有關(guān)

2、(2) 象素間冗余空間冗余，幾何冗余(3) 心理視覺冗余與主觀感覺有關(guān) 減少/消除其中的一種/多種冗余，就能取得數(shù)據(jù)壓縮的效果 1. 1. 編碼冗余編碼冗余 編碼：用符號表達圖像 對圖像編碼需建立碼本來表達圖像數(shù)據(jù)。碼本：碼本：用來表達一定量的信息或一組事件所 需的一系列符號（如字母、數(shù)字等）碼字：碼字：對每個信息或事件所賦的碼符號序列碼字的長度（字長）：碼字的長度（字長）：每個碼字里的符號個數(shù)圖象中灰度出現(xiàn)的概率：不同灰度出現(xiàn)的概率不同。 設(shè)用來表示Sk每個數(shù)值的比特數(shù)是 ，則表示每個像素所需要的平均比特數(shù)為：平均比特數(shù)為：10avg)()(LkkskspslL1 , , 1 , 0)(Lk

3、nnspkks)(ksl如果編碼時所用的碼本不能使上式達到最小，說明存在編碼冗余。變長編碼：變長編碼：用較少的比特數(shù)表示出現(xiàn)概率較大的灰度級，用較多的比特數(shù)表示出現(xiàn)概率較小的灰度級。思考：該圖像的熵是多少？思考：該圖像的熵是多少？2.77(bit)2.77(bit)（2 2） 象素間冗余象素間冗余圖像內(nèi)部相鄰像素之間存在較強的相關(guān)性所造成的冗余00.81051015202500.810510152025規(guī)則 冗余大不規(guī)則冗余?。? 3）心理視覺冗余心理視覺冗余主觀：因人而異，因應用要求而異其存在與人觀察圖象的方式有關(guān) 眼睛對某些視覺信息更敏感 人對某些視覺信

4、息更關(guān)心心理視覺冗余與實在的視覺信息有聯(lián)系心理視覺冗余丟掉后，不能找回，即信息會丟失。 圖像數(shù)據(jù)到底能壓縮多少，除了和圖像本身存在的冗余度大小有關(guān)外，還取決于對圖像質(zhì)量的要求，如 廣播電視 壓縮比31 可視電話 壓縮比15001 三、圖像編碼壓縮的分類三、圖像編碼壓縮的分類 根據(jù)解壓重建后的圖像和原始圖像之間是否具有誤差，圖像編碼壓縮分為：l 無損編碼l 有損編碼 根據(jù)編碼作用域劃分，圖像編碼分為：l 空間域編碼l 變換域編碼 圖像壓縮無損編碼有損編碼霍夫曼編碼行程編碼算術(shù)編碼預測編碼變換編碼其它編碼圖1 圖像編碼壓縮分類圖像保真度準則：描述解碼圖像相對于原始圖像偏離 程度的測度。常用的保真度

5、準則可分為兩大類：l 客觀保真度準則：客觀保真度準則：用編碼輸入圖與解碼輸出圖的某個確定函數(shù)表示損失的信息量， 便于計算或測量l 主觀保真度準則：主觀保真度準則：主觀測量圖象的質(zhì)量，因人而異7 7.2 .2 圖像保真度準則圖像保真度準則一、客觀保真度準則一、客觀保真度準則 最常用的客觀保真度準則是原圖像和解碼圖像之間的均方根誤差和均方根信噪比兩種。 點誤差圖誤差均方根誤差解壓圖像的均方信噪比),(),(),(yxfyxfyxe 1010),(),( MxNyyxfyxf21 10102 rms),(),( 1 MxNyyxfyxfMNe 10102 10102),(),( ),( MxNyMx

6、NymsyxfyxfyxfSNR令 1010),( 1MxNyyxfMNf 10102 10102 ),(),( ),( lg10MxNyMxNyyxfyxffyxfSNR10102 2max),(),(lg10MxNyyxfyxffMNPSNR實際使用中，常將SNRrms歸一化，并用分貝(dB)表示。令令 ，則得峰值信噪比，則得峰值信噪比yxff,maxmax（歸一化）信噪比信噪比：二、主觀保真度準則二、主觀保真度準則 很多解壓圖最終是供人觀看的，一種常用的方法是讓一組（不少于20人）觀察者觀察圖像并給該圖像評分，將他們對該圖像的評分取平均，作為這幅圖像的質(zhì)量。 表1 電視圖象質(zhì)量評價尺度

7、評分評價說 明1優(yōu)秀圖象質(zhì)量非常好，如同人能想象出的最好質(zhì)量。2良好圖象質(zhì)量高，觀看舒服，有干擾但不影響觀看。3可用圖象質(zhì)量可接受，有干擾但不太影響觀看。4剛可看圖象質(zhì)量差，干擾有些妨礙觀看，觀察者希望改進。5差圖象質(zhì)量很差，妨礙觀看的干擾始終存在，幾乎無法觀看。6不能用圖象質(zhì)量極差，不能使用。一、圖像冗余度和編碼效率一、圖像冗余度和編碼效率7.3 7.3 統(tǒng)計編碼方法統(tǒng)計編碼方法 根據(jù)信源的概率分布特性分配可變長碼，使平均碼長非常接近于熵，這種壓縮編碼稱為統(tǒng)計編碼。統(tǒng)計編碼。 根據(jù)Shannon無干擾信息保持編碼定理，若對原始圖像數(shù)據(jù)的信息進行無失真圖像編碼，壓縮后平均碼長存在一個下限，這個

8、下限是圖像信息熵H。理論上最佳信息保持編碼的平均碼長可以無限接近圖像信息熵H，但總是大于或等于圖像的熵H。 iLiippH210log信息熵壓縮后平均碼長 10LiiipB是灰度級i的編碼長度，pi是灰度級i出現(xiàn)的概率i編碼效率為：1HBrrBH11冗余度定義為： 當經(jīng)過編碼壓縮后，圖像信息的冗余度接近于零，或編碼效率接近于1，這類編碼方法稱為高效編碼。二、霍夫曼二、霍夫曼(Huffman)(Huffman)編碼編碼 霍夫曼編碼是1952年由Huffman提出的一種編碼方法，是一種無損編碼方法。這種編碼方法是根據(jù)信源數(shù)據(jù)各信號發(fā)生的概率進行編碼的。 思想：在信源數(shù)據(jù)中出現(xiàn)概率越大的符號，編碼以

9、后相應的碼長越短；出現(xiàn)概率越小的符號，其碼長越長，從而達到用盡可能少的碼符表示信源數(shù)據(jù)。 在無損變長編碼方法中是最佳的。霍夫曼編碼實例： 設(shè)輸入信源為 ，其頻率分布分別為求其霍夫曼編碼。 654321,aaaaaaa 654321,wwwwwwW 3 . 004. 01 . 006. 04 . 01 . 0654321iiapaaaaaaa霍夫曼編碼步驟：霍夫曼編碼步驟：(1) 縮減信源符號數(shù)量 將信源符號按出現(xiàn)概率從大到小排列，然后將概率最小的相加，再重新排序，重復，直到剩下兩個概率為止。0.10.060.00.40.

10、1234a12a5a3a6a4a初始信源信源的消減步驟符號概率(2)對每個信源符號賦值從（消減到）最小的信源開始向前進行編碼，逐步回到初始信源。0.10.060.00.40.61234a12a5a3a6a4a初始信源對消減信源的賦值符號概率10001101000101100010011100010110001101000101001011碼字思考：思考：計算該信源的熵、編碼后的平均碼長及編碼效率?；舴蚵幋a結(jié)果霍夫曼編碼結(jié)果 平均碼長 信源熵 編碼效率2 . 2)543(1 . 02

11、3 . 014 . 010LkiipB14. 2log112LiiiPPH973. 02 . 214. 2BH霍夫曼編碼的計算量霍夫曼編碼的計算量信源：N個符號信源消減次數(shù)：N -2碼賦值次數(shù)：N -2最優(yōu)的變長編碼方法犧牲編碼效率來換取編碼速度對于同一圖像采用霍夫曼編碼，編碼是否唯一？霍夫曼編碼的特點：（1）編碼值不是唯一的；（2）當圖像灰度值分布不均勻時，霍夫曼編碼效率 高；當概率分布比較均勻時，編碼效率低；（3）不能使用某種數(shù)學模型建立信源符號與編碼之 的關(guān)系，而必須通過查表方法建立它們之間 的對應關(guān)系。 利用霍夫曼編碼需要對圖像掃描兩遍，第一遍獲取圖像每個灰度級出現(xiàn)的概率，進行霍夫曼編

12、碼，獲取編碼表；第二遍掃描圖像是根據(jù)編碼表對原圖像各像素編碼，生成壓縮文件。Huffman Huffman 編碼結(jié)果？編碼結(jié)果？自然碼平均碼長：自然碼平均碼長：3思考思考Huffman編碼輸入輸入01234567輸入概率輸入概率0.020.050.000.220.16排序排序輸入輸入65743210輸入概率輸入概率90.050.02Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步0.2

13、60.140.12第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.4201010101

14、010101Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101016=10Huffman編碼第第1步步90.07輸入輸入65743210概率概率

15、90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101015=11Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5

16、步步0.420.320.26第第6步步0.580.42010101010101017=000Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101014=010Huffman編碼第第1步步90.

17、07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101013=011Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.

18、260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101012=0010Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101011=

19、00110Huffman編碼第第1步步90.07輸入輸入65743210概率概率90.050.02第第2步步2第第3步步0.260.16第第4步步0.320.260.220.20第第5步步0.420.320.26第第6步步0.580.42010101010101010=00111編碼結(jié)果代碼代碼001110011000100110101110000碼長碼長55433223輸入輸入01234567輸入概率輸入概率0.020.050.09

20、00.220.16平均碼長：平均碼長：2.81也可用二叉樹二叉樹實現(xiàn)Huffman編碼方法。（1）統(tǒng)計出每個元素出現(xiàn)的頻率；（2）從左到右把上述頻率按從大到小的順序排列；（3）選出頻率最小的兩個值，作為二叉樹的兩個葉子 節(jié)點，將其和作為它們的根節(jié)點，兩個葉子節(jié)點 不再參與排序，新的根節(jié)點同其余元素出現(xiàn)的頻 率排序；（4）重復（3），直到最后得到和為1的根節(jié)點；（5）將形成的二叉樹的子節(jié)點概率大的為0，概率小 的為1。把最上面的根節(jié)點到最小面的葉子節(jié)點 途中遇到的0，1序列串起來，就得到了各個元素 的編碼。 0.2霍夫曼編碼： 10 00 0110 010 0111 11原

21、始信源： a1 a2 a3 a4 a5 a6 2 . 004. 015. 006. 035. 02 . 0654321iiapaaaaaaaa2 0.35 1 0a6 a1 0.2 a4 0.15 a3 0.06 a5 0.04 00.60 0 1 1 00 10 1主要步驟為：(1) 將信源符號依其概率從大到小排列；(2) 將信源符號分成概率和接近的兩部分；(3) 分別給兩部分的信源符號組合賦值；(4) 如果兩部分均只有一個信源符號，編碼結(jié)束，否則返回(2)繼續(xù)進行。三、費諾三、費諾- -仙農(nóng)編碼仙農(nóng)編碼 3 . 004. 01 . 006. 04 . 01 . 0654

22、321iiapaaaaaaa輸入概率a20.41a60.300a10.1100a40.11a30.0610a50.0411000100010101100111編碼編碼四、算術(shù)編碼四、算術(shù)編碼l 算術(shù)編碼是一種從整個符號序列出發(fā)，采用遞推形式連續(xù)編碼的方法。l 算術(shù)編碼中，源符號和碼字間的一一對應關(guān)系并不存在。一個算術(shù)碼字要賦給整個信源符號序列。l 算術(shù)編碼的結(jié)果是在0到1之間的一個實數(shù)。只用到加法和移位運算，所以稱為算術(shù)編碼。算術(shù)編碼示例：算術(shù)編碼示例： 有1個由4-符號信源a1, a2, a3, a4組成的符號序列：b1b2b3b4b5 = a1a2a3a3a40.067 520.068 8

23、100.200.080.040.0720.0560.062 4編碼序列b =22a1b =a1b =3a3b =3a44ab =53aa1a12a2a3a3a3aa12a2a2a3aa1a14a4a4a4a4a0.068各符號出現(xiàn)的概率：P(a1)=0.2 p(a2)=0.2 p(a3)=0.4 p(a4)=0.2解碼過程：0.067 520.068 8100.200.080.040.0720.0560.062 4編碼序列b =22a1b =a1b =3a3b =3a44ab =53aa1a12a2a3a3a3aa12a2a2a3aa1a14a4a4a4a4a各符號出現(xiàn)的概率：P(a1)=0.

24、2 p(a2)=0.2 p(a3)=0.4 p(a4)=0.8解碼解碼0.040.080.160.0680.0480.0560.0720.05920.06240.06880.063880.06496五、行程編碼五、行程編碼 簡稱RLE（Run-Length-Encoding）壓縮方法，也稱游程編碼，是一種建立在統(tǒng)計特性基礎(chǔ)上的無損壓縮編碼方式，是最簡單的圖像壓縮方式之一。 分為：l 一維行程編碼l 二維行程編碼 行程編碼在處理包含大量重復信息的數(shù)據(jù)時可以獲得很好的壓縮效率。 在一個逐行存儲的圖象中，具有相同灰度值的一些象素組成的序列稱為一個行程。編碼時，對于每個行程只存儲一個

25、灰度值及個數(shù)。這種按照行程進行的編碼被稱為行程編碼（Run Length Encoding）。 如“aaabbbbccccddddedddaaa”經(jīng)過行程編碼為：3a4b4c4d1e3d3a。 l 一維行程編碼一維行程編碼只考慮消除行內(nèi)像素間的相關(guān)性。l 二維行程編碼二維行程編碼 利用圖像的二維信息的強相關(guān)性，按照一定的掃描路徑遍歷所有的像素形成一維的序列，對序列進行一維行程編碼的方法。 對一幅灰度圖像進行二維行程編碼，首先將圖像分為一定大小的子塊，然后對每個子塊按照一定的掃描路徑遍歷所有的像素形成一維的序列，進行一維行程編碼，所有子塊的編碼就是圖像的二維行程編碼。圖 二維行程編碼數(shù)據(jù)排列方式

26、例：例：130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f數(shù)據(jù)量：數(shù)據(jù)量：6464* *8=512(bit)8=512(bit)如果按照行掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，129，134，133，129，130； 130，130，130，

27、129，134，133，130，130； 130，130，130，129，132，132，130，130；129，130，130，129，130，130，129，129； 127，128，127，129，131，129，131，130；127，128，127，128，127，128，132，132； 125，126，129，129，127，129，133，132；127，125，128，128，126，130，131，131行程編碼為行程編碼為: :（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），），（1，129），

28、（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），），（2，130），（），（1，129），（），（2，130），（），（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，1

29、26），（），（2，129），），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，127），（），（1，125），），（2，128），（），（1，126），（），（1，130），（），（2，131）數(shù)據(jù)量為數(shù)據(jù)量為:46:46* *（3+83+8）=506(bit) (98.83%)=506(bit) (98.83%)如果按照列掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，129，127，127，125，127； 130，130，130，130，128，128，126，125； 130，130，130，130，127，127，129，12

30、8；129，129，129，129，129，128，129，128； 134，134，132，130，131，127，127，126；133，133，132，130，129，128，129，130； 129，130，130，129，131，132，133，131；130，130，130，129，130，132，132，131行程編碼為行程編碼為: :數(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）

31、，），（2，128），（），（1，126），（），（1，125），（），（4，130），（），（2，127），（），（1，129），），（1，128），（），（5，129），（），（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

32、，131），（），（1，132），（），（1，133），），（1，131），（），（3，130），（），（1，129），（），（1，130），（），（2，132），（），（1，131）如果按照方式(a)掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129

33、，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程編碼為行程編碼為: :數(shù)據(jù)量為數(shù)據(jù)量為:43:43* *（3+83+8）=473(bit) (94.22%)=473(bit) (94.22%)（7，130），（），（2，130），（），（4，129），（），（2，130），（），（1，129）；（）；（1，127），），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，130），（），（1，132），），（2，134），（），（2，133），（），（1

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

35、，（2，127）7.4 7.4 預測編碼預測編碼空域方法，消除象素間的冗余預測編碼的基本思想：通過僅提取每個像素中的新信息并對它們編碼來消除像素間的冗余。預測編碼分為：一、無損預測編碼 信息保存型二、有損預測編碼 信息損失型一、無損預測編碼無損預測編碼系統(tǒng)無損預測編碼系統(tǒng)編碼器 + + 解碼器（有相同的預測器）無損預測編碼系統(tǒng)無損預測編碼過程無損預測編碼過程輸入序列： fn (n = 1, 2, )預測輸出： （舍入成整數(shù)）預測誤差：誤差編碼：在符號編碼器中用變長碼編誤差解壓序列：哪里取得了壓縮？nnnffennnfefnf（消除了象素間冗余）（消除了象素間冗余） 預測編碼中，關(guān)鍵預測編碼中，

36、關(guān)鍵：如何進行預測如何進行預測？最常用的方法是線性預測最常用的方法是線性預測m 階線性預測： miininfaf 1round 式中，m 是線性預測器的階，ai為預測系數(shù)，round為舍入函數(shù)。 1-D線性預測：miinyixfayxf 1)(round )(,即1-D線性預測是當前行掃描到的先前像素的函數(shù)一階(m=1)1-D線性預測：)1(round )(yxafyxfn,eee2exp21)(eep的均方差是誤差ee預測誤差的概率密度函數(shù)：也稱為前值預測。二、有損預測編碼系統(tǒng)二、有損預測編碼系統(tǒng)增加了1個量化器，預測器放在1個反饋環(huán)中 有損預測編碼系統(tǒng)有損預測編碼系統(tǒng)有損預測編碼系統(tǒng)輸入序

37、列： fn (n = 1, 2, )量化輸出：預測輸入：解壓序列：編碼誤差：哪里又又取得了壓縮？nnnfef nnnfef （量化，減少了（量化，減少了 心理視覺冗余）心理視覺冗余） )(nneqe nnff德爾塔調(diào)制（DM）是一種簡單的有損預測編碼方法，其預測器與量化器分別如下： 預測器 量化器預測系數(shù) a 1，常數(shù) c 0 1 nnfaf其它對cecenn0 DM編碼舉例 取a=1,c=6.5 1 nnfaf其它對cecenn0 7.5 7.5 變換編碼變換編碼變換編碼的基本原理：利用可逆的線性變換將圖像從空間域中轉(zhuǎn)換為變換域中的一組系數(shù)，然后對變換系數(shù)進行量化、編碼，達到壓縮數(shù)據(jù)的目的。頻域方法，非信息保