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

1、2008-07-01 1 多媒體技術(shù)教程多媒體技術(shù)教程 第第2章章 數(shù)據(jù)無損壓縮數(shù)據(jù)無損壓縮 2 of 37 第第2章章 數(shù)據(jù)無損壓縮目錄數(shù)據(jù)無損壓縮目錄 n2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余 2.1.1 冗余概念 2.1.2 決策量 2.1.3 信息量 2.1.4 熵 2.1.5 數(shù)據(jù)冗余量 n2.2 統(tǒng)計編碼統(tǒng)計編碼 2.2.1 香農(nóng)-范諾編碼 2.2.2 霍夫曼編碼 2.2.3 算術(shù)編碼 n2.3 RLE編碼編碼 n2.4 詞典編碼詞典編碼 2.4.1 詞典編碼的思想 2.4.2 LZ77算法 2.4.3 LZSS算法 2.4.4 LZ78算法 2.4.5 LZW算法 n參考文獻(xiàn)和站點參考文獻(xiàn)

2、和站點 3 of 37 2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述 n數(shù)據(jù)可被壓縮的依據(jù)數(shù)據(jù)可被壓縮的依據(jù) 數(shù)據(jù)本身存在冗余 聽覺系統(tǒng)的敏感度有限 視覺系統(tǒng)的敏感度有限 n三種多媒體數(shù)據(jù)類型三種多媒體數(shù)據(jù)類型 文字 (text)數(shù)據(jù)無損壓縮 n根據(jù)數(shù)據(jù)本身的冗余(Based on data redundancy) 聲音(audio)數(shù)據(jù)有損壓縮 n根據(jù)數(shù)據(jù)本身的冗余(Based on data redundancy) n根據(jù)人的聽覺系統(tǒng)特性( Based on human hearing system) 圖像(image)/視像(video) 數(shù)據(jù)有損壓縮 n根據(jù)數(shù)據(jù)本身的冗余(Based on

3、 data redundancy) n根據(jù)人的視覺系統(tǒng)特性(Based on human visual system) 4 of 37 2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述(續(xù)續(xù)1) n數(shù)據(jù)無損壓縮的理論數(shù)據(jù)無損壓縮的理論信息論信息論(information theory) 1948年創(chuàng)建的數(shù)學(xué)理論的一個分支學(xué)科，研究信息的編碼、 傳輸和存儲 該術(shù)語源于Claude Shannon (香農(nóng))發(fā)表的“A Mathematical Theory of Communication”論文題目，提議用二進(jìn)制數(shù)據(jù)對信 息進(jìn)行編碼 最初只應(yīng)用于通信工程領(lǐng)域，后來擴(kuò)展到包括計算在內(nèi)的其 他多個領(lǐng)域，如信息

4、的存儲、信息的檢索等。在通信方面， 主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問題。 n數(shù)據(jù)無損壓縮的方法數(shù)據(jù)無損壓縮的方法 霍夫曼編碼(Huffman coding ) 算術(shù)編碼(arithmetic coding) 行程長度編碼(run-length coding) 詞典編碼(dictionary coding) 5 of 37 2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述(續(xù)續(xù)2) nThe Father of Information Theory Claude Elwood Shannon Born: 30 April 1916 in Gaylord, Michigan, USA D

5、ied: 24 Feb 2001 in Medford, Massachusetts, USA http:/www.bell- n信息論之父介紹信息論之父介紹 6 of 37 2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余 n冗余概念冗余概念 人為冗余 n在信息處理系統(tǒng)中，使用兩臺計算機(jī)做同樣的工作是提高 系統(tǒng)可靠性的一種措施-冗余設(shè)備冗余設(shè)備 n在數(shù)據(jù)存儲和傳輸中，為了檢測和恢復(fù)在數(shù)據(jù)存儲或數(shù)據(jù) 傳輸過程中出現(xiàn)的錯誤，根據(jù)使用的算法的要求，在數(shù)據(jù) 存儲或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這 個額外的數(shù)據(jù)就是冗余數(shù)據(jù)冗余數(shù)據(jù)-檢錯碼，糾錯碼檢錯碼，糾錯碼 視聽冗余 n由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，

