數(shù)字圖像處理 第九章 圖像壓縮編碼

數(shù)字圖像處理DigitalImageProcessing第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼562第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼5639.1引言信息傳輸方式發(fā)生了很大的改變通信方式的改變

文字+語音圖像+文字+語音通信對象的改變

人與人人與機(jī)器，機(jī)器與機(jī)器由于通信方式和通信對象的改變帶來的最大問題是：傳輸帶寬、速度、存儲器容量的限制。4數(shù)碼圖像的普及，導(dǎo)致了數(shù)據(jù)量的龐大。圖像的傳輸與存儲，必須解決圖像數(shù)據(jù)的壓縮問題。對于電視畫面的分辨率640*480的彩色圖像，每秒30幀，則一秒鐘的數(shù)據(jù)量為：640*480*24*30=221.12M

播放時(shí)，需要221Mbps的通信回路。在10M帶寬網(wǎng)上實(shí)時(shí)傳輸?shù)脑?，需要壓縮到原來數(shù)據(jù)量的0.045，即0.36bit/pixel。9.1引言5

數(shù)據(jù)冗余例子我們從發(fā)送一封電報(bào)的例子來體會數(shù)據(jù)冗余的概念。你的妻子，Helen，將于明天晚上6點(diǎn)零5分在上海的虹橋機(jī)場接你。

(23*2+10=56個(gè)半角字符)你的妻子將于明天晚上6點(diǎn)零5分在虹橋機(jī)場接你

(20*2+2=42個(gè)半角字符）

Helen將于明晚6點(diǎn)在虹橋接你

(10*2+6=26個(gè)半角字符）9.1引言6圖像信息冗余數(shù)字化后的圖像信息數(shù)據(jù)量非常大，圖像壓縮利用圖像數(shù)據(jù)存在冗余信息，去掉這些冗余信息后可以有效壓縮圖像。常見圖像的冗余類型主要表現(xiàn)在：空間冗余時(shí)間冗余視覺冗余9.1引言7空間冗余一幅圖像表面上各采樣點(diǎn)的顏色之間往往存在著空間連貫性。圖像內(nèi)部相鄰像素之間的相關(guān)性所造成的冗余。

1

2

3

4這是一幅2*2的圖像，圖像的第一個(gè)像素是紅的，第二個(gè)像素是紅的，第三個(gè)像素是紅的，第四個(gè)像素是紅的。這是一幅2*2的圖像，整幅圖都是紅色的。9.1引言8時(shí)間冗余視頻圖像不同幀之間的相關(guān)性所造成的冗余，運(yùn)動(dòng)圖像相鄰幀往往包含相同的背景和移動(dòng)物體，只不過移動(dòng)物體所在的空間位置略有不同，所以后一幀的數(shù)據(jù)與前一幀的數(shù)據(jù)有許多共同之處，稱為時(shí)間冗余。9.1引言9視覺冗余人眼不能感知或不敏感的那部分圖像信息，人類視覺系統(tǒng)對圖像的敏感度是非均勻的。但是，在記錄原始的圖像數(shù)據(jù)時(shí)，通常假定視覺系統(tǒng)是近似線性的和均勻的，對視覺敏感和不敏，感的部分同等對待，從而產(chǎn)生視覺冗余。9.1引言10舉例(248,27,4)(251,32,15)(248,27,4)(248,27,4)33K15K9.1引言11其他的冗余還有：結(jié)構(gòu)冗余：圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。知識冗余：有些圖像中還包含與某些先驗(yàn)知識有關(guān)的信息。圖像編碼的目的就是盡量減小各種冗余信息，特別是空間冗余、視覺冗余，以少的比特?cái)?shù)來表示圖像。9.1引言12數(shù)據(jù)壓縮技術(shù)的理論基礎(chǔ)是信息論從信息論的角度來看，壓縮就是去掉信息中的冗余，即保留不確定的信息，去掉確定的信息（可推知的）。9.1引言9.1.2信息量和信息熵信息論中信源編碼理論解決的主要問題：（2）數(shù)據(jù)壓縮的基本途徑（1）數(shù)據(jù)壓縮的理論極限13信息量等于數(shù)據(jù)量與冗余量之差I(lǐng)=D-du數(shù)據(jù)是用來記錄和傳送信息的，或者說數(shù)據(jù)是信息的載體。信息量與數(shù)據(jù)量的關(guān)系：du—冗余量I—信息量D—數(shù)據(jù)量真正有用的不是數(shù)據(jù)本身，而是數(shù)據(jù)所攜帶的信息。9.1引言14在日常生活中，極少發(fā)生的事件一旦發(fā)生是容易引起人們關(guān)注的，而司空見慣的事不會引起注意，也就是說，極少見的事件所帶來的信息量多。如果用統(tǒng)計(jì)學(xué)的術(shù)語來描述，就是出現(xiàn)概率小的事件信息量多。比如，搶劫銀行事件所帶來的信息量要比單車被盜事件的信息量大得多。因此，事件出現(xiàn)的概率越小，信息量越大。即信息量的多少是與事件發(fā)生頻繁（即概率大小）成反比。信息量的度量9.1引言15信息量En=log2(Pn-1)=-log2(Pn)即表示該符號所需的位數(shù)考慮用0和1組成的二進(jìn)制數(shù)碼為含有n個(gè)符號的某條消息編碼。假設(shè)符號Fn在整條消息中重復(fù)出現(xiàn)的概率為Pn，則該符號的信息量概率Pn即是指某事件在一次實(shí)驗(yàn)中發(fā)生的可能性的大小。信息量的計(jì)算公式被確定為事件發(fā)生概率的倒數(shù)的對數(shù)。即概率越大的事件，信息量就越少，反之，則越多。9.1引言16信息熵Entropy信息熵就是平均信息量大多數(shù)情況下，研究一個(gè)單獨(dú)的事件發(fā)生的信息量是不夠的，還應(yīng)該了解一系列事情整體的性質(zhì)，也就是整體平均信息量，或稱為信息熵。9.1引言pj

