第10章圖像編碼

第十章圖像編碼10.1圖像編碼概述10.2哈夫曼編碼10.3香農(nóng)-范諾編碼

10.4行程編碼10.5LZW編碼10.6算術(shù)編碼

10.7JPEG編碼10.8編程實例10.1圖像編碼概述10.1.1圖像編碼基本原理

雖然表示圖像需要大量的數(shù)據(jù)，但圖像數(shù)據(jù)是高度相關(guān)的，或者說存在冗余（Redundancy）信息，去掉這些冗余信息后可以有效壓縮圖像，同時又不會損害圖像的有效信息。數(shù)字圖像的冗余主要表現(xiàn)為以下幾種形式：空間冗余、時間冗余、視覺冗余、信息熵冗余、結(jié)構(gòu)冗余和知識冗余?？臻g冗余：圖像內(nèi)部相鄰像素之間存在較強(qiáng)的相關(guān)性所造成的冗余。時間冗余：視頻圖像序列中的不同幀之間的相關(guān)性所造成的冗余。視覺冗余：是指人眼不能感知或不敏感的那部分圖像信息。信息熵冗余：也稱編碼冗余，如果圖像中平均每個像素使用的比特數(shù)大于該圖像的信息熵，則圖像中存在冗余，這種冗余稱為信息熵冗余。結(jié)構(gòu)冗余：是指圖像中存在很強(qiáng)的紋理結(jié)構(gòu)或自相似性。知識冗余：是指在有些圖像中還包含與某些先驗知識有關(guān)的信息。圖像數(shù)據(jù)的這些冗余信息為圖像壓縮編碼提供了依據(jù)。例如，利用人眼對藍(lán)光不敏感的視覺特性，在對彩色圖像編碼時，就可以用較低的精度對藍(lán)色分量進(jìn)行編碼。圖像編碼的目的就是充分利用圖像中存在的各種冗余信息，特別是空間冗余、時間冗余以及視覺冗余，以盡量少的比特數(shù)來表示圖像。利用各種冗余信息，壓縮編碼技術(shù)能夠很好地解決在將模擬信號轉(zhuǎn)換為數(shù)字信號后所產(chǎn)生的帶寬需求增加的問題，它是使數(shù)字信號走上實用化的關(guān)鍵技術(shù)之一，表10-1中列出了幾種常見應(yīng)用的碼率。表10-1幾種常見應(yīng)用的碼率10.1.2圖像編碼的方法

根據(jù)編碼過程中是否存在信息損耗可將圖像編碼分為有損壓縮和無損壓縮。無損壓縮無信息損失，解壓縮時能夠從壓縮數(shù)據(jù)精確地恢復(fù)原始圖像；有損壓縮不能精確重建原始圖像，存在一定程度的失真。根據(jù)編碼原理可以將圖像編碼分為熵編碼、預(yù)測編碼、變換編碼和混合編碼等。（1）熵編碼。熵編碼是純粹基于信號統(tǒng)計特性的編碼技術(shù)，是一種無損編碼。熵編碼的基本原理是給出現(xiàn)概率較大的符號賦予一個短碼字，而給出現(xiàn)概率較小的符號賦予一個長碼字，從而使得最終的平均碼長很小。常見的熵編碼方法有行程編碼（RunLengthEncoding）、哈夫曼編碼和算術(shù)編碼。（2）預(yù)測編碼。預(yù)測編碼是基于圖像數(shù)據(jù)的空間或時間冗余特性，用相鄰的已知像素（或像素塊）來預(yù)測當(dāng)前像素（或像素塊）的取值，然后再對預(yù)測誤差進(jìn)行量化和編碼。預(yù)測編碼可分為幀內(nèi)預(yù)測和幀間預(yù)測，常用的預(yù)測編碼有差分脈碼調(diào)制（DifferentialPulseCodeModulation，DPCM）和運動補(bǔ)償法。（3）變換編碼。變換編碼通常是將空間域上的圖像經(jīng)過正交變換映射到另一變換域上，使變換后的系數(shù)之間的相關(guān)性降低。圖像變換本身并不能壓縮數(shù)據(jù)，但變換后圖像的大部分能量只集中到少數(shù)幾個變換系數(shù)上，采用適當(dāng)?shù)牧炕挽鼐幋a就可以有效地壓縮圖像。（4）混合編碼?；旌暇幋a是指綜合了熵編碼、變換編碼或預(yù)測編碼的編碼方法，如JPEG標(biāo)準(zhǔn)和MPEG標(biāo)準(zhǔn)。根據(jù)對壓縮編碼后的圖像進(jìn)行重建的準(zhǔn)確程度，可將常用的圖像編碼方法分為三類：（1）信息保持編碼：也稱無失真編碼，它要求在編解碼過程中保證圖像信息不丟失，從而可以完整地重建圖像。信息保持編碼的壓縮比較低，一般不超過3:1，主要應(yīng)用在圖像的數(shù)字存儲方面，常用于醫(yī)學(xué)圖像編碼中。（2）保真度編碼：主要利用人眼的視覺特性，在允許的失真（Lossy）條件下或一定的保真度準(zhǔn)則下，最大限度地壓縮圖像。保真度編碼可以實現(xiàn)較大的壓縮比，主要用于數(shù)字電視技術(shù)、靜止圖像通信、娛樂等方面。對于這些圖像，過高的空間分辨率和過多的灰度層次，不僅增加了數(shù)據(jù)量，而且人眼也接收不到。因此在編碼過程中，可以丟掉一些人眼不敏感的信息，在保證一定的視覺效果條件下提高壓縮比。（3）特征提?。涸趫D像識別、分析和分類等技術(shù)中，往往并不需要全部圖像信息，而只要對感興趣的部分特征信息進(jìn)行編碼即可壓縮數(shù)據(jù)。例如，對遙感圖像進(jìn)行農(nóng)作物分類時，就只需對用于區(qū)別農(nóng)作物與非農(nóng)作物，以及農(nóng)作物類別之間的特征進(jìn)行編碼，而可以忽略道路、河流、建筑物等其他背景信息。10.1.3圖像編碼新技術(shù)圖像編碼已經(jīng)發(fā)展了幾十年，人們不斷提出新的壓縮方法。如，利用人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork，ANN）的壓縮編碼、分形編碼（FractalCoding）、小波編碼（WaveletCoding）、基于對象的壓縮編碼（ObjectBasedCoding）和基于模型的壓縮編碼（ModelBasedCoding）等等。1）分形編碼分形編碼是在波蘭美籍?dāng)?shù)學(xué)家B.B.Mandelbrot建立的分形幾何理論的基礎(chǔ)上發(fā)展起來的一種編碼方法。分形編碼最大限度地利用了圖像在空間域上的自相似性（即局部與整體之間存在某種相似性），通過消除圖像的幾何冗余來壓縮數(shù)據(jù)。M.Barnsley將迭代函數(shù)系統(tǒng)（IterateFunctionSystem，IFS）用于描述圖像的自相似性，并將其用于圖像編碼，對某些特定圖像獲得了10000:1的壓縮比。分形編碼過程十分復(fù)雜，而解碼過程卻很簡單，故通常用于對圖像編碼一次，而需譯碼多次的信息傳播應(yīng)用中。

