多媒體技術(shù)07壓縮與熵編碼

1、第二篇 壓縮與編碼數(shù)字信號的壓縮與編碼是多媒體的核心技術(shù)和重要內(nèi)容。在第3章所講的，音頻信號的自適應編碼、差分編碼和預測編碼等，都是典型的壓縮編碼。本篇先介紹壓縮的基本概念，再講解可用于靜態(tài)圖像編碼的若干常用熵編碼壓縮算法，然后介紹DCT與JPEG編碼、運動圖像和伴音的MPEG編碼壓縮算法、新興的H.264/AVC視頻編碼、以及可以用于JPEG 2000和MPEG-4編碼的小波變換。本篇分為如下5章：n 第7章 壓縮與熵編碼n 第8章 DCT與JPEG編碼n 第9章 MPEG編碼方法n 第10章 n 第11章 小波變換與JPEG 2000編碼第7章 壓縮與熵編碼由于多媒體信號的數(shù)據(jù)量巨大，為了

2、節(jié)省存儲空間和傳輸帶寬，需進行壓縮編碼。多媒體數(shù)據(jù)的壓縮方法，可以分成三大類，其中的熵編碼是基礎(chǔ)，源編碼是重點，而將它們二者相結(jié)合的混合編碼則是各種編碼標準所采用的主要方法。本章先介紹壓縮的基本概念，包括：壓縮的需要與可能、算法的特點與分類和一般的編碼過程。然后，在了解熵定義的基礎(chǔ)上，討論若干常用的熵編碼算法，包括：Shannon-Fano編碼、Huffman編碼、算術(shù)編碼、RLE和可用于GIF和PNG圖像編碼LZW算法。7.1 壓縮概論數(shù)據(jù)壓縮(data compression) ，在電子與通信領(lǐng)域也常被稱為信號編碼(signal coding)，包括壓縮（compress）和還原（deco

3、mpress，解壓縮/重構(gòu)）即編碼（encode/code）和解碼（decode，譯碼）兩個步驟。與壓縮相關(guān)的學科有：信息論、數(shù)學、信號處理、數(shù)據(jù)壓縮、編碼理論和方法。 壓縮的需要與可能由于多媒體信號的數(shù)據(jù)量巨大，所以需要壓縮；同時，由于在多媒體數(shù)據(jù)中，存在著各種冗余，所以可以壓縮。l 壓縮的需要數(shù)據(jù)量巨大是多媒體信號的特點，例如：n 一幅1024*1024真彩圖：1024行 * 1024列 * 3B彩色 = 3MBn 4分鐘的CD音樂：44100樣本/秒 * 2B(16b)/樣 * 2聲道 * 60秒 * 4分鐘 = 40.37MBn 90分鐘的PAL視頻：625行 * 864列 * 3B彩

4、色 * 25幀/秒 * 60秒 * 90分為了節(jié)省存儲空間和傳輸帶寬、進行實時高質(zhì)的多媒體通信（如視頻/音頻點播、網(wǎng)絡(luò)現(xiàn)場直播、可視電話、視頻會議等），必須對多媒體數(shù)據(jù)進行壓縮編碼。l 壓縮的可能多媒體數(shù)據(jù)和人類感覺存在著各種冗余：n 空間冗余：圖像的相鄰像素相關(guān)；n 時間冗余：相鄰音頻樣本相關(guān)、相鄰視頻幀相關(guān)；n 信道冗余：（環(huán)繞）立體聲的聲道之間相關(guān)、立體電影/電視的左右視覺信號之間相關(guān)；n 頻率冗余：相鄰的頻譜值相關(guān)，人對高頻信號不敏感或分辨率低；n 統(tǒng)計冗余：信號中有的字符出現(xiàn)的頻率高，可以采用較短的編碼；有的有的信號特征有標度不變性或統(tǒng)計自相似性（如紋理和分形等）；n 結(jié)構(gòu)冗余：多媒

