無損數(shù)據(jù)壓縮

第二章無損壓縮技術(shù)主要內(nèi)容數(shù)據(jù)壓縮的基本原理和方法數(shù)據(jù)壓縮技術(shù)的性能指標數(shù)據(jù)冗余的類型與壓縮方法分類常用數(shù)據(jù)壓縮方法1．信息的含義在信息理論中，經(jīng)常用到消息和信息的概念。1)消息消息是由符號、文字、數(shù)字或語音組成的表達一定含義的一個序列，如一份電報和報紙上的一段文字。消息是信息的載體，是表達信息的工具。2)信息信息是消息的內(nèi)涵，是消息中的不確定性內(nèi)容。2.1數(shù)據(jù)壓縮的基本原理和方法消息中事件發(fā)生的不確定性小，即可能性大，則事件的信息量就??；反之，一個發(fā)生可能性很小的事件，攜帶的信息量就很大。2.1數(shù)據(jù)壓縮的基本原理和方法2.信息的量度1)信息量及熵

(1)信息量定義設(shè)信源x由屬于集合Am＝{a1,a2,…,am}的m個可能的符號產(chǎn)生，若信源事件aj的概率為P(aj)，則定義事件aj的信息量I(aj) I(aj)＝-logP(aj)(2.1)作為事件aj所包含的信息量的量度，稱為自信息。 單位：取2為底的對數(shù)，則單位為比特(bit)； 取e為底的對數(shù)，則單位為奈特。2.1數(shù)據(jù)壓縮的基本原理和方法 從信息量的定義可以看出，信息是事件aj的不確定因素的度量。事件發(fā)生的概率越大，事件的信息量越小；反之，一個發(fā)生可能性很小的事件，攜帶的信息量就很大，甚至使人們“震驚”。 例如：在32個數(shù)碼中任選1個數(shù)碼時，設(shè)每個數(shù)碼選中的概率是相等的，則

那么，任一數(shù)碼的信息量為

2.1數(shù)據(jù)壓縮的基本原理和方法

(2)信源的熵一個通信系統(tǒng)并非只傳送1個符號，而是多個符號，這就需要定義整個信源符號的平均信息量的大小。 我們把自信息的統(tǒng)計平均值——數(shù)學(xué)期望

(2.2)

即信源x中每個符號的平均信息量，稱為信源x的熵。 當信源x中的每個符號是等概率的且是獨立的時候，平均信息量最大，此時，j=1，2，…，m

代入式(2.2)得(2.3)2.1數(shù)據(jù)壓縮的基本原理和方法 例如：若信號x{a1,a2}的概率分別為P(a1)＝0.9，P(a2)＝0.1，則符號的平均信息量，即信源x的熵為

H(x)=-(0.9×lb0.9+0.1×lb0.1)=0.467bit

若a1,a2等概率，P(a1)=P(a2)=0.5，則信源x的平均信息量達到最大，即

所以二進制1位數(shù)據(jù)(0/1)的每1位的信息量即為1比特。數(shù)據(jù)無損壓縮的理論——信息論(InformationTheory)1948年創(chuàng)建的數(shù)學(xué)理論的一個分支學(xué)科，研究信息的編碼、傳輸和存儲；該術(shù)語源于ClaudeShannon(香農(nóng))發(fā)表的“AMathematicalTheoryofCommunication”論文題目，提議用二進制數(shù)據(jù)對信息進行編碼；最初只應(yīng)用于通信工程領(lǐng)域，后來擴展到包括計算在內(nèi)的其他多個領(lǐng)域，如信息的存儲、信息的檢索等。在通信方面，主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問題。2.1數(shù)據(jù)壓縮的基本原理和方法TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA/news/2001/february/26/1.html信息論之父2.1數(shù)據(jù)壓縮的基本原理和方法返回2.2數(shù)據(jù)壓縮技術(shù)的性能指標