6、在圖像數(shù)據(jù)和聲 音數(shù)據(jù)中，有些數(shù)據(jù)確實是多余的，使用算法將其去掉后 并不會丟失實質(zhì)性的信息或含義，對理解數(shù)據(jù)表達(dá)的信息 幾乎沒有影響 數(shù)據(jù)冗余 n不考慮數(shù)據(jù)來源時，單純數(shù)據(jù)集中也可能存在多余的數(shù)據(jù)， 去掉這些多余數(shù)據(jù)并不會丟失任何信息，這種冗余稱為數(shù) 據(jù)冗余，而且還可定量表達(dá) 7 of 37 2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)1) n決策量決策量(decision content) 在有限數(shù)目的互斥事件集合中，決策量是事 件數(shù)的對數(shù)值 在數(shù)學(xué)上表示為 H0=log(n) 其中，n是事件數(shù) 決策量的單位由對數(shù)的底數(shù)決定 nSh (Shannon): 用于以2為底的對數(shù) nNat (natural

7、 unit): 用于以e為底的對數(shù) nHart (hartley)：用于以10為底的對數(shù) 8 of 37 2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)2) n信息量信息量(information content) 具有確定概率事件的信息的定量度量 在數(shù)學(xué)上定義為 其中， 是事件出現(xiàn)的概率 一個等概率事件的集合，每個事件的信息量等 于該集合的決策量 22 ( )log 1/( )log( )I xp xp x ( )p x 9 of 37 舉例：假設(shè)假設(shè)X=a,b,c是由是由3個事件構(gòu)成的集合，個事件構(gòu)成的集合，p(a)=0.5， p(b)=0.25，p(b)=0.25分別是事件分別是事件a, b和和c出

8、現(xiàn)的概率，這些事出現(xiàn)的概率，這些事 件的信息量分別為，件的信息量分別為， I(a)=log2(1/0.50)=1 sh I(b)=log2(1/0.25)=2 sh I(c)=log2(1/0.25)=2 sh p(a)=0.5是符號a 在I中出現(xiàn)的概率； log2(1/ p(a)表示包含在I 中的信息量，也就是編碼 a所需要的位數(shù)。 例如例如: : 一幅用一幅用256256級灰度表示的圖像，如果每一個象素級灰度表示的圖像，如果每一個象素 點灰度的概率均為點灰度的概率均為P=1/256 1/256 ，編碼每一個象素點就需，編碼每一個象素點就需 要要8 8位。位。 10 of 37 2.1 數(shù)據(jù)

9、的冗余數(shù)據(jù)的冗余(續(xù)續(xù)3) n熵熵(entropy) 按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的 集合中，熵為事件的信息量的平均值，也稱事件的平均信息 量(mean information content) 用數(shù)學(xué)表示為 熵熵-最佳平均編碼位數(shù)最佳平均編碼位數(shù) 11 of 37 2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)4) n數(shù)據(jù)的冗余量數(shù)據(jù)的冗余量 12 of 37 2.2 統(tǒng)計編碼統(tǒng)計編碼 n統(tǒng)計編碼統(tǒng)計編碼 給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮方法 n編碼方法編碼方法 香農(nóng)-范諾編碼 霍夫曼編碼 算術(shù)編碼 n編碼特性編碼特性 香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是

10、根據(jù)符 號集中各個符號出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越出現(xiàn)次數(shù)越 多的符號，給它分配的代碼位數(shù)越少多的符號，給它分配的代碼位數(shù)越少 算術(shù)編碼使用0和1之間的實數(shù)的間隔長度代表概率大 小，概率越大間隔越長，編碼效率可接近于熵 13 of 37 2.2.1 統(tǒng)計編碼統(tǒng)計編碼香農(nóng)香農(nóng)-范諾編碼范諾編碼 n香農(nóng)香農(nóng)-范諾編碼范諾編碼(ShannonFano coding) 在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不 可壓縮的信息量 在計算熵時，如果對數(shù)的底數(shù)用2，熵的單位就用 “香農(nóng)(Sh)”，也稱“位(bit)” ?！拔弧笔?948年 Shannon首次使用的術(shù)語。例如 最早闡述和實現(xiàn)“從上到下”