5、體數(shù)據(jù)存在分布模式，相近的圖區(qū)可分類（用于矢量量化方法）；n 聽覺冗余：人耳的低音聽閾高、強純音的頻率屏蔽、相鄰聲音的時域屏蔽；n 視覺冗余：人眼對亮度變化比對色彩的變化更敏感、對高亮區(qū)的量化誤差不敏感、視網(wǎng)膜分頻道。 壓縮算法的特點與分類用于多媒體數(shù)據(jù)的壓縮方法眾多，可按主要特點將它們分成不同的類型。l 特點n 無損與有損u 無損壓縮：能夠無失真地從壓縮后的數(shù)據(jù)重構(gòu)，準確地還原原始數(shù)據(jù)?？捎糜趯?shù)據(jù)的準確性要求嚴格的場合，如可執(zhí)行文件和普通文件的壓縮、磁盤的壓縮，也可用于多媒體數(shù)據(jù)的壓縮。該方法的壓縮比一般較小。如差分編碼、RLE、Huffman編碼、LZW編碼、算術(shù)編碼等。u 有損壓縮：有

6、失真，不能完全準確地恢復原始數(shù)據(jù)，重構(gòu)的數(shù)據(jù)只是原始數(shù)據(jù)的一個近似。可用于對數(shù)據(jù)的準確性要求不高的場合，如多媒體數(shù)據(jù)的壓縮。該方法的壓縮比一般較大。例如預測編碼、音感編碼、JPEG、MPEG等。n 對稱性若編解碼算法的復雜性和所需時間差不多，則為對稱的編碼方法，多數(shù)壓縮算法都是對稱的。但也有不對稱的，一般是編碼難而解碼容易，如Huffman編碼與分形編碼。但用于密碼學的編碼方法則相反，是編碼容易，而解碼則非常非常難。n 幀間與幀內(nèi)在視頻編碼中會同時用到幀內(nèi)與幀間的編碼方法，幀內(nèi)編碼是指在一幀圖像內(nèi)獨立完成的編碼方法，同靜態(tài)圖像的編碼，如JPEG；而幀間編碼則需要參照前后幀才能進行編解碼，并在編

7、碼過程中考慮對幀之間的時間冗余的壓縮，如MPEG。n 實時性在有些多媒體的應用場合，需要實時處理或傳輸數(shù)據(jù)（如現(xiàn)場的數(shù)字錄音和錄影、播放MP3/RM/VCD/DVD、視頻/音頻點播、網(wǎng)絡(luò)現(xiàn)場直播、可視電話、視頻會議），編解碼一般要求延時50ms。這需要簡單/快速/高效的算法和高速/復雜的CPU/DSP芯片。n 分級處理有些壓縮算法可以同時處理不同分辨率、不同傳輸速率、不同質(zhì)量水平的多媒體數(shù)據(jù)，如JPEG2000、MPEG-2/4。l 分類1. 熵編碼熵編碼(entropy encoding)是一類利用數(shù)據(jù)的統(tǒng)計信息進行壓縮的無語義數(shù)據(jù)流的無損編碼。信息熵為信源的平均信息量（不確定性的度量）。常

8、見的熵編碼有：行程編碼(RLE)、LZW編碼、香農(nóng)編碼、哈夫曼編碼和算術(shù)編碼等。2. 信源編碼（信）源編碼(source coding)是一類利用信號原數(shù)據(jù)在時間域和頻率域中的相關(guān)性和冗余進行壓縮的用語義常有損的編碼。種類繁多，可進一步分為：u 預測編碼(predictive coding)：利用先前和現(xiàn)在的數(shù)據(jù)對在時間或空間上相鄰的下面或后來的數(shù)據(jù)進行預測，從而達到壓縮的目的。如增量調(diào)制(DM)、差分和自適應編碼(ADPCM)等；u 變換編碼(transformation coding)：采用各種數(shù)學變換方法，將原時間域或空間域的數(shù)據(jù)變換到頻率域或其他域，利用數(shù)據(jù)在變換域中的冗余或人類感覺的

9、特征來進行壓縮。常見的變換編碼有：FFT（快速富立葉變換）、DCT（離散余弦變換）、DWT（離散小波變換）和IFS（迭代函數(shù)系統(tǒng)）等；u 分層編碼(layered coding)：將原數(shù)據(jù)在時空域或頻率域上分成若干子區(qū)域，利用人類感覺的特征進行壓縮編碼，然后再合并。如二值位(bit position)、子采樣(subsampling)、子帶編碼(sub-band coding)等；u 其他編碼：包括矢量量化(vector quantization)、運動補償(motion compensation)、音感編碼(perceptual audio coding)等。3. 混合編碼混合編碼(hybr

10、id coding) = 熵編碼 + 源編碼。大多數(shù)壓縮標準都采用混合編碼的方法進行數(shù)據(jù)壓縮，一般是先利用信源編碼進行有損壓縮，再利用熵編碼做進一步的無損壓縮。如H.263、JPEG、MPEG等。表7-1是常見編碼方法的匯總。表7-1 常見編碼算法PCM預測變換熵其他圖像視頻線性PCM非線性A/自適應量化APCM差分DM自適應ADPCMFFTDCTDWTW-HHaarK-LSlantRLELZWShannonFanoHuffman算術(shù)矢量量化子帶輪廓二值音感對象方塊漸顯逐層內(nèi)插比特平面抖動幀內(nèi)預測幀間編碼幀間預測運動估計運動補償條件補償內(nèi)插其中，W-H = Walsh-Hadamard沃爾什-

