多媒體數(shù)據(jù)壓縮(第2章)

1、第二章第二章 數(shù)據(jù)壓縮的理論基礎數(shù)據(jù)壓縮的理論基礎l掌握數(shù)據(jù)壓縮的理論極限掌握數(shù)據(jù)壓縮的理論極限l尋找數(shù)據(jù)壓縮的基本途徑尋找數(shù)據(jù)壓縮的基本途徑2.12.1數(shù)據(jù)壓縮與信息論數(shù)據(jù)壓縮與信息論 經(jīng)典的數(shù)據(jù)壓縮技術(shù)是建立在信息論的基礎上。一個故事：一個故事：據(jù)說在歐洲的一個小鎮(zhèn),有一個叫Albert的年輕學者在專利局工作，從事專利審核工作，上班的第一天，上司讓他審核這樣一份申請：該申請人自稱發(fā)明了一種裝置，能將任意一份計算機存儲的計算機的英文文件，以10個字母只需1bit的壓縮率存儲起來Albert束手無策，請教好友克勞德（通信工程師），他看完專利申請后，告訴Albert，這個專利破壞了信息論中的基本

2、極限，因而不可能實現(xiàn)。Shanon信息論認為，信源所含有的平均信息量就是無失真壓縮的理論極限。英文文件由27個字符組成：27英文字母和一個空格，其信源的熵為bit/字符（參考周炯磐信息論基礎）4 . 1)(XH2.22.2信源的熵信源的熵 一、信息量與熵1.“1.“消息消息”與與“信息信息” 在人們的日常的生活中，如果收到一封電報，接到一個電話，從信息論的角度來看，只能稱之為“消息”（message），而不能到“信息”（information），不過信息存在于消息之中，而且同樣一個消息會帶有不相等的信息量。 2.2.信息量信息量不同的消息中包含的信息有多有少不同的消息中包含的信息有多有少比如同

3、樣收到一封儀器成功的電報。如果原先預計成功的可能性為99%，那么它所帶來的信息量是微小的，好象“不出所料”，但是如果預計的可能性不大，比如只有1%的可能，而這時受到成功的電報，就會提供極大的信息量，似乎有“十分意外”的感覺。此時對人們的心理上的鼓勵作用，從技術(shù)的肯定性，都表明消息所含有的信息量是較多的。顯然，用戶在收到消息之前，是處于某種不確定狀態(tài)中，而收到此消息之后，就解除了不確定性，從而獲得信息。 山農(nóng)信息論應用“概率”來描述不確定性，也就是說，事件出現(xiàn)的概率越小，不確定性越多。)(ipH？不確定函數(shù)，要滿足以下幾個基本要求:1）當事件為確定事件時，即 ，則 , 此時毫不確定而言。) 越小

4、，不確定性越大，反之越小。3) 如果兩件事件同時存在，則有聯(lián)合不確定性。且當兩事件相互獨立時，有： )(ipH1ip0)(ipHip)(),(,kjkjbpapHpH)()(,kjkjbpHapHpH根據(jù)以上三條要求，人們成功找到了不確定性的合理表達式：iippHlog)(3. 3. 自信息量自信息量信源:是信息的來源，它一般以符號的形式發(fā)出信息，包含信息的符號常常有隨機性。信源連續(xù)信源：隨機變量取值于連續(xù)區(qū)間離散信源：隨機變量取值于離散區(qū)間 假設某一離散信源X可能發(fā)生各種可用的符號所組成的離散符號集為 ，各種符號出現(xiàn)的概率為自信息量：自信息量：符號出現(xiàn)所攜帶的自信息量定義為上式中，對數(shù)的底不

5、同，取值也不同，單位也不同。取2時， 單位為比特（bit）。取e時，單位為奈特（nat）。取10時，單位為哈特（hart）。ja. 信源的熵信源的熵(entropy)u 信源的熵是對該信源進行無失真編碼的極限。u 對信源進行無失真編碼的最低碼率就是該信源的熵。u 如果對信源進行編碼的碼率小于信源的熵，則這種編碼是有失真的。2) 熵對數(shù)據(jù)壓縮編碼的理論意義11( ). ( ).logmmjjjjjjH XP I aPP1)定義：某一信源 中各種可能出現(xiàn)的符號的自信息量的概率平均值，即11.jmjmaaaXppp例題 例：某一信源X有四個符號，其出現(xiàn)概率為： 8/ 18/ 14/ 12/ 1432