11、的熵編碼方法的人是 Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范 諾(Shannon- Fano)編碼法 14 of 37 2.2.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼 n香農(nóng)香農(nóng)-范諾編碼舉例范諾編碼舉例 有一幅40個像素組成的灰度圖像，灰度共有5級，分別用符號 A，B，C，D和E表示。40個像素中出現(xiàn)灰度A的像素數(shù)有15 個，出現(xiàn)灰度B的像素數(shù)有7個，出現(xiàn)灰度C的像素數(shù)有7個， 其余情況見表2-1 n(1) 計算該圖像可能獲得的壓縮比的理論值 n(2) 對5個符號進(jìn)行編碼 n(3) 計算該圖像可能獲得的壓縮比的實際值 表表2-1 符號在圖像中出現(xiàn)的數(shù)目符號在圖像中出現(xiàn)的

12、數(shù)目 符號ABCDE 出現(xiàn)的次數(shù)157765 出現(xiàn)的概率15/407/407/406/405/40 15 of 37 符號符號ABCDE 出現(xiàn)的次數(shù)出現(xiàn)的次數(shù)157765 按照仙農(nóng)理論，這幅圖像的熵熵為 H(x) = (15/40)loglog2 2(40/15) + (7/40)loglog2 2(40/7) + + (5/40) loglog2 2(40/5) =2.196 這就是說每個符號用2.196位表示，40個象素需用87.84位。 因此在理論上，這幅圖像的的壓縮比為因此在理論上，這幅圖像的的壓縮比為 120:87.841.37:1， 實際上就是實際上就是 3:2.1961.37 按

13、照常規(guī)的編碼方法，表示5個符號最少需要3位，這就意味每個像素 用3位，編碼這幅圖像總共需要120位。 16 of 37 2.2.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼(續(xù)續(xù)2) (2) 符號編碼符號編碼 對每個符號進(jìn)行編碼時采用“從上到下從上到下”的方法。 首先按照符號出現(xiàn)的頻度或概率排序，如A，B，C， D和E，見表2-2。然后使用遞歸方法分成兩個部分， 每一部分具有近似相同的次數(shù)，如圖所示 17 of 37 采用從上到下的方法進(jìn)行編碼。首先按照符號出現(xiàn)的頻度或概率排序，例采用從上到下的方法進(jìn)行編碼。首先按照符號出現(xiàn)的頻度或概率排序，例 如如A A、B B、C C、D D和和E E，然后使用遞歸方法

