數(shù)據(jù)壓縮霍夫曼編碼算術(shù)編碼

數(shù)據(jù)壓縮霍夫曼編碼算術(shù)編碼第一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三主要內(nèi)容圖像壓縮編碼簡(jiǎn)介Huffman編碼算術(shù)編碼簡(jiǎn)介算術(shù)編碼原理算術(shù)編碼的發(fā)展及應(yīng)用第二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三一圖像壓縮編碼簡(jiǎn)介第三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

霍夫曼編碼 霍夫曼編碼(Huffmancoding)根據(jù)給定數(shù)據(jù)集中霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法各元素所出現(xiàn)的頻率來(lái)壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少?gòu)V泛用在JPEG,MPEG,H.26X等各種信息編碼標(biāo)準(zhǔn)中第四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三熵(entropy)按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量的平均值，也稱事件的平均信息量(meaninformationcontent)(依概率平均)用數(shù)學(xué)表示為熵是數(shù)據(jù)壓縮的極限第五頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼(1)計(jì)算該字符串的霍夫曼碼步驟①：按照符號(hào)出現(xiàn)概率大小的順序?qū)Ψ?hào)進(jìn)行排序步驟②：把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)P1步驟③：重復(fù)步驟②，得到節(jié)點(diǎn)P2，P3，P4，……，

PN，形成一棵樹(shù)，其中的PN稱為根節(jié)點(diǎn)步驟④：從根節(jié)點(diǎn)PN開(kāi)始到每個(gè)符號(hào)的樹(shù)葉，從上到下

標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則

無(wú)關(guān)緊要，但通常把概率大的標(biāo)成1，概率小的

標(biāo)成0.(標(biāo)記)步驟⑤：從根節(jié)點(diǎn)PN開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫出

每個(gè)符號(hào)的代碼.(反向編碼)第六頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼霍夫曼編碼舉例1現(xiàn)有一個(gè)由5個(gè)不同符號(hào)組成的30個(gè)符號(hào)的字符串：BABACACADADABBCBABEBEDDABEEEBB計(jì)算(1)該字符串的霍夫曼碼(2)該字符串的熵(3)該字符串的平均碼長(zhǎng)(4)編碼前后的壓縮比第七頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼符號(hào)出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.585?A81.907?C33.322?D42.907?E52.585?合計(jì)30符號(hào)出現(xiàn)的概率第八頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼符號(hào)B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代碼B(11)A(10)E(00)D(011)C(010)第九頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼符號(hào)出現(xiàn)的次數(shù)log2(1/pi）分配的代碼需要的位數(shù)B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合計(jì)306730個(gè)字符組成的字符串需要67位5個(gè)符號(hào)的代碼第十頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼

(2)計(jì)算該字符串的熵

其中，是事件的集合，

并滿足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)

=(44.3136－24.5592)/9.0308＝

2.1874(Sh)

理論上可獲得的壓縮比為：3:2.1874=1.37第十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三霍夫曼編碼(3)

計(jì)算該字符串的平均碼長(zhǎng)平均碼長(zhǎng)：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝2.233位/符號(hào)

壓縮比:90/67=1.34:1

平均碼長(zhǎng)：67/30=2.233位(4)計(jì)算編碼前后的壓縮比編碼前：5個(gè)符號(hào)需3位，30個(gè)字符，需要90位編碼后：共67位第十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三算術(shù)編碼簡(jiǎn)介算術(shù)編碼(ArithmeticCoding)：和霍夫曼編碼不同，算術(shù)編碼跳出。分組編碼的范疇,從全序列出發(fā),采用遞推形式的連續(xù)編碼不是將單個(gè)信源符號(hào)映射成一個(gè)碼字,而是將整個(gè)輸入符號(hào)序列映射為實(shí)數(shù)軸上[0,1)區(qū)間內(nèi)的一個(gè)小區(qū)間,其長(zhǎng)度等于該序列的概率,再在該小區(qū)間選擇一個(gè)代表性的二進(jìn)制小數(shù),作為實(shí)際的編碼輸出。第十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三算術(shù)編碼

算術(shù)編碼(arithmeticcoding)給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無(wú)損壓縮技術(shù)基本思想是用0和1之間的一個(gè)數(shù)值范圍表示輸入流中的一個(gè)字符（串），而不是給輸入流中的每個(gè)字符分別指定一個(gè)碼字實(shí)質(zhì)上是為整個(gè)輸入字符流分配一個(gè)“碼字”，因此它的編碼效率可接近于熵

第十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

算術(shù)編碼(1)基本思想：基于遞歸概率區(qū)間劃分的二進(jìn)制編碼．具體過(guò)程：①把信源符號(hào)序列{Xi|i=1,2,…,n}發(fā)生的概率用實(shí)數(shù)區(qū)間[0，1]上的間隔（Xi的取值范圍）來(lái)表示②按符號(hào)概率大小來(lái)分配符號(hào)間隔，使[0，1]隨迭代計(jì)算次數(shù)的增加而逐次變窄；③所求最后范圍便是替代{Xi}符號(hào)串編碼的取值范圍⑵應(yīng)用實(shí)例：待編碼符號(hào)串為X1,X2,X3,X4,X5第十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

算術(shù)編碼處理過(guò)程的編碼區(qū)間分配可用圖解法表示：

