CH3 圖像壓縮編碼

圖像通信原理與技術(shù)第3章圖像壓縮編碼第

3

章圖像壓縮編碼3.1圖像壓縮編碼的分類3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)

3.2.1數(shù)據(jù)壓縮與數(shù)據(jù)冗余

3.2.2圖像壓縮編碼系統(tǒng)的基本構(gòu)成

3.2.3信息論基礎(chǔ)3.3霍夫曼編碼3.4游程長度編碼第

3

章圖像壓縮編碼（續(xù)）3.4.1二值圖像的游程編碼

3.4.2一維游程編碼

3.4.3二維游程編碼

3.4.4游程編碼綜述3.5算術(shù)編碼

3.5.1算術(shù)編碼原理

3.5.2算術(shù)碼分析第

3

章圖像壓縮編碼（續(xù)）3.5.3算術(shù)編碼的效率*3.6LZW字典編碼

3.1圖像壓縮編碼的分類(1)冗余度壓縮方法，也稱無損壓縮、信息保持編碼或熵編碼。熵編碼是純粹基于信號統(tǒng)計特性的一種編碼方法。它利用圖像信源概率分布的不均勻性，通過變長編碼來減少信源數(shù)據(jù)冗余，解碼后的重建圖像和壓縮編碼前的原始圖像完全相同，沒有失真。

無損壓縮中經(jīng)常采用的方法有霍夫曼(Huffman)編碼、游程編碼(Run-lengthcode)、算術(shù)編碼（ArithmeticCoding）和字典LZW編碼等。(2)信息量壓縮方法，也稱有損壓縮、失真度編碼或熵壓縮編碼。該方法利用了人類視覺對圖像中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息。常用的有損壓縮方法有：脈沖編碼調(diào)制(PCM)、預(yù)測編碼(DPCM、運動補償)、變換編碼（DFT、DCT、K-L變換、Walsh-Hadamard變換、小波變換）等，以及灰度圖像的方塊編碼、比特平面分層編碼及抖動編碼等。還有一種按照描述圖像或視頻源的信源模型來進(jìn)行分類的方法，可分為基于波形編碼和基于內(nèi)容編碼兩大類?；诓ㄐ尉幋a的信源模型通常是采用像素來表示圖像的，像素是最基本單元，盡可能精確地用像素值表示在該像素點的光強和顏色值，不考慮一組像素可能代表一個具體物理對象這一事實情況。

另一類是其信源模型的基本單元不是像素而是對象的編碼方法，稱為基于內(nèi)容(對象)的編碼技術(shù)?；趯ο蟮姆治鼍C合編碼、物體基編碼、模型基和語義基編碼都屬于這一類。顯然。以對象特征信息來描述圖像是一種比用像素來描述的更高層次的編碼方法，可以達(dá)到更高的壓縮率。

3.2數(shù)據(jù)壓縮與信息論基礎(chǔ)3.2.1數(shù)據(jù)壓縮與數(shù)據(jù)冗余

數(shù)據(jù)壓縮，就是以最少的數(shù)碼表示信源所發(fā)送的信號，減少容納給定消息集合或數(shù)據(jù)采樣集合的信號空間。圖像數(shù)據(jù)中存在著大量的冗余，即圖像的各像素數(shù)據(jù)之間存在著極強的相關(guān)性。利用這些相關(guān)性，一部分像素的數(shù)據(jù)可以由另一部分像素的數(shù)據(jù)推導(dǎo)出來，如此可使圖像數(shù)據(jù)量極大地壓縮。經(jīng)過分析發(fā)現(xiàn)，圖像數(shù)據(jù)壓縮機(jī)理來自兩個方面：一是圖像信號中存在大量冗余可供壓縮，并且這種冗余度在解碼后還可無失真地恢復(fù)；二是利用人眼的視覺特性，在不被主觀視覺察覺的范圍內(nèi)，通過減少表示信號的精度，以一定的客觀失真換取數(shù)據(jù)壓縮。

