數(shù)據(jù)壓縮與信源編碼第4講算術(shù)編碼

數(shù)據(jù)壓縮與信源編碼第4講算術(shù)編碼第一頁，共58頁。算術(shù)編碼的提出Huffman編碼是最佳變長碼，但仍包含冗余信息。符號a1a2a3a4a5概率0.20.40.20.10.1Huffman編碼10011011101111Huffman編碼平均碼長=0.2*2+0.4*1+0.2*3+0.1*4+0.1*4=2.2bits信源的熵Huffman編碼冗余度=Huffman編碼平均碼長-信源的熵=0.078bits/symbol第二頁，共58頁。算術(shù)編碼的提出為什么Huffman編碼不能達(dá)到理論上的極限？符號a1a2a3a4a5概率0.20.40.20.10.1信息量bit2.321.322.323.323.32Huffman編碼10011011101111Huffman編碼的問題在于每個符號的編碼長度只能為整數(shù)，而信息論告訴我們，對每個符號的最佳編碼長度為其信息量。能否用小數(shù)個二進(jìn)制位來進(jìn)行編碼呢？行！這就是算術(shù)編碼。1948年，香農(nóng)提出了算術(shù)編碼的基本思想，并證明了其優(yōu)越性。第三頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟10①將當(dāng)前區(qū)間定義為[0,1)。第四頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟SWIM空格10.50.40.20.10②把當(dāng)前區(qū)間分割為長度正比于符號概率的子區(qū)間。示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮符號SWIM空格頻率51211概率0.50.10.20.10.1第五頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟SWIM空格10.50.40.20.10③為輸入的符號選擇一個子區(qū)間，將其定義為新的當(dāng)前區(qū)間。示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮第一個字符為S，對應(yīng)區(qū)間為[0.5,1.0)，將其作為當(dāng)前區(qū)間，按照概率進(jìn)行分割10.50.5+0.5*0.1=0.550.5+0.5*0.2=0.60.5+0.5*0.4=0.70.5+0.5*0.5=0.75第六頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟SWIM空格10.750.70.60.550.5③為輸入的符號選擇一個子區(qū)間，將其定義為新的當(dāng)前區(qū)間。示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮第二個字符為W，對應(yīng)區(qū)間為[0.7,0.75)，將其作為當(dāng)前區(qū)間，按照概率進(jìn)行分割0.70.750.7+0.05*0.1=0.7050.7+0.05*0.2=0.710.7+0.05*0.4=0.720.7+0.05*0.5=0.725第七頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟SWIM空格③為輸入的符號選擇一個子區(qū)間，將其定義為新的當(dāng)前區(qū)間。示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮第三個字符為I，對應(yīng)區(qū)間為[0.7,0.75)，將其作為當(dāng)前區(qū)間，按照概率進(jìn)行分割0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715第八頁，共58頁。算術(shù)編碼的主要步驟算術(shù)編碼主要步驟將當(dāng)前區(qū)間定義為[0,1)。把當(dāng)前區(qū)間分割為長度正比于符號概率的子區(qū)間。為輸入的符號選擇一個子區(qū)間，將其定義為新的當(dāng)前區(qū)間。重復(fù)②③兩步，知道所有符號輸入完成。以當(dāng)前區(qū)間中的任意一個數(shù)字作為輸入符號序列的編碼。SWIM空格0.70.750.7050.710.720.7250.710.720.71+0.01*0.1=0.7110.71+0.01*0.2=0.7120.71+0.01*0.4=0.7140.71+0.01*0.5=0.715第九頁，共58頁。算術(shù)編碼的示例1示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮符號下限上限S0.51.0W0.70.75I0.710.72S0.7150.72S0.71750.72空格0.71750.71775M0.7175250.71755I0.7175300.717535S0.71753250.717535S0.717533750.717535第十頁，共58頁。算術(shù)編碼的示例1示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮輸入序列”SWISSMISS”對應(yīng)區(qū)間為輸入序列”SWISSMISS”包含10個字符，0.717534只包含6個十進(jìn)制數(shù)字，數(shù)碼縮短，完成數(shù)據(jù)壓縮。算術(shù)編碼基本過程可以用下面兩個式子迭代來完成[0.71753375,0.717535)選擇該區(qū)間中任意一個數(shù)字可代表該輸入序列，如0.717534。第十一頁，共58頁。算術(shù)編碼的示例1示例1：對壓縮序列0.717534進(jìn)行解碼0.717534在[0.5,1)范圍內(nèi)，因此第一個符號為S。0.435068在[0.4,0.5)范圍內(nèi)，因此第二個符號為W。0.35068在[0.2,0.4)范圍內(nèi)，因此第三個符號為I。0.7534在[0.5,1.0)范圍內(nèi)，因此第四個符號為S。SWIM空格10.50.40.20.10第十二頁，共58頁。算術(shù)編碼的示例1示例1：對壓縮序列0.717534進(jìn)行解碼0.5068在[0.5,1.0)范圍內(nèi)，因此第五個符號為S。0.0136在[0.0,0.1)范圍內(nèi)，因此第六個符號為空格。0.136在[0.1,0.2)范圍內(nèi)，因此第七個符號為M。SWIM空格10.50.40.20.10第十三頁，共58頁。算術(shù)編碼的示例1示例1：對壓縮序列0.717534進(jìn)行解碼0.8在[0.5,1.0)范圍內(nèi)，因此第九個符號為S。0.6在[0.5,1.0)范圍內(nèi)，因此第十個符號為S。0.36在[0.2,0.4)范圍內(nèi)，因此第八個符號為I。解碼過程可以用下式來表示SWIM空格10.50.40.20.10第十四頁，共58頁。算術(shù)編碼的示例1問題1：第十個符號S解碼出來以后，數(shù)值為0.6，如何知道碼流解碼已經(jīng)結(jié)束？0.6在[0.5,1.0)范圍內(nèi)，因此第十個符號為S。解答1：在編碼過程中記錄碼流的長度，添加在壓縮碼流的前面進(jìn)行存儲/傳送。解碼時首先獲得碼流長度，當(dāng)解碼到指定長度時結(jié)束。解答2：人為添加一個概率非常小的字符EOF在原始碼流的最后一起編碼，當(dāng)解碼出現(xiàn)EOF的時候結(jié)束。第十五頁，共58頁。算術(shù)編碼的示例2示例2：對輸入序列”SWIS”進(jìn)行壓縮符號SWIEOF頻率5111概率0.40.20.20.2區(qū)間[0.6,1.0)[0.4,0.6)[0.2,0.4)[0.0,0.2)符號下限上限S0.61.0W0.6+0.4*0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688第十六頁，共58頁。算術(shù)編碼的示例2示例2：對輸入序列”SWIS”進(jìn)行壓縮符號SWIEOF頻率5111概率0.40.20.20.2區(qū)間[0.6,1.0)[0.4,0.6)[0.2,0.4)[0.0,0.2)符號下限上限S0.61.0W0.6+0.4*0.4=0.760.6+0.4*0.6=0.84I0.76+0.2*0.08=0.7760.76+0.4*0.08=0.792S0.776+0.016*0.6=0.78560.792EOF0.7856+0.0064*0=0.78560.7856+0.0064*0.2=0.78688可以選擇0.7856或者0.786作為輸出第十七頁，共58頁。算術(shù)編碼的示例2示例2：對壓縮序列0.786進(jìn)行解碼0.786在[0.6,1)范圍內(nèi)，因此第一個符號為S。0.465在[0.4,0.6)范圍內(nèi)，因此第二個符號為W。0.325在[0.2,0.4)范圍內(nèi)，因此第三個符號為I。0.625在[0.6,1.0)范圍內(nèi)，因此第四個符號為S。0.125在[0,0.2)范圍內(nèi)，因此第五個符號為EOF，解碼結(jié)束。SWIEOF10.60.40.20第十八頁，共58頁。整數(shù)算術(shù)編碼在算術(shù)編碼中，當(dāng)前區(qū)間的下限LOW和上限HIGH隨著碼流長度的增大，將變的無限長。而實際上，雙精度的實數(shù)也只有16位有效數(shù)字，更長精度的數(shù)無法表示。比如一個1MB的文件被壓縮成100KB，即當(dāng)前區(qū)間需要用100KB長的數(shù)來表示，而兩個這樣的數(shù)進(jìn)行加減乘除都需要很長的時間。因此，一個實用的方案應(yīng)當(dāng)采用有限長度的整數(shù)運算。即使有一種方法能夠表示足夠長的數(shù)據(jù)精度，兩個很長的數(shù)進(jìn)行運算，花費的時間也無法承受。第十九頁，共58頁。整數(shù)算術(shù)編碼早在1948年，香農(nóng)就提出了算術(shù)編碼的基本思想。1960年，PeterElias提出了算術(shù)編碼的概念，但他發(fā)現(xiàn)實際當(dāng)中根本無法實現(xiàn)。直到1976年，R.Pasco和J.Rissanen才分別用定長的寄存器實現(xiàn)了有限精度的算術(shù)編碼。1987年Witten等人發(fā)表了一個實用的算術(shù)編碼程序，后用于ITU-T的H.263視頻壓縮標(biāo)準(zhǔn)。第二十頁，共58頁。整數(shù)算術(shù)編碼示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮符號下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500如何利用有限字長寄存器來實現(xiàn)算術(shù)編碼？第二十一頁，共58頁。整數(shù)算術(shù)編碼示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮符號下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500在算術(shù)編碼中，當(dāng)前區(qū)間的下限LOW和上限HIGH左邊的數(shù)字一旦相同，就不會再變化。第二十二頁，共58頁。整數(shù)算術(shù)編碼示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮相同的數(shù)字可以直接輸出到壓縮碼流，這樣LOW和HIGH中可以不用再保留它們，將它們從LOW和HIGH中移出去。這個特點使得LOW和HIGH可以使用較短的長度來表示。符號下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500第二十三頁，共58頁。整數(shù)算術(shù)編碼示例1：對輸入序列”SWISSMISS”進(jìn)行壓縮相同的數(shù)字可以直接輸出到壓縮碼流，這樣LOW和HIGH中可以不用再保留它們，將它們從LOW和HIGH中移出去。這個特點使得LOW和HIGH可以使用較短的長度來表示。符號下限上限S0.51.0W0.700.75I0.710.72S0.7150.720S0.71750.720空格0.717500.71775M0.7175250.717550I0.7175300.717535S0.71753250.7175350S0.717533750.71753500第二十四頁，共58頁。整數(shù)算術(shù)編碼以0.0000…表示0，以0.99999…表示1。以4位表示，則初始值LOW=0000，HIGH=9999。如果最高位數(shù)字相等，則移出最高位，然后LOW的右邊補(bǔ)0，HIGH的右邊補(bǔ)9。符號SWIM空格頻率51211概率0.50.10.20.10.1區(qū)間[0.5,1.0)[0.4,0.5)[0.2,0.4)[0.1,0.2)[0,0.1)LowCumFreq54210HighCumFreq105421第二十五頁，共58頁。整數(shù)算術(shù)編碼示例3：對輸入序列”SWISSMISS”進(jìn)行壓縮，輸出為717533750符號下限計算上限計算輸出下限上限S0000+10000*5/10=50000000+10000*10/10-1=999950009999W5000+5000*4/10=70005000+5000*6/10-1=7499700004999I0000+5000*2/10=10000000+5000*4/10-1=1999100009999S0000+10000*5/10=50000000+10000*10/10-1=999950009999S5000+5000*5/10=75005000+5000*10/10-1=999975009999空格7500+2500*0/10=75007500+2500*2/10-1=7749750007499第二十六頁，共58頁。整數(shù)算術(shù)編碼示例3：對輸入序列”SWISSMISS”進(jìn)行壓縮，輸出為717533750符號下限計算上限計算輸出下限上限空格7500+2500*0/10=75007500+2500*2/10-1=7749750007499M5000+2500*1/10=52505000+2500*2/10-1=5499525004999I2500+2500*2/10=30002500+2500*4/10-1=3499300004999S0000+5000*5/10=25000000+5000*10/10-1=499925004999S2500+2500*5/10=37502500+2500*10/10-1=4999375037504999編碼結(jié)束時，當(dāng)前下限應(yīng)當(dāng)輸出，即輸出3750或輸出4。第二十七頁，共58頁。整數(shù)算術(shù)編碼示例3：對輸入序列”SWISSMISS”進(jìn)行壓縮，輸出為717533750符號下限計算上限計算輸出下限上限S0000+10000*5/10=50000000+10000*10/10-1=999950009999W5000+5000*4/10=70005000+5000*6/10-1=7499700004999I0000+5000*2/10=10000000+5000*4/10-1=1999100009999S0000+10000*5/10=50000000+10000*10/10-1=999950009999S5000+5000*5/10=75005000+5000*10/10-1=999975009999空格7500+2500*0/10=75007500+2500*2/10-1=7749750007499M5000+2500*1/10=52505000+2500*2/10-1=5499525004999I2500+2500*2/10=30002500+2500*4/10-1=3499300004999S0000+5000*5/10=25000000+5000*10/10-1=499925004999S2500+2500*5/10=37502500+2500*10/10-1=4999375037504999第二十八頁，共58頁。整數(shù)算術(shù)編碼整數(shù)算術(shù)編碼的解碼過程如下：并截尾到最近的整數(shù)如果Low和High最左邊的數(shù)字相等，就把Low和High和Code左移一位。Low的右邊補(bǔ)0，High的右邊補(bǔ)9，Code的右邊補(bǔ)上壓縮碼流的下一位數(shù)字用Index和累積頻率表相比較，解出下一個符號。重復(fù)上述過程直到解碼結(jié)束。第二十九頁，共58頁。整數(shù)算術(shù)編碼示例3：對壓縮碼流717533750進(jìn)行解碼。計算輸出修正Index=((7175-0+1)*10-1)/(9999-0+1)=7.1759S7175Low=0+(9999-0+1)*5/10=50005000High=0+(9999-0+1)*10/10-1=99999999Index=((7175-5000+1)*10-1)/(9999-5000+1)=4.3518W1753Low=5000+(9999-5000+1)*4/10=70000000High=5000+(9999-5000+1)*5/10-1=74994999第三十頁，共58頁。整數(shù)算術(shù)編碼示例3：對壓縮碼流717533750進(jìn)行解碼。計算輸出修正Index=((1753-0000+1)*10-1)/(4999-0000+1)=3.5078I7533Low=0000+(4999-0000+1)*2/10=10000000High=0000+(4999-0000+1)*4/10-1=19999999Index=((7533-0+1)*10-1)/(9999-0+1)=7.5339S7533Low=0+(9999-0+1)*5/10=50005000High=0+(9999-0+1)*10/10-1=99999999第三十一頁，共58頁。整數(shù)算術(shù)編碼示例3：對壓縮碼流717533750進(jìn)行解碼。計算輸出修正Index=((7533-5000+1)*10-1)/(9999-5000+1)=5.0678S7533Low=5000+(9999-5000+1)*5/10=75000000High=5000+(9999-5000+1)*10/10-1=99994999Index=((7533-7500+1)*10-1)/(9999-7500+1)=0.1356空格5337Low=7500+(9999-7500+1)*0/10=75005000High=7500+(9999-7500+1)*1/10-1=77497499第三十二頁，共58頁。整數(shù)算術(shù)編碼示例3：對壓縮碼流717533750進(jìn)行解碼。計算輸出修正Index=((5337-5000+1)*10-1)/(9999-5000+1)=1.3516M3375Low=5000+(9999-5000+1)*1/10=52502500High=5000+(9999-0+1)*2/10-1=54994999Index=((3375-2500+1)*10-1)/(4999-2500+1)=3.5063I3750Low=2500+(4999-2500+1)*2/10=30000000High=2500+(4999-2500+1)*4/10-1=34994999第三十三頁，共58頁。整數(shù)算術(shù)編碼示例3：對壓縮碼流717533750進(jìn)行解碼。計算輸出修正Index=((3750-0000+1)*10-1)/(4999-0000+1)=7.5018S3750Low=0000+(4999-0000+1)*5/10=25002500High=0000+(4999-0000+1)*10/10-1=49994999Index=((3750-2500+1)*10-1)/4999-2500+1)=5.0036S3375Low=2500+(4999-2500+1)*5/10=37502500High=2500+(4999-2500+1)*10/10-1=49994999解碼結(jié)果為SWISSMISS第三十四頁，共58頁。整數(shù)算術(shù)編碼問題2：當(dāng)LOW和HIGH計算出現(xiàn)3999和4000時，區(qū)間長度只有1，繼續(xù)編碼LOW和HIGH的值將一直保持3999和4000。在這種情況下，直到輸入碼流結(jié)束，編碼器都將不會產(chǎn)生輸出。如何避免這種情況？解答：在區(qū)間變短的時候就要提前進(jìn)行處理。比如在出現(xiàn)39xx和40xx的時候，就要對區(qū)間進(jìn)行比例放大。第三十五頁，共58頁。整數(shù)算術(shù)編碼解答：當(dāng)出現(xiàn)39xx和40xx的時候，將次高位9和0移出，LOW和HIGH變?yōu)?xx0和4xx9，使得區(qū)間放大。這個過程可能重復(fù)若干次，直到區(qū)間變的足夠大。以Scale記錄移出次高位的次數(shù)，每當(dāng)次高位移出，變量Scale加1。繼續(xù)迭代，直到區(qū)間變?yōu)閇3xxx,3xxx)或[4xxx,4xxx)。輸出最高位。如果最高位為3，則輸出Scale個9；如果最高位為4，則輸出Scale個0。將Scale清0。第三十六頁，共58頁。整數(shù)算術(shù)編碼下限3999399039003000迭代3xxx上限4000400940994999迭代3xxxScale01230輸出無無無無無3999實際上是3999xxx，因為999先被移出去了下限3999399039003000迭代4xxx上限4000400940994999迭代4xxxScale01230輸出無無無無無4000實際上是4000xxx，因為000先被移出去了第三十七頁，共58頁。整數(shù)算術(shù)編碼問題3：LOW和HIGH需要使用多少位？用000表示0，用999表示1行不行？解答：High和Low都是整數(shù)，要保證在每次迭代時每個符號的區(qū)間寬度大于0，無法進(jìn)行表示。TotalCumFreq等價于數(shù)據(jù)長度，數(shù)據(jù)越長，LOW和HIGH需要的位數(shù)越多。第三十八頁，共58頁。二進(jìn)制算術(shù)編碼以m個0代表0，1個1和m-1個0代表0.5，m個1代表1。以表示符號i出現(xiàn)的次數(shù)，定義編碼下限l和上限u可以用下式迭代：第三十九頁，共58頁。二進(jìn)制算術(shù)編碼如果l和u的最高位都是b，或者Scale條件成立如果l和u的最高位都是b將b輸出到碼流將l左移1位，最低位補(bǔ)0將u左移1位，最低位補(bǔ)1如果Scale>0，輸出b的補(bǔ)，scale減1如果Scale條件成立將l左移1位，最低位補(bǔ)0將u左移1位，最低位補(bǔ)1l和u最高位取反，scale加1LOWHIGH0X0X輸出01X1X輸出10010正常區(qū)間0111正常區(qū)間0011正常區(qū)間0110Scale區(qū)間第四十頁，共58頁。二進(jìn)制算術(shù)編碼假定對序列1,3,2,1進(jìn)行算術(shù)編碼，其統(tǒng)計參數(shù)XCount(X)CumCount(X)0001404021413950選用8位二進(jìn)制數(shù)計算，初始值Scale=0，Low=0=(00000000)2，High=255=(11111111)2第四十一頁，共58頁。二進(jìn)制算術(shù)編碼第一個符號是1XCount(X)CumCount(X)0001404021413950最高位不相等，無輸出第四十二頁，共58頁。二進(jìn)制算術(shù)編碼第二個符號是3XCount(X)CumCount(X)0001404021413950最高位相等，輸出最高位1。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1第四十三頁，共58頁。二進(jìn)制算術(shù)編碼現(xiàn)在Low=01xxxxxx，High=10xxxxxx，將區(qū)間比例放大。Low和High分別左移1位，最高位取反，右邊分別補(bǔ)0和1，標(biāo)志變量Scale加1。第二個符號的輸出為1第四十四頁，共58頁。二進(jìn)制算術(shù)編碼第三個符號是2XCount(X)CumCount(X)0001404021413950最高位相等，輸出最高位1。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1。因Scale=1，再輸出最高位的補(bǔ)碼，即1個0，將Scale減1變?yōu)?。第四十五頁，共58頁。二進(jìn)制算術(shù)編碼最高位仍然相等，輸出最高位0。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1最高位仍然相等，輸出最高位0。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1第四十六頁，共58頁。二進(jìn)制算術(shù)編碼最高位仍然相等，輸出最高位1。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1最高位仍然相等，輸出最高位0。low和High左移1位，Low最低位補(bǔ)0，High最低位補(bǔ)1。第四十七頁，共58頁。二進(jìn)制算術(shù)編碼現(xiàn)在Low=01xxxxxx，High=10xxxxxx，將區(qū)間比例放大。Low和High分別左移1位，最高位取反，右邊分別補(bǔ)0和1，標(biāo)志變量Scale加1。第三個符號的輸出為100010第四十八頁，共58頁。二進(jìn)制算術(shù)編碼第四個符號是1最高位不相等，無輸出。因碼流結(jié)束，應(yīng)輸出結(jié)束時的Low，即輸出8個0。又因Scale=1，在輸出第1個0之后應(yīng)插入1個1。因此第四個符號的輸出為010000000碼流1,3,2,1的輸出為11000第四十九頁，共58頁。二進(jìn)制算術(shù)編碼解碼過程剛好相反以Index解碼符