1）壓縮的必要性音頻、視頻的數(shù)據(jù)量很大，如果不進行處理，計算機系統(tǒng)幾乎無法對它進行存取和交換。例如：一幅中等分辨率（640*480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為0.9MB/幀，若要達到每秒25幀的全動態(tài)顯示要求，每秒所需的數(shù)據(jù)量約為22MB。對于聲音也是如此，CD音質(zhì)的聲音每秒將有約為172KB的數(shù)據(jù)量。2）數(shù)據(jù)可被壓縮的依據(jù)數(shù)據(jù)本身存在冗余聽覺系統(tǒng)的敏感度有限視覺系統(tǒng)的敏感度有限2.2數(shù)據(jù)壓縮技術(shù)的性能指標

3）從哪些方面評價一個壓縮系統(tǒng)2.2數(shù)據(jù)壓縮技術(shù)的性能指標●壓縮比●圖像質(zhì)量●壓縮解壓速度●硬件和軟件壓縮比

輸入數(shù)據(jù)和輸出數(shù)據(jù)之比。例如：圖像512×480，24位輸入＝(512×480×24)/8=737280B若輸出＝15000B

則壓縮比＝737280/15000＝492.2數(shù)據(jù)壓縮技術(shù)的性能指標圖像質(zhì)量壓縮方法：無損壓縮有損壓縮有損壓縮：失真情況很難量化，只能對測試的圖像進行估計。

2.2數(shù)據(jù)壓縮技術(shù)的性能指標壓縮解壓速度在許多應(yīng)用中，壓縮和解壓可能不同時用，在不同的位置不同的系統(tǒng)中。所以，壓縮、解壓速度分別估計。靜態(tài)圖像中，壓縮速度沒有解壓速度嚴格；動態(tài)圖像中，壓縮、解壓速度都有要求，因為需實時地從攝像機或其他設(shè)備中抓取動態(tài)視頻。2.2數(shù)據(jù)壓縮技術(shù)的性能指標硬軟件系統(tǒng)

有些壓縮解壓工作可用軟件實現(xiàn)。設(shè)計系統(tǒng)時必須充分考慮：算法復(fù)雜——壓縮解壓過程長算法簡單——壓縮效果差目前有些特殊硬件可用于加速壓縮/解壓。硬件系統(tǒng)速度快，但各種選擇在初始設(shè)計時已確定，一般不能更改。因此在設(shè)計硬接線壓縮/解壓系統(tǒng)時必須先將算法標準化。2.2數(shù)據(jù)壓縮技術(shù)的性能指標冗余的基本概念

指信息存在的各種性質(zhì)的多余度。舉例：（1）廣播員讀文稿時每分鐘約讀180字，一個漢字占兩個字節(jié)；文本數(shù)據(jù)量為360B；（2）如果對語音錄音，由于人說話的音頻范圍為20Hz到4kHz，即語音的帶寬為4kHz，若設(shè)量化位數(shù)為8bits,則一秒鐘的數(shù)據(jù)量為：4k×8×2=64kbit/s=8KB/s則一分鐘的數(shù)據(jù)是480KB。

2.3數(shù)據(jù)冗余的類型與壓縮方法分類360B

480KB 設(shè)一幅圖片有4個灰度級S={A，B，C，D}，這4個灰度級所出現(xiàn)的概率分別為P(aj)={0.6，0.2，0.06，0.14}，則

H(x)=-(0.6×lb0.6+0.2×lb0.2+0.06×lb0.06+0.14×lb0.14)=1.547bit

即其平均信息熵為1.547bit。這說明表示這4個灰度級所使用的最少平均位數(shù)為1.547bit。 平均信息熵是一種理論上的最佳編碼的平均碼長。我們平常使用的一般為自然碼編碼，表示每一事件的位數(shù)是相同的。如果對A、B、C、D4個灰度級采用自然碼進行編碼，即2.3數(shù)據(jù)冗余的類型與壓縮方法分類A 00B 01C 10D 11

每一個灰度級用兩位二進制表示，則4個灰度級的平均碼長為2，而平均信息熵是理論上的最佳編碼的平均碼長，為1.547位。顯然，自然碼編碼和理論上的最佳編碼存在一定的差距，這一差距常用冗余度