圖像信號的冗余度存在于結(jié)構(gòu)和統(tǒng)計兩方面。正如我們在第二章中圖像的統(tǒng)計特性中分析的，圖像信號結(jié)構(gòu)上的冗余度表現(xiàn)為很強的空間（幀內(nèi)的）和時間（幀間的）上的相關(guān)性。

若用相同碼長表示不同出現(xiàn)概率的符號，則會造成比特數(shù)的浪費。如果采用可變長編碼技術(shù)，對出現(xiàn)概率大的符號用短碼字表示，對出現(xiàn)概率小的符號用長碼字表示，則可去除信號統(tǒng)計上的冗余，從而節(jié)約碼字。

信號統(tǒng)計上的冗余度來源于被編碼信號概率密度分布的不均勻。3.2.2圖像壓縮編碼系統(tǒng)的基本構(gòu)成圖3-2圖像壓縮編碼系統(tǒng)組成框圖圖3-3信源編碼器與解碼器的組成框圖

在以上框圖中，不同的圖像編碼系統(tǒng)可能采用上述框圖中的不同組合，變換器和編碼器是可逆的，而量化器是不可逆的。所以，無失真的信源編碼器不能包含量化器，在大多數(shù)實用情況下，為了得到期望的比特率，必須允許圖像質(zhì)量有少許的下降，有損壓縮方法既利用了圖像的結(jié)構(gòu)冗余和統(tǒng)計冗余，同時又利用了其視覺冗余特性。3.2.3信息論基礎(chǔ)1.信源模型及其熵

（1）獨立信源最簡單的信源就是獨立信源，在一個獨立信源中，連續(xù)發(fā)生的各個符號都是統(tǒng)計獨立的。信息量定義為：

若對一個獨立信源中所有可能符號的信息量取平均，就得到信源中每個符號的平均信息量，又叫做熵

可以證明，對于具有一定數(shù)目的符號的任一獨立信源，當(dāng)各個符號的發(fā)生概率都相等時，其熵取最大值。（2）馬爾可夫信源在實際中，信源發(fā)出的各個符號之間往往并不是相互獨立，而是具有統(tǒng)計的關(guān)聯(lián)性。2.無失真編碼定理與最佳編碼

無失真編碼定理：對于離散信源，對其編碼時每個符號能達(dá)到的平均碼長滿足以下不等式該定理一方面指出了每個符號平均碼長的下限為信源的熵，另一方面說明存在任意接近該下限的編碼。對于獨立信源，該定理適用于對單個符號編碼的情況，也適用于對符號塊編碼的情況；對于N階的馬爾可夫信源，只適用于對不少于N個符號的符號塊編碼的情況。對離散信源進(jìn)行編碼時，可以通過等長與不等長編碼實現(xiàn)。等長編碼對于一個消息集合中的不同消息，若采用相同長度的不同碼字去代表，就叫做等長編碼。（2）變長碼的基本分析與等長編碼相對應(yīng)，對一個消息集合中的不同消息，也可以用不同長度的碼字來表示。當(dāng)每個符號的碼長都等于其信息量時，編碼的平均碼長可達(dá)到其下限，即信源的熵。當(dāng)然，這只有當(dāng)每個符號的信息量都是整數(shù)時才可能實現(xiàn)。按照信息量的定義，這相當(dāng)于，應(yīng)為概率較大的符號分配較短的碼字，而為概率較小的符號分配較長的碼字，這正是變長編碼的基本原則。采用變長碼可以提高編碼效率，即對相同信息量所需的平均編碼長度可以短一些。采用等長編碼的優(yōu)點是編碼過程和解碼過程簡單。但由于這種編碼方法沒有考慮各個符號出現(xiàn)的概率，實際上就是將它們當(dāng)作等概率事件來處理的，因而它的編碼效率較低。變長編碼方法中，表示符號的碼字的長度不是固定不變的，而是隨符號出現(xiàn)的概率而變化：給出現(xiàn)概率高的符號分配較短的碼字，給出現(xiàn)概率低的符號分配較長的碼字?？梢宰C明，在非均勻符號概率分布的情況下，變長編碼總的編碼效率要高于等字長編碼。但是，變長碼在編碼時要預(yù)先知道各種消息符號出現(xiàn)的概率，而解碼也遠(yuǎn)比等長碼復(fù)雜：對于等長碼只要使不同的消息對應(yīng)不同的碼字，而收端只要能正確識別出一個碼字的起始位置就能正確譯碼；但對變長碼要正確識別碼字起點就不那么容易，并且還存在唯一可譯性、譯碼實時性及與勻速輸入輸出匹配的緩存問題。（3）編碼效率編碼效率是信源的熵與平均碼長之比，（4）壓縮比壓縮比是編碼前后平均碼長之比（5）比特率通常指編碼的平均碼長，借助熵的概念可以定義量度任何特定碼性能的準(zhǔn)則，即平均碼字長度，單位也是比特/字符。3.3霍夫曼編碼在變長編碼中，如果碼字長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小逆序排列，則其平均碼字長度為最小，這就是變長最佳編碼定理。變長最佳編碼定理是霍夫曼編碼的理論基礎(chǔ)。要注意的是，變長編碼是一種信息保持型編碼(熵編碼)，即編解碼的過程并不引起信息量的損失，因為它的符號和碼字之間是唯一對應(yīng)的?；舴蚵幋a的基本步驟如下：

