無失真壓縮統(tǒng)計(jì)模式(共43張PPT)

第五章無失真壓縮—統(tǒng)計(jì)模式1.Shannon-Fano編碼2.Huffman編碼3.適應(yīng)性Huffman編碼4.算術(shù)編碼5.高階次模式與適應(yīng)性模式靜宜大學(xué)資訊工程系1第1頁，共43頁。無失真壓縮無失真壓縮統(tǒng)計(jì)模式(StatisticalModel)必須前置統(tǒng)計(jì)所有要處理資料中，個別符號的出線機(jī)率。利用個別符號出現(xiàn)的機(jī)率來編碼一個符號對應(yīng)到一個編碼樣式(codepattern)屬於這一類的壓縮技術(shù)霍夫曼編碼法（Huffmancoding）Shannon-Fanocoding算術(shù)編碼法（Arithmeticcoding）2第2頁，共43頁。無失真壓縮無失真壓縮字典模式(DictionaryModel)利用單一編碼樣式來表示一個字串。相較於統(tǒng)計(jì)模式一次只能處理一個符號，字典模式一次處理包含多個符號構(gòu)成的字串。屬於這一類的壓縮技術(shù)LZ77LZ78LZW3第3頁，共43頁。無失真壓縮最小累贅編碼(MinimumRedundancyCoding)給定欲壓縮的資料，我們可以計(jì)算出在這資料中，個別符號出現(xiàn)的機(jī)率。最小累贅編碼具有下列特性：不同的編碼樣式(codepattern)的長度(length)不同。出現(xiàn)機(jī)率較低的符號，其所使用的編碼樣式之長度較長;反之出現(xiàn)機(jī)率較高的符號其編碼樣式之長度較短。整個編碼的技術(shù)必須要能夠唯一解碼。4第4頁，共43頁。無失真壓縮—統(tǒng)計(jì)模式機(jī)率表的建立靜態(tài)模式分析一段具有代表性的資料，然後建立對應(yīng)的機(jī)率表，並依照機(jī)率表建立所需的統(tǒng)計(jì)資料與解碼樹。如果輸入資料與統(tǒng)計(jì)資料不一致，壓縮比會降低。實(shí)作規(guī)範(fàn)為每一筆輸入資料都建立對應(yīng)的機(jī)率表機(jī)率表必須在編碼資料前送到解碼端。5第5頁，共43頁。無失真壓縮—統(tǒng)計(jì)模式機(jī)率表的建立適應(yīng)性模式（adaptive）一般讀入資料，編碼，一邊更新統(tǒng)計(jì)資料。不需事先看過輸入資料來產(chǎn)生機(jī)率表。編碼與解碼必須要能夠同步（synchronization）。難度較靜態(tài)模式的處理來的高。6第6頁，共43頁。無失真壓縮—統(tǒng)計(jì)模式7第7頁，共43頁。無失真壓縮—統(tǒng)計(jì)模式8第8頁，共43頁。5.1Shannon-Fano編碼(5)重要性質(zhì)：不同的碼使用不等的位元數(shù)。低出現(xiàn)機(jī)率的符號編碼使用較多的位元；高出現(xiàn)機(jī)率的符號編碼使用較少的位元。雖然碼的長度不一，但是可以唯一解碼，事實(shí)上它是及時碼。解碼樹由上往下建立，先找出每個碼的MSB位元，然後依序往下做，直到樹葉為止。9第9頁，共43頁。10第10頁，共43頁。5.1Shannon-Fano編碼(8)SymbolCountCodeA 1500B 701D 6110C 610E 5111Firstdivision2nddivision3rddivision4thdivisionAtotalof39symbols11第11頁，共43頁。3985.2589ACSIICodeneeds39×8=312bits5.1Shannon-Fano編碼(9)12第12頁，共43頁。5.1Shannon-Fano編碼圖5.213第13頁，共43頁。5.2Huffman編碼(10)重要性質(zhì)：不同的碼使用不等的位元數(shù)。低出現(xiàn)機(jī)率的符號編碼使用較多的位元；高出現(xiàn)機(jī)率的符號編碼使用較少的位元。具有唯一解碼性質(zhì)的及時碼。Huffman解碼樹由樹葉開始，往由下往上建立，先找出每個碼的LSB位元，然後依序往上做，直到樹根（root）為止。14第14頁，共43頁。15第15頁，共43頁。5.2Huffman編碼firstroundsecondround圖5.316第16頁，共43頁。5.2Huffman編碼圖5.417第17頁，共43頁。5.2Huffman編碼89873918第18頁，共43頁。5.3適應(yīng)性Huffman編碼(15)利用已讀過的資料機(jī)動地調(diào)整Huffman樹。壓縮端與解壓縮端必須維持同步。壓縮的程序設(shè)定模式起始狀況迴圈：讀入下一個符號c對c編碼並輸出為c的加入做必要的更新回到迴圈直到資料結(jié)束為止解壓縮的程序設(shè)定模式起始狀況迴圈：對輸入解碼得到下一個符號c輸出c為c的加入做必要的更新回到迴圈直到解碼結(jié)束為止19第19頁，共43頁。5.3.2Huffman樹的更新(18)當(dāng)加入一個符號c時，要改變機(jī)率表中的對應(yīng)統(tǒng)計(jì)值，並重建Huffman樹。將c的出現(xiàn)頻率加1依照新的統(tǒng)計(jì)表重建Huffman樹。需要非常多的計(jì)算時間，即使建立Huffman樹是一件相當(dāng)簡單而且快速的工作。利用兄弟性質(zhì)（siblingproperty）來重建Huffman樹。如果一棵樹的節(jié)點(diǎn)可以依照加權(quán)比重從小到大排列，而且每個節(jié)點(diǎn)又和自己的兄弟相鄰，我們稱這棵樹具有兄弟性質(zhì)。20第20頁，共43頁。5.3.2Huffman樹的更新(19)圖5.521第21頁，共43頁。A的出現(xiàn)頻率加一圖Huffman樹的更新(20)22第22頁，共43頁。A的出現(xiàn)頻率再次加一圖Huffman樹的更新(21)23第23頁，共43頁。第一步：low0.與BD的父節(jié)點(diǎn)（加權(quán)比重較A小而且節(jié)點(diǎn)編號最高）最小累贅編碼具有下列特性：output(c);如何建立起始符號統(tǒng)計(jì)表4算術(shù)編碼（arithmeticcoding）2Huffman樹的更新(23)一開始將Huffman樹設(shè)定只含有兩個特殊符號：EOF以及ESC，兩個符號的加權(quán)比重皆為1。Bonus:Sensitivetorecentsymbols,andthusabettercompressionratio.Huffman編碼不需事先看過輸入資料來產(chǎn)生機(jī)率表。算術(shù)編碼法（Arithmeticcoding）不同的編碼樣式(codepattern)的長度(length)不同。第六步：輸出low。JPEG,MPEG-1/2usesHuffmanandarithmeticcoding–preprocessedbyDPCM交換A（引起兄弟性質(zhì)不在滿足的節(jié)點(diǎn)）與D（加權(quán)比重較A小而且節(jié)點(diǎn)編號最高）圖Huffman樹的更新(22)24第24頁，共43頁。641020A的出現(xiàn)頻率再次加一5.3.2Huffman樹的更新25第25頁，共43頁。A的出現(xiàn)頻率再次加一交換A（引起兄弟性質(zhì)不在滿足的節(jié)點(diǎn)）與BD的父節(jié)點(diǎn)（加權(quán)比重較A小而且節(jié)點(diǎn)編號最高）圖Huffman樹的更新(23)26第26頁，共43頁。5.3適應(yīng)性Huffman編碼(24)如何建立起始符號統(tǒng)計(jì)表假設(shè)所有的符號都出現(xiàn)一次從一個空的統(tǒng)計(jì)表開始，只有當(dāng)符號被讀到時才將其加入統(tǒng)計(jì)表內(nèi)一開始將Huffman樹設(shè)定只含有兩個特殊符號：EOF以及ESC，兩個符號的加權(quán)比重皆為1。若讀入的符號已存在Huffman樹中，將這個符號的Huffman碼送出，然後將對應(yīng)的加權(quán)比重加1。若讀入的符號未曾出現(xiàn)過，編碼端會先送出ESC的Huffman碼，然後再送出這個符號的ASCII碼。最後將這個符號加入Huffman樹中並設(shè)定其加權(quán)比重為1。27第27頁，共43頁。5.3適應(yīng)性Huffman編碼溢位問題（overflowproblem）當(dāng)壓縮程序開始後，每個節(jié)點(diǎn)的加權(quán)比重逐漸加。某個節(jié)點(diǎn)的比重超過一個整數(shù)變數(shù)所能容納的值時，就產(chǎn)生了溢位的問題。解決的方法通常是將所有的節(jié)點(diǎn)的加權(quán)比重都除2?？赡軙?dǎo)致新的Huffman樹產(chǎn)生違反兄弟性質(zhì)的狀況。失去了原本統(tǒng)計(jì)表的精準(zhǔn)度。將節(jié)點(diǎn)的加權(quán)比重縮小恰好等於降低過去資料所產(chǎn)生的影響，而加重了最近資料的影像力。28第28頁，共43頁。5.3適應(yīng)性Huffman編碼圖5.1029第29頁，共43頁。圖5.115.3適應(yīng)性Huffman編碼溢位問題30第30頁，共43頁。圖5.125.3適應(yīng)性Huffman編碼溢位問題31第31頁，共43頁。5.3適應(yīng)性Huffman編碼適應(yīng)性Huffman編碼Bonus:Sensitivetorecentsymbols,andthusabettercompressionratio.COMPACTinUNIXusesadaptiveHuffmancoding.Huffmancodinghasbeenproventhebestfixedlengthcodingmethodavailable.HuffmancodeshavetobeanintegralnumberofbitslongEntropyvalueofasymbolmaybeafactionnumberTheoreticalpossiblecompressedmessagecannotbeachieved32第32頁，共43頁。5.4算術(shù)編碼(28)算術(shù)編碼：算術(shù)編碼避開了一個符號一個碼的想法採取一串符號用一個實(shí)數(shù)來表示的方式對於比較長，比較複雜的訊息，輸出的實(shí)數(shù)需要多一點(diǎn)的位元來表示。33第33頁，共43頁。5.4算術(shù)編碼（arithmeticcoding）Character