6、14aaaaA則該信源的熵為： = 1.75 bit/符號 平均碼長: L= =1/2*1+1/4*2+1/8*3= 1.75 bit/符號81log41*241log4121log)21()(xH 1111101004321aaaaiilp3. 性質(zhì)u 非負性 u 確定性 u 嚴格上凸性u 極值性 0)(pH(1,0,.,0)(0,1,.,0) .(0,0,.,1)0mmmHHH所有的概率分布所構(gòu)成的熵，以等概率時最大。最大熵定理 12111(,.,)(,.,)logmmmHp ppHmm mmmax()()log()rHXH XmH X對一個兩符號的信源，其熵函數(shù)的曲線為1p11(,1)H

7、 pp啟示：只要信源不是等概率分布的，就存在無失真數(shù)據(jù)壓縮的可能性。 啟示：既然非負，嚴格上凸，且等概率時達到最大，任一時達到最小值0，那么我們可以通過某中變換 T:，使中某一個符號發(fā)生的概率盡可能大（）使其他的盡可能?。ǎ@將有利于壓縮，這就是變換編碼的途徑之一。 )(pHmjp=1mmBA 10,21mmbbbB二、率失真理論率失真理論(Rate-distortion Theory) ,jmaA編碼器編碼輸出集Y,jnbB 信源X有失真壓縮編碼的理論極限 研究在限定失真下為了恢復信源符號所必需的編碼率，簡稱率失真理論。一、幾個重要的定義. 聯(lián)合概率( ,)ijP a b信源發(fā)出 ，編碼輸

8、出 的概率 iajb. 條件概率()ijaPb()jibQa已知編碼輸出為 ，估計對應信源發(fā)出符號 的概率 jbia已知信源發(fā)出符號為 ，估計編碼輸出為 的概率 jbia. 條件自信量 4. 條件熵 )(log)(jijibaPbaI已知編碼輸出為時，對猜測信源是否發(fā)出的不確定程度。 jbia)(log)(ijijabQabI()( ,). (/)ijjiijYHp a bI baX表示已知編碼輸入集為X時，編碼輸出集為Y所剩余的不確定性。 ()( ,). (/)ijijijXHp a bI abY5. 聯(lián)合熵 (; )( ,)log( ,)ijijijH X Yp a bp a b 表示輸入

9、為，輸出為時，整個系統(tǒng)所具有的不確定程度. 互信息量 (; )()(/)I X YH XH X Y已知編碼輸出為Y時，編碼輸入集為X所剩余的不確定性。X所含有的不確定性?！癥已知后，所獲得的關(guān)于的信息量”或者說“中所含有的的信息量”(; )()(/)( )log( )( ,).log(/)(/). ( )( )log( )( ). (/).log()iiijijiijjiiiiijiiijjI X YH XH X Yp ap ap a bP abQ bap ap ap ap a Q baQ b 在已知，的情況下，互信息量是條件概率的函數(shù)(; )I X YX()H XY( )H Y(/)H X

10、Y( /)H YX(; )I X Y(; )H X YXY()H X( )H Y(/)()H X YH X( /)( )H YXH Y(; )0I X Y (; )H X YX和相互獨立時XY()H X( )H Y(/)( /)0H X YH YX(; )()( )I X YH XH Y(; )()( )H X YH XH YX和一一映射時11111010110001101000100087654321: jiba1110010087654321比如 輸入和輸出一一對應 ,無失真 iiba 輸入和輸出不是一一對應,有失真,每個符號節(jié)省1bit 可見，只要允許誤差存在，就可以減少編碼輸出的字符數(shù)

11、，降低碼率。輸出字符數(shù)越少，譯碼誤差失真就越大。問題是：在給定的失真條件下，最起碼需要多大的碼率，才能保證不超過允許的失真？二、離散信源的率失真函數(shù)二、離散信源的率失真函數(shù) 1a1b2a2b是對應關(guān)系，無失真1a1b2a2b2b1a2a1b有誤差),(jibad設 代表某種失真度量1111( )( ,). ( ,)( ). (/). ( ,)mnmnijijijiijijijD Qp a bd a bp a Q bad a b則平均失真若要求平均失真不超過D，即DQD)(則必存在這樣概率)(ijabQ)(QD使 不超過D。定義 DQDQQD)(|1.1.失真的度量失真的度量互信息量是的函數(shù)(;

12、 )I X Y將率失真函數(shù) 定義為在 范圍內(nèi)尋找最起碼的平均互信息量。()R DDQ即( )min (; )DQ QR DI X Y. 率失真函數(shù)的定義率失真函數(shù)的定義率失真函數(shù)是在允許失真為D的條件下，信源編碼給出的平均互信息量的下界。 有失真時的信源編碼的逆定理當編碼碼率R時，無論用何種編碼方式，其平均失真必大于D )(DR)(DR. . 的性質(zhì)：的性質(zhì)：)()0(XHR)0(Ru，代表失真為0時的編碼。)(DRuD a2 a1 a2 a1 a3 a2例：信源符號概率碼A碼B碼C碼D碼E碼Fa11/2000000a21/40110010110a31/8111110011011101a41/

13、8101111110111111111不可不可不是不是不是3.23.2哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼 哈夫曼與1952年提出一種編碼方法，他完全依據(jù)字符出現(xiàn)概率概率來構(gòu)造品均長度最短的異字頭碼字。在變長編碼中，若各碼字長度嚴格按照所對應符號出現(xiàn)概率的大小逆序排列，則其平均碼長最小。實現(xiàn)步驟：實現(xiàn)步驟：將信源符號出現(xiàn)概率按減小的順序排列；將兩個最小的概率進行組合相加，并繼續(xù)這一步；對每隊組合中的上邊指定為1，下邊指定為0；畫出由每個信源符號概率到1、0處的路徑，記下路徑的1和0；對于每個信源符號，寫出1、0序列。則從右到左就得到哈夫曼碼。例：信源符號 概率a1 0.20

14、a2 0.19a3 0.18a4 0.17a5 0.15a6 0.10a7 0.01u需要統(tǒng)計概率u需要存儲或傳輸碼表哈夫曼編碼的缺點：哈夫曼編碼的缺點：通常，給出通用碼表，省略以上過程3.33.3游程編碼（游程編碼（Run-Length Coding) )游程長度(RL):由字符(或信號采樣值)構(gòu)成的數(shù)據(jù)流中各個字符重復出現(xiàn)而形成字符串的長度。如果給出了形成串的字符、串的長度及串的位置，就能換算出原來的數(shù)據(jù)流。游程長度編碼(RLC)就是用二進制碼字給出上述信息的一類方法。基本的RLC就是在數(shù)據(jù)流中直接用三個字符來給出上述三種信息。數(shù)據(jù)流ajScRL常將游程編碼與Huffman編碼等結(jié)合起來，