每個(gè)信息出現(xiàn)的概率17輸入字符串：aabbaccbaaa、b、c出現(xiàn)的概率分別為0.5、0.3和0.2，他們的信息量分別為：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322總信息量也即表達(dá)整個(gè)字符串需要的位數(shù)為：E=Ea*5+Eb*3+Ec*2=14.855位舉例說明：如果用二進(jìn)制等長編碼,需要多少位?20位9.1引言18平均碼長與信息熵如果對字符aj的編碼長度為Lj，則信號L的平均碼長為：m:信號中所出現(xiàn)不同字符的個(gè)數(shù)。9.1引言19平均碼長≈H(X)(稍大于H(X))：平均碼長>>H(X)：平均碼長<H(X)：熵值是平均碼長的下限

有冗余，不是最佳；不可能是最佳編碼9.1引言20符號S1S2S3S4出現(xiàn)概率1/21/41/81/8該數(shù)據(jù)流的信息熵及相應(yīng)編碼方式的平均碼長?舉例：輸入數(shù)據(jù)流：S1S2S1S3S2S1S1S4等長編碼00011011霍夫曼010110111H(X)=1.75L1=2L2=1.759.1引言21數(shù)據(jù)壓縮的理論極限是信息熵。只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。數(shù)據(jù)壓縮的基本途徑之一：使各字符的編碼長度盡量等于字符的信息量。9.1引言22一個(gè)典型的信號壓縮系統(tǒng)如圖所示：通過時(shí)間軸上采樣和幅度量化將連續(xù)信號變成離散數(shù)字信號。將信號中絕大部分能量集中在少數(shù)幾個(gè)變換系數(shù)上，去除信號中的相關(guān)性。信號壓縮真正體現(xiàn)在量化階段。一般先是游程編碼，然后Huffman編碼或算術(shù)編碼進(jìn)一步提高壓縮比。9.1引言23圖像壓縮編碼分類：根據(jù)時(shí)間第一代壓縮編碼八十年代以前，主要是根據(jù)傳統(tǒng)的信源編碼方法。9.1引言像素編碼變換編碼預(yù)測編碼位平面編碼增量調(diào)制熵編碼算術(shù)編碼DCT變換DPCM調(diào)制第一代壓縮編碼其他編碼行程編碼24第二代壓縮編碼八十年代以后，突破信源編碼理論，結(jié)合分形、模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分利用視覺系統(tǒng)生理心理特性和圖像信源的各種特性。子帶編碼模型編碼分層編碼分型編碼第二代壓縮編碼9.1引言25根據(jù)編碼原理：熵編碼：無損編碼，給出現(xiàn)概率較大的符號賦予一個(gè)短碼字，而給出現(xiàn)概率較小的符號賦予一個(gè)長碼字，從而使得最終的平均碼長很小。預(yù)測編碼：基于圖像數(shù)據(jù)的空間或時(shí)間冗余特性，用相鄰的已知像素（或像素塊）來預(yù)測當(dāng)前像素（或像素塊）的取值，然后再對預(yù)測誤差進(jìn)行量化和編碼。變換編碼：將空間域上的圖像變換到另一變換域上，變換后圖像的大部分能量只集中到少數(shù)幾個(gè)變換系數(shù)上，采用適當(dāng)?shù)牧炕挽鼐幋a就可以有效地壓縮圖像。9.1引言26無損編碼重構(gòu)圖像與原圖像完全一樣。對原始信號的準(zhǔn)確程度要求高的場合。在醫(yī)療或商業(yè)文件的歸檔，有損壓縮因?yàn)榉稍蚨唤埂Ｐl(wèi)星成像的收集，考慮數(shù)據(jù)使用和所花費(fèi)用，不希望有任何數(shù)據(jù)損失。X光拍片，信息的丟失會導(dǎo)致診斷的正確性。減少像素間冗余減少編碼冗余9.1引言27無損編碼霍夫（Huffman）編碼其它變長編碼算術(shù)編碼LZW編碼位平面編碼無損預(yù)測編碼9.1引言28有損編碼解碼后重新構(gòu)造的圖像與原始圖像存在不同。利用心理冗余和空間冗余。容易取得較好的壓縮比。9.1引言29圖像編碼評價(jià)評價(jià)圖像壓縮算法的優(yōu)劣主要有以下4個(gè)參數(shù)：

1）算法的編碼效率

2）編碼圖像的質(zhì)量

3）算法的適用范圍