14、分成兩個部分，每一部分具有近似，然后使用遞歸方法分成兩個部分，每一部分具有近似 相同的次數(shù)相同的次數(shù) 符號符號 AB C D E 出現(xiàn)的次出現(xiàn)的次 數(shù)數(shù) 15 7 7 6 5 ABC DE 按照這種方法進(jìn)行編碼得到的總位數(shù)為 15*2+7*2+7*2+6*3+5*3=91實際的壓縮比為120:911.32 : 1 01 01 01 0 1 A 00 B 01 C 10 D 110 E 111 18 of 37 2.2.2 統(tǒng)計編碼統(tǒng)計編碼霍夫曼編碼霍夫曼編碼 n霍夫曼編碼霍夫曼編碼(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和描述的“從下 到上”的熵編碼

15、方法 根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的 一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次 數(shù)越多，其編碼的位數(shù)就越少 廣泛用在JPEG, MPEG, H.26X等各種信息編碼標(biāo)準(zhǔn)中 19 of 37 即從下到上的編碼方法，編碼步驟：即從下到上的編碼方法，編碼步驟： ：初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M(jìn)行排序。 ：把概率最小的兩個符號組成一個節(jié)點P1 ：重復(fù)步驟，得到節(jié)點P2，P3，P4，PN，形成一棵樹，其中 的PN稱為根節(jié)點 ：從根節(jié)點PN開始到每個符號的樹葉，從上到標(biāo)上0(上枝)和1(下 枝)，至于哪個為1哪個為0則無關(guān)緊要，最后的結(jié)果只是分配的 代碼不同，代碼

16、的平均長度是相同的。 ：從根節(jié)點PN開始順著樹枝到每個葉子分別寫出每個符號的代碼 次數(shù)次數(shù) 概率概率 A 15 0.375 B70.175 C70.175 D60.150 E50.125 0.275 0.35 0.625 0 1 0 1 0 1 0 1 0 100 101 110 111 編碼得到的總位數(shù)為1*15+3*(7+7+6+5)=90 20 of 37 2.2.2 霍夫曼編碼 Case Study 1 n霍夫曼編碼舉例霍夫曼編碼舉例1 現(xiàn)有一個由5個不同符號組成的30個符號的字符串： BABACACADADABBCBABEBEDDABEEEBB 計算 (1) 該字符串的霍夫曼碼 (2

17、) 該字符串的熵 (3) 該字符串的平均碼長 (4) 編碼前后的壓縮比 21 of 37 2.2.2 霍夫曼編碼 Case Study 1 (續(xù)續(xù)1) 符號 出現(xiàn)的 次數(shù) 概率log2(1/pi）分配的代碼需要的位數(shù) B100.331.585? A80.271.907? C30.13.322? D40.132.907? E50.172.585? 合計30 符號出現(xiàn)的概率符號出現(xiàn)的概率 22 of 37 2.2.2 霍夫曼編碼霍夫曼編碼 Case Study 1 (續(xù)續(xù)3) 符號符號 B (10) A (8) E (5) D (4) C (3)P1 (0.23) P2 (0.4) P3 (0.6

18、) P4 (1.0) 0 1 1 0 1 0 1 0 代碼代碼 B(11) A(10) E(00) D(011) C(010) 0.33 0.27 0.17 0.13 0.1 23 of 37 2.2.2 霍夫曼編碼霍夫曼編碼 Case Study 1 (續(xù)續(xù)4) 符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù) B101.5851120 A81.9071016 C33.3220109 D42.90701112 E52.5850010 合計301.067 30個字符組成的字符串需要個字符組成的字符串需要67位位 5個符號的代碼 24 of 37 2.2.2 霍夫曼編碼霍夫曼編碼 Case

19、 Study 1 (續(xù)續(xù)5) 2 11 ()( ) ( )( )log( ) nn iiii ii H Xp x I xp xp x (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 (8lg8 10lg10 3lg3 4lg4 5 lg5) / (30log22) = ( 44.313624.5592)/ 9.0308 2.1874 (Sh) 符 號 出現(xiàn)的 次數(shù) 概率log2(1/pi

20、） B100.331.585 A80.271.907 C30.13.322 D40.132.907 E50.172.585 =0.33*1.585+0.27*1.907+0.1*3.322+0.13*2.907+0.17*2.585 =2.1876 25 of 37 2.2.2 霍夫曼編碼霍夫曼編碼 Case Study 1 (續(xù)續(xù)6) (3) 計算該字符串的平均碼長計算該字符串的平均碼長 平均碼長： (28210333425)/30 2.233 位/符號 壓縮比壓縮比: 90/67=1.34:1 1 ( ) N ii i ll p l 平均碼長：平均碼長：67/30=2.233位位 (4)

21、計算編碼前后的壓縮比計算編碼前后的壓縮比 n編碼前：5個符號需3位，30個字符，需要90 位 n編碼后：共67位 26 of 37 2.2.3 統(tǒng)計編碼統(tǒng)計編碼算術(shù)編碼算術(shù)編碼 n算術(shù)編碼算術(shù)編碼(arithmetic coding) 給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮技術(shù) 基本思想是用0和1之間的一個數(shù)值范圍表示輸入流中 的一個字符，而不是給輸入流中的每個字符分別指定 一個碼字 實質(zhì)上是為整個輸入字符流分配一個“碼字”，因此 它的編碼效率可接近于熵 27 of 37 2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例 n例例2.3（取自教材）（取自教材） 假設(shè)信源符號為00, 01, 10, 11

22、，它們的概率分別為 0.1, 0.4, 0.2, 0.3 對二進(jìn)制消息序列10 00 11 00 10 11 01 進(jìn)行算術(shù)編碼 (1)初始化初始化 根據(jù)信源符號的概率把間隔0, 1)分成如表2-4所示的4個子間 隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)。其中x, y)的表示半開 放間隔 符號00011011 概率0.3 初始編碼間隔0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1 28 of 37 算術(shù)編碼中，消息用算術(shù)編碼中，消息用0 0到到1 1之間的實數(shù)進(jìn)行編碼之間的實數(shù)進(jìn)行編碼 兩個基本的參數(shù)：兩個基本的參數(shù)：符