以少代多思想：用最終求得的編碼表示范圍子區(qū)間的任何值（如：0.10603），來(lái)替代被編碼符號(hào)串X1X2X3X4X5第十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期三無(wú)論是否是二元信源，也不論數(shù)據(jù)的概率分布如何，算術(shù)編碼可以二進(jìn)制小數(shù)表示，其平均碼長(zhǎng)可以接近無(wú)損壓縮的熵極限。因此：第十七頁(yè)，共二十七頁(yè)，編輯于2023年，星期三算術(shù)編碼的發(fā)展歷史：1960年，P.Elias首先提出把這種依附Shannon編碼概念推廣到對(duì)符號(hào)序列直接編碼上，推出了所謂的算術(shù)編碼（ArithmeticCoding）；1948年，Shannon提出將信源依其概率降序排序,用符號(hào)序列累積概率的二進(jìn)制表示對(duì)信源的編碼;1976年,R.Pasco和J.Rissanen分別用定長(zhǎng)的寄存器實(shí)現(xiàn)了有限精度的算術(shù)編碼;1979年,Rissanen和G.G.Langdon將算術(shù)編碼系統(tǒng)化，并于1981年將AC推廣應(yīng)用到二值圖像編碼上,大大提高了起壓縮效率；1987年,Witten等人發(fā)表了一個(gè)實(shí)用的算術(shù)編碼程序(CACM87,后用于H.263);同期IBM公司發(fā)表了著名的Q-編碼器(后用于JPEG和JPIG);第十八頁(yè)，共二十七頁(yè)，編輯于2023年，星期三設(shè)一個(gè)信源，它有兩個(gè)符號(hào)a和b，出現(xiàn)的概率分別是p和1–p，設(shè)有一個(gè)基準(zhǔn)區(qū)域[0，1]，對(duì)它進(jìn)行劃分，以便與信源輸出序列相對(duì)應(yīng)。abp1aabap1p+p(1-p)bbabaabap2bbab圖A符號(hào)序列與區(qū)域劃分示意算術(shù)編碼的基本原理第十九頁(yè)，共二十七頁(yè)，編輯于2023年，星期三ab0.81aaba0.810.96bbabaaba0.64bbabaaabab0.810.960.64bbaaba0.5120.7680.9920.928bbbbaaabbaab例設(shè)一個(gè)信源，它有兩個(gè)符號(hào)a和b，出現(xiàn)的概率分別是0.8和0.2，有3個(gè)符號(hào)輸出時(shí)，符號(hào)序列與區(qū)域劃分的對(duì)應(yīng)關(guān)系。圖B3符號(hào)輸出時(shí)的符號(hào)序列與區(qū)域劃分示意第二十頁(yè)，共二十七頁(yè)，編輯于2023年，星期三字符串a(chǎn)abaa對(duì)應(yīng)的區(qū)域?yàn)閇0.512，0.59392)該區(qū)域的二進(jìn)制表示[0.1000001…，0.1001100…)二進(jìn)制數(shù)0.1001輸出編碼1001因此第二十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期三對(duì)于這個(gè)信源：H（X）=0.7219Huffman編碼:算術(shù)編碼:平均碼長(zhǎng)R=0.8平均碼長(zhǎng)R=1相比Huffman編碼，算術(shù)編碼的編碼效率有明顯提高。對(duì)于長(zhǎng)序列，理論上算術(shù)編碼可以達(dá)到信源的熵。編碼效率第二十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期三算術(shù)編碼過(guò)程:依據(jù)字符的發(fā)生概率對(duì)碼區(qū)間的分割過(guò)程(即子區(qū)間寬度與正編碼字符發(fā)生概率相乘的過(guò)程)。算術(shù)解碼過(guò)程:只需知道最終編碼區(qū)間中的某一個(gè)值就可以解碼。算術(shù)編碼每次遞推都要做乘法，而且必須在一個(gè)信源符號(hào)的處理周期內(nèi)完成，有時(shí)難以實(shí)時(shí)，為此采用了查表等許多近似計(jì)算來(lái)代替乘法。小結(jié)：第二十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期三固定編碼模式概率統(tǒng)計(jì)與區(qū)間分配直接影響編碼效率。自適應(yīng)模式各符號(hào)的概率初始值都相同，但依據(jù)實(shí)際出現(xiàn)的符號(hào)而相應(yīng)地改變。兩種編碼模式：第二十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期三算術(shù)編碼的發(fā)展及應(yīng)用jpeg、mpeg-1和mpeg-2等國(guó)際標(biāo)準(zhǔn)采用的圖像壓縮編碼方案都是傳統(tǒng)的“DCT+運(yùn)動(dòng)補(bǔ)償+算術(shù)編碼”模式JPEG2000、MQ算術(shù)編碼器嵌入位平面圖像編碼器EZW、SPIHT和SPECK中也采用這種通用算法編碼器第二十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期三

算術(shù)碼評(píng)述

能夠自適應(yīng)地估計(jì)條件概率,從信源的統(tǒng)計(jì)特性

出發(fā),建立數(shù)據(jù)的概率模型。它不必預(yù)先定義信

源的概率模型,尤其適用于不可能進(jìn)行概率統(tǒng)計(jì)

的場(chǎng)合;

適用于信源符號(hào)概率比較接近的場(chǎng)合，在幾種主

要的統(tǒng)計(jì)編碼