第10章圖像編碼

10.1.1圖像壓縮的必要性

在數(shù)字圖像的處理中，圖像數(shù)據已成為多媒體信息中最重要的組成部分，其編碼壓縮技術受到人們的普遍關注。是一種數(shù)據量很大的信息源。例如，保存一幅色的圖像需要的存儲空間為，假設每秒傳送32幅同樣大小的圖像，那么每秒需要保存的圖像數(shù)據就為，如果要用1G的u盤保存這種視頻的話，也只能保存32秒。如果能將上述圖像信號壓縮幾倍、十幾倍，甚至上百倍，將十分有利于圖像的傳輸和存儲。10.1.2圖像壓縮的可能性

雖然數(shù)字圖像的數(shù)據量巨大，但圖像數(shù)據是高度相關的。一幅圖像的內部相鄰象素之間，相鄰行之間的視頻序列中相鄰圖像之間有大量冗余信息，這些冗余信息包括以下幾種：（1）空間冗余，即圖像內部相鄰像素之間存在較強的相關性所造成的冗余；（2）時間冗余，即視頻圖像序列中的不同幀之間的相關性所造成的冗余，（3）視覺冗余，即指人眼不能感知或不敏感的那部分圖像信息；（4）信息熵冗余，也稱編碼冗余，即如果圖像中平均每個像素使用的比特數(shù)大于該圖像的信息熵，則圖像中存在冗余；（5）結構冗余，即圖像中存在很強的紋理結構或自相似性；（6）知識冗余，即在有些圖像中還包含與某些先驗知識有關的信息。圖像數(shù)據的這些冗余信息為圖像壓縮編碼提供了依據。

10.1.3圖像壓縮的技術指標

（1）圖像熵與平均碼長圖像熵是指圖像含有的平均信息量。若一幅圖像共有種灰度，某一種灰度用表示，其中，且出現(xiàn)的概率為，則圖像熵定義為：

1當N種灰度出現(xiàn)的概率相等時，圖像熵取得最大值；2當=1時，H(x)=0，這說明常值圖像的熵為零，常值圖像的信息量為零；3圖像的熵非負，即。編碼后的平均碼字長度稱平均碼長，是碼字長度的數(shù)學期望，即（10-1-2）圖像熵和平均碼長的單位都是比特/字符。根據香農的信息保持編碼定理，要保持信源的全部信息就必須有（10-1-3）否則，在解壓縮時一定會產生圖像的失真。（2）編碼效率編碼效率可定義為（10-1-4）從式（10-1-4）可知，對于無失真編碼來說，平均碼長越接近圖像熵，編碼效率就越高。（3）壓縮比通常將壓縮比定義為壓縮前圖像的平均碼長與壓縮后的平均碼長之比，即（10-1-5）若，則值越大，壓縮效率越高。（4）壓縮后圖像的質量圖像質量評價可分為客觀質量評價和主觀質量評價。最常用的客觀質量評價指標是均方誤差（MSE）和峰值信噪比（PSNR），其定義如下：

(10-1-6)

(10-1-7)（5）算法的適用范圍特定的圖像編碼算法具有其相應的適用范圍，并不對所有圖像都有效。一般說來，大多數(shù)基于圖像信息統(tǒng)計特性的壓縮算法具有較廣的適用范圍，而一些特定的編碼算法的適用范圍較窄，如分形編碼主要用于自相似性高的圖像。（6）算法的復雜度算法的復雜度即指完成圖像壓縮和解壓縮所需的運算量和硬件實現(xiàn)該算法的難易程度。優(yōu)秀的壓縮算法要求有較高的壓縮比，壓縮和解壓縮快，算法簡單，易于硬件實現(xiàn)，還要求解壓縮后的圖像質量較好。選用編碼方法時一定要考慮圖像信源本身的統(tǒng)計特性、多媒體系統(tǒng)(硬件和軟件產品)的適應能力、應用環(huán)境以及技術標準。根據對壓縮編碼后的圖像進行重建的準確程度，可將常用的圖像編碼方法分為三類：（1）信息保持編碼：也稱無失真編碼，它要求在編解碼過程中保證圖像信息不丟失，從而可以完整地重建圖像，常用于醫(yī)學圖像編碼中。（2）保真度編碼：主要利用人眼的視覺特性，在允許的失真（Lossy）條件下或一定的保真度準則下，最大限度地壓縮圖像。保真度編碼可以實現(xiàn)較大的壓縮比，主要用于數(shù)字電視技術、靜止圖像通信、娛樂等方面。對于這些圖像，過高的空間分辨率和過多的灰度層次，不僅增加了數(shù)據量，而且人眼也接收不到。因此在編碼過程中，可以丟掉一些人眼不敏感的信息，在保證一定的視覺效果條件下提高壓縮比。（3）特征提?。涸趫D像識別、分析和分類等技術中，往往并不需要全部圖像信息，而只要對感興趣的部分特征信息進行編碼即可壓縮數(shù)據。根據編碼原理可以將圖像編碼分為熵編碼、預測編碼、變換編碼和混合編碼等。（1）熵編碼。熵編碼是純粹基于信號統(tǒng)計特性的編碼技術，是一種無損編碼。（2）預測編碼。預測編碼是根據離散信號之間存在著一定關聯(lián)性的特點，利用前面一個或多個信號預測下一個信號，然后對實際值和預測值的差（預測誤差）進行編碼。（3）變換編碼。變換編碼通常是將空間域上的圖像經過正交變換映射到另一變換域上，使變換后的系數(shù)之間的相關性降低。（4）混合編碼?；旌暇幋a是指綜合了熵編碼、變換編碼或預測編碼的編碼方法，如JPEG標準和MPEG標準。10.2編碼方法

