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

1、算術(shù)編碼 Arithmetic Coding,主要內(nèi)容,圖像壓縮編碼簡(jiǎn)介 Huffman編碼 算術(shù)編碼簡(jiǎn)介 算術(shù)編碼原理 算術(shù)編碼的發(fā)展及應(yīng)用,一 圖像壓縮編碼簡(jiǎn)介,霍夫曼編碼,霍夫曼編碼(Huffman coding) 根據(jù)給定數(shù)據(jù)集中霍夫曼(D.A. Huffman)在1952年提出和描述的“從下到上”的熵編碼方法 各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少 廣泛用在JPEG, MPEG, H.26X等各種信息編碼標(biāo)準(zhǔn)中,熵(entropy) 按照香農(nóng)(Shannon)的理論，在有限的互斥和聯(lián)合窮舉事件的集合中，熵為事件的信息量

2、的平均值，也稱事件的平均信息量(mean information content) (依概率平均) 用數(shù)學(xué)表示為,熵是數(shù)據(jù)壓縮的極限,霍夫曼編碼,(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，形成一棵樹，其中的PN稱為根節(jié)點(diǎn) 步驟：從根節(jié)點(diǎn)PN開始到每個(gè)符號(hào)的樹葉，從上到下 標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則 無關(guān)緊要，但通常把概率大的標(biāo)成1，概率小的 標(biāo)成0.(標(biāo)記) 步驟：從根節(jié)點(diǎn)PN開始順著樹枝到每個(gè)葉子分別寫出 每個(gè)符號(hào)的代碼.(反向編碼),霍

3、夫曼編碼,霍夫曼編碼舉例1 現(xiàn)有一個(gè)由5個(gè)不同符號(hào)組成的30個(gè)符號(hào)的字符串：BABACACADADABBCBABEBEDDABEEEBB 計(jì)算 (1) 該字符串的霍夫曼碼 (2) 該字符串的熵 (3) 該字符串的平均碼長(zhǎng) (4) 編碼前后的壓縮比,霍夫曼編碼,符號(hào)出現(xiàn)的概率,霍夫曼編碼,符號(hào) B (10) A (8) E (5) D (4) C (3),P1 (7),P2 (12),P3 (18),P4 (30),0,1,1,0,1,0,1,0,代碼 B(11) A(10) E(00) D(011) C(010),霍夫曼編碼,30個(gè)字符組成的字符串需要67位,5個(gè)符號(hào)的代碼,霍夫曼編碼,(2)

4、 計(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.313624.5592)/ 9.0308 2.1874 (Sh),理論上可獲得的壓縮比為： 3:2.1874=1.37,霍夫曼編碼,(3) 計(jì)算該字符串的平均碼長(zhǎng) 平均碼長(zhǎng)： (28210333425)/30 2.233 位/符號(hào),壓縮比: 90/67=1.34:1,平均碼長(zhǎng)：67/30=2.233位,(4) 計(jì)算編碼前后的壓縮

5、比 編碼前：5個(gè)符號(hào)需3位，30個(gè)字符，需要90位 編碼后：共67位,算術(shù)編碼簡(jiǎn)介,算術(shù)編碼(Arithmetic Coding )：,和霍夫曼編碼不同，算術(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í)際的編碼輸出。,算術(shù)編碼,算術(shù)編碼(arithmetic coding) 給已知統(tǒng)計(jì)信息的符號(hào)分配代碼的數(shù)據(jù)無損壓縮技術(shù) 基本思想是用0和1之間的一個(gè)數(shù)值范圍表示輸入流中的一個(gè)字符（串），而不是給輸

6、入流中的每個(gè)字符分別指定一個(gè)碼字 實(shí)質(zhì)上是為整個(gè)輸入字符流分配一個(gè)“碼字”，因此它的編碼效率可接近于熵,算術(shù)編碼 (1)基本思想：基于遞歸概率區(qū)間劃分的二進(jìn)制編碼具體過程： 把信源符號(hào)序列Xi|i=1,2,n發(fā)生的概率用實(shí)數(shù)區(qū)間 0，1上的間隔（Xi的取值范圍）來表示 按符號(hào)概率大小來分配符號(hào)間隔， 使0，1隨迭代計(jì)算次數(shù)的增加而逐次變窄； 所求最后范圍便是替代Xi符號(hào)串編碼的取值范圍 應(yīng)用實(shí)例：待編碼符號(hào)串為X1,X2,X3,X4,X5,算術(shù)編碼處理過程的編碼區(qū)間分配可用圖解法表示： 以少代多思想：用最終求得的編碼表示范圍子區(qū)間的 任何值（如：0.10603），來替代被編碼符號(hào)串X1X2X3

7、X4X5,無論是否是二元信源，也不論數(shù)據(jù)的概率分 布如何，算術(shù)編碼可以二進(jìn)制小數(shù)表示，其平均碼長(zhǎng)可以接近無損壓縮的熵極限。,因此：,算術(shù)編碼的發(fā)展歷史：,1960年，P. Elias首先提出把這種依附Shannon編碼概念推廣到對(duì)符號(hào)序列直接編碼上，推出了所謂的算術(shù)編碼（Arithmetic Coding）；,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)化，并于19