15、以進一步去除冗余，提高壓縮比。 3.4MH/MR編碼 、Modified Huffman (MH)針對二值圖像（僅有黑、白兩個亮度值的圖像，如傳真機掃描的二值圖像）的壓縮方法。 MH碼的主要方法是：以多幀標準傳真圖像樣本為統(tǒng)計依據(jù)，根據(jù)各種RL的出現(xiàn)的概率編出哈夫曼碼表，實際過程只是查表，可以實時處理。由于規(guī)定每行標準取樣1728點，又根據(jù)統(tǒng)計結(jié)果，實際RL在063居多，故MH編碼表分為結(jié)尾碼與組合基于碼。MH碼表(一)結(jié)尾碼RL長度白游程碼字黑游程碼字00011010100001101111000111010201111131000104101101151100001163001101000

16、00001100111MH碼表(二)組合基于碼RL長度白游程碼字黑游程碼字64110110000001111128100100000110010001921728EOL000000000001000000000001編碼規(guī)則如下：RL=063,用一個相應的結(jié)尾碼表示；RL=641728，用一個組合基于碼加一個補充結(jié)尾碼，例如RL(白)=128,其編碼為10010 00110101 補充結(jié)尾碼為(白)。若RL(白)=129，則其編碼為10010 000111規(guī)定每行都從白游程開始，若實際掃描行由黑開始，則需要在行首加零長度的游程；每行結(jié)束時，要加行同步碼EOL，每頁文件第一個數(shù)據(jù)前加EOL;為了