哈夫曼編碼是一種一致性編碼方法，用于數(shù)據的無損耗壓縮，使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據每一個源字符出現(xiàn)的概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度降低，從而達到無損壓縮數(shù)據的目的）。這種方法是由David.A.Huffman發(fā)展起來的。哈夫曼編碼是可變字長編碼(VLC)的一種，是Huffman于1952年提出一種編碼方法，該方法完全依據字符出現(xiàn)概率來構造平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。（1）哈夫曼編碼的理論基礎根據信息論中信源編碼理論，當平均碼長R大于等于圖像熵H時，總可設計出一種無失真編碼。當平均碼長遠大于圖像熵時，表明該編碼方法效率很低；當平均碼長等于或很接近于（但不大于）圖像熵時，稱此編碼方法為最佳編碼，此時不會引起圖像失真；當平均碼長小于圖像熵時，壓縮比較高，但會引起圖像失真。在編碼中，如果碼字長度嚴格按照對應符號出現(xiàn)的概率大小逆序排列，則其平均碼字長度最小，這就是可變碼長最佳編碼定理，它是哈夫曼編碼的理論基礎。（2）哈夫曼編碼算法哈夫曼編碼是以信源概率分布為基礎的，但一般無法事先知道信源的概率分布，通常采用對大量數(shù)據進行統(tǒng)計后得到的近似分布來代替，這樣會導致實際應用時哈夫曼編碼無法達到最佳性能。通過利用根據輸入數(shù)據序列自適應地匹配信源概率分布的方法，可以較好地改進哈夫曼編碼的性能。哈夫曼編碼的一般算法如下：1首先統(tǒng)計信源中各符號出現(xiàn)的概率，按符號出現(xiàn)的概率將各符號從大到小降序排序。2把最小的兩個概率相加合并成新的概率，與剩余的概率組成新的概率集合。3對新的概率集合重新排序，再次把其中最小的兩個概率相加，組成新的概率集合。如此重復進行，直到最后兩個概率的和為1。4分配碼字。碼字分配從最后一步開始反向進行，對于每次相加的兩個概率，給大的賦“0”，小的賦“1”（也可以全部相反，如果兩個概率相等，則從中任選一個賦“0”，另一個賦“1”即可），讀碼字時由該符號開始一直走到最后的概率和“1”，將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號進行哈夫曼編碼后的碼字。對不同概率分布的信源，哈夫曼編碼的編碼效率有所差別。根據信息論中信源編碼理論，對于二進制編碼，當信源概率為2的負冪次方時，哈夫曼編碼的編碼效率可達100%，其平均碼字長度也很短，而當信源概率為均勻分布時，其編碼效果明顯降低。在表10-1中，顯然，第二種情況的概率分布也服從2的負冪次方，故其編碼效率η也可以達到100%，但由于它服從均勻分布，其熵最大，因此從其它指標看（如壓縮比），其編碼效率最低。也就是說，在信源概率接近于均勻分布時，一般不使用哈夫曼編碼。（3）哈夫曼編碼的性能對圖像進行哈夫曼編碼的優(yōu)點有以下4點：1保證了概率大的灰度對應于短碼，概率小的灰度對應于長碼，短碼得到了充分利用。2每次縮減信源的最后兩個碼字總是最后一位碼元不同，前面各位相同。3每次縮減信源的最后兩個碼字有相同的碼長。4編碼不唯一，且碼字長度可變（變長碼），哈夫曼編碼在無失真的編碼方法中效率優(yōu)于其它編碼方法，是一種最佳變長碼。對圖像進行哈夫曼編碼的缺點有以下2點：1當信源數(shù)據成分復雜時，龐大的信源集致使Huffman碼表較大，碼表生成的計算量增加，編譯碼速度相應變慢。2不等長編碼致使硬件譯碼電路實現(xiàn)困難。10.2.2費諾編碼

