CH3 圖像壓縮編碼

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

3

章圖像壓縮編碼3.1圖像壓縮編碼的分類(lèi)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游程長(zhǎng)度編碼第

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圖像壓縮編碼的分類(lèi)(1)冗余度壓縮方法，也稱無(wú)損壓縮、信息保持編碼或熵編碼。熵編碼是純粹基于信號(hào)統(tǒng)計(jì)特性的一種編碼方法。它利用圖像信源概率分布的不均勻性，通過(guò)變長(zhǎng)編碼來(lái)減少信源數(shù)據(jù)冗余，解碼后的重建圖像和壓縮編碼前的原始圖像完全相同，沒(méi)有失真。

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

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

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

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

圖像信號(hào)的冗余度存在于結(jié)構(gòu)和統(tǒng)計(jì)兩方面。正如我們?cè)诘诙轮袌D像的統(tǒng)計(jì)特性中分析的，圖像信號(hào)結(jié)構(gòu)上的冗余度表現(xiàn)為很強(qiáng)的空間（幀內(nèi)的）和時(shí)間（幀間的）上的相關(guān)性。

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

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

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

（1）獨(dú)立信源最簡(jiǎn)單的信源就是獨(dú)立信源，在一個(gè)獨(dú)立信源中，連續(xù)發(fā)生的各個(gè)符號(hào)都是統(tǒng)計(jì)獨(dú)立的。信息量定義為：

若對(duì)一個(gè)獨(dú)立信源中所有可能符號(hào)的信息量取平均，就得到信源中每個(gè)符號(hào)的平均信息量，又叫做熵

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

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

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

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

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

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