11、哈達馬、K-L = Karhumen-Loeve卡乎門-勞夫。 編碼過程編碼的主要過程是：壓縮存儲/傳輸解壓縮，在進行編碼之前一般還需要進行若干準備工作。在各種編碼的準備工作中，主要是模數(shù)轉(zhuǎn)換(A/D)和預處理。n A/D轉(zhuǎn)換（Analog-to-Digital conversion）：將在時空和取值上都連續(xù)的模擬數(shù)據(jù)，經(jīng)過采樣(sampling)和量化(quantization)變成離散的數(shù)字信號：n 預處理（pretreatment）：指對得到的初始數(shù)字信號進行必要的處理，包括過濾、去噪、增強、修復等；目的是除去數(shù)據(jù)中的不必要成分、提高信號的信噪比、修復數(shù)據(jù)的錯誤等。多媒體數(shù)據(jù)編解碼的一般

12、過程為：A/D 預處理 壓縮 存儲多媒體信號 數(shù)字信號 處理過的數(shù)字信號 壓縮數(shù)據(jù) (子)采樣/量化 過濾/去噪/增強/修復源編碼/熵編碼 傳輸存儲 解碼 D/A 壓縮數(shù)據(jù) 重構(gòu)的數(shù)字信號 顯示/播放傳輸 還原/重構(gòu)(插值)圖7-1 多媒體數(shù)據(jù)的編解碼過程7.2 熵編碼熵編碼(entropy encoding)是一類利用數(shù)據(jù)的統(tǒng)計信息進行壓縮的無語義數(shù)據(jù)流之無損編碼。本章先介紹熵的基本概念，然后介紹哈夫曼(Huffman)編碼、算術(shù)編碼(arithmetic coding)、行程編碼(RLE)和LZW編碼等常用的熵編碼方法。 熵熵(entropy)本來是熱力學中用來度量熱力學系統(tǒng)無序性的一種物

13、理量（熱力學第二定律：孤立系統(tǒng)內(nèi)的熵恒增）：對可逆過程，（孤立系統(tǒng)）其中，S為熵、Q為熱量、T為絕對溫度。（信息）熵H的概念則是美國數(shù)學家Claude Elwood Shannon（香農(nóng)/仙農(nóng)/向農(nóng)）于1948年在他所創(chuàng)建的信息論中引進的，用來度量信息中所含的信息量：（為自信息量的均值數(shù)學期望）其中，H為信息熵（單位為bit），S為信源，pi為符號si在S中出現(xiàn)的概率。例如，一幅用256級灰度表示的圖像，若每種灰度的象素點出現(xiàn)概率均為pi=1/256，則即編碼每一個象素點都需要8位(I )，平均每一個象素點也需要8位(H)。熵編碼(entropy encoding)是一類利用數(shù)據(jù)的統(tǒng)計信息，對

14、無語義的數(shù)據(jù)流進行壓縮的無損型編碼。熵可用來度量數(shù)據(jù)中所包含的信息量，也可以用于刻畫熵編碼的下限。7.2.2 Huffman編碼David Albert Huffman（哈夫曼/赫夫曼/霍夫曼）在MIT攻讀博士學位期間于1952年提出了一種從下到上的編碼方法，現(xiàn)在被稱為Huffman編碼，它是一種統(tǒng)計最優(yōu)的變碼長符號編碼，讓最頻繁出現(xiàn)的符號具有最短的編碼。Huffman編碼被廣泛用于多種壓縮算法之中，如JPEG和MPEG等。l 編碼過程與步驟Huffman編碼的過程 = 自底向頂生成一棵二叉樹（H樹），樹中的葉節(jié)點為被編碼符號及其概率、中間節(jié)點為兩個概率最小符號（串）的并所構(gòu)成的符號串及其概率