2）小波編碼

1989年，S.G.Mallat首次將小波變換用于圖像編碼。經(jīng)過小波變換后的圖像，具有良好的空間方向選擇性，而且是多分辨率的，能夠保持原圖像在各種分辨率下的精細(xì)結(jié)構(gòu)，與人的視覺特性十分吻合。

3）模型編碼模型編碼是近幾年發(fā)展起來的一種很有前途的低比特率編碼方法，其基本出發(fā)點是在編、解碼兩端分別建立起相同的模型，編碼時利用先驗?zāi)Ｐ统槿D像中的主要信息并用模型參數(shù)的形式表示，解碼時則利用所接收的模型參數(shù)重建圖像。10.1.4圖像編碼評價

隨著眾多圖像壓縮算法的出現(xiàn)，如何評價圖像壓縮算法就成為重要的課題。一般說來，評價圖像壓縮算法的優(yōu)劣主要有以下4個參數(shù)。1）算法的編碼效率

算法的編碼效率通常有幾種表現(xiàn)形式：平均碼字長度（R），圖像的壓縮比（rate，r），每秒鐘所需的傳輸比特數(shù)（bitspersecond，bps），圖像熵與平均碼長之比（η），這些表現(xiàn)形式很容易相互轉(zhuǎn)換。下面給出與圖像編碼效率有關(guān)的幾個定義。設(shè)一幅灰度級為N的圖像，圖像中第k級灰度出現(xiàn)的概率為Pk，圖像大小為Nx×Ny，每個像素用d比特表示，每兩幀圖像間隔Δt，則按信息論中信息熵的定義，數(shù)字圖像的熵H由下式定義：（10-1）由此可見，圖像熵H表示各灰度級比特數(shù)的統(tǒng)計平均值。對于一種圖像編碼方法，設(shè)第k級灰度的碼字長度為Bk，則該圖像的平均碼字長度R為（10-2）于是，可定義編碼效率η為每秒鐘所需的傳輸比特數(shù)bps為（10-3）（10-4）壓縮比r為（10-5）由于同一壓縮算法對不同圖像的編碼效率會有所不同，因此常需定義一些“標(biāo)準(zhǔn)圖像”，如國際上流行的三幅圖像Lena、Barbara和Mandrill。一般通過測量不同壓縮算法對同一組“標(biāo)準(zhǔn)圖像”的編碼性能來評價各圖像壓縮算法的編碼效率。

2）編碼圖像的質(zhì)量圖像質(zhì)量評價可分為客觀質(zhì)量評價和主觀質(zhì)量評價。最常用的客觀質(zhì)量評價指標(biāo)是均方誤差（MSE）和峰值信噪比（PSNR），其定義如下：(10-6)(10-7)主觀質(zhì)量評價是指由一批觀察者對編碼圖像進(jìn)行觀察并打分，然后綜合所有人的評判結(jié)果，給出圖像的質(zhì)量評價?？陀^質(zhì)量評價能夠快速有效地評價編碼圖像的質(zhì)量，但符合客觀質(zhì)量評價指標(biāo)的圖像不一定具有較好的主觀質(zhì)量。主觀質(zhì)量評價能夠與人的視覺效果相匹配，但其評判過程緩慢費時。3）算法的適用范圍特定的圖像編碼算法具有其相應(yīng)的適用范圍，并不對所有圖像都有效。一般說來，大多數(shù)基于圖像信息統(tǒng)計特性的壓縮算法具有較廣的適用范圍，而一些特定的編碼算法的適用范圍較窄，如分形編碼主要用于自相似性高的圖像。4）算法的復(fù)雜度