利用費諾提出的編碼方法對圖像進行編碼時步驟如下：（1）將圖像灰度按其概率大小降序排列；（2）將排序后的圖像灰度分成兩組，使每組的概率和盡量接近，給第一組灰度分配代碼“0”，第二組分配代碼“1”；（3）若每組還是由兩個或兩個以上的灰度組成，重復上述步驟，直至每組只有一個灰度為止。10.2.3香農編碼

香農在1948年提出了將信源符號按其概率降序排列，用符號序列累積概率的二進制表示作為對信源的唯一可譯編碼。利用香農提出的編碼方法對圖像進行編碼時步驟如下：（1）將N個灰度按其概率進行降序排列；（2）求編碼后表示概率為的第i個灰度所需的二進制位數(shù)；（10-2-7）（3）計算與相對應的累積概率,取與相對應的二進制數(shù)的小數(shù)點后的前位作為碼字。10.2.4算術編碼

（1）算術編碼的基本思想算術編碼是80年代發(fā)展起來的一種無損數(shù)據壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號，然后對每個符號進行編碼，而算術編碼的基本思想是按照符號序列的出現(xiàn)概率對概率區(qū)間分割，用一個實數(shù)代表一個數(shù)據流的輸入符號，再將這個實數(shù)轉化為一定位數(shù)的二進制代碼，此二進制代碼就是對此數(shù)據流的編碼。（2）算術編碼的步驟1把當前區(qū)間定義為；2把當前區(qū)間分割為長度正比于符號概率的子區(qū)間；3為輸入數(shù)據流中的每個符號x選擇一個子區(qū)間，并將其定義為新的當前區(qū)間；4重復2、3，直到把輸入數(shù)據流中的所有符號都處理完后，輸出的即為能唯一確定當前區(qū)間的數(shù)，再將此數(shù)轉化為一定位數(shù)的二進制代碼，則取此二進制代碼小數(shù)點后的部分就是所要求的碼字。算術編碼有兩種模式：一種是基于信源概率統(tǒng)計特性的固定編碼模式，另一種是針對未知信源概率模型的自適應模式。自適應模式中各個符號的概率初始值都相同，它們依據出現(xiàn)的符號而相應地改變。只要編碼器和解碼器都使用相同的初始值和相同的改變值的方法，那么它們的概率模型將保持一致。上述兩種形式的算術編碼均可用硬件實現(xiàn)，其中自適應模式適用于不進行概率統(tǒng)計的場合。有關實驗數(shù)據表明，在未知信源概率分布的情況下，算術編碼一般要優(yōu)于Huffman編碼。在JPEG擴展系統(tǒng)中，就用算術編碼取代了哈夫曼編碼。下面結合一個實例來闡述固定模式的算術編碼的具體方法。10.3JPEG編碼