15、所組成的父節(jié)點、根節(jié)點為所有符號之串及其概率1。具體編碼步驟為：(1) 將符號按概率從小到大順序從左至右排列葉節(jié)點；(2) 連接兩個概率最小的頂層節(jié)點來組成一個父節(jié)點，并在到左右子節(jié)點的兩條連線上分別標記0和1；(3) 重復步驟2，直到得到根節(jié)點，形成一棵二叉樹；(4)從根節(jié)點開始到相應于每個符號的葉節(jié)點的0/1串，就是該符號的二進制編碼。由于符號按概率大小的排列既可以從左至右、又可以從右至左，而且左右分枝哪個標記為0哪個標記為1是無關(guān)緊要的，所以最后的編碼結(jié)果可能不唯一，但這僅僅是分配的代碼不同，而代碼的平均長度是相同的。表7-2 符號出現(xiàn)的次數(shù)l 例子符號ABCDE出現(xiàn)的次數(shù)2010515

16、10例如，有一幅40個象素組成的灰度圖像，灰度共有5級，分別用符號A、B、C、D和E表示，40個象素中各級灰度出現(xiàn)次數(shù)見表7-2。如果直接用二進制編碼，則5個等級的灰度值需要3位表示，也就是每個象素用3位表示，編碼這幅圖像總共需要60 * 3 = 180位。按照香農(nóng)理論，這幅圖像的熵為H = (20/60)×log2(60/20) + (10/60)×log2 (60/10) + (5/60)×log2(60/5) + (15/60)×log2 (60/15) + (10/60) ×log2 (60/10) 即平均每個符號用2.189位表示就夠

17、了，60個象素共需用131.33位，壓縮比約為3 / 2.189 1.37 : 1。下面對該圖像進行Huffman編碼，參見圖7-2和表7-3。CE(1/4)第1步： 0 1C(1/12) E(1/6)B(1/6)D(1/4)A(1/3)CE(1/4) BD(5/12)第2步： 0 1 0 1C(1/12) E(1/6)B(1/6)D(1/4)A(1/3) ACE(7/12) 01第3步： CE(1/4) BD(5/12) 01 0 1C(1/12) E(1/6)A(1/3) B(1/6) D(1/4) ABCDE(1) 0 1 ACE(7/12) 第4步： 01 CE(1/4)BD(5/12

18、) 01 0 1 C(1/12) E(1/6)A(1/3) B(1/6) D(1/4)圖7-2 Huffman編碼過程例符號次數(shù)(pi)log2(1/pi)編碼需位數(shù)A20 (1/3)1.5850140B10 (1/6)851020C5 (1/12)3.58500015D15 (1/4)2.0001130E10 (1/6)8500130合計60 (1)135表7-3 Huffman算法舉例表平均碼長為135/60 = 2.25，壓縮比為180/135 = 4/3 1.33 : 1。l 特點與問題哈夫曼編碼的碼長雖然都是可變的，但卻不需要另外附加同步代碼（即在譯碼時分割符號的特殊代碼）。這時因為

19、每個符號都是二叉樹的葉結(jié)點，它們都沒有子節(jié)點（即某個符號編碼開頭的另一個符號編碼）。如上例中，若哈夫曼編碼的碼串中的頭兩位為01，那末肯定是符號A，因為表示其他符號的代碼沒有一個是以01開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現(xiàn)“000”，那么它就代表符號C。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿（H表），那么就可以根據(jù)碼簿一個碼一個碼地依次進行譯碼。但是哈夫曼編碼存在兩個值得注意的問題：n 沒有錯誤保護功能在譯碼時，如果碼串中有哪怕僅僅是1位出現(xiàn)錯誤，則不但這個碼本身譯錯，而且后面的碼都會跟著錯。稱這種現(xiàn)象為錯誤傳播，計算機對這種錯誤也無能為力，不能知道錯誤

20、出在哪里，更談不上去糾正它。n 不能隨機定位因是可變長度碼，因此很難在壓縮文件中直接對指定音頻或圖像位置的內(nèi)容進行譯碼，這就需要在存儲代碼之前加以考慮。盡管存在上面這些問題，但哈夫曼編碼還是得到了廣泛應用。l H表與自適應哈夫曼編碼利用哈夫曼方法進行編解碼，在編碼時需要計算造H表（哈夫曼表），存儲和傳輸時需要存儲和傳輸H表，解碼時則需要查H表。有時為了加快編碼速度、減少存儲空間和傳輸帶寬，可以對多媒體數(shù)據(jù)使用標準的H表，但其壓縮率一般比計算所造的表稍低。所以，如果只關(guān)心編碼速度、存儲空間和傳輸帶寬，可以采用標準H表方法；如果更關(guān)心壓縮質(zhì)量和壓縮比，則可以自己計算造H表。即使是計算造表，也一般只