算法的復(fù)雜度即指完成圖像壓縮和解壓縮所需的運算量和硬件實現(xiàn)該算法的難易程度。優(yōu)秀的壓縮算法要求有較高的壓縮比，壓縮和解壓縮快，算法簡單，易于硬件實現(xiàn)，還要求解壓縮后的圖像質(zhì)量較好。選用編碼方法時一定要考慮圖像信源本身的統(tǒng)計特性、多媒體系統(tǒng)(硬件和軟件產(chǎn)品)的適應(yīng)能力、應(yīng)用環(huán)境以及技術(shù)標(biāo)準(zhǔn)。10.2哈夫曼編碼

1.哈夫曼編碼的理論基礎(chǔ)根據(jù)信息論中信源編碼理論，當(dāng)平均碼長R大于等于圖像熵H時，總可設(shè)計出一種無失真編碼。當(dāng)平均碼長遠(yuǎn)大于圖像熵時，表明該編碼方法效率很低；當(dāng)平均碼長等于或很接近于（但不大于）圖像熵時，稱此編碼方法為最佳編碼，此時不會引起圖像失真；當(dāng)平均碼長大于圖像熵時，壓縮比較高，但會引起圖像失真。在變長編碼中，如果碼字長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小逆序排列，則其平均碼字長度為最小，這就是變長最佳編碼定理。變長最佳編碼定理是哈夫曼編碼的理論基礎(chǔ)。設(shè)D為編碼所使用的數(shù)制，則變長最佳編碼的平均碼字長度R的范圍為(10-8)

2.哈夫曼編碼算法哈夫曼編碼是以信源概率分布為基礎(chǔ)的，但一般無法事先知道信源的概率分布，通常采用對大量數(shù)據(jù)進(jìn)行統(tǒng)計后得到的近似分布來代替，這樣會導(dǎo)致實際應(yīng)用時哈夫曼編碼無法達(dá)到最佳性能。通過利用根據(jù)輸入數(shù)據(jù)序列自適應(yīng)地匹配信源概率分布的方法，可以較好地改進(jìn)哈夫曼編碼的性能。哈夫曼編碼的一般算法如下：（1）首先統(tǒng)計信源中各符號出現(xiàn)的概率，按符號出現(xiàn)的概率從大到小排序。（2）把最小的兩個概率相加合并成新的概率，與剩余的概率組成新的概率集合。（3）對新的概率集合重新排序，再次把其中最小的兩個概率相加，組成新的概率集合。如此重復(fù)進(jìn)行，直到最后兩個概率的和為1。（4）分配碼字。碼字分配從最后一步開始反向進(jìn)行，對于每次相加的兩個概率，給大的賦“0”，小的賦“1”（也可以全部相反，如果兩個概率相等，則從中任選一個賦“0”，另一個賦“1”即可），讀出時由該符號開始一直走到最后的概率和“1”，將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的哈夫曼編碼。

