ch02數(shù)據(jù)無損壓縮高教書苑

1、多媒體技術(shù)教程多媒體技術(shù)教程第第2章章 數(shù)據(jù)無損壓縮數(shù)據(jù)無損壓縮1高級教育第第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參考文獻和站點參考文獻和站點 2 of 42高級教育2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述n

2、數(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 data redundancy)n根據(jù)人的視覺系統(tǒng)特性(based on human

3、visual system) 3 of 42高級教育2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述(續(xù)續(xù)1)n數(shù)據(jù)無損壓縮的理論數(shù)據(jù)無損壓縮的理論信息論信息論(information theory) 1948年創(chuàng)建的數(shù)學理論的一個分支學科，研究信息的編碼、傳輸和存儲該術(shù)語源于claude shannon (香農(nóng))發(fā)表的“a mathematical theory of communication”論文題目，提議用二進制數(shù)據(jù)對信息進行編碼最初只應用于通信工程領域，后來擴展到包括計算在內(nèi)的其他多個領域，如信息的存儲、信息的檢索等。在通信方面，主要研究數(shù)據(jù)量、傳輸速率、信道容量、傳輸正確率等問題。 n數(shù)據(jù)

4、無損壓縮的方法數(shù)據(jù)無損壓縮的方法霍夫曼編碼(huffman coding )算術(shù)編碼(arithmetic coding)行程長度編碼(run-length coding)詞典編碼(dictionary coding) 4 of 42高級教育2.0 數(shù)據(jù)無損壓縮概述數(shù)據(jù)無損壓縮概述(續(xù)續(xù)2)nthe father of information theoryclaude elwood shannonborn: 30 april 1916 in gaylord, michigan, usadied: 24 feb 2001 in medford, massachusetts, usan信息論之父介

5、紹信息論之父介紹 5 of 42高級教育2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余n冗余概念冗余概念人為冗余n在信息處理系統(tǒng)中，使用兩臺計算機做同樣的工作是提高系統(tǒng)可靠性的一種措施此種冗余乃有意為之n在數(shù)據(jù)存儲和傳輸中，為了檢測和恢復在數(shù)據(jù)存儲或數(shù)據(jù)傳輸過程中出現(xiàn)的錯誤，根據(jù)使用的算法的要求，在數(shù)據(jù)存儲或數(shù)據(jù)傳輸之前把額外的數(shù)據(jù)添加到用戶數(shù)據(jù)中，這個額外的數(shù)據(jù)就是冗余數(shù)據(jù)比如數(shù)字簽名、水印等等視聽冗余n由于人的視覺系統(tǒng)和聽覺系統(tǒng)的局限性，在圖像數(shù)據(jù)和聲音數(shù)據(jù)中，有些數(shù)據(jù)確實是多余的，使用算法將其去掉后并不會丟失實質(zhì)性的信息或含義，對理解數(shù)據(jù)表達的信息幾乎沒有影響數(shù)據(jù)冗余n不考慮數(shù)據(jù)來源時，單純數(shù)據(jù)集中也可能

6、存在多余的數(shù)據(jù)，去掉這些多余數(shù)據(jù)并不會丟失任何信息，這種冗余稱為數(shù)據(jù)冗余，而且還可定量表達 6 of 42高級教育2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)1)n決策量決策量(decision content)在有限數(shù)目的互斥事件集合中，決策量是事件數(shù)的對數(shù)值在數(shù)學上表示為 h0=log(n) 其中，n是事件數(shù)決策量的單位由對數(shù)的底數(shù)決定nsh (shannon): 用于以2為底的對數(shù)nnat (natural unit): 用于以e為底的對數(shù)nhart (hartley)：用于以10為底的對數(shù) 7 of 42高級教育2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)2)n信息量信息量(information con

7、tent)具有確定概率事件的信息的定量度量在數(shù)學上定義為 其中， 是事件出現(xiàn)的概率 舉例：假設x=a,b,c是由3個事件構(gòu)成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分別是事件a, b和c出現(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一個等概率事件的集合，每個事件的信息量等于該集合的決策量22( )log 1/( )log( )i xp xp x ( )p x 8 of 42高級教育2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)3)n熵熵(entropy)按

8、照香農(nóng)(shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(mean information content) 用數(shù)學表示為 9 of 42高級教育2.1 數(shù)據(jù)的冗余數(shù)據(jù)的冗余(續(xù)續(xù)4)n數(shù)據(jù)的冗余量數(shù)據(jù)的冗余量 10 of 42高級教育2.2 統(tǒng)計編碼統(tǒng)計編碼n統(tǒng)計編碼統(tǒng)計編碼給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮方法n編碼方法編碼方法香農(nóng)-范諾編碼霍夫曼編碼算術(shù)編碼n編碼特性編碼特性香農(nóng)-范諾編碼和霍夫曼編碼的原理相同，都是根據(jù)符號集中各個符號出現(xiàn)的頻繁程度來編碼，出現(xiàn)次數(shù)越多的符號，給它分配的代碼位數(shù)越少算術(shù)編碼使用0和1之間的

9、實數(shù)的間隔長度代表概率大小，概率越大間隔越長，編碼效率可接近于熵 11 of 42高級教育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)“從上到下”的熵編碼方法的人是shannon(1948年)和fano(1949年)，因此稱為香農(nóng)-范諾(shannon- fano)編碼法 12 of 42高級教育2.2.1 香