4）算法的復(fù)雜度9.1引言30第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼56319.2.1哈夫曼編碼9.2.2香農(nóng)-范諾編碼9.2.3行程編碼9.2.4輪廓編碼9.2.5位平面編碼9.2.6LZW編碼9.2.7算術(shù)編碼9.2無損編碼32先統(tǒng)計(jì)數(shù)據(jù)中各字符出現(xiàn)的概率，再按字符出現(xiàn)頻率高低的順序分別賦以由短到長的代碼，從而保證文件整體的大部分字符是由較短的編碼所構(gòu)成。哈夫曼（Huffman）編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。即使在今天，在許多知名的壓縮工具和壓縮算法里（如WinZip、gzip和JPEG），也都有HuffmanCoding的身影。編碼思想9.2無損編碼9.2.1Huffman編碼33將信源符號按概率遞增順序排列；將兩個(gè)最小的概率加起來作為新符號的概率；并保證每層節(jié)點(diǎn)左小，右大；重復(fù)步驟①和②，直到概率和等于1；完成上述步驟后沿路徑返回進(jìn)行編碼。尋找從每一信源符號到概率為1處的路徑，每層有兩個(gè)分支，左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。編碼從根節(jié)點(diǎn)開始到葉子節(jié)點(diǎn)得到每個(gè)符號的編碼。9.2無損編碼編碼過程9.2.1Huffman編碼343010402020402002020303020402040灰度值：010203040出現(xiàn)頻率：1/161/167/163/164/169.2無損編碼9.2.1Huffman編碼統(tǒng)計(jì)出每級灰度出現(xiàn)的頻率：35灰度值：010304020出現(xiàn)頻率：1/161/163/164/167/1630104020204020020203030204020409.2無損編碼9.2.1Huffman編碼從左到右把上述頻率按從小到大的順序排列。36選出頻率最小的兩個(gè)值（1/16，1/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和2/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：1/161/162/169.2無損編碼9.2.1Huffman編碼灰度值：010304020出現(xiàn)頻率：1/161/163/164/167/162/163/164/167/1637選出頻率最小的兩個(gè)值（2/16，3/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和5/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：

1/161/162/163/165/162/16

3/164/167/16

4/165/167/169.2無損編碼9.2.1Huffman編碼38選出頻率最小的兩個(gè)值（4/16，5/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)將頻率和9/16作為它們的根節(jié)點(diǎn),新的根節(jié)點(diǎn)再參與其它頻率排序：1/161/162/163/165/164/169/16

4/165/167/167/169/169.2無損編碼9.2.1Huffman編碼39最后兩個(gè)頻率值（7/16，9/16）作為二叉樹的兩個(gè)葉子節(jié)點(diǎn)，將頻率和1作為它們的根節(jié)點(diǎn)。1/161/162/163/165/164/169/167/1617/16

9/169.2無損編碼9.2.1Huffman編碼403010402020402002020303020402040分配碼字。將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0,1序列串起來，就得到了各級灰度的編碼.01003014002001110灰度值：010304020出現(xiàn)頻率：1/161/163/164/167/169.2無損編碼9.2.1Huffman編碼41各灰度的編碼如下：

灰度值：

204030100哈夫曼編碼：01011111011100則圖所示的圖像哈夫曼編碼為：11111010100101100000111111010100共用了32比特，原圖像占128比特，壓縮比較高。0100301400200111030104020204020020203030204020409.2無損編碼9.2.1Huffman編碼42常用的且有效的方法是將圖像分割成若干的小塊，對每塊進(jìn)行獨(dú)立的Huffman編碼。8*8分塊的編碼效率為47.27%16*16分塊的編碼效率約為61%9.2無損編碼9.2.1Huffman編碼43假設(shè)某個(gè)字符的出現(xiàn)概率為80%，該字符只需要-log2(0.8)=0.322位編碼，但Huffman編碼一定會為其分配一位0

或一位1

的編碼。由此可得知，整個(gè)信息的80%在壓縮后幾乎相當(dāng)于理想長度的3倍左右。存在問題分析：編碼中每個(gè)符號的編碼長度只能為整數(shù)，如果源符號集的概率分布不是2的負(fù)n次方的形式，則無法達(dá)到熵極限。為可變長度碼,譯碼復(fù)雜。需要事先知道輸入符號集的概率分布。編碼效率高只在圖像灰度分布不均勻的時(shí)候?；舴蚵幋a的局限性：9.2無損編碼9.2.1Huffman編碼44香農(nóng)-范諾編碼的理論基礎(chǔ)是符號的碼字長度Ni完全由該符號出現(xiàn)的概率來決定，即：式中，D為編碼所用的數(shù)制。香農(nóng)－范諾編碼與Huffman編碼相反，采用從上到下的方法。在理想意義上，它與哈夫曼編碼一樣，并未實(shí)現(xiàn)碼詞（codeword）長度的最低預(yù)期；然而，與哈夫曼編碼不同的是，它確保了所有的碼詞長度在一個(gè)理想的理論范圍。9.2無損編碼9.2.2香農(nóng)-范諾編碼45首先將編碼字符集中的字符按照出現(xiàn)頻度和概率大小進(jìn)行排序。編碼（從根結(jié)點(diǎn)開始）。用遞歸的方法分成兩部分，使兩個(gè)部分的概率和接近于相等。給前一個(gè)子集合賦值為0，后面的賦值為1直至不可再分，即每一個(gè)葉子對應(yīng)一個(gè)字符。具體步驟：9.2.2香農(nóng)-范諾編碼9.2無損編碼46如：設(shè)一副灰度級為8的圖象中，各灰度所對應(yīng)的概率分別為0.04，0.05，0.06，0.07，0.10，0.10，0.18，0.40