21、對高頻符號計算編碼，而對其他符號則直接編碼。這種方法尤其適用于有大量不同的輸入符號，但只有少數(shù)高頻符號的情況。還有一種自適應哈夫曼編碼(adaptive Huffman coding)，不需要存儲和傳輸H表，而是按與編碼嚴格一致的方法建立同樣的H表，還可以利用兄弟節(jié)點的特征來加快更新H樹的過程。由于篇幅有限，這里就不做詳細介紹。7.2.3 算術(shù)編碼算術(shù)編碼(arithmetic coding)是由P.Elias于1960年提出雛形、算法，由Rissanen和G.G.Langdon于1979年系統(tǒng)化并于1981年實現(xiàn)，最后由Rissanen于1984年完善并發(fā)布的一種無損壓縮算法。從信息論上講，

22、算術(shù)編碼是與Huffman編碼一樣的最優(yōu)變碼長的熵編碼。其主要優(yōu)點是，克服了Huffman編碼必須為整數(shù)位，這與實數(shù)的概率值相差大的缺點。如在Huffman編碼中，本來只需要0.1位就可以表示的符號，卻必須用1位來表示，結(jié)果造成10 倍的浪費。算術(shù)編碼所采用的解決辦法是，不用二進制代碼來表示符號，而改用0，1)中的一個寬度等于其出現(xiàn)概率的實數(shù)區(qū)間來表示一個符號，符號表中的所有符號剛好布滿整個0，1)區(qū)間（概率之和為1，不重不漏）。把輸入符號串（數(shù)據(jù)流）映射成0，1)區(qū)間中的一個實數(shù)值。l 編碼方法符號串編碼方法：將串中使用的符號表按原編碼（如字符的ASCII編碼、數(shù)字的二進制編碼）從小到大順序

23、排列成表，計算表中每種符號si出現(xiàn)的概率pi，然后依次根據(jù)這些符號概率大小pi來確定其在0, 1)期間中對應的小區(qū)間范圍xi, yi)：其中，p0 = 0。顯然，符號si所對應的小區(qū)間的寬度就是其概率pi。參見圖7-3。s1s2. si. sm0|x1 p1 y1|x2 p2 y2 . xi pi yi . xm pm ym|1圖7-3 算術(shù)編碼的字符概率區(qū)間然后對輸入符號串進行編碼：設(shè)串中第j個符號cj為符號表中的第i個符號si，則可根據(jù)si在符號表中所對應區(qū)間的上下限xi和yi，來計算編碼區(qū)間Ij = lj, rj)：其中，dj = rj - lj為區(qū)間Ij的寬度，l0 = 0，r0 =

24、1，d0 = 1。顯然，lj而dj與rj。串的最后一個符號所對應區(qū)間的下限ln就是該符號串的算術(shù)編碼值。l 例子例如：輸入符號串為“helloworld”（10個字符），符號表含7個符號，按字母順序排表7-4 符號表（符號及其概率與區(qū)間）列，容易計算它們各自出現(xiàn)概率和所對應的區(qū)間。表7-4是符號序號符號pixi, yi)1d0.0, 0.1)2e0.1, 0.2)3h0.2, 0.3)4l0.3, 0.6)5o0.6, 0.8)6r0.8, 0.9)7w0.9, 1.0)表及其符號的概率和對應區(qū)間。表7-5則是對輸入符號串“helloworld”的編碼過程，編碼輸出為l10 = 0.21461

25、57880。算術(shù)編碼的過程，也可以用圖7-4所示的逐步映射來表示。表7-5 算術(shù)編碼的編碼過程表序號符號liridi0初值1h2e3l4l5o6w7o8r9l10d0de h lo r w0.0 0.1 0.20.3 0.6 0.8 hdhe hh hlho hr hw0.2 hedhee heh hel heo herhew111 12 13 16 18 19 0.22heldhele helh hell helo helrhelw13 33 136 139 148 154 157 0.216 helloworl0.21461568 helloworld 0.2146157880 輸出 圖7

