【正文】 因此數(shù)據(jù)壓縮和還原速度都較慢。由此產(chǎn)生的全部信息的總碼長(zhǎng)將小于實(shí)際信息的符號(hào)長(zhǎng)度，從而達(dá)到壓縮的目的。 Huffman編碼基本原理 Huffman編碼的基本原理是用較短的代碼代替出現(xiàn)概率較高的數(shù)據(jù)，用較長(zhǎng)的代碼代替出現(xiàn)概率較低的數(shù)據(jù)，所有代碼都采用二進(jìn)制碼，其碼的長(zhǎng)度是可變的，且每個(gè)數(shù)據(jù)的代碼各不相同。該編碼是在 1952年為文本文件建立的，編碼方法簡(jiǎn)單且有效，因而得到廣泛的應(yīng)用。 值得注意的是，規(guī)則數(shù)據(jù)具有可預(yù)測(cè)性，即從一個(gè)數(shù)據(jù)可預(yù)測(cè)到下一個(gè)將可能是什么數(shù)據(jù)。常用于 GIF格式的圖像壓縮，其平均壓縮比在 2： 1以上，最高壓縮比可達(dá)到 3： 1。 LZW壓縮技術(shù)可壓縮任何類型和格式的數(shù)據(jù)。對(duì)于簡(jiǎn)單圖像和平滑且噪音小的信號(hào)源具有較高的壓縮比，并且有較高的壓縮和解壓縮速度。并把代碼和數(shù)據(jù)的對(duì)應(yīng)關(guān)系建立一個(gè)轉(zhuǎn)換表，又叫 “字符串表 ”或“編碼對(duì)照表 ”。 例如用數(shù)值 0x100代替字符串 “abccddeee”這樣每當(dāng)出現(xiàn)該字符串時(shí)，都用 0x100代替。 壓縮過程生成的轉(zhuǎn)換表，記錄了代碼和數(shù)據(jù)的對(duì)應(yīng)關(guān)系，并且只用于壓縮過程。 LZW壓縮基本原理 LZW壓縮的基本原理是： LZW壓縮把每一個(gè)第一次出現(xiàn)的字符串用一個(gè)數(shù)值來編碼，在還原程序中再將這個(gè)數(shù)值還成原來的字符串。 1985年，美國(guó)人 Welch將LempelZiv壓縮技術(shù)從概念發(fā)展到實(shí)際運(yùn)用階段，因而被命名為“ Lempel Ziv Welch”壓縮技術(shù)，簡(jiǎn)稱“ LZW”技術(shù)。 LZW編碼 LZW（ Lempel Ziv Welch）壓縮編碼是一種壓縮效率較高的無損數(shù)據(jù)壓縮技術(shù)。 該方法使總數(shù)據(jù)量降低，達(dá)到數(shù)據(jù)壓縮的目的。 統(tǒng)計(jì)編碼 需要在信源符號(hào)和碼字之間確定嚴(yán)格的一一對(duì)應(yīng)關(guān)系，以便準(zhǔn)確無誤地在先原來信源，同時(shí)使平均碼長(zhǎng)盡量小。 事件發(fā)生的概率越小，則其熵值越大，表示信息量越大，而發(fā)生的概率越大，則其熵值越小。也就是要找到去除信源的相關(guān)性和概率分布的不均勻性的方法。 信息論認(rèn)為信源中存在的冗余度來自于信源本身的相關(guān)性和信源概率分布的不均勻性。當(dāng)人們收到這個(gè)消息后，就消除了這種“不確定”性。也就是說，信息中可能存在著冗余信息，要去除信息的冗余部分，使編碼后單位數(shù)據(jù)量等于其信息源的熵，就達(dá)到了壓縮極限。 統(tǒng)計(jì)編碼 又稱熵編碼。 統(tǒng)計(jì)編碼 統(tǒng)計(jì)編碼屬于一種無失真的編碼，具體實(shí)現(xiàn)的方法有多種，包括行程編碼、 LZW編碼、 Huffman編碼、算術(shù)編碼。在較高的壓縮比下，也能獲得較好的圖像質(zhì)量。 例如，使用 JPEG編碼時(shí)， 當(dāng)壓縮比為 20:1時(shí)，能看到圖像稍微有點(diǎn)變化， 當(dāng)壓縮比大于 20:1時(shí)，一般圖像質(zhì)量開始變壞。 有損壓縮才可能影響人對(duì)媒體的感知效果。 例如，多媒體 CDROM的制作過程可以不是實(shí)時(shí)的，但解壓縮必須是實(shí)時(shí)的，否則用戶看到的就不是連續(xù)的圖像。例如：電視會(huì)議的圖形傳輸。 對(duì)于一個(gè)壓縮系統(tǒng)而言，有 對(duì)稱壓縮 和 非對(duì)稱壓縮 之分。 壓縮速度 壓縮速度指編碼或解碼的快慢程度。但是 MPEG對(duì)圖像的壓縮算法，所提供的壓縮比可以高達(dá) 200:1。文字、圖像普遍采用無損壓縮。 有損壓縮有很高的壓縮比 采用不同的壓縮編碼可得到不同的壓縮比。 數(shù)據(jù)壓縮的性能指標(biāo) 衡量一種數(shù)據(jù)壓縮技術(shù)的重要性能指標(biāo)有壓縮比、壓縮速度、壓縮質(zhì)量和計(jì)算量。 其他編碼方法常見的有： 混合編碼（ Hybrid Coding）、 矢量量化（ Vector Quantize， VQ）、 LZW算法等。 變換編碼一般經(jīng)過 變換、變換域采樣和量化 三個(gè)步驟 分析 /合成編碼 ： 是 基于某種模型 的編碼方法，這些模型可以是聲道模型、語音模型、人體模型等。 關(guān)鍵的是要尋找一個(gè)最佳變換，使信息中最重要的部分易于識(shí)別。 變換編碼 ：屬于有失真的編碼。 如果所有的信源符號(hào)出現(xiàn)的概率相同，則說明平均信息量最大，也就不存在信源的冗余。根據(jù)信源符號(hào)出現(xiàn)概率的分布特性進(jìn)行編碼，讓概率大的信源符號(hào)用短碼字表示，讓概率小的信源符號(hào)用長(zhǎng)碼字表示，從而去除數(shù)據(jù)之間的冗余 而 達(dá)到壓縮的目的。這些被舍去的信息值是無法再找回的，所以還原后的數(shù)據(jù)與原始數(shù)據(jù)存在差異。 該編碼在壓縮時(shí)不丟失任何數(shù)據(jù)，即把所有的數(shù)據(jù)都作為比特序列，解壓后的數(shù)據(jù)與原始數(shù)據(jù)完全一致。 根據(jù)解碼后的數(shù)據(jù)與壓縮之前的原始數(shù)據(jù)是否完全一致，可以分為 無損壓縮編碼 和 有損壓縮編碼 。 而各種壓縮方法應(yīng)該符合一定范圍內(nèi)的性能指標(biāo)，以滿足實(shí)際應(yīng)用的領(lǐng)域的需要。 本章 主要介紹 了數(shù)據(jù)壓縮的基本原理和方法，以及數(shù)據(jù)壓縮的編碼原理和壓縮標(biāo)準(zhǔn)。數(shù)字化后的視頻和音頻等媒體信息具有海量性，與當(dāng)前計(jì)算機(jī)所提供的計(jì)算機(jī)存儲(chǔ)資源和網(wǎng)絡(luò)帶寬之間有很大差距，這樣對(duì)多媒體信息的存儲(chǔ)造成很大困難。 因此，多媒體信息以壓縮的形式進(jìn)行存儲(chǔ)和傳播成為必要，同時(shí)因?yàn)槎嗝襟w數(shù)據(jù)之間存在大量冗余現(xiàn)象，如空間冗余、時(shí)間冗余、結(jié)構(gòu)冗余、知識(shí)冗余、視覺冗余、圖像區(qū)域的相同性冗余和紋理統(tǒng)計(jì)冗余，使得多媒體數(shù)據(jù)壓縮成為可能。 第 7 章 多媒體壓縮技術(shù) 數(shù)據(jù)壓縮的基本原理和方法 根據(jù)多媒體不同的表現(xiàn)形式和不同場(chǎng)合以及質(zhì)量方面的應(yīng)用需求，必須有針對(duì)性地進(jìn)行設(shè)計(jì)。 數(shù)據(jù)壓縮方法的分類 數(shù)據(jù)壓縮技術(shù)自從 1948年提出以來，經(jīng)過 50多年的發(fā)展。 無損壓縮編碼具有可恢復(fù)性和可逆性 。 有損壓縮編碼不具有可恢復(fù)性和可逆性，該編碼在壓縮時(shí)舍棄冗余的數(shù)據(jù)， 例如人眼較難分辨的顏色或人耳難以分辨的方向源信號(hào)，實(shí)際取決于初始信號(hào)的類型、信號(hào)的相關(guān)性以及語義等內(nèi)容。 統(tǒng)計(jì)編碼 ：屬于無失真編碼。 預(yù)測(cè)編碼 ：根據(jù)離散信號(hào)之間存在一定的相關(guān)性特點(diǎn)，利用前面的一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測(cè)，然后對(duì)實(shí)際值和預(yù)測(cè)值的差值進(jìn)行編碼。 根據(jù)數(shù)據(jù)壓縮的原理可以分為： 統(tǒng)計(jì)編碼、預(yù)測(cè)編碼、變換編碼、分析 合成編碼和其他編碼。變換編碼是將原始數(shù)據(jù)從初始空間或時(shí)間域進(jìn)行數(shù)學(xué)變換，變換為更適合于壓縮的抽象域。 變換本身是可逆的無損的，為了取得更好的效果，忽略了一些編碼位數(shù)較長(zhǎng)的系數(shù)而成為了有損編碼。 通過分析模型的具體特征，確定與之匹配的編碼 。 還有近年來新出現(xiàn)的編碼方法 ： 人工神經(jīng)元網(wǎng)絡(luò)（ Artificial Neural Network，ANN）算法、 分形（ Fractal）算法、小波（ Wavelet）算法、 基于對(duì)象（ ObjectBased）的算法、 基于模型（ ModelBased）的算法等。 壓縮比 壓縮比是指原始數(shù)據(jù)量和壓縮后數(shù)據(jù)量的比值。 無損壓縮能實(shí)現(xiàn)的壓縮比，一般只有數(shù)倍，而且與被壓縮的對(duì)象有關(guān)。 例如， MPGE是一種包含音頻和圖像在內(nèi)的壓縮技術(shù)，利用 MPEGMPEG MPEG4三個(gè)方案， 對(duì)音頻的感知編碼中， MPEG1方案的音頻壓縮比是 1:4， MPEG2方案的音頻壓縮比是 1:6…1:8 ， MPEG4方案的音頻壓縮比是 1:10…1:12 。利用 JPEG也可以有多種圖像的壓縮比，甚至可以減小到原圖像的百分之一（壓縮比 100:1）。不同的應(yīng)用場(chǎng)合，對(duì)壓縮速度要求是不同的。 所謂 對(duì)稱壓縮 ，就是壓縮和解壓縮都需要實(shí)時(shí)進(jìn)行的。 非對(duì)稱壓縮 常常在解壓縮方面要求是實(shí)時(shí)的，但壓縮可以不是實(shí)時(shí)的。 壓縮質(zhì)量 壓縮質(zhì)量是指壓縮以后對(duì)媒體的感知效果 。 壓縮質(zhì)量的好壞與 壓縮算法 、 數(shù)據(jù)內(nèi)容 和 壓縮比 有密切的關(guān)系。 但使用 MPEG編碼時(shí)，可以得到很好的數(shù)據(jù)壓縮而依然保持 CD聲音質(zhì)量的原樣。 計(jì)算量 圖像數(shù)據(jù)壓縮需要進(jìn)行大量計(jì)算，從目前的技術(shù)來看，壓縮的計(jì)算量比解壓縮計(jì)算量要大，例如動(dòng)態(tài)圖象的壓縮編碼計(jì)算量約為解壓縮的計(jì)算量的 4倍。本節(jié)在介紹了統(tǒng)計(jì)編碼的基本思想之后，為讀者引見 LZW編碼、 Huffman編碼、算術(shù)編碼等幾種實(shí)現(xiàn)方法。根據(jù)信息論的原理，我們可以找到最佳的壓縮編碼方法，數(shù)據(jù)壓縮的理論極限是信息熵。 信息論指出，如果一個(gè)事件（例如收到一個(gè)信號(hào)）有 n個(gè)等可能性的結(jié)局，那么結(jié)局未出現(xiàn)前的不確定程度 H與 n的自然對(duì)數(shù)成正比，即有： H=Cln n (C為常數(shù) ) 如果一個(gè)消息有 10個(gè)可能的結(jié)果，不確定程度就是 Cln10。這樣，一個(gè)消息中所含有的信息量，就用表示有多少個(gè)不確定程度的 H來定義，申農(nóng)（香農(nóng)）把這個(gè)不確定程度 H 稱為 信息熵 。 熵編碼要解決的問題，是如何利用信息熵理論減少數(shù)據(jù)在存儲(chǔ)和傳輸中的冗余度 。 事件間的統(tǒng)計(jì)特性與熵 有這樣的關(guān)系。 統(tǒng)計(jì)編碼 就是根據(jù)信源符號(hào)出現(xiàn)概率的分布特性而進(jìn)行工作的。 統(tǒng)計(jì)編碼對(duì)于出現(xiàn)概率比較高的數(shù)據(jù)分配短碼，而對(duì)那些出現(xiàn)概率比較低的數(shù)據(jù)則分配長(zhǎng)碼。 常用的統(tǒng)計(jì)編碼有 LZW編碼、 Huffman編碼和算術(shù)編碼。 1977年，兩位以色列教授 Lempel和 Ziv提出了查找冗余字符和用較短的符號(hào)標(biāo)記替代冗余字符的概念，稱為L(zhǎng)empelZiv壓縮技術(shù)。 LZW被廣泛用于圖像壓縮領(lǐng)域。 轉(zhuǎn)換表是在壓縮或解壓縮過程中動(dòng)態(tài)生成的表，該轉(zhuǎn)換表只在進(jìn)行壓縮或解壓縮過程中需要，一旦壓縮或解壓縮結(jié)束，該表將不再起任何作用。在解壓縮過程中， LZW壓縮編碼會(huì)生成另一個(gè)用于解壓縮的轉(zhuǎn)換表，該表與壓縮時(shí)產(chǎn)生的轉(zhuǎn)換表完全相同，數(shù)據(jù)以嚴(yán)格對(duì)應(yīng)的無損方式被還原。把數(shù)據(jù)流中復(fù)雜的數(shù)據(jù)用簡(jiǎn)單的代碼來表示，就起到了壓縮的作用。 LZW壓縮的特點(diǎn) LZW壓縮技術(shù)的處理過程比其他壓縮過程復(fù)雜，但過程完全可逆。對(duì)機(jī)器硬件條件要求不高。對(duì)于任意寬度和像素位長(zhǎng)度的圖像，都具有穩(wěn)定的壓縮過程。 LZW壓縮技術(shù)還可以被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域，對(duì)于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串， LZW壓縮技術(shù)具有很高的壓縮比。但 LZW壓縮技術(shù)對(duì)于可預(yù)測(cè)性不大的數(shù)據(jù)具有較好的處理效果 Huffman編碼 Huffman（ 哈夫曼）編碼 是統(tǒng)計(jì)編碼的一種，屬于無損壓縮編碼?，F(xiàn)在已經(jīng)派生出很多變體。 例如，對(duì)于原始數(shù)據(jù)序列 A、 B、 C、 E、 D這五個(gè)字母，假定對(duì)應(yīng)于每個(gè)字母出現(xiàn)的概率分別為 、 、 、 、和 ，則可以編碼為 A(00)、 B(01)、 C(10)、 (D110)、 (D111)，壓縮后為000110110111。 整個(gè)編碼過程實(shí)際上建立二 叉 樹的過程，所以編碼時(shí)需要對(duì)原始數(shù)據(jù)掃描兩遍，第一遍掃描要精確地統(tǒng)計(jì)出原始數(shù)據(jù)中的每個(gè)值出現(xiàn)的頻率，第二遍是通過合并最小概率來建立霍夫曼樹，同時(shí)還要進(jìn)行編碼。 編碼過程 根據(jù)以上編碼原理， Huffman編碼的實(shí)際編碼過程如下： 。 1和 2，直到概率的和值等于 1。也可以相反表示，可以對(duì)概率大的符號(hào)用編碼 1表示，概率小的符號(hào)用編碼 0表示。 設(shè)信號(hào)源為： x={x1， x2， x3， x4， x5} 對(duì)應(yīng)的概率為 ： p={， ， ， ， } 則編碼過程如圖 72所示，其中第一次將 率進(jìn)行合并，結(jié)果為 。 當(dāng)前信號(hào)源 X1 X2 X3 X4 X5 概率 0 0 0 0