17、同步操作的需要,規(guī)定一個編碼的結(jié)束時間T最小為20ms，最大為5 s，不是20ms的行需要再EOL之前填充足夠的0，不可填在數(shù)據(jù)中間。每行恢復像素應為1728個，否則認為該行的傳輸有誤。連續(xù)發(fā)6個EOL碼，表示文件傳輸結(jié)束，轉(zhuǎn)回控制規(guī)程，以后發(fā)送機將按照幀格式的CCITT建議.30規(guī)定的控制信號速率發(fā)送各種報文后命令。二、二、MRMR編碼編碼1978年12月，日本提出READ(Relative Element Address Designate)編碼方案最后形成標準時，又參照其他國家的提案，對READ進行了修改，即Modified READ，簡稱MR 1. MR提出的動機MH僅使用了每一掃描行

18、內(nèi)的相關(guān)性， 沒有充分利用圖象的相關(guān)性MR編碼是MH編碼的擴展，是一種二維逐行編碼方式。 把一頁文件沿列掃描方向分成若干組，每組有K行圖像數(shù)據(jù); 第一行用一維MH編碼，其余K-1行則利用行間相關(guān)性對當前像素模式識別后編碼。MR編碼方法1)1) 遷移像素遷移像素沿掃描行由黑變白或由白變黑的的第一像素 參考行：編碼行：.a0a1a2b1b2a0：在編碼行上起參考作用的一個遷移像素。在編碼行的開始，a0為假想的白像素，位于該行第一個實際像素之前，在編碼過程中，由前一次編碼來確定。a1：在參考行上位于a0之后的下一個遷移像素。a2：在參考行上位于a1之后的下一個遷移像素。b1：在參考行上位于a0右邊，

19、且與a0顏色相反的第一個遷移像素。b2：在參考行上位于b1之后的下一個遷移像素。2 2）編碼的模式）編碼的模式READ方案將掃描行的各種變化歸納為三種格式，MRC就是識別編碼行上的每一個遷移像素應屬于哪一個模式，并輸出相應的碼字，從而編碼簡化，壓縮比提高。特征特征:a1位于b2右邊的一種模式； 編碼方法編碼方法:在通過模情況下，無論a0、b2多長，只用一個碼字“0001”表示其長度。 此后開始下一個模式編碼，以b2正下方的像素 作為下一個編碼模式的參考模式a0。 u 通過模通過模( (用用P P表示表示) ) 參考行：編碼行：.a0a1b1b2a00au垂直模（用垂直模（用V V表示）表示）

20、參考行：編碼行：.a0a1a2b1b2特征特征:a1位于b2左邊，且 的一種模式1 13ab 以a1作為下一個編碼模式的a0編碼方法編碼方法:按下表的碼字對 的長度編碼。1 1ab模模需編碼的像素需編碼的像素符號符號碼字碼字通過a0 b2p0001水平a0 a1 a1a2H001+M(a0 a1 )+ M(a1a2 )垂直a1正好在b1之下a1b1=0V(0)1a1在b1右面a1b1=1VR(1)011a1b1=2VR(2)000011a1b1=3VR(3)0000011a1在b1左面a1b1=1VL(1)010a1b1=2VL(2)000010a1b1=3VL(3)0000010MRMR碼表

21、碼表u 水平模水平模( (用用H H表示表示) ) 特征特征:a1位于b2左邊且a1b13的一種模式。 編碼方法編碼方法:統(tǒng)計表明，對a1b1編碼還不如直接對a0 a1 和a1 a2兩個游程長度編碼的效率高。 編碼之后，a2作為下一次編碼時的a0 程序演示程序演示3.5 3.5 算術(shù)編碼算術(shù)編碼(Arithmetic Coding)(Arithmetic Coding) 1.1.引言引言 早在60年代初期，Elias就提出了算術(shù)編碼的概念，Rissanen和Pasco首次介紹了他的實用技術(shù)。算術(shù)編碼方法的具體實現(xiàn)方法，在80年代才有了報道。到目前為止，這一方法還不為很多人知道。近期出版了數(shù)據(jù)編