26、-4 算術(shù)編碼的過程l 解碼方法由符號表（包括符號對應的概率與區(qū)間）和實數(shù)編碼ln，可以按下面的解碼算法來重構(gòu)輸入符號串：設(shè)v1 = ln = 碼值若vj xi , yi) cj = si , j = 1, , nvj+1 = (vj - xi) / pi , j = 1, , n-1例如上例的解碼過程見表7-6。重構(gòu)輸入符號串為v10 = “helloworld”。jvjicj = si13h22e34l4(0.4615788 - 0.3) / 0.3 = 4l5( - 0.3) / 0.3 = 5o6( - 0.6) / 0.2 = 7w7( - 0.9) / 0.1 = 5o8( - 0

27、.6) / 0.2 = 0.836r9(0.83 - 0.8) / 0.1 = 0.34l10(0.3 - 0.3) / 0.3 = 0.01d表7-6 算術(shù)編碼的解碼過程表l 若干說明在算術(shù)編碼中需要注意的幾個問題：(1) 由于實際計算機的浮點運算器不夠長（一般為80位），可用定長的整數(shù)寄存器低進高出來接收碼串，用整數(shù)差近似實數(shù)差來表示范圍，但可能會導致誤差積累。(2) 算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔0, 1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。(3) 算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個字符序列被譯錯

28、。算術(shù)編碼可以是靜態(tài)的或者自適應的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在自適應算術(shù)編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。需要開發(fā)動態(tài)算術(shù)編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切實際的。當壓縮數(shù)據(jù)時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率，它成為確定編碼器壓縮效率的關(guān)鍵。 RLE行程編碼RLE（Run Length Encoding，游程長度編碼）是一種使用廣泛的簡單熵編碼，它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于傳真機。l RLE的編碼方法RLE視數(shù)字信息為無語義

29、的字符序列（字節(jié)流），對相鄰重復的字符，用一個數(shù)字表示連續(xù)相同字符的數(shù)目（稱為行程長度），可達到壓縮信息的目的。如未壓縮的數(shù)據(jù)：ABCCCCCCCCDEFFGGGRLE編碼：AB8CDEFF3G對比該RLE編碼例前后的代碼數(shù)可以發(fā)現(xiàn)，在編碼前要用17個代碼表示的數(shù)據(jù)，而編碼后只要用10個代碼，壓縮比為1.7 : 1。這說明RLE確實是一種壓縮技術(shù)，而且這種編碼技術(shù)相當直觀，也非常經(jīng)濟。RLE所能獲得的壓縮比有多大，這主要是取決于數(shù)據(jù)本身的特點。如果圖像數(shù)據(jù)（如人工圖形）中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之（如自然照片），壓縮比就越小。RLE譯碼采用與編碼相同的規(guī)

30、則，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。因此，RLE是一種無損壓縮技術(shù)。RLE壓縮編碼特別適用于計算機生成的圖形，對減少這類圖像文件的存儲空間非常有效。然而，RLE對顏色豐富多變的自然圖像就顯得力不從心，這時在同一行上具有相同顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來的圖像數(shù)據(jù)變得更大。但是，這并不意味著RLE編碼方法在自然圖像的壓縮中毫無用處，恰恰相反，在各種自然圖像的壓縮方法中（如JPEG），仍然不可缺少RLE。只不過，不是單獨使用RLE一種編碼方法，而是和其他壓縮技術(shù)聯(lián)合應用。l BMP中的RL

31、E1編碼在BMP文件中，對16色和256色的普通格式的位圖可進行RLE壓縮（BI_RLE4和BI_RLE8），編碼由若干信息單位構(gòu)成，每個信息單位有2個字節(jié)。第一字節(jié)>0：重復的象素數(shù)第二字節(jié)BI_RLE8：一個顏色索引值(8b)BI_RLE4：兩個顏色索引值（高4位為第一個象素，低4位為第二個象素）表7-7 BMP的RLE編碼信息單位的組成1信息單位的第一個字節(jié)一般為同一色索引的象素數(shù)，這時第二個字節(jié)對BI_RLE8為一個顏色索引(8b)，對BI_RLE4為兩個顏色索引（各4b，高4位為第一個象素，低4位為第二個象素）。參見表7-7。第一字節(jié)0：特殊含義第二字節(jié)0：線結(jié)束1：位圖結(jié)束2