來表示。2.3數(shù)據(jù)冗余的類型與壓縮方法分類 冗余度表示原始圖像編碼中所包含冗余信息的多少，應(yīng)越小越好。在本例中，灰度級的自然碼編碼長度為2bit，平均信息熵是理論上的最佳編碼碼長，為1.547bit，顯然，在自然碼編碼中包含有冗余信息。如何找出一種編碼方法，使其平均碼長盡量接近信息熵，是圖像編碼所追求的目標。 另外，如果4個灰度級是等概率出現(xiàn)的，均為0.25，則信源的平均信息熵為

即在等概率的情況下，自然碼編碼的冗余度為0。2.3數(shù)據(jù)冗余的類型與壓縮方法分類數(shù)據(jù)冗余的類別空間冗余時間冗余統(tǒng)計冗余信息熵冗余結(jié)構(gòu)冗余知識冗余視覺冗余聽覺冗余2.3數(shù)據(jù)冗余的類型與壓縮方法分類●空間冗余2.3數(shù)據(jù)冗余的類型與壓縮方法分類同一景物表面上采樣點的顏色之間往往存在著空間連貫性，但是基于離散像素采樣來表示物體顏色的方式通常沒有利用這種連貫性。例如：圖像中有一片連續(xù)的區(qū)域，其像素為相同的顏色，空間冗余產(chǎn)生?！駮r間冗余序列圖像（如電視圖像和運動圖像）和語音數(shù)據(jù)的前后有著很強的相關(guān)性，經(jīng)常包含著冗余。在播出該序列圖像時，時間發(fā)生了推移，但若干幅畫面的同一部位沒有變化，變化的只是其中某些地方，這就形成了時間冗余?？臻g冗余和時間冗余是把圖像信號看作概率信號時反應(yīng)出的統(tǒng)計特性，因此，這兩種冗余也被稱為統(tǒng)計冗余。2.3數(shù)據(jù)冗余的類型與壓縮方法分類●統(tǒng)計冗余●結(jié)構(gòu)冗余在某些場景中，存在著明顯的圖像分布模式，這種分布模式稱作結(jié)構(gòu)。圖像中重復(fù)出現(xiàn)或相近的紋理結(jié)構(gòu)，結(jié)構(gòu)可以通過特定的過程來生成。例如：方格狀的地板，蜂窩，磚墻，草席等圖結(jié)構(gòu)上存在冗余。已知分布模式，可以通過某一過程生成圖像。2.3數(shù)據(jù)冗余的類型與壓縮方法分類●信息熵冗余信息熵實際情況又稱編碼冗余。信息熵是指一組數(shù)所攜帶的信息量。由圖像的記錄方式與人對圖像的知識差異所產(chǎn)生的冗余稱為知識冗余?！裰R冗余

人類的視覺系統(tǒng)對于圖像場的注意在非均勻和非線性的，視覺系統(tǒng)并不是對圖像的任何變化都能感知?！褚曈X冗余●聽覺冗余人耳對不同頻率的聲音的敏感性是不同的，并不能察覺所有頻率的變化，對某些頻率不必特別關(guān)注，因此存在聽覺冗余。2.3數(shù)據(jù)冗余的類型與壓縮方法分類數(shù)據(jù)壓縮技術(shù)分類指使壓縮后的數(shù)據(jù)進行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合。

典型的算法有：Huffman編碼，算術(shù)編碼，行程編碼等。特點：壓縮比較低，為2:1——5:1，一般用來壓縮文本，數(shù)據(jù)。2.3數(shù)據(jù)冗余的類型與壓縮方法分類●無損壓縮是指使用壓縮后的數(shù)據(jù)進行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達的信息造成誤解。典型的算法有：混合編碼的JPEG標準，預(yù)測編碼，變換編碼等。特點：壓縮比高，為幾十到幾百倍一般用于圖像，聲音，視頻壓縮。2.3數(shù)據(jù)冗余的類型與壓縮方法分類●有損壓縮數(shù)據(jù)壓縮的方法統(tǒng)計編碼預(yù)測編碼變換編碼混合編碼

分析合成編碼2.4常用數(shù)據(jù)壓縮方法的基本原理

根據(jù)消息出現(xiàn)概率的分布特性而進行的壓縮編碼。

Huffman編碼

算術(shù)編碼

行程編碼