22、碼的書，也僅僅簡單提及。算術(shù)編碼在有些方面優(yōu)于Huffman方法，算術(shù)編碼方法使表示的信息盡量緊湊，并對輸入的數(shù)據(jù)信息沒有分塊的要求，算術(shù)編碼方法計算效率高并且容易提供自適應模式。2.2.算術(shù)編碼原理算術(shù)編碼原理算術(shù)編碼就是將被編碼的信息表示成實數(shù)0和1之間的一個間隔，信息越大，編碼表示它的間隔就越小，表示這一間隔所需要的二進制位就越多。 例：假定信源中可能出現(xiàn)的符號有a, e, I, o, u, l，出現(xiàn)的概率如下，用算術(shù)編碼對輸入串eaiil編碼2 . 0 , 0字符 概率 范圍（range） rangelow ,rangehigh) a 0.2e 0.3 5 . 0 , 2 . 0i 0

23、.1 6 . 0 , 5 . 0o 0.2 8 . 0 , 6 . 0u 0.1 9 . 0 , 8 . 0l 0.1 1 , 9 . 001aeioul定義：range(n)=high(n)-low(n) 。下一次low(n+1) = low(n) + range(n) * rangelow high(n+1) = low(n) + range(n) * rangehig初始 high(0) =1，low(0) =0。low = 0 + 1 * 0.2=0.2high = 0 + 1* 0.5=0.5range=high low =0.5-0.2=0.3e 編碼過程a low = 0.2 +

24、 0.3 * 0=0.2high = 0.2 + 0.3* 0.2=0.26range=high low =0.26-0.2=0.061 1）編碼過程）編碼過程編碼字符區(qū)間范圍lowhigh初始01)e0.20.5)a0.20.26)i0.230.26)i0.2330.2336)l0.233540.2336)euoieaeuoieaeuoieaeuoieaeuoieaeuoiea0.20.50.20.260.230.260.2330.2360.233540.2336）解碼過程）解碼過程只要將編碼后的最后范圍以二進制形式存儲即可。從而達到壓縮l如果解碼器也知道這一最后的范圍2336. 0 ,23

25、354. 0馬上就可以解出第一個字符e,只有e產(chǎn)生的范圍能包含2336. 0 ,23354. 0l在解出e后，范圍變成5 . 0 , 2 . 0l得到這個范圍，我們就可以對上述所有字符再依據(jù)上式計算，并與最終范圍比較，不難解出第二個字符為a。 l依次類推 算術(shù)編碼除了有基于概率統(tǒng)計的固定模式外，還有其他模式。 自適應模式各個符號的概率初始值都相同，它們依據(jù)出現(xiàn)的符號而相應地改變。只要編解碼器使用相同的初始值和改變值的規(guī)則，則它們的概率模型將保持一致。 ）算術(shù)編碼的特點：）算術(shù)編碼的特點：l算術(shù)編碼的方法不必預先統(tǒng)計概率；l當信源概率比較接近時，Huffman編碼的效率不高，算術(shù)編碼要好于Huf

26、fman。l算術(shù)編碼的實現(xiàn)方法要比Huffman方法復雜一些.6 LZ .6 LZ 編碼（基于編碼（基于字典字典的無失真編碼方法）的無失真編碼方法）一、基本定義一、基本定義：基于字典的編碼方法基于字典的編碼方法是由生活中的字典概念而引申的。例：A good example of how dictionary based compression 采用簡明硬漢詞典（共有2200頁，每頁單詞少于256），對上述8個詞編碼如下：1/1 811/3 674/4 1343/60 928/75 550/32 173/46 421/2頁號該頁單詞的序號分析：未編碼時：43 Bytes編碼時：頁碼：12 bit

27、s, 詞條序號8 bits，對一個詞的編碼共需2.5 Bytes這段話共需8 2.520Bytes靜態(tài)字典：字典是不變的，編碼簡單，效率較低動態(tài)字典：字典隨編碼過程而變，編碼復雜，效率較高字典二、分類二、分類Ziv和Lempel(兩位以色列人）在1977和1978年在IEEE Transactions on Information Theory 發(fā)表的兩篇論文A universal algorithm for sequential data compression77787878787878LZSSLZLZWLZSLZELZLZSELZEPLZSEPLZY目前許多計算機的壓縮軟件，如Winzip，Arj等均基于LZ算法三、實現(xiàn)方