32、：偏移（后跟的兩個字節(jié)分別表示從當前位置向右和向下偏移的象素數(shù)）?3255：后跟的未壓縮的象素（色索引）數(shù)表7-8 BMP的RLE編碼信息單位的組成2若信息單位的第一個字節(jié)為0，這時，第二個字節(jié)表示特殊意義：0線結(jié)束、1位圖結(jié)束、2偏移（后跟的兩個字節(jié)分別表示從當前位置向右和向下偏移的象素數(shù)）、3255后跟的未壓縮的象素（色索引）數(shù)（填充到雙字節(jié)邊界，不足時補0）。參見表7-8。2例子1）BI_RLE8Compressed data Expanded data03 04 04 04 04 05 06 06 06 06 06 06 00 03 45 56 67 00 45 56 67 02 78

33、 78 78 00 02 05 01 Move 5 right and 1 down 02 78 78 78 00 00 End of line 09 1E 1E 1E 1E 1E 1E 1E 1E 1E 1E 00 01 End of RLE bitmap2）BI_RLE4Compressed data Expanded data03 04 0 4 005 06 0 6 0 6 0 00 06 45 56 67 00 4 5 5 6 6 7 04 78 7 8 7 8 00 02 05 01 Move 5 right and 1 down 04 78 7 8 7 8 00 00 End of

34、 line 09 1E 1 E 1 E 1 E 1 E 100 01 End of RLE bitmap LZW算法（邏輯更簡單、速度更快、硬件實現(xiàn)更廉價），因此人們把這種編碼方法稱為LZW(Lempel-Ziv Walch)算法。圖7-5 第二類詞典編碼概念LZW屬于第二類詞典編碼，該類詞典編碼的思路是試圖從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典”，這里的“短語”（phrases，詞匯/單詞）可是任意字符的組合。編碼數(shù)據(jù)過程中當遇到已經(jīng)在詞典中出現(xiàn)的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身，參見圖7-5。LZW算法被GIF和PNG圖像所采用，并被廣泛應用于文件的壓縮打包（

35、如ZIP和RAR）和磁盤壓縮。l 編碼算法LZW算法是一種基于字典的編碼將變長的輸入符號串映射成定長的碼字形成一本短語詞典索引（串表），利用字符出現(xiàn)的頻率冗余度及串模式高使用率冗余度達到壓縮的目的。該算法只需一遍掃描，且具有自適應的特點（從空表開始逐步生成串表，碼字長從象素位數(shù)n+1逐步增加到12），不需保存和傳送串表。串表具有前綴性若串wc（w為字符串，c為字符）在表中，則串w也在串表中（所以，可初始化串表為含所有單個字符的串）。匹配采用貪婪算法每次只識別與匹配串表中最長的已有串w（輸出對應的碼字）、并可與下一輸入字符c拼成一個新的碼字wc。對串表的改進：用w的碼字來代替wc中的w，則串表中

36、的串等長；當串表已滿時（一般表長為212），可清表重來（輸出清表碼字）。清表碼字=2n，結(jié)束碼字=1+2n。所以，第一個可用的多字符串的碼字=2+2n。n LZW壓縮算法：初始化：將所有單個字符的串放入串表ST中；（共2n項碼字為02n-1，實際操作時不必放入，只需空出串表的前2n項，字符對應碼字所對應的串表索引即可）讀首字符入前綴串w；設(shè)置碼長codeBits=n+1；設(shè)置串表中當前表項的索引值next=初始碼字=2n+2；循環(huán)：讀下一輸入字符c；若c=EOF（文件結(jié)束符），則輸出w的碼字，結(jié)束循環(huán)（輸出結(jié)束碼字）；若wc已在串表中，則w=wc，轉(zhuǎn)到循環(huán)開始處；否則，輸出w的碼字，將wc放入

37、ST中的next處，next+；令w=c，轉(zhuǎn)到循環(huán)開始處；若next的位數(shù)超過碼長(>codeBits)，則codeBits+；若串表已滿（next的位數(shù)已超過最大碼長12），則清空串表，輸出清表碼字，轉(zhuǎn)到初始化開始處。n LZW還原算法：初始化：將所有單個字符的串放入串表ST中；（共2n項碼字為02n-1，實際操作時不必放入，只需空出串表的前2n項，字符對應碼字對應串表索引即可）串表中當前表項的索引next=2n+2；設(shè)置碼長codeBits=n+1；讀首個碼字（所對應的單個字符）入老串old，輸出該字符；循環(huán)：讀下一碼字new；若new=結(jié)束碼字，結(jié)束循環(huán)；若new=清表碼字，則清空