現(xiàn)在對其進(jìn)行二分法香農(nóng)－范諾編碼。9.2.2香農(nóng)-范諾編碼9.2無損編碼47s0,s1,s2,s3,s4,s5,s6,s7s2,s3,s4,s5,s6,s7s0,s10.580.42s2,s3s4,s5,s6,s7s0s1s4,s5s6,s7s2s3s4s5s6s7s00.40s1s2s3s4s5s60.180.100.100.07s70.060.050.040.200.220.130.0901010101010101S0:00S1:01S2:100S3:101S4:1100S5:1101S6:1110S7:11119.2無損編碼48香農(nóng)－范諾編碼效率不如霍夫曼編碼。9.2.2香農(nóng)-范諾編碼9.2無損編碼編碼方案取決于分組方案的效果是否最佳，當(dāng)信源中消息的數(shù)量較多時(shí)，尋找最佳分方案將是一件費(fèi)力的事。49行程編碼又稱行程長度編碼（RunLengthEncoding，RLE)，是一種熵編碼，其編碼原理是將具有相同值的連續(xù)串用其串長和一個(gè)代表值來代替，該連續(xù)串就稱為行程，串長稱為行程長度。圖像中—行程：具有相同灰度值的像素序列。將一行中顏色值相同的相鄰象素（行程）用一個(gè)計(jì)數(shù)值（行程的長度）和該顏色值（行程的灰度）來代替，從而去除像素冗余。RLE編碼簡單直觀，編碼/解碼速度快，因此許多圖形、圖像和視頻文件，如.BMP、.TIFF及AVI等格式文件的壓縮均采用此方法。9.2無損編碼9.2.3行程編碼50定長行程編碼：編碼的行程長度所用的二進(jìn)制位數(shù)固定。變長行程編碼：不同范圍的行程長度用不同編碼位，需要增加標(biāo)志位來表明所使用的二進(jìn)制位數(shù)。問題？不知道各行程應(yīng)在何處分?jǐn)唷Ｏ旅娼榻B：二值圖變長行程編碼的一種方法。例1：aabbbcddddd的行程編碼為2a3b1c5d。9.2無損編碼9.2.3行程編碼513124911110010010011111001001001分?jǐn)啵孔冮L行程編碼：編碼規(guī)則

b+[(Code)2-1]可表示行程長度值編碼b？？編碼長度

1-40??35-810???59-16110????717-321110?????933-6411110??????1165-128111110???????13如：1100的編碼為：1100-1=1011（十進(jìn)制11）行程編碼為：11010119.2無損編碼9.2.3行程編碼52

