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

《第章無損數(shù)據(jù)壓縮》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第4章無損數(shù)據(jù)壓縮　　數(shù)據(jù)壓縮可分成兩種類型，一種叫做無損壓縮，另一種叫做有損壓縮?！　o損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合。一個很常見的例子是磁盤文件的壓縮。根據(jù)目前的技術(shù)水平，無損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)壓縮算法。　　有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后

2、的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號不一定非要和原始信號完全相同的場合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺系統(tǒng)和聽覺系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比。　　本章主要介紹目前用得最多和技術(shù)最成熟的無損壓縮編碼技術(shù)，包括包含霍夫曼編碼、算術(shù)編碼、RLE編碼和詞典編碼。對于不打算開發(fā)壓縮技術(shù)和編寫壓縮程序的讀者可不必深究編譯碼的詳細(xì)過程。4.1香農(nóng)-范諾

3、與霍夫曼編碼4.1.1香農(nóng)-范諾編碼　　香農(nóng)-范諾編碼算法需要用到下面兩個基本概念：　　1、Entropy(熵)的概念　　1）熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學(xué)上就是概率越小?！　?）某個事件的信息量用Ii=-log2Pi表示，其中pi為第i個事件的概率，0

4、含在Si中的信息量，也就是編碼Si所需要的位數(shù)。例如，一幅用256級灰度表示的圖像，如果每一個象素點(diǎn)灰度的概率均為Pi=1/256，編碼每一個象素點(diǎn)就需要8位?！　例4.1]有一幅40個象素組成的灰度圖像，灰度共有5級，分別用符號A、B、C、D和E表示，40個象素中出現(xiàn)灰度A的象素數(shù)有15個，出現(xiàn)灰度B的象素數(shù)有7個，出現(xiàn)灰度C的象素數(shù)有7個等等，如表4-01所示。如果用3個位表示5個等級的灰度值，也就是每個象素用3位表示，編碼這幅圖像總共需要120位。表4-01符號在圖像中出現(xiàn)的數(shù)目符號ABCDE出

5、現(xiàn)的次數(shù)157765　　按照仙農(nóng)理論，這幅圖像的熵為　　H(S)=(15/40)′log2(40/15)+(7/40)′log2(40/7)+???+(5/40′log2(40/5)=2.196這就是說每個符號用2.196位表示，40個象素需用87.84位。　　最早闡述和實(shí)現(xiàn)這種編碼的是Shannon(1948年)和Fano(1949年)，因此被稱為仙農(nóng)-范諾(Shannon-Fano)算法。這種方法采用從上到下的方法進(jìn)行編碼。首先按照符號出現(xiàn)的頻度或概率排序，例如，A，B，C，D和E，如表4-02所示

6、。然后使用遞歸方法分成兩個部分，每一部分具有近似相同的次數(shù)，如圖4-01所示。按照這種方法進(jìn)行編碼得到的總位數(shù)為91。壓縮比約為1.3:1。表4-02Shannon-Fano算法舉例表符號出現(xiàn)的次數(shù)(Pi)log2(1/P)分配的代碼需要的位數(shù)A15(0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5(0.125)3.000011115　圖4-01香農(nóng)-范諾算法編碼舉例4.1.2霍夫曼編碼　　霍夫曼(H

7、uffman)在1952年提出了另一種編碼方法，即從下到上的編碼方法。現(xiàn)仍以一個具體的例子說明它的編碼步驟：　　1、初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M(jìn)行排序，如表4-03和圖4-02所示?！　?、把概率最小的兩個符號組成一個節(jié)點(diǎn)，如圖4-02中的D和E組成節(jié)點(diǎn)P1?！　?、重復(fù)步驟2，得到節(jié)點(diǎn)P2、P3和P4，形成一棵“樹”，其中的P4稱為根節(jié)點(diǎn)?！　?、從根節(jié)點(diǎn)P4開始到相應(yīng)于每個符號的“樹葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)，至于哪個為“1”哪個為“0”則無關(guān)緊要，最后的

8、結(jié)果僅僅是分配的代碼不同，而代碼的平均長度是相同的?！　?、從根節(jié)點(diǎn)P4開始順著樹枝到每個葉子分別寫出每個符號的代碼，如表4-03所示?！　?、按照仙農(nóng)理論，這幅圖像的熵為　　　H(S)＝(15/39)′log2(39/15)+(7/39)′log2(39/7)+???+(5/39)′log2(39/5)＝2.1859log2壓縮比1.37:1。表4-03霍夫曼編碼舉例符號出現(xiàn)的次數(shù)log2(1/pi)分配的代碼需要的位數(shù)A15(0.384