例10-1設(shè)一幅灰度級為8（分別用S0、S1、S2、S3、S4、S5、S6、S7表示）的圖像中，各灰度所對應(yīng)的概率分別為0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04?，F(xiàn)對其進(jìn)行哈夫曼編碼編碼過程如圖10-1所示，具體步驟如下：(1)首先對信源概率從大到小排序，選出最小的兩個概率（0.04和0.05），相加得0.09，與其他概率組成新的概率集合{0.40，0.18，0.10，0.10，0.07，0.06，0.09}。(2)對新的概率集合重新排序，選出最小的兩個概率（0.06和0.07），相加得0.13，組成新的概率集合{0.40，0.18，0.10，0.10，0.09，0.13}。(3)對新的概率集合重新排序，選出最小的兩個概率（0.10和0.09），相加得0.19，組成新的概率集合{0.40，0.18，0.13，0.10，0.19}。(4)對新的概率集合重新排序，選出最小的兩個概率（0.13和0.10），相加得0.23，組成新的概率集合{0.40，0.19，0.18，0.23}。(5)對新的概率集合重新排序，選出最小的兩個概率（0.19和0.18），相加得0.37，組成新的概率集合{0.40，0.23，0.37}。(6)對新的概率集合重新排序，選出最小的兩個概率（0.23和0.37），相加得0.60，組成新的概率集合{0.40，0.60}。(7)直到最后兩個概率（0.60和0.40）相加和為1。(8)分配碼字。從最后一步反向進(jìn)行，首先給最后相加的兩個概率（0.60和0.40）分配碼字，由于0.60大于0.40，于是給0.60賦“0”，給0.40賦“1”。如此依次給每次相加的兩個概率分配碼字。(9)最后寫出每個符號的哈夫曼編碼。以符號S1（對應(yīng)的概率為0.18）為例，在從0.18到1.0的路徑上，它所遇到的賦值（“0”或“1”）依次為1、0、0，將其反向排列成“001”，于是就形成了符號S1的哈夫曼碼字“001”。圖10-1哈夫曼編碼過程上述哈夫曼編碼方法形成的碼字是可識別的，即能夠保證一個符號的碼字不會與另一個符號的碼字的前幾位相同。比如說，如果S0的碼字為1，S1的碼字為001，而S2的碼字為011，則當(dāng)編碼序列中出現(xiàn)0011時，就不能判別它是S2的碼字還是S1的碼字后面跟了一個S0的碼字1。下面來看一下哈夫曼編碼的編碼效率。平均碼長R為數(shù)字圖像的熵H為則哈夫曼編碼的編碼效率η為由此可見，哈夫曼編碼的編碼效率是相當(dāng)高的，其冗余度只有2.2%。如果采用等長編碼，由于有8種灰度級，則每種灰度級別至少需要3比特來表示，對于例10-1中的圖像而言，其編碼的平均碼長為3，編碼效率為85%。對不同概率分布的信源，哈夫曼編碼的編碼效率有所差別。根據(jù)信息論中信源編碼理論，對于二進(jìn)制編碼，當(dāng)信源概率為2的負(fù)冪次方時，哈夫曼編碼的編碼效率可達(dá)100%，其平均碼字長度也很短，而當(dāng)信源概率為均勻分布時，其編碼效果明顯降低。在表10-2中，顯然，第二種情況的概率分布也服從2的負(fù)冪次方，故其編碼效率η也可以達(dá)到100%，但由于它服從均勻分布，其熵最大，平均編碼長度很大，因此從其他指標(biāo)看（如，壓縮比r），其編碼效率最低。也就是說，在信源概率接近于均勻分布時，一般不使用哈夫曼編碼。10-2啥夫曼編碼在不同概率分布下的編碼效果對比10.3香農(nóng)-范諾編碼香農(nóng)-范諾（Shannon-Fannon）編碼也是一種常見的可變字長編碼。與哈夫曼編碼相似，當(dāng)信源符號出現(xiàn)的概率正好為2-i（i<0）時，采用香農(nóng)-范諾編碼同樣能夠達(dá)到100%的編碼效率。香農(nóng)-范諾編碼的理論基礎(chǔ)是符號的碼字長度Ni完全由該符號出現(xiàn)的概率來決定，即（10-9）式中，D為編碼所用的數(shù)制。香農(nóng)-范諾編碼的步驟如下：（1）將信源符號按其出現(xiàn)概率從大到小排序；（2）按照式（10-9）計算出各概率對應(yīng)的碼字長度Ni；（3）計算累加概率Ai，即

Ai=Ai-1+Pi-1

i=1,2,…,N-1；A0=0 (10-10)（4）把各個累加概率Ai由十進(jìn)制轉(zhuǎn)化為二進(jìn)制，取該二進(jìn)制數(shù)的前Ni位作為對應(yīng)信源符號的碼字。為便于比較，仍以例10-1中圖像為對象，對其進(jìn)行香農(nóng)-范諾編碼，結(jié)果如表10-3所示。由于在此采用二進(jìn)制對碼字賦值，故在利用式（10-9）計算碼字長度Ni時，D取為2。以符號S4為例，其出現(xiàn)概率為0.07，按照式（10-9）計算得到它的碼字長度應(yīng)為4，按式（10-10）計算得到它的累加概率A4為0.78，將0.78轉(zhuǎn)化為二進(jìn)制并取其前4位即得符號S4的碼字為1100（省去了“0.”，有的浮點數(shù)不能完全轉(zhuǎn)化，轉(zhuǎn)化時只需完成前Ni位即可）。表10-3香農(nóng)-范諾編碼除此之外，還有二分法香農(nóng)-范諾編碼方法。其步驟如下：（1）首先統(tǒng)計出每個符號出現(xiàn)的概率；（2）從左到右對上述概率從大到小排序；（3）從這個概率集合中的某個位置將其分為兩個子集合，并盡量使兩個子集合的概率和近似相等，給前面一個子集合賦值為0，后面一個子集合賦值為1；（4）重復(fù)步驟3，直到各個子集合中只有一個元素為止；（5）將每個元素所屬的子集合的值依次串起來，即可得到各個元素的香農(nóng)-范諾編碼。表10-4二分法香農(nóng)-范諾編碼10.4行程編碼10.4.1行程編碼基本方法