0101101011011110100031249111100100100110101111100001011010110111101000還原方法：從符號串左端開始往右搜索，遇到第一個(gè)0時(shí)停下來，計(jì)算這個(gè)0的前面有幾個(gè)1。設(shè)1的個(gè)數(shù)為K，則在0后面讀K+2個(gè)符號，這K+2個(gè)符號所表示的二進(jìn)制數(shù)加上1的值就是第1個(gè)行程的長度。9.2無損編碼9.2.3行程編碼53開始搜索第一個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符10+01=11第二個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1011+0001=1100第三個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符11+01=100第四個(gè)0該0前1的個(gè)數(shù)為2讀2+2個(gè)字符1000+0001=1001第五個(gè)0該0前1的個(gè)數(shù)為0讀0+2個(gè)字符00+01=01(1)01011101101111100000000000009.2無損編碼9.2.3行程編碼1249111100100100154對于有大面積色塊的圖像，壓縮效果很好。對于紛雜的圖像，壓縮效果不好，最壞情況下（圖像中每兩個(gè)相鄰點(diǎn)的顏色都不同），會使數(shù)據(jù)量加倍，所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多，PCX文件算是其中之一。9.2無損編碼9.2.3行程編碼55二維行程編碼要解決的核心問題是：將二維排列的像素，采用某種方式轉(zhuǎn)化成一維排列的方式。之后按照一維行程編碼方式進(jìn)行編碼。兩種典型的二維行程編碼的排列方式。9.2無損編碼9.2.3行程編碼56數(shù)據(jù)量：64*8=512(bit)9.2無損編碼9.2.3行程編碼57如果按照方式(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，133，133；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程編碼為:規(guī)定行程碼長度為3bit數(shù)據(jù)量為:43*（3+8）=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），（4，133），（1，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），（2，127）9.2無損編碼58通常，為了達(dá)到比較好的壓縮效果，一般不單獨(dú)使用行程編碼，而是和其他編碼方法結(jié)合使用。如：在JPEG中，就綜合使用了行程編碼、DCT、量化編碼以及哈夫曼編碼。9.2無損編碼9.2.3行程編碼59任何編碼的技術(shù)的成功與否，最終取決于他與給定的圖像結(jié)構(gòu)匹配的如何。設(shè)計(jì)一個(gè)好的編碼器，首先是了解原始圖像的結(jié)構(gòu)，然后選擇一種適合哪種結(jié)構(gòu)的最佳編碼方法。在某些應(yīng)用中，原始圖像顯示出一些簡單的圖像結(jié)構(gòu)，如灰度級較少的氣象云圖，大幅人頭像等，邊界往往是感興趣的結(jié)構(gòu)特性。本節(jié)介紹的輪廓編碼就是針對這種圖形的編碼方法。9.2.4輪廓編碼（或等值線編碼）9.2無損編碼60編碼思想：一幅數(shù)字圖像的灰度級是有限的，我們可以把一幅數(shù)字圖像看做由和那多等灰度區(qū)所構(gòu)成的。如圖：其中每條等值線刻畫出一條等灰度區(qū)的邊界，如能將各個(gè)灰度去邊界的位置和灰度級進(jìn)行編碼、傳輸、在接收端就可以重現(xiàn)原始圖像；且因各個(gè)灰度區(qū)內(nèi)部的像素部可編碼，從而使數(shù)據(jù)得到大量的壓縮。關(guān)鍵：確定等值線的起點(diǎn)和移動(dòng)方向來編碼。9.2無損編碼9.2.4輪廓編碼（或等值線編碼）61IP例：左圖為圖像f(x,y)中的目標(biāo)區(qū)域，采用八方位碼。45671023八方位碼9.2無損編碼9.2.4輪廓編碼（或等值線編碼）則區(qū)域鏈碼0422412242614261716162一種能有效減少像素間冗余的技術(shù)，對相關(guān)性強(qiáng)的圖像，它的編碼效率比霍夫曼碼更高?；痉椒ǎ簩⒍嗉増D像（灰度圖像或彩色圖像）分解成一系列的二值圖像，然后對二值圖像應(yīng)用二值圖像編碼方法，以達(dá)到對多值圖像編碼的目的。位平面分解的兩種方法二值圖像位平面灰度編碼位平面9.2.5位平面編碼9.2無損編碼63設(shè)灰度圖像的灰度級需要m比特表示，那么任意一個(gè)灰度級g都可以表示成一個(gè)以2為底的多項(xiàng)式：（二進(jìn)制計(jì)算）其中ai=0/1，i=0,1,2,…,m-1圖像的同一個(gè)比特位的系數(shù)的集合就是一個(gè)二值圖像，稱為一個(gè)“位平面”。位平面編號從0開始，直到m-1。將m個(gè)位平面組合，顯然又可以恢復(fù)原來的灰度圖像。127（011111112）和128（100000002）二值圖像位平面分解：9.2無損編碼9.2.5位平面編碼6412810000000127011111110111111012501111101128127126125灰度級就差一位黑白很分明??！缺點(diǎn)：圖像在灰度級上稍有變化就會對位平面的復(fù)雜性產(chǎn)生顯著影響。9.2無損編碼9.2.5位平面編碼659.2無損編碼9.2.5位平面編碼二值圖像位平面二值圖像位平面灰度編碼位平面灰度編碼位平面66灰度編碼分解位平面為減少這種小灰度值變化的影響可用1個(gè)mbit的灰度碼來表示圖像?；叶却a（格雷碼）和二進(jìn)制碼的互相轉(zhuǎn)換可由右式計(jì)算：異或格雷碼的優(yōu)點(diǎn)：差值為1的兩個(gè)數(shù)值的格雷碼只有一位不同。127（01000000g）,128（11000000g），轉(zhuǎn)換后就只在第7個(gè)位平面有一個(gè)0到1的變化。127（011111112）128（100000002）m=89.2無損編碼9.2.5位平面編碼67灰度碼（格雷碼）128110000001270100000001000001125010000111281271261259.2無損編碼9.2.5位平面編碼68位平面分解方法總結(jié)低位面圖比高位面圖復(fù)雜，即低位面圖比高位面圖包括的細(xì)節(jié)要多，也更隨機(jī)?；叶染幋a表達(dá)的位面圖復(fù)雜度較低，但具有視覺意義信息的位面圖數(shù)量更多。圖形圖像或文本圖像。大量的是連續(xù)的白色背景，對這些連續(xù)的塊指定短碼字，可以達(dá)到壓縮的效果。9.2.5位平面編碼9.2無損編碼69利用了文本類圖像中空白較多的特點(diǎn)。將圖像的一行分成若干段，規(guī)定每段有k個(gè)象素；若k個(gè)象素全是空白，則用“0”表示；否則用“1”表示，后接直接編碼。例：不同的10個(gè)像素，它們相應(yīng)的代碼如下：10個(gè)象素 相應(yīng)的代碼0000000000 0000000000110000000001100000000111000000001當(dāng)k=10時(shí)，對大多數(shù)文本文件比較合適。9.2無損編碼9.2.6空白編碼70

9.2無損編碼9.2.6空白編碼擴(kuò)展到二維，是對圖像中大片的連續(xù)的1或0的區(qū)域（黑白塊）進(jìn)行識別編碼。設(shè)圖像被分解為若干塊，每一塊的大小一致，為a

b。這些塊只有三種類型：全白色、全黑色、混合區(qū)域。統(tǒng)計(jì)這三類區(qū)域的出現(xiàn)概率。碼字分配：出現(xiàn)概率最大的類型用1比特碼字“0”表示，其他的用2比特碼字“10”和“11”表示，后接對應(yīng)區(qū)域的直接編碼。71進(jìn)一步提高編碼效率的方法是使用迭代的方法將二值圖像分解為越來越小的塊，逐層進(jìn)行編碼。逐層編碼算法：純白色的圖像塊用1比特碼字“0”表示。其他類型圖像用1比特碼字“1”表示，并且對圖像進(jìn)行四等份分割，得到四個(gè)子塊。對每一個(gè)子塊重復(fù)過程(1)(2)，

一直到規(guī)定的最小子塊尺寸。圖像最小子塊采用原圖像信息的直接編碼。9.2無損編碼9.2.6空白編碼72LZW（Lempel-Ziv&Welch）編碼又稱字串表編碼，屬于一種無損編碼，LZW編碼與行程編碼類似，也是對字符串進(jìn)行編碼從而實(shí)現(xiàn)壓縮，但它在編碼的同時(shí)還生成了特定字符串以及與之對應(yīng)的索引字符串表。9.2無損編碼9.2.7LZW編碼73LZW壓縮使用字典庫查找方案。它讀入待壓縮的數(shù)據(jù)并與一個(gè)字典庫（庫開始是空的）中的字符串對比，如有匹配的字符串，則輸出該字符串?dāng)?shù)據(jù)在字典庫中的位置索引，否則將該字符串插入字典中。算法思想9.2無損編碼9.2.7LZW編碼74對LZW算法的分析：LZW算法的適用范圍是原始數(shù)據(jù)串最好是有大量的子串多次重復(fù)出現(xiàn)，重復(fù)的越多，壓縮效果越好。反之則越差，可能真的不減反增了。LZW壓縮技術(shù)對于可預(yù)測性不大的數(shù)據(jù)具有較好的處理效果，常用于GIF格式的圖像壓縮，其平均壓縮比在2:1以上，最高壓縮比可達(dá)到3:1。除了用于圖像數(shù)據(jù)處理以外，LZW壓縮技術(shù)還被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域。對于任意寬度和像素位長度的圖像，都具有穩(wěn)定的壓縮過程。壓縮和解壓縮速度較快。9.2無損編碼9.2.7LZW編碼75如果“否”，則輸出與當(dāng)前前綴S1相對應(yīng)的碼字；將S1＋S2添加到詞典中；步驟1：將詞典初始化為包含所有可能的單字字符，當(dāng)前前綴S1初始化為空。步驟2：當(dāng)前字符S2:=字符流中的下一個(gè)字符。LZW編碼算法9.2無損編碼9.2.7LZW編碼令S1:=S2，現(xiàn)在的S1僅包含一個(gè)字符S2步驟3：判斷S1＋S2是否在詞典中如果“是”，則用S2擴(kuò)展S1，即讓S1:=S1＋S2步驟4：判斷碼字流中是否還有碼字要譯如果“是”，就返回到步驟2；如果“否”把代表當(dāng)前前綴P的碼字輸出到碼字流；結(jié)束。76初始化字符串表字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5HLZW編碼實(shí)例aabcabbbbd