10、農(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-1n(1) 計算該圖像可能獲得的壓縮比的理論值n(2) 對5個符號進行編碼n(3) 計算該圖像可能獲得的壓縮比的實際值表表2-1 符號在圖像中出現(xiàn)的數(shù)目符號在圖像中出現(xiàn)的數(shù)目符號abcde出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/40 13 of 42高級教育2.2.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼(續(xù)續(xù)1)(1) 壓縮比

11、的理論值壓縮比的理論值按照常規(guī)的編碼方法，表示5個符號最少需要3位，如用000表示a，001表示b，100表示e，其余3個代碼 (101，110，111)不用。這就意味每個像素用3位，編碼這幅圖像總共需要120位。按照香農(nóng)理論，這幅圖像的熵為21222222()( )log( ) ( )log ( ( )( )log ( ( )( )log ( ( ) = (15/40)log (40/15)+(7/40)log (40/7)+ +(5/40)log (40/5)2.196niiih xp xp xp ap ap bp bp ep e 這個數(shù)值表明，每個符號不需要用3位構(gòu)成的代碼表示，而用2.

12、196位就可以，因此40個像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.841.37:1，實際上就是3:2.1961.37 14 of 42高級教育2.2.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼(續(xù)續(xù)2)(2) 符號編碼符號編碼對每個符號進行編碼時采用“從上到下”的方法。首先按照符號出現(xiàn)的頻度或概率排序，如a，b，c，d和e，見表2-2。然后使用遞歸方法分成兩個部分，每一部分具有近似相同的次數(shù)，如圖2-1所示 15 of 42高級教育2.2.1 香農(nóng)香農(nóng)-范諾編碼范諾編碼(續(xù)續(xù)3)（3）壓縮比的實際值）壓縮比的實際值按照這種方法進行編碼需要的總位數(shù)為30+14+14+1

13、8+1591，實際的壓縮比為120:911.32 : 1 圖2-1 香農(nóng)-范諾算法編碼舉例 16 of 42高級教育2.2.2 統(tǒng)計編碼統(tǒng)計編碼霍夫曼編碼霍夫曼編碼n霍夫曼編碼霍夫曼編碼(huffman coding)霍夫曼(d.a. huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少廣泛用在jpeg, mpeg, h.26x等各種信息編碼標準中 17 of 42高級教育2.2.2 霍夫曼編碼 case study 1n霍夫曼編碼舉例霍夫曼編碼舉例1現(xiàn)有一個由5

14、個不同符號組成的30個符號的字符串：babacacadadabbcbabebeddabeeebb計算(1) 該字符串的霍夫曼碼(2) 該字符串的熵(3) 該字符串的平均碼長(4) 編碼前后的壓縮比 18 of 42高級教育2.2.2 霍夫曼編碼 case study 1 (續(xù)續(xù)1)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)b101.585?a81.907?c33.322?d42.907?e52.585?合計30符號出現(xiàn)的概率符號出現(xiàn)的概率 19 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 1 (續(xù)續(xù)2)(1) 計算該字符串的霍夫曼碼計算該字符串的霍夫曼

15、碼步驟：按照符號出現(xiàn)概率大小的順序?qū)Ψ栠M行排序步驟：把概率最小的兩個符號組成一個節(jié)點p1步驟：重復步驟，得到節(jié)點p2，p3，p4， pn，形成一棵樹，其中的pn稱為根節(jié)點步驟：從根節(jié)點pn開始到每個符號的樹葉，從上到下 標上0(上枝)和1(下枝)，至于哪個為1哪個為0則 無關(guān)緊要，但通常把概率大的標成1，概率小的 標成0步驟：從根節(jié)點pn開始順著樹枝到每個葉子分別寫出 每個符號的代碼 20 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 1 (續(xù)續(xù)3)符號符號b (10)a (8)e (5)d (4)c (3)p1 (7)p2 (12)p3 (18)p4 (30)0

16、1101010代碼代碼b(11)a(10)e(00)d(011)c(010) 21 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 1 (續(xù)續(xù)4)符號出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)b101.5851120a81.9071016c33.3220109d42.90701112e52.5850010合計301.06730個字符組成的字符串需要個字符組成的字符串需要67位位5個符號的代碼 22 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 1 (續(xù)續(xù)5) (2) 計算該字符串的熵計算該字符串的熵 其中， 是事件 的集合， 并滿足

17、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 4 lg4 5 lg5) / (30log22) = ( 44.313624.5592)/ 9.0308 2.1874 (sh)1 ,nxxx1( )1niip x(1,2, )ix in211()( ) ( )( )log( )nniiiiiih xp x i xp xp x 23 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 cas

18、e study 1 (續(xù)續(xù)6)(3) 計算該字符串的平均碼長計算該字符串的平均碼長平均碼長： (28210333425)/30 2.233 位/符號 壓縮比壓縮比: 90/67=1.34:11( )niiill p l 平均碼長：平均碼長：67/30=2.233位位(4) 計算編碼前后的壓縮比計算編碼前后的壓縮比n編碼前：5個符號需3位，30個字符，需要90位n編碼后：共67位 24 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 2n霍夫曼編碼舉例霍夫曼編碼舉例2編碼前nn = 8 symbols: a,b,c,d,e,f,g,h, n3 bits per symb

19、ol (n =23=8)np(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) 編碼效率 25 of 42高級教育2.2.2 霍夫曼編碼霍夫曼編碼 case study 2 (續(xù)續(xù)2)average length per symbol (before coding):8133 bits/symbol( )ilp i82125821 bits/symbol( )log( ).ihp ip i2 6

20、3 bits/symbol .hufl98/%hufh l(2) entropy:(3) average length per symbol (with huffman coding):(4) efficiency of the code: 26 of 42高級教育2.2.3 統(tǒng)計編碼統(tǒng)計編碼算術(shù)編碼算術(shù)編碼n算術(shù)編碼算術(shù)編碼(arithmetic coding)給已知統(tǒng)計信息的符號分配代碼的數(shù)據(jù)無損壓縮技術(shù)算術(shù)編碼是把一個信源表示為實軸上0和1之間的一個區(qū)間，信源集合中的每一個元素都用來縮短這個區(qū)間。 實質(zhì)上是為整個輸入字符流分配一個“碼字”，因此它的編碼效率可接近于熵 27 of 42高級

21、教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例n例例2.3假設信源符號為00, 01, 10, 11，它們的概率分別為 0.1, 0.4, 0.2, 0.3 對二進制消息序列10 00 11 00 10 11 01 進行算術(shù)編碼 28 of 42高級教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例(續(xù)續(xù)1)符號00011011概率0.10.40.20.3初始編碼間隔0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1表表2-4 2-4 例例2.32.3的信源符號概率和初始編碼間隔的信源符號概率和初始編碼間隔 n初始化初始化根據(jù)信源符號的概率把間隔0, 1)分成如表2-4所示的4個子間隔：0, 0.