(1)按概率從大到小的順序排列信源符號。

(2)把最小的兩個概率相加合并成新的概率，與剩余的概率組成新的概率集合。(3)對新的概率集合重新按照從大到小排序，再次把其中最小的兩個概率相加，組成新的概率集合。如此重復(fù)進(jìn)行，直到最后兩個概率的和為1。(4)分配碼字。碼字分配從最后一步開始反向進(jìn)行，對于每次相加的兩個概率，給大概率分配“0”，小概率分配“1”(也可以全部相反，如果兩個概率相等，則從中任選一個賦“0”，另一個賦“1”即可)，讀出時由最終一個符號開始，將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的霍夫曼編碼。需要注意：①霍夫曼編碼的算法是確定的，但編出的碼并非是唯一的。②由于霍夫曼編碼的依據(jù)是信源符號的概率分布，故其編碼效率取決于信源的統(tǒng)計特性?；舴蚵幋a的局限性在于，該編碼方法只適用于離散信源，即信源符號個數(shù)為有限數(shù)；編碼時需要知道輸入符號集的概率分布；在進(jìn)行Huffman編碼壓縮時，計算量大而復(fù)雜，尤其是譯碼復(fù)雜度較高。由于碼長不等，還存在一個輸入與輸出的速率匹配問題。3.4游程長度編碼游程長度編碼(Run-Lengthcoding，RLC)的基本思想，是將具有相同數(shù)值的、連續(xù)出現(xiàn)的信源符號構(gòu)成的符號串用其數(shù)值及串的長度表示。3.4.1二值圖像的游程編碼二值圖像游程編碼的基本思想是，當(dāng)按照二值圖像從左到右的掃描順序觀察每一行時發(fā)現(xiàn)，二值圖像的每一掃描行均由交替出現(xiàn)的白像素游程(稱作自長)和黑像素游程(稱作黑長)組成。白游程的后面必然是黑游程，反之亦然，黑游程的后面必然是白游程。因而只要知道了各掃描線的頭一個游程是黑還是白，就不再需要指示游程黑白的信息了。進(jìn)一步對不同長度的白長和黑長按其出現(xiàn)概率的不同分別配以不同長度的碼字，就是二值圖像的RLC。圖3-7游程編碼示意圖3.4.2一維游程編碼下面介紹傳真三類機(jī)（G3）所采用的改進(jìn)型Huffman編碼（ModifiedHuffman）的方法。視覺特性根據(jù)一維游程編碼原理，一維游長編碼規(guī)則如下：①當(dāng)RL=0～63，用一個相應(yīng)的終止碼表示；②當(dāng)RL=64～l728，用一個終止碼加一個起始碼。③規(guī)定每行都從白游程開始，若實際掃描行由黑開始，則需在行首加零長度白游程；行結(jié)束要加行同步碼EOL(見表3-2)。3.4.3二維游程編碼