行程編碼又稱行程長度編碼（RunLengthEncoding，RLE），是一種熵編碼，其編碼原理相當(dāng)簡單，即將具有相同值的連續(xù)串用其串長和一個代表值來代替，該連續(xù)串就稱為行程，串長稱為行程長度。例如，有一字符串“aabbbcddddd”，則經(jīng)行程長度編碼后，該字符串可以只用“2a3b1c5d”來表示。行程編碼分為定長和不定長編碼兩種。定長編碼是指編碼的行程長度所用的二進(jìn)制位數(shù)固定，而變長行程編碼是指對不同范圍的行程長度使用不同位數(shù)的二進(jìn)制位數(shù)進(jìn)行編碼。使用變長行程編碼需要增加標(biāo)志位來表明所使用的二進(jìn)制位數(shù)。行程編碼比較適合于二值圖像的編碼，一般用于量化后出現(xiàn)大量零系數(shù)連續(xù)的場合，用行程來表示連零碼。如果圖像是由很多塊顏色或灰度相同的大面積區(qū)域組成的，那么采用行程編碼可以達(dá)到很高的壓縮比。如果圖像中的數(shù)據(jù)非常分散，則行程編碼不但不能壓縮數(shù)據(jù)，反而會增加圖像文件的大小。為了達(dá)到較好的壓縮效果，一般不單獨采用行程編碼，而是和其他編碼方法結(jié)合使用。例如，在JPEG中，就綜合使用了行程編碼、DCT、量化編碼以及哈夫曼編碼，先對圖像作分塊處理，再對這些分塊圖像進(jìn)行離散余弦變換（DCT），對變換后的頻域數(shù)據(jù)進(jìn)行量化并作Z字形掃描，接著對掃描結(jié)果作行程編碼，對行程編碼后的結(jié)果再作哈夫曼編碼。10.4.2PCX文件中的行程編碼

PCX文件分為文件頭和圖像壓縮數(shù)據(jù)兩個部分。如果是256色圖像，則還有一個256色調(diào)色板存于文件尾部。文件頭全長128字節(jié)，包含了圖像的大小和顏色以及PCX文件的版本標(biāo)識等信息，圖像壓縮數(shù)據(jù)緊跟在文件頭之后。如果沒有使用調(diào)色板，那么圖像壓縮數(shù)據(jù)存儲的是實際像素值；否則，存儲的是調(diào)色板的索引值。當(dāng)壓縮數(shù)據(jù)是實際的像素值時，它們按顏色平面和掃描行存儲，即每行先存儲所有R分量，再存儲所有G分量，最后存儲所有B分量，一行數(shù)據(jù)存儲完后，接著存儲下一行數(shù)據(jù)。如果使用了調(diào)色板，則不會分解為單獨的顏色平面存儲。讀者可以查閱圖像文件格式的相關(guān)書籍了解PCX文件的詳細(xì)格式。下面以256色PCX文件為例，說明PCX文件中的行程編碼。在256色PCX文件中，每個像素占一字節(jié)，壓縮數(shù)據(jù)以字節(jié)為單位逐行進(jìn)行編碼，每行填充到偶數(shù)字節(jié)。PCX文件規(guī)定編碼時的最大行程長度為63，如果行程長度大于63，則必須分多次存儲。對于長度大于1的行程，編碼時先存入其行程長度（長度L加上192即0xC0），再存入該行程的代表值，行程長度和行程的代表值分別占一字節(jié)。對于長度為1的行程，即單個像素，如果該像素的值小于或等于0xC0，則編碼時直接存入該像素值，而不存儲長度信息；否則，先存入0xC1，再存入該像素值，這樣做的目的是為了避免該像素值被誤認(rèn)為長度信息。例如，連續(xù)100個灰度值為0x80的像素，其編碼(以十六進(jìn)制表示)應(yīng)為FF802580。上面的編碼中出現(xiàn)FF的長度信息是由63與0xC0相加所得。對256色PCX文件解碼時，首先從壓縮數(shù)據(jù)部分讀取一個字節(jié)，判斷該值是否大于0xC0，如果是，則表明該字節(jié)是行程長度信息，取其低六位（相當(dāng)于減去0xC0）作為行程長度L，讀取下一個字節(jié)作為像素值并重復(fù)L次存入圖像數(shù)據(jù)緩沖區(qū)；否則，直接將該字節(jié)存入圖像數(shù)據(jù)緩沖區(qū)。雖然幾乎所有的圖像應(yīng)用軟件都支持PCX文件格式，但由于它的壓縮比不高，因而現(xiàn)在用得不是很多。10.5LZW編碼10.5.1LZW編碼方法