22、1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)。其中x, y)的表示半開放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界 29 of 42高級教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例(續(xù)續(xù)2)n確定符號的編碼范圍確定符號的編碼范圍編碼時輸入第1個符號是10，找到它的編碼范圍是0.5, 0.7消息中第2個符號00的編碼范圍是0, 0.1)，它的間隔就取0.5, 0.7)的第一個十分之一作為新間隔0.5, 0.52)編碼第3個符號11時，取新間隔為0.514, 0.52)編碼第4個符號00時，取新間隔為0.514, 0.5146)依此類推消息的編碼輸出可以是

23、最后一個間隔中的任意數(shù)n整個編碼過程如圖整個編碼過程如圖2-3所示所示n編碼和譯碼的全過程分別見表編碼和譯碼的全過程分別見表2-5和表和表2-6 30 of 42高級教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例(續(xù)續(xù)3)圖2-3 例2.3的算術(shù)編碼過程 31 of 42高級教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例(續(xù)續(xù)4) 32 of 42高級教育2.2.3 算術(shù)編碼舉例算術(shù)編碼舉例(續(xù)續(xù)5) 33 of 42高級教育算術(shù)編碼的特點算術(shù)編碼的特點 不必預先定義概率模型 , 自適應模式具有獨特的優(yōu)點;信源符號概率接近時 , 建議使用算術(shù)編碼 , 這種情況下其效率高于 huffman 編碼; 34 o

24、f 42高級教育算術(shù)編碼特點續(xù)算術(shù)編碼特點續(xù)n算術(shù)編碼繞過了用一個特定的代碼替代一個輸入符號的想法 , 用一個浮點輸出數(shù)值代替一個流的輸入符號 , 較長的復雜的消息輸出的數(shù)值中就需要更多的位數(shù)。n算術(shù)編碼實現(xiàn)方法復雜一些 , 但 jpeg 成員對多幅圖像的測試結(jié)果表明 , 算術(shù)編碼比huffman 編碼提高了 5% 左右的效率 , 因此在 jpeg 擴展系統(tǒng)中用算術(shù)編碼取代 huffman 編碼。 35 of 42高級教育2.3 rle編碼編碼n行程長度編碼(run-length coding)一種無損壓縮數(shù)據(jù)編碼技術(shù)，它利用重復的數(shù)據(jù)單元有相同的數(shù)值這一特點對數(shù)據(jù)進行壓縮。對相同的數(shù)值只編碼一次，同時計算