9.2無損編碼9.2.7LZW編碼77輸入數(shù)據(jù)S2S1+S2輸出結(jié)果S1生成的新字符串及索引NULLaabcabbbbdNULLNULLaaaaa0H0Habbccaababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abb<AH>bb<BH>bbd<CH>S1+S2在字符表中,S1=S1+S2aa不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2結(jié)果已存在,故輸出結(jié)果為空S1+S2在字符表中,S1=S1+S2此時(shí)已無輸入輸出S1的索引3H輸出LZW_EOI標(biāo)志的索引78HuffmanCoding并沒有徹底達(dá)到信息熵的極限，直觀上可以看做是由于限制了每個(gè)符號的編碼必須是整數(shù)位二進(jìn)制數(shù)所造成的。如果能夠采用不一定整數(shù)長度的編碼(

譬如0.112個(gè)0或0.555個(gè)1?)就使編碼的長度能夠真正朝信息熵極限逼近。二十多年前，天才數(shù)學(xué)家們用一種巧妙的思路完美地解決了這個(gè)問題--算術(shù)編碼。算術(shù)編碼繞過了用一個(gè)特定的代碼替代一個(gè)輸入符號的想法,用一個(gè)浮點(diǎn)輸出數(shù)值代替一個(gè)流的輸入符號,較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù)。信源符號概率接近時(shí),建議使用算術(shù)編碼,這種情況下其效率高于Huffman編碼。

9.2無損編碼9.2.8算術(shù)編碼79算術(shù)編碼有兩種模式：一種是基于信源概率統(tǒng)計(jì)特性的靜態(tài)算術(shù)編碼。另一種是針對未知信源概率模型的自適應(yīng)模式。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。

9.2無損編碼9.2.8算術(shù)編碼80用一個(gè)例子來說明一下固定算數(shù)編碼的過程：

待編碼的數(shù)據(jù)序列為“dacab”，那么我們規(guī)定信源中的符號取值范圍是{a,b,c,d},各符號出現(xiàn)的概率依次為：P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。初始時(shí)，取區(qū)間為[0，1]；這個(gè)區(qū)間內(nèi)我們認(rèn)為被a,b,c和d按各自概率劃分了，其中：a=［0,0.4）b=［0.4,0.6）c=［0.6,0.8）d=［0.8,1.0]9.2無損編碼9.2.8算術(shù)編碼81a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

首先讀入d：令初始間隔為［0.8,1.0)第二個(gè)輸入a：令新的間隔為StartN=0.8+0×(1.0-0.8)=0.8則“a”的實(shí)際編碼區(qū)間在［0.8,0.88)之間?！癮”的取值范圍應(yīng)在前一符號間隔［0.8,1.0)的［0,0.4)子區(qū)間內(nèi)EndN=0.8+0.4×(1.0-0.8)=0.88dacab9.2無損編碼82a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）輸入c：StartN=0.8+0.6×(0.88-0.8)=0.848“c”的取值范圍應(yīng)在前一符號間隔［0.8,0.88)的［0.6,0.8)子區(qū)間內(nèi)EndN=0.8+0.8×(0.88-0.8)=0.864“c”的實(shí)際編碼區(qū)間在［0.848,0.864)之間dacab9.2無損編碼StartN=StartB+LeftC×L

