Lecture15

ImageCodingand

CompressionPurpose

圖像壓縮的概念、目的和意義圖像的霍夫曼編碼、香農編碼、算術編碼、行程編碼方法ExplainContents

了解圖像壓縮的目的和意義，熟悉圖像保真度準則掌握圖像霍夫曼編碼、香農編碼、算術編碼、行程編碼方法

圖像壓縮(ImageCompression)的概念

數據壓縮的研究內容包括數據的表示、傳輸、變換和編碼方法，目的是減少存儲數據所需的空間和傳輸所用的時間。

圖像壓縮就是在一個可以接受的還原狀況的前提下用盡可能少的比特數來表示源信號，即把需要存儲或傳輸的圖像數據的比特數減少到最少程度。圖像壓縮是通過編碼實現的。

概述

圖像數據壓縮的必要性

圖像數據的特點之一是信息量大。海量數據需要巨大的存儲空間。如多媒體中的海量圖像數據，不進行編碼壓縮處理，一張600M字節的光盤，只能存放20秒左右的640×480像素的圖像。沒有編碼壓縮，多媒體信息保存有多么困難是可想而知的。在現代通信中，圖像傳輸已成為重要內容之一。采用編碼壓縮技術，減少傳輸數據量，是提高通信速度的重要手段。可見，沒有圖像編碼與壓縮技術的發展，大容量圖像信息的存儲與傳輸是難以實現的，多媒體、信息高速公路等新技術在實際中的應用會遇到很大困難。概述

圖像數據壓縮的可能性概述

從信息論觀點看，描述圖像信源的數據由有用數據和冗余數據兩部分組成。信息量數據量冗余量

冗余量是可以壓縮的，在實際應用中應盡量保證去除冗余量而不會減少信息量，即壓縮數據在一定條件可以近似恢復。數據冗余(DataRedundancy)

編碼冗余(CodingRedundancy)等長編碼平均碼長為3變長編碼平均碼長為2.7數據冗余

像素間冗余(InterpixelRedundancy)

圖像是由按一定規則排列起來的像素組成，圖像中相鄰像素的灰度往往相同或相近，這就稱為像素間冗余或空間冗余。數據冗余

心理視覺冗余(PsychovisualRedundancy)175K1.46M

受生理和心理上的影響，人眼對黑白和彩色信息的分辨率是有限的。光學上不一致的圖像在視覺上可能是一樣。圖像壓縮系統模型信源信源編碼器信道編碼器通信線路或存儲介質信源解碼器信道解碼器信宿壓縮的有效性編碼的可靠性圖像保真度準則描述解碼圖像相對原始圖像偏離程度的測度一般稱為保真度。常用的保真度準則可分為兩大類：客觀保真度準則和主觀保真度準則。客觀保真度準則最常用的客觀保真度準則是原圖像和解碼圖像之間的均方根誤差和均方根信噪比兩種。主觀保真度準則

很多解壓圖最終是供人觀看的，一種常用的方法是讓一組（不少于20人）觀察者觀察圖像并給該圖像評分，將他們對該圖像的評分取平均，作為這幅圖像的質量。信息論要素(ElementsofInformationTheory)

熵(Entropy)根據Shannon無干擾信息保持編碼定理，若對原始圖像數據的信息進行無失真圖像編碼，壓縮后平均碼長存在一個下限，這個下限是圖像信息熵H。理論上最佳信息保持編碼的平均碼長可以無限接近圖像信息熵H。但總是大于或等于圖像的熵H。

平均碼長(AverageCodeLength)平均信息量度，圖像中各灰度級比特數的統計平均值。M:灰度級數Pk:灰度級Wk出現的概率

編碼效率CodingEfficiency

冗余度Redundancy熵編碼目的：使R盡量減少至H

信息論要素(ElementsofInformationTheory)例題設一離散信源如下：

信源概率編碼求信源X的熵、平均碼長和編碼效率。解：

比特平均碼長：編碼效率：比特

變長最佳編碼定理

對概率大的消息符號賦予短碼字，而對概率小的信息符號賦予長碼字，則編碼的平均碼長一定最短。

如：WmWnPm<PnPm：概率低Pn：概率高

tm>tntm：長碼tn：短碼符合定理的平均碼長不符合定理的平均碼長

唯一可譯編碼