LZW（Lempel-Ziv&Welch）編碼又稱字串表編碼，屬于一種無損編碼，是Welch將Lempel和Ziv所提出的無損壓縮技術(shù)改進(jìn)后的壓縮方法。LZW編碼與行程編碼類似，也是對字符串進(jìn)行編碼從而實現(xiàn)壓縮，但它在編碼的同時還生成了特定字符串以及與之對應(yīng)的索引字符串表。LZW編碼的基本思想是：在編碼過程中，將所遇到的字符串建立一個字符串表，表中的每個字符串都對應(yīng)一個索引，編碼時用該字符串在字串表中的索引來代替原始的數(shù)據(jù)串。例如，一幅8位的灰度圖像，我們可以采用12位來表示每個字符串的索引，前256個索引用于對應(yīng)可能出現(xiàn)的256種灰度，由此可建立一個初始的字符串表，而剩余的3840個索引就可分配給在壓縮過程中出現(xiàn)的新字符串，這樣就生成了一個完整的字符串表，壓縮數(shù)據(jù)就可以只保存它在字符串表中的索引，從而達(dá)到壓縮數(shù)據(jù)的目的。字符串表是在壓縮過程中動態(tài)生成的，不必將它保存在壓縮文件里，因為解壓縮時字符串表可以由壓縮文件中的信息重新生成。GIF（GraphicsInterchangeFormat）最初是由美國CompuServe于1987年開發(fā)的一種壓縮位圖格式。它可支持多達(dá)256種的顏色，具有極佳的壓縮效率，已成為Internet上一種流行的文件格式。GIF圖像文件采用的是一種改良的LZW壓縮算法，通常稱為GIF-LZW壓縮算法。GIF圖像文件以塊（又稱為區(qū)域結(jié)構(gòu)）的方式來存儲圖像相關(guān)的信息，具體的文件格式可參考圖像文件格式的相關(guān)書籍。下面簡要介紹GIF-LZW的編碼方法。設(shè)S1、S2為兩個存放字符串的臨時變量，LZW_CLEAR和LZW_EOI分別為字符表初始化標(biāo)志和編碼結(jié)束標(biāo)志，GIF-LZW的編碼步驟如下：（1）根據(jù)圖像中使用的顏色數(shù)初始化一個字串表，字串表中的每個顏色對應(yīng)一個索引。在初始字串表的末尾再添加兩個符號（LZW_CLEAR和LZW_EOI）的索引。設(shè)置字符串變量S1、S2并初始化為空。（2）接著輸出LZW_CLEAR在字串表中的索引。（3）從圖像數(shù)據(jù)流中第一個字符（假設(shè)數(shù)據(jù)以字符串表示）開始，每次讀取一個字符，將其賦給字符串變量S2。（4）判斷“S1+S2”是否已存在于字串表中。如果字串表中存在“S1+S2”，則S1=S1+S2；否則，輸出S1在字串表中的索引，并在字串表末尾為“S1+S2”添加索引，同時，S1=S2。（5）重復(fù)第3和第4步，直到所有字符讀完為止。（6）輸出S1中的字符串在字串表中的索引，然后輸出結(jié)束標(biāo)志LZW_EOI的索引，編碼完畢。GIF-LZW的解碼過程比較復(fù)雜，它和編碼過程正好相反，即將編碼后的碼字轉(zhuǎn)換成對應(yīng)的字符串，重新生成字串表，然后依次輸出對應(yīng)的字符串即可。GIF-LZW的解碼流程如圖10-2所示，表中的Code和OldCode是兩個存放索引的臨時變量。圖10-2GIF-LZW解碼流程10.5.2LZW編碼實例