詞典編碼2.4常用數(shù)據(jù)壓縮方法的基本原理●統(tǒng)計編碼Huffman編碼統(tǒng)計獨立信源，能達到最小平均碼長的編碼方法。編碼效率高?；舴蚵?D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法。根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少。廣泛用在JPEG,MPEG,H.26X等各種信息編碼標準中。統(tǒng)計編碼一Huffman編碼編碼步驟：

(1)初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序。

(2)把概率最小的兩個符號組成一個節(jié)點。

(3)重復(fù)步驟（2）。

(4)從根節(jié)點開始到相應(yīng)于每個符號的“樹葉”，從上到下標上“0”(上枝)或者“1”(下枝)，至于哪個為“1”哪個為“0”則無關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長度是相同的。

(5)從根節(jié)點開始順著樹枝到每個葉子分別寫出每個符號的代碼。統(tǒng)計編碼一霍夫曼編碼舉例現(xiàn)有一個由5個不同符號組成的30個符號的字符串：BABACACADADABBCBABEBEDDABEEEBB計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼前后的壓縮比統(tǒng)計編碼一符號出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D42.907?E52.585?合計30符號出現(xiàn)的概率統(tǒng)計編碼一(1)計算該字符串的霍夫曼碼步驟①：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M行排序步驟②：把概率最小的兩個符號組成一個節(jié)點P1步驟③：重復(fù)步驟②，得到節(jié)點P2，P3，P4，……，

PN，形成一棵樹，其中的PN稱為根節(jié)點步驟④：從根節(jié)點PN開始到每個符號的樹葉，從上到下

標上0(上枝)和1(下枝)，至于哪個為1哪個為0則

無關(guān)緊要，但通常把概率大的標成1，概率小的

標成0步驟⑤：從根節(jié)點PN開始順著樹枝到每個葉子分別寫出