23、號的概率和它的和它的編碼間隔。 信源符號信源符號 00011011 概率概率0.3 初始編碼間隔初始編碼間隔0, 0.1)0, 0.1)0.1, 0.5)0.1, 0.5)0.5, 0.7)0.5, 0.7)0.7, 1) 0.7, 1) 如果二進(jìn)制消息序列的輸入為：10 00 11 00 10 11 01。 編碼時首先輸入的符號是編碼時首先輸入的符號是1010, ,找到它的編碼范圍是找到它的編碼范圍是0.5, 0.7), 0.5, 0.7), d=0.2d=0.2 輸入的符號輸入的符號00,00,編碼范圍是編碼范圍是0, 0.1)0, 0.1) low=0.5+ low=0

24、.5+d d* *0 0=0.5+=0.5+0.20.2* *0 0=0.5=0.5 high=0.5+ high=0.5+d d* *0.10.1=0.5+=0.5+0.20.2* *0.10.1=0.52 =0.52 輸出編碼為輸出編碼為0.50.5，0.520.52） d=high-low=0.02d=high-low=0.02 3 3） 輸入的符號輸入的符號11,11,編碼范圍是編碼范圍是0.7, 1)0.7, 1) low=0.5+ low=0.5+0.020.02* *0.70.7=0.514=0.514 high=0.5+ high=0.5+0.020.02* *1 1=0.52

25、 =0.52 輸出編碼為輸出編碼為0.5140.514，0.520.52） d=0.006d=0.006 29 of 37 4) 輸入的符號輸入的符號00,00,編碼范圍是編碼范圍是0, 0.1)0, 0.1) low=0.514+ low=0.514+0.0060.006* *0 0=0.514=0.514 high=0.514+ high=0.514+0.0060.006* *0.10.1=0.5146 =0.5146 輸出編碼為輸出編碼為0.5140.514，0.51460.5146） d=0.0006d=0.0006 5) 輸入的符號輸入的符號10,10,編碼范圍是編碼范圍是0.5,

26、0.7)0.5, 0.7) low=0.514+ low=0.514+0.00060.0006* *0.50.5=0.5143=0.5143 high=0.514+ high=0.514+0.00060.0006* *0.70.7=0.51442 =0.51442 輸出編碼為輸出編碼為0.51430.5143，0.514420.51442） d=0.00012d=0.00012 依次類推依次類推 注意注意: :消息的編碼輸出可以是最后一個間隔中的任意數(shù)消息的編碼輸出可以是最后一個間隔中的任意數(shù) 30 of 37 31 of 37 32 of 37 在算術(shù)編碼中需要注意的幾個問題：在算術(shù)編碼中需

27、要注意的幾個問題： 運算中出現(xiàn)溢出是一個明顯的問題， 算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，在間隔0, 1)中的一個實數(shù)，因此譯 碼器在接受到表示這個實數(shù)的所有位之前不能進(jìn)行譯碼。 如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。 靜態(tài)算術(shù)編碼-信源符號的概率是固定的。 自適應(yīng)算術(shù)編碼中-信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地 進(jìn)行修改，在編碼期間估算信源符號概率的過程叫做建模。 33 of 37 2.3 RLE編碼編碼 n行程長度編碼(Run-Length Coding) 一種無損壓縮數(shù)據(jù)編碼技術(shù)，它利用重復(fù)的數(shù)據(jù)單元有相同的數(shù)值這一 特點對數(shù)據(jù)進(jìn)行壓縮。對相同的數(shù)值只編碼一次，同時計算出相同值重 復(fù)出現(xiàn)的次數(shù)行程長度行程長度。在JPEG