設(shè)有一來源于4色（以a、b、c、d表示）圖像的數(shù)據(jù)流aabcabbbbd，現(xiàn)對其進(jìn)行LZW編碼。編碼過程如下：編碼前，首先需要初始化一個字符串表。由于圖像中只有四種顏色，因而我們可以只用4比特表示字符串表中每個字符串的索引，表中的前4項代表4種顏色，后兩項分別表示初始化和圖像結(jié)束標(biāo)志，建立的初始化字符串表如表10-5所示。接著把S1和S2初始化為空（即NULL），輸出LZW_CLEAR的在字符串表中的索引值4H，接下來是對圖像數(shù)據(jù)的編碼。表10-5初始化字符串表讀取圖像數(shù)據(jù)流的第一個字符“a”，賦給S2，因S1+S2=“a”已存在字串表中，所以S1=S1+S2=“a”。接著讀入下一個字符“a”賦給S2，因S1+S2=“aa”不存在于字串表中，所以輸出S1=“a”的索引0H，同時在字符串表末尾添加新字符串“aa”的索引6H，并使S1=S2=“a”。依次讀取數(shù)據(jù)流中的每個字符，如果S1+S2沒有出現(xiàn)在字符串表中，則輸出S1中的字符串的索引，并在字符串表末尾為新字符串S1+S2添加索引，并使S1=S2；否則，不輸出任何結(jié)果，只是使S1=S1+S2。所有字符處理完畢后，輸出S1中的字符串的索引，最后輸出結(jié)束標(biāo)志LZW_EOI的索引。至此，編碼完畢，完整的編碼過程如表10-6所示，最后的編碼結(jié)果為“4001271B35”（以十六進(jìn)制表示）。表10-6GIF-LZW編碼過程下面對上述編碼結(jié)果“4001271B35”進(jìn)行解碼。按圖10-2的解碼流程，首先讀取第一個編碼Code=4H，由于它為LZW_CLEAR，因此需初始化字符串表，結(jié)果如表10-5所示（在實際應(yīng)用中，可根據(jù)文件頭中給定的信息建立初始字符串表）。讀入下一個編碼Code=0H，由于它不等于LZW_CLEAR，因此輸出字串表中0H對應(yīng)的字符串“a”，同時使OldCode=Code=0H。讀入下一個編碼Code=0H，由于字串表中存在該索引，因此輸出0H所對應(yīng)的字符串“a”，然后將OldCode=0H所對應(yīng)的字符串“a”加上Code=0H所對應(yīng)的字符串的第一個字符“a”，即“aa”添加到字串表中，其索引為6H，同時使ldCode=Code=0H。讀入下一個編碼Code=1H，由于字串表中存在該索引，因此輸出1H所對應(yīng)的字符串“b”，然后將OldCode=0H所對應(yīng)的字符串“a”加上Code=1H所對應(yīng)的字符串的第一個字符“b”，即“ab”添加到字串表中，其索引為7H，同時使OldCode=Code=1H。讀入下一個編碼Code=2H，由于字串表中存在該索引，因此輸出2H所對應(yīng)的字符串“c”，然后將OldCode=1H所對應(yīng)的字符串“b”加上Code=2H所對應(yīng)的字符串的第一個字符“c”，即“bc”添加到字串表中，其索引為8H，同時使OldCode=Code=2H。讀入下一個編碼Code=7H，由于字串表中存在該索引，因此輸出7H所對應(yīng)的字符串“ab”，然后將OldCode=2H所對應(yīng)的字符串“c”加上Code=7H所對應(yīng)的字符串的第一個字符“a”，即“ca”添加到字串表中，其索引為9H，同時使OldCode=Code=7H。讀入下一個編碼Code=1H，由于字串表中存在該索引，因此輸出1H所對應(yīng)的字符串“b”，然后將OldCode=7H所對應(yīng)的字符串“ab”加上Code=1H所對應(yīng)的字符串的第一個字符“b”，即“abb”添加到字串表中，其索引為AH，同時使OldCode=Code=1H。讀入下一個編碼Code=BH，由于字串表中不存在該索引，因此輸出OldCode=1H所對應(yīng)的字符串“b”加上該字符串的第一個字符“b”，即“bb”，同時將“aa”添加到字串表中，其索引為BH，同時使OldCode=Code=BH。讀入下一個編碼Code=3H，由于字串表中存在該索引，因此輸出其對應(yīng)的字符串“d”，然后將OldCode=BH所對應(yīng)的字符串“bb”加上Code=3H所對應(yīng)的字符串的第一個字符“d”，即“bbd”添加到字串表中，其索引為CH，同時使OldCode=Code=3H。讀入下一個編碼Code=5H，它等于LZW_EOI，數(shù)據(jù)解碼完畢，最后的解碼結(jié)果為aabcabbbbd。為清晰起見，完整的解碼過程如表10-7所示。表10-7GIF-LZW解碼過程10.6算術(shù)編碼算術(shù)編碼有兩種模式：一種是基于信源概率統(tǒng)計特性的固定編碼模式，另一種是針對未知信源概率模型的自適應(yīng)模式。自適應(yīng)模式中各個符號的概率初始值都相同，它們依據(jù)出現(xiàn)的符號而相應(yīng)地改變。只要編碼器和解碼器都使用相同的初始值和相同的改變值的方法，那么它們的概率模型將保持一致。上述兩種形式的算術(shù)編碼均可用硬件實現(xiàn)，其中自適應(yīng)模式適用于不進(jìn)行概率統(tǒng)計的場合。有關(guān)實驗數(shù)據(jù)表明，在未知信源概率分布的情況下，算術(shù)編碼一般要優(yōu)于Huffman編碼。在JPEG擴(kuò)展系統(tǒng)中，就用算術(shù)編碼取代了哈夫曼編碼。下面結(jié)合一個實例來闡述固定模式的算術(shù)編碼的具體方法。設(shè)一待編碼的數(shù)據(jù)序列（即信源）為“dacab”，信源中各符號出現(xiàn)的概率依次為P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。首先，數(shù)據(jù)序列中的各數(shù)據(jù)符號在區(qū)間［0,1］內(nèi)的間隔（賦值范圍）設(shè)定為a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d=［0.8,1.0）為便于討論，再給出一組關(guān)系式：StartN=StartB+LeftC×L

EndN=StartB+RightC×L