每個符號的代碼統(tǒng)計編碼一符號B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010編碼B(11)A(10)E(00)D(011)C(010)統(tǒng)計編碼一符號出現(xiàn)的次數(shù)lb(1/pi）分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合計301.0675個符號的代碼統(tǒng)計編碼一

(2)計算該字符串的熵

其中，是事件的集合，并滿足H(S)=(8/30)×log2(30/8)+(10/30)×log2(30/10)+

(3/30)×log2(30/3)+(4/30)×log2(30/4)+

(5/30)×log2(30/5)

=[30lg30–(8×lg8＋10×lg10＋3×lg3＋4

×lg4＋5lg5)]/(30×log22)

=(44.3136－24.5592)/9.0308＝2.1874(Sh)統(tǒng)計編碼一(3)計算該字符串的平均碼長平均碼長：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝67/30=2.233位/符號(4)計算編碼前后的壓縮比編碼前（等長）：5個符號需3位，30個字符，90位編碼后：共67位 壓縮比:90/67=1.34:1統(tǒng)計編碼一霍夫曼編碼舉例2編碼前N=8symbols:{a,b,c,d,e,f,g,h},3bitspersymbol(N=23=8)P(a)=0.01,P(b)=0.02,P(c)=0.05,P(d)=0.09,P(e)=0.18,P(f)=0.2,P(g)=0.2,

P(h)=0.25計算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼效率統(tǒng)計編碼一該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(4)編碼效率統(tǒng)計編碼一Huffman編碼的注意點Huffman編碼沒有錯誤保護功能，如果碼中有錯誤，則可能引起接下來的一連串譯碼錯誤。Huffman編碼是可變長編碼，因此很難隨意查找或調(diào)用中的文件內(nèi)容。Huffman依賴于信源的統(tǒng)計特性。Huffman編碼的每個碼字都是整數(shù)，因此實際上平均碼長很難達到信息熵的大小。Huffman編碼解碼必須要有碼表，如果消息數(shù)目很多，那么所需要存儲的碼表也很大，這將影響系統(tǒng)的存儲量及編、譯碼速度。統(tǒng)計編碼一010.11010.2600.3510.611101000.391.00碼字碼長01200233344平均碼長：2.72Huffman編碼過程a10.20a20.19a30.18a40.17a50.15a60.10a70.01算術(shù)編碼算術(shù)編碼把一個信源集合表示為實數(shù)線上的0到1之間的一個區(qū)間。這個集合中的每個元素都要用來縮短這個區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要一些更多的數(shù)位來表示這個區(qū)間，這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個信源的概率模型，然后用這些概率來縮小表示信源集的區(qū)間。統(tǒng)計編碼二算術(shù)編碼新子區(qū)間的起始位置＝前子區(qū)間的起始位置＋當前符號的區(qū)間左端×前子區(qū)間長度新子區(qū)間的長度＝前子區(qū)間的長度×當前符號的概率（等價于范圍長度）

最后得到的子區(qū)間的長度決定了表示該區(qū)域內(nèi)的某一個數(shù)所需的位數(shù)。統(tǒng)計編碼二算術(shù)編碼[例]假設(shè)信源符號為{00,01,10,11}，這些符號的概率分別為{0.1,0.4,0.2,0.3}，根據(jù)這些概率可把間隔[0,1)分成4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，其中[x,y)表示半開放間隔，即包含x不包含y。上面的信息可綜合在下表中。符號00011011概率0.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)統(tǒng)計編碼二算術(shù)編碼統(tǒng)計編碼二算術(shù)編碼要注意的幾個問題：由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔[0,1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。統(tǒng)計編碼二行程編碼是最簡單、最古老的壓縮技術(shù)之一，主要技術(shù)是檢測重復(fù)的比特或字符序列，并用它們的出現(xiàn)次數(shù)取而代之。該方法有兩大模式：一是消零(消空白)，二是行(游)程(runlength)編碼。

消零(或消空白)法

將數(shù)字中連續(xù)的“0”或文本中連續(xù)的空白用一個標識符(或特殊字符)后跟數(shù)字N(連續(xù)“0”的個數(shù))來代替。

如數(shù)字序列：742300000000000000000055編碼為：7423Z1855統(tǒng)計編碼三行程編碼法

任何重復(fù)的字符序列可被一個短格式取代。該算法適合于任何重復(fù)的字符。一組n個連續(xù)的字符c將被

c和一個特殊的字符取代。當然，若給定字符僅重復(fù)兩次就不要用此方法。 任何重復(fù)的字符由“該字符＋記號(M)＋重復(fù)次數(shù)”代替。例如字符序列：Name:..........CR

編碼為：Name:

.M10CR統(tǒng)計編碼三詞典編碼詞典編碼(dictionaryencoding)根據(jù)數(shù)據(jù)本身包含有重復(fù)代碼這個特性。例如文本文件和光柵圖像。兩類統(tǒng)計編碼四第一類: 查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。

統(tǒng)計編碼四第二類:從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典(dictionaryofthephrases)”，編碼數(shù)據(jù)過程中當遇到已經(jīng)在詞典中出現(xiàn)的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身。統(tǒng)計編碼四統(tǒng)計編碼四LZW編碼簡介LZW通過建立一個字符串表,用較短的代碼來表示較長的字符串來實現(xiàn)壓縮（第二類）。字符串和編碼的對應(yīng)關(guān)系是在壓縮過程中動態(tài)生成的,并且隱含在壓縮數(shù)據(jù)中,解壓的時候根據(jù)表來進行恢復(fù),是一種無損壓縮。全稱Lempel-Ziv-WelchEncoding，簡稱LZW的壓縮算法。統(tǒng)計編碼四LZW壓縮有三個重要的對象數(shù)據(jù)流(CharStream)編碼流(CodeStream)編譯表(StringTable)。在編碼時，數(shù)據(jù)流是輸入對象（文本文件的數(shù)據(jù)序列），編碼流就是輸出對象（經(jīng)過壓縮運算的編碼數(shù)據(jù)）；在解碼時，編碼流則是輸入對象，數(shù)據(jù)流是輸出對象；而編譯表是在編碼和解碼時都須要用借助的對象。統(tǒng)計編碼四LZW編碼基本原理提取原始文本文件數(shù)據(jù)中的不同字符，基于這些字符創(chuàng)建一個編譯表，然后用編譯表中的字符的索引來替代原始文本文件數(shù)據(jù)中的相應(yīng)字符，減少原始數(shù)據(jù)大