所編碼字序列能唯一地譯出來。單義性、非續長碼是唯一可譯編碼。單義性代碼：任意一個有限長的碼字序列只能被唯一地分割成一個個碼字。非續長代碼：集合中的碼字不能由其他碼字在后面添加碼元構成。如：信源概率碼I碼II碼III碼IVW11/20000W21/4011001W31/8100110011W41/810111110111碼I：非單義性、續長碼如：00110W1W2W3W4W1W1W3W3W1W1W1W3W3W2碼II：非單義性、續長碼如：

010011W1W2W3W4W1W2W1W1W4

W1W2W1W3W2W2W1W2W1W1W2W2碼III：單義性、非續長碼如：010110111W1W2W3W4碼IV：單義性、續長碼如：0010110111W1W2W3W4單義非續長代碼平均碼長最短單義代碼的充要條件：

D：代碼中的碼元種類；n：代碼中的碼字個數；ti：第i個碼字的碼長；如上例：圖像編碼壓縮的分類圖像壓縮無損編碼有損編碼霍夫曼編碼行程編碼算術編碼預測編碼變換編碼其它編碼根據解壓重建后的圖像和原始圖像之間是否具有誤差，圖像編碼壓縮分為無損（亦稱無失真、無誤差、信息保持）編碼和有損（有失真或有誤差）編碼兩大類。Huffman編碼是1952年由Huffman提出的一種編碼方法。這種編碼方法是根據信源數據符號發生的概率進行編碼的。霍夫曼編碼(HuffmanCoding)思想：在信源數據中出現概率越大的符號，編碼以后相應的碼長越短；出現概率越小的符號，其碼長越長，從而達到用盡可能少的碼符表示信源數據。它在無損變長編碼方法中是最佳的。把輸入符號按出現的概率從大到小排列起來,接著把概率最小的兩個符號的概率求和;把它（概率之和）同其余符號概率由大到小排序,然后把兩個最小概率求和;重復2,直到最后只剩下兩個概率為止。在上述工作完畢之后，從最后兩個概率開始逐步向前進行編碼。對于概率大的消息賦予0，小的賦予1。在反向進行的過程中，若概率不變，保留原碼字；若概率分裂為兩個，前幾位保留原碼字，最后一位一個賦“0”，另一個賦“1”碼。

編碼方法：符號集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman編碼符號集經排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.08符號集經排序的概率分布第一次合并后排序第二次合并后排序第三次合并后排序第四次合并后排序第五次合并后排序x10.400.400.400.400.601x20.200.200.230.370.40x30.120.170.200.23x40.110.120.17x50.090.11x60.0801100010100000111100000000101001101001100100011符號集x1x2x3x4x5x6概率分布0.400.200.120.110.090.08Huffman編碼100001001100100011

用二叉樹方法實現Huffman編碼方法也較為便利。

計算該信源的熵、編碼后的平均碼長，并思考對于同一圖像采用Huffman編碼，編碼是否唯一？？0.230.4

x10.6

0.11

x4

10

100.37

0.20

x2

0.08

x60.09

x50.17

10

10

100.12

x3香農編碼(ShannonCoding)編碼方法：1、將輸入灰度級按出現的概率由大到小排列；2、按計算各概率對應的碼長；3、計算各灰度級對應的累加概率：

4、把各個累加概率由十進制數轉換成二進制數：轉換規則：乘2取整，先取的整數為高位，后取的整數為低位。5、將二進制表示的累加概率去掉多于ti的尾數，即得Wi對應的碼字。算術編碼(ArithmeticCoding)思想：

按照符號序列的出現概率區間分割，用一個實數代表一個數據流的輸入符號，再將這個實數轉化為一定位數的二進制代碼。對于較長的消息，二進制代碼的位數也會增加。它們是通過算術運算逐步形成碼字的，因而得名。

設四階Markov信源符號集為｛a,b,c,d｝，其概率分布為｛0.2,0.2,0.4,0.2｝。（1）若對該信源進行Huffman編碼，可得其平均碼長為2.0比特/字符（2）若信源發出序列為｛b,c,a,c,d｝，算數編碼過程如下：各個數據符號在半封閉實數區間[0，1）內按概率進行賦值范圍設定為數據流bcacd編碼區間[0.2,0.4）[0.28,0.36）[0.28,0.296）[0.2864,0.2928）[0.29152,0.2928）區間長度0.20.080.0160.00640.00128新子區間左端＝前一子區間左端＋新子區間左邊累加概率×前子區間長度新子區間長度＝當前區間概率×前子區間長度行程編碼(Run-