EndN=StartB+RightC×L

83輸入a：StartN=0.848+0×(0.864-0.848)=0.848“a”取值范圍應(yīng)在前一符號間隔［0.848,0.864)的［0,0.4)子區(qū)間內(nèi)EndN=0.848+0.4×(0.864-0.848)=0.8544“a”的實(shí)際編碼區(qū)間在［0.848,0.8544)之間dacab9.2無損編碼a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

84輸入b：StartN=0.848+0.4×(0.8544-0.848)=0.85056“b”取值范圍應(yīng)在前一符號間隔［0.848,0.8544)的［0.4,0.6)子區(qū)間內(nèi)EndN=0.848+0.6×(0.8544-0.848)=0.85184“b”的實(shí)際編碼區(qū)間在［0.85056,0.85184)之間9.2無損編碼dacaba=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

85數(shù)據(jù)序列“dacab”已被描述為一個(gè)實(shí)數(shù)區(qū)間［0.85056,0.85184］，在此區(qū)間內(nèi)的任一實(shí)數(shù)值都惟一對應(yīng)該數(shù)據(jù)序列。這樣，就可以用一個(gè)實(shí)數(shù)表示這一數(shù)據(jù)序列。把區(qū)間［0.85056,0.85184］用二進(jìn)制形式表示為［0.110110011011,0.110110100001］。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。9.2無損編碼9.2.8算術(shù)編碼860.110110100001–0.000000000001=0.110110100000》0.1101100110110.1101101位于這個(gè)區(qū)間內(nèi)并且其編碼最短，故把其作為數(shù)據(jù)序列“dacab”的編碼輸出。不考慮“0.”，把1101101作為本例中的數(shù)據(jù)序列的算術(shù)編碼。由此可見，數(shù)據(jù)序列“dacab”用7比特的二進(jìn)制代碼就可以表示，平均碼長為1.4比特／字符。解碼是編碼的逆過程。9.2無損編碼9.2.8算術(shù)編碼87第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼56889.3有損編碼有損壓縮編碼：通過犧牲圖像的準(zhǔn)確率來達(dá)到加大壓縮率的目的壓縮比：在圖像壓縮比大于30:1時(shí)，仍然能夠重構(gòu)圖像在圖像壓縮比為10:1到20:1時(shí)，重構(gòu)圖像與原圖幾乎沒有差別無損壓縮的壓縮比很少有能超過3:1的有損無損壓縮方法的根本差別在于有沒有量化模塊89源數(shù)據(jù)編碼與解碼的模型源數(shù)據(jù)編碼的模型源數(shù)據(jù)解碼的模型符號解碼器數(shù)據(jù)數(shù)據(jù)量化器符號編碼器9.3有損編碼90量化器基本思想：減少數(shù)據(jù)量的最簡單的辦法是將圖像量化成較少的灰度級，通過減少圖像的灰度級來實(shí)現(xiàn)圖像的壓縮。這種量化是不可逆的，因而解碼時(shí)圖像有損失。例：如果輸入是256個(gè)灰度級，對灰度級量化后輸出，只剩下4個(gè)層次，數(shù)據(jù)量被大大減少。sts1s2s3t1t2t39.3有損編碼91第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼5692主要內(nèi)容預(yù)測編碼原理無損預(yù)測編碼有損預(yù)測編碼DM有損預(yù)測編碼9.4預(yù)測編碼93利用視頻圖像幀間的相關(guān)性，即時(shí)間相關(guān)性，來達(dá)到圖像壓縮的目的，廣泛用于普通電視、會議電視、視頻電話、高清晰度電視的壓縮編碼。無損預(yù)測編碼有損預(yù)測編碼

9.4預(yù)測編碼9.4.1預(yù)測編碼原理94（1）系統(tǒng)組成：編碼器+解碼器（有相同的預(yù)測器）

9.4預(yù)測編碼9.4.2無損預(yù)測編碼第95頁（2）編碼過程：輸入序列：f1,…,fn-1

計(jì)算預(yù)測：（舍入成整數(shù)）計(jì)算預(yù)測差值：

差值編碼：在符號編碼器中用變長碼編產(chǎn)生壓縮數(shù)據(jù)流的下一個(gè)元素。

解碼預(yù)測，輸出序列：1,…,fn-1

獲得當(dāng)前幀：

哪里取得了壓縮？只傳輸預(yù)測與實(shí)際的差值9.4預(yù)測編碼第96頁

（3）幾種預(yù)測器

m階線性預(yù)測：

在1-D線性預(yù)測編碼中，設(shè)掃描沿行進(jìn)行，預(yù)測值可寫：