8、81年將AC推廣應(yīng)用到二值圖像編碼上,大大提高了起壓縮效率；,1987年, Witten等人發(fā)表了一個(gè)實(shí)用的算術(shù)編碼程序(CACM87,后用于H.263); 同期IBM公司發(fā)表了著名的Q-編碼器 (后用于JPEG和JPIG);,設(shè)一個(gè)信源，它有兩個(gè)符號(hào)a和b，出現(xiàn)的概率分別是p和1p，設(shè)有一個(gè)基準(zhǔn)區(qū)域0，1，對(duì)它進(jìn)行劃分，以便與信源輸出序列相對(duì)應(yīng)。,圖A 符號(hào)序列與區(qū)域劃分示意,算術(shù)編碼的基本原理,aa,ba,0.8,1,0.96,bb,ab,aa,ba,0.64,bb,ab,例,設(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)系。,

9、圖B 3符號(hào)輸出時(shí)的 符號(hào)序列與區(qū)域劃分示意,字符串 aabaa,對(duì)應(yīng)的區(qū)域?yàn)?0.512，0.59392),該區(qū)域的二進(jìn)制表示 0.1000001，0.1001100 ),二進(jìn)制數(shù)0.1001 輸出編碼 1001,因此,對(duì)于這個(gè)信源：,相比Huffman編碼，算術(shù)編碼的編碼效率有明顯提高。對(duì)于長(zhǎng)序列，理論上算術(shù)編碼可以達(dá)到信源的熵。,編碼效率,算術(shù)編碼過程:,依據(jù)字符的發(fā)生概率對(duì)碼區(qū)間的分割過程(即子區(qū)間寬度與正編碼字符發(fā)生概率相乘的過程)。,算術(shù)解碼過程:,只需知道最終編碼區(qū)間中的某一個(gè)值就可以解碼。,算術(shù)編碼每次遞推都要做乘法，而且必須在一個(gè)信源符號(hào)的處理周期內(nèi)完成，有時(shí)難以實(shí)時(shí)，為此采

10、用了查表等許多近似計(jì)算來代替乘法。,小結(jié)：,固定編碼模式,概率統(tǒng)計(jì)與區(qū)間分配直接影響編碼效率。,自適應(yīng)模式,各符號(hào)的概率初始值都相同，但依據(jù)實(shí)際出現(xiàn)的符號(hào)而相應(yīng)地改變。,兩種編碼模式：,算術(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中也采用這種通用算法編碼器,算術(shù)碼評(píng)述,能夠自適應(yīng)地估計(jì)條件概率, 從信源的統(tǒng)計(jì)特性 出發(fā), 建立數(shù)據(jù)的概率模型。它不必預(yù)先定義信 源的概率模型, 尤其適用于不可能進(jìn)行概率統(tǒng)計(jì) 的場(chǎng)合;,適用于信源符號(hào)概率比較接近的場(chǎng)合，在幾種主