10.3.1JPEG基本系統(tǒng)編碼JPEG是面向靜態(tài)圖像編碼的國際標準。在相同圖像質量條件下，JPEG文件擁有比其他圖像文件格式更高的壓縮比。JPEG目前被廣泛應用于多媒體和網絡程序中，是現(xiàn)今萬維網中使用最廣泛的兩種圖像文件格式之一。JPEG是一種有損壓縮，即在壓縮過程中會丟失數(shù)據，每次編輯JPEG圖像后，圖像就會被重復壓縮一次，損失就會有所增加。JPEG允許四種編碼模式：（1）順序式（Sequential）DCT方式：從左到右、從上到下對圖像順序進行基于離散余弦變換（DCT）的編碼。DCT理論上是可逆的，但在計算時存在誤差，因而基于DCT的編碼模式是一種有損編碼。（2）漸進式（Progressive）DCT方式：基于DCT對圖像分層次進行處理，從模糊到清晰地傳輸圖像（與GIF文件的交錯方式類似）。有兩種實現(xiàn)方法，一種是頻譜選擇法，即按Z形掃描的序號將DCT量化序數(shù)分成幾個頻段，每個頻段對應一次掃描，每塊均先傳送低頻掃描數(shù)據，得到原圖概貌，再依次傳送高頻掃描數(shù)據，使圖像逐漸清晰；另一種是逐次逼近法，即每次掃描全部DCT量化序數(shù)，但每次的表示精度逐漸提高。（3）無失真（Lossless）方式：使用線性預測器（如DPCM，而不是DCT）對圖像分層次進行處理。（4）分層（Hierarchical）方式：在空間域將源圖像以不同的分辨率表示，每個分辨率對應一次掃描，處理時可以基于DCT或預測編碼，可以是漸進式，也可以是順序式。JPEG定義了三種系統(tǒng)：基本系統(tǒng)（BaselineSystem）、擴展系統(tǒng)（ExtendedSystem）和無失真壓縮系統(tǒng)（LosslessSystem）。一個符合JPEG標準的編解碼器至少要滿足基本系統(tǒng)的技術指標?；镜腏PEG算法屬于變換類編碼，下面針對基于DCT的順序式基本系統(tǒng)編碼來說明JPEG的編碼方法。（1）數(shù)據分塊對圖像進行編碼前，將每個分量圖像分割成不重疊的8×8圖像數(shù)據塊，每一個8×8圖像數(shù)據塊稱為一個數(shù)據單元（DU）。在彩色圖像中，JPEG分別壓縮圖像的每個彩色分量。雖然JPEG可以壓縮通常的紅綠藍分量，但在YCbCr空間的壓縮效果會更好。這是因為人眼對色彩的變化不如對亮度的變化敏感，因而對色彩的編碼可以比對亮度的編碼粗糙些，這主要體現(xiàn)在不同的采樣頻率和量化精度上。因此，編碼前一般先將圖像從RGB空間轉換到YCbCr空間，再把各分量圖像分割成8×8圖像數(shù)據塊。（2）DCT處理圖像數(shù)據分割成圖像數(shù)據塊（DU）后，順序將DU進行二維離散余弦變換。對以無符號數(shù)表示的具有P位精度的輸入數(shù)據，在DCT前要減去2P-1，轉換成有符號數(shù)，而在IDCT后，應加上2P-1，轉換成無符號數(shù)。對每個8×8的數(shù)據塊DU進行DCT后，得到的64個系數(shù)代表了該圖像塊的頻率成分，其中低頻分量集中在左上角，高頻分量分布在右下角。系數(shù)矩陣左上角的叫做直流（DC）系數(shù)，它代表了該數(shù)據塊的平均值，其余63個叫交流（AC）系數(shù)。（3）系數(shù)量化在DCT處理中得到的64個系數(shù)中，低頻分量包含了圖像亮度等主要信息。在從空間域到頻域的變換中，圖像中的緩慢變化比快速變化更易引起人眼的注意，所以在重建圖像時，低頻分量的重要性高于高頻分量。因而在編碼時可以忽略高頻分量，從而達到壓縮的目的，這也是量化的根據和目的。在JPEG標準中，用具有64個獨立元素的量化表來規(guī)定DCT域中相應的64個系數(shù)的量化精度，使得對某個系數(shù)的具體量化階取決于人眼對該頻率分量的視覺敏感程度。理論上，對不同的空間分辨率、數(shù)據精度等情況，應該有不同的量化表。（4）Z形掃描DCT系數(shù)量化后，構成一個稀疏矩陣，用Z（Zigzag）形掃描將其變成一維數(shù)列，將有利于熵編碼。Z形掃描的順序如表10-6所示。（5）DC系數(shù)編碼DC系數(shù)反映了一個8×8數(shù)據塊的平均亮度，一般與相鄰塊有較大的相關性。JPEG對DC系數(shù)作差分編碼，即用前一數(shù)據塊的同一分量的DC系數(shù)作為當前塊的預測值，再對當前塊的實際值與預測值的差值（DIFF）作哈夫曼編碼。若DC系數(shù)的動態(tài)范圍為-1024～+1024，則差值的動態(tài)范圍為-2047～+2047。如果為每個差值賦予一個碼字，則碼表過于龐大。因此，JPEG對碼表進行了簡化，采用“前綴碼（SSSS）+尾碼”來表示。前綴碼指明了尾碼的有效位數(shù)B，可以根據DIFF從表10-7中查出前綴碼對應的哈夫曼編碼。尾碼的取值取決于DC系數(shù)的差值和前綴碼。如果DC系數(shù)的差值DIFF大于等于0，則尾碼的碼