probability

Range

^(space) 1/10 A 1/10 B 1/10 E 1/10G 1/10I 1/10L 2/10S 1/10T 1/10 34第34頁，共43頁。5.4算術(shù)編碼（arithmeticcoding）算術(shù)編碼之編碼程序：第一步：low

0.0；high

1.0第二步：讀入下一個符號c第三步：rangehigh-low第四步：查範(fàn)圍表，若c的範(fàn)圍為lrh設(shè)定highlow+rangeh

lowlow+rangel第五步：如果還有符號沒有編碼，則回到第二步，否則執(zhí)行第六步。第六步：輸出low。35第35頁，共43頁。r=r/(high_range(c)-low_range(c));介於low到high之間的實(shí)數(shù)。2Huffman樹的更新(23)2nddivision高出現(xiàn)機(jī)率的符號編碼使用較少的位元。第五步：如果還有符號沒有編碼，則回到SupposethatwewanttoencodethemessageSymbolCountCode與D（加權(quán)比重較A小而且節(jié)點(diǎn)編號最高）不同的碼使用不等的位元數(shù)。必須前置統(tǒng)計(jì)所有要處理資料中，個別符號的出線機(jī)率。當(dāng)加入一個符號c時，要改變機(jī)率表中的對應(yīng)統(tǒng)計(jì)值，並重建Huffman樹。第六步：輸出low。Encodingalgorithmforarithmeticcoding.Low=0.0;high=1.0;whilenotEOFdo range=high-low;read(c); high=low+rangehigh_range(c); low=low+rangelow_range(c);enddooutput(low);5.4算術(shù)編碼（arithmeticcoding）36第36頁，共43頁。37第37頁，共43頁。5.4算術(shù)編碼（arithmeticcoding）Supposethatwewanttoencodethemessage

BILLGATES

So,thefinalvalue0.2572167752(or,anyvaluebetween0.2572167752and0.2572167756,ifthelengthoftheencodedmessageisknownatthedecodeend),willuniquelyencodethemessage‘BILLGATES’.38第38頁，共43頁。算術(shù)編碼之解碼程序：39第39頁，共43頁。5.4算術(shù)編碼（arithmeticcoding）Decodingalgorithmr=input_coderepeatsearchcsuchthatrfallsinitsrange;output(c); r=r-low_range(c);r=r/(high_range(c)-low_range(c));untilEOForthelen