一階1-D線性預(yù)測：round是舍入函數(shù)，ai是預(yù)測系數(shù)9.4預(yù)測編碼第97頁9.4預(yù)測編碼（4）舉例對于輸入序列{10，15，20，15，10}采用一維線性編碼進(jìn)行無損預(yù)測編碼。預(yù)測值等于上一個(gè)像素的值f0=null編碼f1=10f2’=10f2=15e=5,解碼f1=10f2’=10f2=f2’+e=15編碼f2=15f3’=15f3=20e=5,解碼f2=15f3’=15f3=f3’+e=20編碼f3=20f4’=20f4=15e=-5,解碼f3=20f4’=20f4=f4’+e=15編碼f4=15f5’=15f5=10e=-5,解碼f4=15f5’=15f5=f5’+e=10第98頁

9.4.3有損預(yù)測編碼（LossyPredictiveCoding)增加了量化器，量化器插在符號編碼器和預(yù)測誤差產(chǎn)生處之間，且把原來無損編碼器中的整數(shù)舍入模塊吸收了進(jìn)來。它的作用是將預(yù)測誤差映射進(jìn)有限個(gè)輸出中。9.4預(yù)測編碼99算法的演變有損預(yù)測編碼的演變——引入量化：將en

用 編碼：

解碼：9.4預(yù)測編碼1009.4預(yù)測編碼9.4.4德爾塔調(diào)制(增量調(diào)制)DM(Deltamodulation) 預(yù)測器 量化器預(yù)測系數(shù)a≤

1，常數(shù)c>0101DM編碼示例a=1，C=6.5輸入序列：14,15,14,15,13,15,15,14,20,26,27,28,27,27,29,37,47,62,75,77,78,79,80,81,81,82,82102失真問題：1）顆粒噪聲：當(dāng)c遠(yuǎn)大于輸入中的最小變化時(shí)，如n＝1、n＝7等2）斜率過載：當(dāng)c遠(yuǎn)小于輸入中的最大變化時(shí)，如n＝14到n＝21輸入信號斜率大，量化跟不上：因?yàn)槊總€(gè)抽樣間隔內(nèi)只容許有一個(gè)量化電平的變化，所以當(dāng)輸入信號的斜率比抽樣周期決定的固定斜率大時(shí)。9.4預(yù)測編碼103第九章圖像壓縮編碼引言無損編碼213有損編碼4預(yù)測編碼

變換編碼

混合編碼561049.5.1變換編碼（TransformCoding）系統(tǒng)圖像分解：減少變換的計(jì)算復(fù)雜度圖像變換：解除每個(gè)子圖像內(nèi)部像素之間的相關(guān)性，或者說將盡可能多的信息集中到盡可能少的變換系數(shù)上壓縮不是在變換中而是在量化變換系數(shù)時(shí)及編碼取得的9.5變換編碼第105頁子圖像尺寸選擇:影響變換編碼誤差和計(jì)算復(fù)雜度（壓縮量和計(jì)算復(fù)雜度都隨子圖像尺寸的增加而增加）兩個(gè)條件： ①相鄰子圖像之間的相關(guān)（冗余）減少到某個(gè)可接受的水平；②子圖像的長和寬都是2的整數(shù)次冪最常用的子圖像尺寸：8

8和16

169.5變換編碼106變換編碼重建誤差與子圖像尺寸的關(guān)系:9.5變換編碼第107頁原理：根據(jù)傅立葉變換的性質(zhì)，如果變換函數(shù)是一個(gè)連續(xù)的實(shí)偶函數(shù)，既存在f(x)=f(-x)時(shí)，則有下面結(jié)果：變換后只含有余弦項(xiàng)。故稱為余弦變換。因?yàn)橛嘞液瘮?shù)是偶函數(shù)，所以變換后的頻率函數(shù)也是偶函數(shù)。如果把離散序列拓展成某種偶對稱函數(shù)，那么他的離散傅里葉變換也就只包含余弦項(xiàng)了。9.5變換編碼9.5.2一維DCT的變換108

定義如下：設(shè){f(x)|x=0,1,…,N-1}為離散的信號列。式中，u,x=0,1,2,…,N－1。令9.5變換編碼109分開表示：式中F(u)是第u個(gè)余弦變換系數(shù)，u是廣義頻率變量，u=1,2,…,N-1；f(x)是時(shí)域N點(diǎn)序列x=0,1,2,…,N-1。

9.5變換編碼110將變換式展開整理后，可以寫成矩陣的形式，即F=Gf其中9.5變換編碼111舉例：如果令N=4，由一維解析式定義可得如下展開式：寫成矩陣形式：[F(u)]=[G][f(x)]G=9.5變換編碼112

一維DCT的逆變換IDCT定義為式中，

x,u=0,1,2,…,N－1?？梢娨痪SDCT的逆變換核與正變換核是相同的。9.5變換編碼113N=4，可得到反變換展開形式：寫成矩陣形式：[f(x)]=[A]T[F(u)]9.5變換編碼1149.5.3二維離散余弦變換式中，C(u)和C(v)的定義同前面；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。二維DCT定義如下：設(shè)f(x,y)為M×N的數(shù)字圖像矩陣，則9.5變換編碼115二維DCT逆變換定義如下：式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。9.5變換編碼116式中：C(x)和C(y)的定義同前；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。9.5變換編碼同時(shí)，由上面的兩個(gè)式子可知二維DCT的逆變換核與正變換核相同，且是可分離的，即117類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下：F=GfGT9.5變換編碼第118頁

余弦變換的物理意義：先將整體圖像分成N×N像素塊,然后對N×N像素塊逐一進(jìn)行DCT變換其中N是像塊的水平、垂直像素?cái)?shù)，一般取N=8。N大于8時(shí)效率增加不多而