式中，StartN、EndN分別表示新間隔（或稱之為區(qū)間）的起始位置和結(jié)束位置，StartB表示前一間隔的起始位置，L為前一間隔的長度，LeftC、RightC分別表示當(dāng)前編碼符號的初始區(qū)間的左端和右端。第一個被壓縮的符號為“d”，其初始間隔為［0.8,1.0)；第二個被壓縮的符號為“a”，由于前面的符號“d”的取值區(qū)間被限制在［0.8,1.0)范圍內(nèi)，所以“a”的取值范圍應(yīng)在前一符號間隔［0.8,1.0)的［0,0.4)子區(qū)間內(nèi)，根據(jù)上式可知StartN=0.8+0×(1.0-0.8)=0.8EndN=0.8+0.4×(1.0-0.8)=0.88即“a”的實際編碼區(qū)間在［0.8,0.88)之間。第三個被壓縮的符號為“c”，其編碼取值范圍應(yīng)在［0.8,0.88)區(qū)間的［0.6,0.8)的子區(qū)間內(nèi)，據(jù)上式可知第四個被壓縮的符號為“a”，同理，根據(jù)上式可知StartN=0.848+0×(0.864-0.848)=0.848EndN=0.848+0.4×(0.864-0.848)=0.8544第五個被壓縮的符號為“b”，同理，根據(jù)上式可知StartN=0.848+0.4×(0.8544-0.848)=0.84856EndN=0.848+0.6×(0.8544-0.848)=0.85144至此，數(shù)據(jù)序列“dacab”已被描述為一個實數(shù)區(qū)間［0.85056,0.85184］，或者說在此區(qū)間內(nèi)的任一實數(shù)值都惟一對應(yīng)該數(shù)據(jù)序列。這樣，就可以用一個實數(shù)表示這一數(shù)據(jù)序列。我們把區(qū)間［0.85056,0.85184］用二進(jìn)制形式表示為［0.110110011011,0.110110100001］。從這個區(qū)間可以看出，0.1101101位于這個區(qū)間內(nèi)并且其編碼最短，故把其作為數(shù)據(jù)序列“dacab”的編碼輸出。考慮到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有“0.”，所以在編碼時，可以不考慮“0.”，于是把1101101作為本例中的數(shù)據(jù)序列的算術(shù)編碼。由此可見，數(shù)據(jù)序列“dacab”用7比特的二進(jìn)制代碼就可以表示，平均碼長為1.4比特／字符。解碼是編碼的逆過程，根據(jù)編碼時的概率分配表和壓縮后數(shù)據(jù)代碼所在的范圍，確定代碼所對應(yīng)的每一個數(shù)據(jù)符號。由此可見，算術(shù)編碼的實現(xiàn)方法要比哈夫曼編碼復(fù)雜一些。10.7JPEG編碼10.7.1JPEG基本系統(tǒng)編碼JPEG是面向靜態(tài)圖像編碼的國際標(biāo)準(zhǔn)。在相同圖像質(zhì)量條件下，JPEG文件擁有比其他圖像文件格式更高的壓縮比。JPEG目前被廣泛應(yīng)用于多媒體和網(wǎng)絡(luò)程序中，是現(xiàn)今萬維網(wǎng)中使用最廣泛的兩種圖像文件格式之一。JPEG是一種有損壓縮，即在壓縮過程中會丟失數(shù)據(jù)，每次編輯JPEG圖像后，圖像就會被重復(fù)壓縮一次，損失就會有所增加。JPEG允許四種編碼模式：（1）順序式（Sequential）DCT方式：從左到右、從上到下對圖像順序進(jìn)行基于離散余弦變換（DCT）的編碼。DCT理論上是可逆的，但在計算時存在誤差，因而基于DCT的編碼模式是一種有損編碼。（2）漸進(jìn)式（Progressive）DCT方式：基于DCT，對圖像分層次進(jìn)行處理，從模糊到清晰地傳輸圖像（與GIF文件的交錯方式類似）。有兩種實現(xiàn)方法，一種是頻譜選擇法，即按Z形掃描的序號將DCT量化序數(shù)分成幾個頻段，每個頻段對應(yīng)一次掃描，每塊均先傳送低頻掃描數(shù)據(jù)，得到原圖概貌，再依次傳送高頻掃描數(shù)據(jù)，使圖像逐漸清晰；另一種是逐次逼近法，即每次掃描全部DCT量化序數(shù)，但每次的表示精度逐漸提高。（3）無失真（Lossless）方式：使用線性預(yù)測器，如DPCM，而不是基于DCT。（4）分層（Hierarchical）方式：在空間域?qū)⒃磮D像以不同的分辨率表示，每個分辨率對應(yīng)一次掃描，處理時可以基于DCT或預(yù)測編碼，可以是漸進(jìn)式，也可以是順序式。JPEG定義了三種系統(tǒng)：基本系統(tǒng)（BaselineSystem）、擴(kuò)展系統(tǒng)（ExtendedSystem）和無失真壓縮系統(tǒng)（LosslessSystem）。一個符合JPEG標(biāo)準(zhǔn)的編解碼器至少要滿足基本系統(tǒng)的技術(shù)指標(biāo)?；镜腏PEG算法屬于變換類編碼，下面針對基于DCT的順序式基本系統(tǒng)編碼來說明JPEG的編碼方法。圖10-3JPEG編碼流程圖1）數(shù)據(jù)分塊對圖像進(jìn)行編碼前，將每個分量圖像分割成不重疊的8×8像素塊，每一個8×8像素塊稱為一個數(shù)據(jù)單元（DU）。在彩色圖像中，JPEG分別壓縮圖像的每個彩色分量。雖然JPEG可以壓縮通常的紅綠藍(lán)分量，但在YCbCr空間的壓縮效果會更好。這是因為人眼對色彩的變化不如對亮度的變化敏感，因而對色彩的編碼可以比對亮度的編碼粗糙些，這主要體現(xiàn)在不同的采樣頻率和量化精度上。因此，編碼前一般先將圖像從RGB空間轉(zhuǎn)換到Y(jié)CbCr空間，再把各分量圖像分割成8×8數(shù)據(jù)塊。在對圖像采樣時，可以采用不同的采樣頻率，這種技術(shù)稱為二次采樣。由于亮度比色彩更重要，因而對Y分量的采樣頻率可高于對Cb、Cr的采樣頻率，這樣有利于節(jié)省存儲空間。常用的采樣方案有YUV422和YUV411。把采樣頻率最低的分量圖像中一個DU所對應(yīng)的像區(qū)上覆蓋的所有各分量上的DU按順序編組為一個最小編碼單元（MCU）。對灰度圖像而言，只有一個Y分量，MCU就是一個數(shù)據(jù)單元。而對彩色