38、串表，轉(zhuǎn)到初始化開始處；若new>=next，則輸出串newStr= old+old0（例外處理）；若new<next，則輸出串newStr；將old+newStr0放入串表STnext中，next+；若next的位數(shù)超過碼長(>codeBits)，則codeBits+；但若加一后的codeBits > 12，則重新讓codeBits = 12；old=newStr，轉(zhuǎn)到循環(huán)開始處。其中：newStr=STnew（即串表中索引為new的串）表7-9 編碼字符串l 例子位置123456789字符ABBABABAC被編碼字符串見表7-9，它只包含3個不同的單字符A、B、C。

39、步驟碼字詞典輸出(1)A(2)B(3)C1(1)-A2(2)(4)ABB3(2)(5)BBB4(4)(6)BAAB5(7)(7)ABAABA6(3)(8)ABACC步驟位置詞典輸出(1)A(2)B(3)C11(4)AB(1)22(5)BB(2)33(6)BA(2)44(7)ABA(4)56(8)ABAC(7)6-(3)表7-10 LZW的編碼過程 表7-11 LZW的譯碼過程編碼過程如表7-10，其中：“步驟”欄表示編碼步驟、“位置”欄表示在輸入數(shù)據(jù)中的當前位置、“詞典”欄表示添加到詞典中的綴符串，它的索引在括號中、“輸出”欄表示碼字輸出。譯碼過程如表7-11。每個譯碼步驟譯碼器讀一個碼字，輸

40、出相應的綴符串，并把它添加到詞典中。例如，在步驟4中，先前碼字(2)（對應于單字符串“B”）存儲在老碼字(old)中，當前碼字(new)是(4)，對應的當前綴符串newStr是輸出(“AB”)，先前綴符串old ("B")加上當前綴符串newStr ("AB")的第一個字符“A”，其結(jié)果old+newStr0("BA") 添加到詞典中（STnext），它的索引號next是(6) 。表7-9 編碼字符串l GIF文件格式可交換圖形格式（GIF=Graphics Interchange Format），由CompuServe公司于87年起

41、定義，現(xiàn)有87a與89a兩個主要版本，采用變長LZW壓縮算法，只支持索引色（最多8位）。GIF文件的格式見表7-1219（其中，多字節(jié)整數(shù)的低位在前，無符號）。內(nèi)容大小取值標識3B必須為”GIF”版本3B”87a”或”89a”圖像寬度2B象素數(shù)圖像高度2B象素數(shù)全局標志1B定全局色表選項背景色索引1B用于圖外色象素縱橫比1B一般為0全局色表N*3B可選，每項為RGB數(shù)據(jù)塊變長可多個GIF結(jié)束符1B;(59,0x3B)表7-14 數(shù)據(jù)塊格式1（圖像塊）表7-12 GIF文件格式表7-13 全局標志位名稱大小含義02pixel3bpixelBits-13reserved (87a)1b保留，必須為

42、0sort (89a)=0色表未排序=1色表已按重要性排序46cr3bcolorBits-17M1b=0無全局色表=1有全局色表表7-15 局部標志其中：n 像素位數(shù)n=pixelBits=pixel+1=顏色位數(shù)colorBits=cr+1= 18n 顏色數(shù)N=2pixelBits=2colorBits=2(18)n 象素縱橫比：若=0，則Aspect Ratio為1:1；若>0，則Aspect Ratio = (Pixel Aspect Ratio + 15) / 64內(nèi)容大小取值圖像分隔符1B,(44,0x2C)圖像左邊左上角坐標2B象素數(shù)圖像頂端2B象素數(shù)圖像寬度2B象素數(shù)圖像高

43、度2B象素數(shù)局部標志1B定局部色表及交叉選項編碼長度1B位數(shù)局部色表N*3B可選，RGB數(shù)據(jù)子塊子塊大小bc1B可選，可多個圖像編碼bcB子塊序列結(jié)束符1B0（大小為0的子塊）位名稱大小含義02pixel3bpixelBits-134reserved2b保留，必須為05reserved (87a)1b保留，必須為0sort (89a)=0色表未排序=1色表已按重要性排序6I1b=0順序編碼=1行交叉編碼7M1b=0用全局色表=1有局部色表其中：象素位數(shù)n=pixelBits=pixel+1=18，顏色數(shù)N=2pixelBits=2(18) I=1時為行交叉編碼（用于漸顯），行的交叉順序為（4遍掃描）：第一遍：0行、8行、8