二維游程編碼方法，不是直接對游程長度本身進(jìn)行編碼，而是對掃描行之間游程長度變化的差值進(jìn)行編碼。由于圖像所存在的相關(guān)性。這種編碼的數(shù)碼率一定會下降。圖3-9二維游程編碼示意圖3.4.4游程編碼綜述游程編碼的優(yōu)點是算法簡單、易于實現(xiàn)，由于是將信源符號序列中的相同字符轉(zhuǎn)換成一個計數(shù)字段再加上一個重復(fù)字符標(biāo)志，所以對于二值圖像最為有效；缺點是對于特定的不連續(xù)符號序列，會出現(xiàn)編碼后數(shù)據(jù)量增加的情況。此外，變長碼的固有缺點仍然存在，即需要較大容量的緩沖和較低誤碼的優(yōu)質(zhì)信道。3.5算術(shù)編碼3.5.1算術(shù)編碼原理算術(shù)編碼是一種從整個符號系列出發(fā)，采用遞推形式連續(xù)編碼的方法。在算術(shù)編碼中，字母表中的符號和碼字間不再存在一一對應(yīng)關(guān)系，一個算術(shù)碼字要賦給整個信源符號序列（即不是一次編一個號），而碼字本身確定0和1之間的一個實數(shù)區(qū)間。算術(shù)編碼和上述霍夫曼塊編碼的區(qū)別就在于：在算術(shù)編碼中，輸入序列（即被賦給單個碼字的符號塊）的長度，是可變的，可以說，算術(shù)編碼是將可變長碼字賦給可變長符號塊。正是由于算術(shù)編碼不需要為定長符號塊分配整數(shù)長的碼字，理論上能達(dá)到無損編碼定理所規(guī)定的最低限。算術(shù)編碼在編碼過程中，盡管在計算時有乘法運算，但可以通過移位實現(xiàn)，即通過加法和移位實現(xiàn)算術(shù)運算。在解碼時，要除以符號區(qū)間概率，也可以通過移位實現(xiàn)，即通過減法和移位實現(xiàn)算術(shù)解碼。這正是把這種編碼方法稱為算術(shù)碼的原因。3.5.2算術(shù)碼分析算術(shù)編碼跳出了分組編碼的范疇，從全序列出發(fā)，采用遞推形式的連續(xù)編碼，它不是將單個的信源符號映射成一個碼字，而是將整個符號序列映射為實數(shù)軸上[0,1）區(qū)間內(nèi)的一個小區(qū)間，其長度等于該序列的概率。從小區(qū)間內(nèi)選擇一個代表性的二進(jìn)制小數(shù)，作為實際的編碼輸出，從而達(dá)到高效編碼的目的。不論是否是二元信源，也不論數(shù)據(jù)的概率分布如何，其平均碼長均能逼近信源的熵。隨著輸入符號越來越多，子區(qū)間分割越來越精細(xì)，因此表示其左端點的數(shù)值的有效位數(shù)也越來越多。如果等整個符號序列輸入完畢后再將最終得到的左端點輸出，將遇到兩個問題：第一，當(dāng)符號序列很長時，將不能實時編解碼；第二，有效位太長的數(shù)難以表示。

為了解決這個問題，通常采用兩個有限精度的移位寄存器存放碼字的最新部分，隨著序列中符號的不斷輸入，不斷地將其中的高位移出到信道上，以實現(xiàn)實時編解碼。3.5.3算術(shù)編碼的效率算術(shù)編碼的最大優(yōu)點之一在于它具有自適應(yīng)性和高編碼效率。算術(shù)編碼的模式選擇直接影響編碼效率。其模式有固定模式和自適應(yīng)模式兩種。固定模式是基于概率分布模型的，而在自適應(yīng)模式中，其各符號的初始概率都相同，但隨著符號順序的出現(xiàn)而改變，在無法進(jìn)行信源概率模型統(tǒng)計的條件下，非常適于使用自適應(yīng)