无失真压缩统计模式(共43张PPT)

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

0.0；high

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

lowlow+rangel第五步：如果還有符號沒有編碼，則回到第二步，否則執行第六步。第六步：輸出low。35第35页，共43页。r=r/(high_range(c)-low_range(c));介於low到high之間的實數。2Huffman樹的更新(23)2nddivision高出現機率的符號編碼使用較少的位元。第五步：如果還有符號沒有編碼，則回到SupposethatwewanttoencodethemessageSymbolCountCode與D（加權比重較A小而且節點編號最高）不同的碼使用不等的位元數。必須前置統計所有要處理資料中，個別符號的出線機率。當加入一個符號c時，要改變機率表中的對應統計值，並重建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算術編碼（arithmeticcoding）36第36页，共43页。37第37页，共43页。5.4算術編碼（arithmeticcoding）Supposethatwewanttoencodethemessage

BILLGATES

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