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

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

變換編碼

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

變換編碼

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

文字+語音圖像+文字+語音通信對(duì)象的改變

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

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

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

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

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

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

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

1

2

3

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

每個(gè)信息出現(xiàn)的概率輸入字符串：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)制等長(zhǎng)編碼,需要多少位?20位9.1引言平均碼長(zhǎng)與信息熵如果對(duì)字符aj的編碼長(zhǎng)度為L(zhǎng)j，則信號(hào)L的平均碼長(zhǎng)為：m:信號(hào)中所出現(xiàn)不同字符的個(gè)數(shù)。9.1引言平均碼長(zhǎng)≈H(X)(稍大于H(X))：平均碼長(zhǎng)>>H(X)：平均碼長(zhǎng)<H(X)：熵值是平均碼長(zhǎng)的下限

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

1）算法的編碼效率

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

3）算法的適用范圍

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

變換編碼

混合編碼569.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無損編碼先統(tǒng)計(jì)數(shù)據(jù)中各字符出現(xiàn)的概率，再按字符出現(xiàn)頻率高低的順序分別賦以由短到長(zhǎng)的代碼，從而保證文件整體的大部分字符是由較短的編碼所構(gòu)成。哈夫曼（Huffman）編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。即使在今天，在許多知名的壓縮工具和壓縮算法里（如WinZip、gzip和JPEG），也都有HuffmanCoding的身影。編碼思想9.2無損編碼9.2.1Huffman編碼將信源符號(hào)按概率遞增順序排列；將兩個(gè)最小的概率加起來作為新符號(hào)的概率；并保證每層節(jié)點(diǎn)左小，右大；重復(fù)步驟①和②，直到概率和等于1；完成上述步驟后沿路徑返回進(jìn)行編碼。尋找從每一信源符號(hào)到概率為1處的路徑，每層有兩個(gè)分支，左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。編碼從根節(jié)點(diǎn)開始到葉子節(jié)點(diǎn)得到每個(gè)符號(hào)的編碼。9.2無損編碼編碼過程9.2.1Huffman編碼3010402020402002020303020402040灰度值：010203040出現(xiàn)頻率：1/161/167/163/164/169.2無損編碼9.2.1Huffman編碼統(tǒng)計(jì)出每級(jí)灰度出現(xiàn)的頻率：灰度值：010304020出現(xiàn)頻率：1/161/163/164/167/1630104020204020020203030204020409.2無損編碼9.2.1Huffman編碼從左到右把上述頻率按從小到大的順序排列。選出頻率最小的兩個(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/16選出頻率最小的兩個(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編碼選出頻率最小的兩個(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編碼最后兩個(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編碼3010402020402002020303020402040分配碼字。將形成的二叉樹的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0,1序列串起來，就得到了各級(jí)灰度的編碼.01003014002001110灰度值：010304020出現(xiàn)頻率：1/161/163/164/167/169.2無損編碼9.2.1Huffman編碼各灰度的編碼如下：

灰度值：

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

或一位1

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

現(xiàn)在對(duì)其進(jìn)行二分法香農(nóng)－范諾編碼。9.2.2香農(nóng)-范諾編碼9.2無損編碼s0,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無損編碼香農(nóng)－范諾編碼效率不如霍夫曼編碼。9.2.2香農(nóng)-范諾編碼9.2無損編碼編碼方案取決于分組方案的效果是否最佳，當(dāng)信源中消息的數(shù)量較多時(shí)，尋找最佳分方案將是一件費(fèi)力的事。行程編碼又稱行程長(zhǎng)度編碼（RunLengthEncoding，RLE)，是一種熵編碼，其編碼原理是將具有相同值的連續(xù)串用其串長(zhǎng)和一個(gè)代表值來代替，該連續(xù)串就稱為行程，串長(zhǎng)稱為行程長(zhǎng)度。圖像中—行程：具有相同灰度值的像素序列。將一行中顏色值相同的相鄰象素（行程）用一個(gè)計(jì)數(shù)值（行程的長(zhǎng)度）和該顏色值（行程的灰度）來代替，從而去除像素冗余。RLE編碼簡(jiǎn)單直觀，編碼/解碼速度快，因此許多圖形、圖像和視頻文件，如.BMP、.TIFF及AVI等格式文件的壓縮均采用此方法。9.2無損編碼9.2.3行程編碼定長(zhǎng)行程編碼：編碼的行程長(zhǎng)度所用的二進(jìn)制位數(shù)固定。變長(zhǎng)行程編碼：不同范圍的行程長(zhǎng)度用不同編碼位，需要增加標(biāo)志位來表明所使用的二進(jìn)制位數(shù)。問題？不知道各行程應(yīng)在何處分?jǐn)?。下面介紹：二值圖變長(zhǎng)行程編碼的一種方法。例1：aabbbcddddd的行程編碼為2a3b1c5d。9.2無損編碼9.2.3行程編碼3124911110010010011111001001001分?jǐn)啵孔冮L(zhǎng)行程編碼：編碼規(guī)則

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

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行程編碼

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

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

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

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

9.2無損編碼9.2.7LZW編碼輸入數(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)志的索引HuffmanCoding并沒有徹底達(dá)到信息熵的極限，直觀上可以看做是由于限制了每個(gè)符號(hào)的編碼必須是整數(shù)位二進(jìn)制數(shù)所造成的。如果能夠采用不一定整數(shù)長(zhǎng)度的編碼(

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

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

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

待編碼的數(shù)據(jù)序列為“dacab”，那么我們規(guī)定信源中的符號(hào)取值范圍是{a,b,c,d},各符號(hào)出現(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ù)編碼a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）Sta