【文章內(nèi)容簡介】 ( ) l og 1()1 ( ) l og 1 1() ( ) l og ( ) 2 ( ) 2 2Anl P lPPPPP P PH X nH X?????????????????? ? ?????? ? ?? ? ? ??????xxxxxxx x x? ? ? ? ? ? ? ? 2 2 n AAn H X l n H X H X l H X n? ? ? ? ? ? ?算術(shù)編碼 在算術(shù)編碼中需要注意的問題： 由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有 16位、32位或者 64位的精度，因此這個問題可使用比例縮放方法解決。 算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔 [0, 1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。 算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。 算術(shù)編碼 ? 算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。 ?開發(fā)動態(tài)算術(shù)編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切實際的。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。 帶縮放的算術(shù)編碼 ?編碼器： ?一旦我們到達 1. 或 2.，就可以忽略 [0,1)的另一半 ?還需要告知解碼器標(biāo)識所在的半?yún)^(qū)間： ?發(fā)送 0/1 比特用來指示下上界所在區(qū)間 ?將標(biāo)識區(qū)間縮放到 [0, 1): ?E1: [0, ) = [0, 1)。 E1(x) = 2x ?E2: [0. 5,1) = [0, 1)。 E2(x) = 2() ?注意：在縮放過程中我們丟失了最高位 ?但這不成問題 —我們已經(jīng)發(fā)送出去了 ?解碼器 ?根據(jù) 0/1比特并相應(yīng)縮放 ?與編碼器保持同步 帶縮放的算術(shù)編碼 ? 考慮隨機變量 X() = i ? 對序列 1 3 2 1編碼： 1,0 )0()0( ?? ul? ?? ?( 1 ) ( 0 ) ( 0 ) ( 0 )( 1 ) ( 0 ) ( 0 ) ( 0 )( 1 ) ( 1 )( 1 ) ( 1 )( 0) 0( 1 ) 0. 8[ , ) [ 0 , 0. 5 )[ , ) [ 0. 5 , 1 )XXl l u l Fu l u l Fluluge t ne x t symbol? ? ? ?? ? ? ????Input: 1321 Output: ? ?? ?( 2 ) ( 1 ) ( 1 ) ( 1 )( 2 ) ( 1 ) ( 1 ) ( 1 )( 2 )( 2 )( 2) 0. 65 6( 3 ) 0. 8[ 0. 65 6 , 0. 8 ] [ 0. 5 , 1 )2 ( 0. 65 6 0. 5 ) 0. 31 22 ( 0. 8 0. 5 ) 0. 6XXl l u l Fu l u l Flu? ? ? ?? ? ? ??? ? ? ?? ? ? ?Input: 321 Output: 1 帶縮放的算術(shù)編碼 Input: 21 Output: 11 Input: 1 Output: 110 Input: 1 Output: 1100 Input: 1 Output: 11000 帶縮放的算術(shù)編碼 ?假設(shè)碼字長為 6 ?輸入： 110001100000 ? = ?第 1位： 1 ? : 1 ? ? ? ?**0 .7 6 5 6 2 5 0 0 .8 0 0 .9 5 7 0( 2 ) 0 .8 2 1 (3 )XXtF t F? ? ? ?? ? ? ?? ?? ?( 2 ) ( 1 ) ( 1 ) ( 1 )( 2 ) ( 1 ) ( 1 ) ( 1 )( 2 ) 0 .6 5 6(3 ) 0 .8XXl l u l Fu l u l F? ? ? ?? ? ? ?: 110001100000 : 13 10001100000 (左移 ) ( 2 )( 2 )2 ( 0 .6 5 6 0 .5 ) 0 .3 1 22 ( 0 .8 0 .5 ) 0 .6lu? ? ? ?? ? ? ?? ? ? ?**0 .5 4 6 8 7 5 0 .3 1 2 0 .6 0 .3 1 2 0 .8 1 5 5( 1 ) 0 .8 0 .8 2 ( 2 )XXtF t F? ? ? ?? ? ? ?: 10001100000 () : 132 ? ?? ?( 3 ) ( 2 ) ( 2 ) ( 2 )( 3 ) ( 2 ) ( 2 ) ( 2 )( 1 ) 0 .5 4 2 4( 2 ) 0 .5 4 8 1 6XXl l u l Fu l u l F? ? ? ?? ? ? ?? ?? ?( 3 )( 3 )2 0 .5 4 2 4 0 .5 0 .0 8 4 82 0 .5 4 8 1 6 0 .5 0 .0 9 6 3 2lu? ? ? ?? ? ? ?: 001100000 (左移 ) : 0001100000 (左移 ) ( 1 )( 1 )0 (1 0 ) 0 00 (1 0 ) 0 .8 0 .8lu? ? ? ? ?? ? ? ? ?帶縮放的算術(shù)編碼 此時解碼最后一個符號 ( 3 )( 3 )2 2 lu? ? ?? ? ?: 01100000 (左移 ) ( 3 )( 3 )2 2 lu? ? ?? ? ?: 1100000 (左移 ) ( 3 )( 3 )2 2 lu? ? ?? ? ?: 100000 (左移 ) ( 4 )( 4 )0 .3 5 6 8 ( 0 .5 4 1 1 2 0 .3 5 6 8 ) ( 0 ) 0 .3 5 6 80 .3 5 6 8 ( 0 .5 4 1 1 2 0 .3 5 6 8 ) ( 1 ) 0 .5 0 4 2 5 6XXlFuF? ? ? ?? ? ? ?: 100000 ? ?* 2*1 0 0 0 0 0 0 .5 ,( 0 ) 0 0 .8 ( 1 )XXtF t F??? ? ? ?: 1321 ?應(yīng)用背景： ? 對于“局部冗余”的特殊類型。 ? 主要應(yīng)用于圖象表達、處理。 ?原因： ?數(shù)字化的有大量的“局部冗余” ?占空間大 ?（一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。） 語義依賴 典型： 行程編碼（ ） 差異映射 ( ) 詞典編碼 ( ) 語義依賴 差異映射： 算法思想： 圖象表示為相鄰像素在亮度 /顏色上的差異陣列，而不是像素本身的亮度 /顏色值 例 [ .1986] 8 (256 ) 3 語義依賴 詞典編碼 詞典： 全部詞語（） 常用詞語 +詞語結(jié)束符號 編碼方法： 指向詞典的指針表 指向詞典的指針表（常用詞語） +編碼（不常用詞語） 語義依賴 分解與編碼 ?源信息 代碼（長度）： ? ? ? ? ?例：“ ” ? ? (120) ? ? a 000 ? b 001 ? c 010 ? d 011 ? e 100 ? f 101 ? g 110 ? 111 分解與編碼 ?例： ” ? (30) ? ? 0 ? 1 ? 10 ? 11 ? 100 ? 101 ? 110 ? 111 分解與編碼 ―定義字 ‖與 ―自由分解 ‖方法 定義字（）方式 源信息分解的長度在編碼調(diào)用之前已確定 自由分解（）方式 編碼算法本身決定源信息分解的長度（變長） 分解與編碼 典型算法 定義字方式的： (通用碼 ) (算術(shù)編碼 ) 自由分解方式的： 行程編碼（） ?基本原理： ? 它通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字段再加上一個重復(fù)字符標(biāo)志實現(xiàn)壓縮。 ? 行程編碼（） ?行程編碼 (）算法 : ?x1, x2, …… ( c1 1 ), ( c22 ), …… ( ) ? : 亮度 /顏色 ? :第 i行程（相同亮度 /顏色的像素的序列）的長度 ?不需要存儲每一個象素的顏色值，而僅僅存儲一個象素的顏色值，以及具有相同顏色的象素數(shù)目就可以；或者存儲一個象素的顏色值，以及具有相同顏色值的行數(shù)。 ?具有相同顏色并且是連續(xù)的象素數(shù)目稱為行程長度。 行程編碼（） ?例： ?代碼字為： ?（ 0， 8),（ 1， 3),（ 8， 50),（ 1， 4),(0， 8） 行程編碼（） ? 所能獲得的壓縮比 ——主要是取決于圖像本身的特點。 ? 如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。 ? 是無損壓縮技術(shù)。 行程編碼（） 應(yīng)用： 尤其適用于計算機生成的圖像，對減少圖像文件的存儲空間非常有效。（對顏色豐富的自然圖像不能單純使用一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。） 商業(yè)數(shù)據(jù)處理（如連續(xù)多個 0，空格） 行程編碼（） 特點： 利用兩個字節(jié)代替連續(xù)出現(xiàn)的同一數(shù)據(jù)。通常需要在表示重復(fù)次數(shù)的字節(jié)中利用前一位或兩位作為標(biāo)志位，提示應(yīng)用程序中隨后的極為表示次數(shù)，另一字節(jié)表示重復(fù)數(shù)據(jù)的值。 舉例說明： d (共 22*8=176 ) 4a3b2c1d5e7f (共 12*8=96 ) 行程編碼 ?8的編碼方式： ? 由 2個字節(jié)組成，第一個字節(jié)指定使用相同顏色的象素數(shù)目，第二個字節(jié)指定使用的顏色索引。此外，這個字節(jié)對中的第一個字節(jié)可設(shè)置為 0，聯(lián)合使用第二個字節(jié)的值表示： 第二個字節(jié)的值為 0：行的結(jié)束。 第二個字節(jié)的值為 1：圖象結(jié)束。 第二個字節(jié)的值為 2：其后的兩個字節(jié)表示下一個象素從當(dāng)前開始的水平和垂直位置的偏移量。 行程編碼 ?例如： 0304050602780002050102780000091E0001 ?這些壓縮數(shù)據(jù)可解釋為： 0304 040404 0506 0606060606 0278 7878 00020501 從當(dāng)前位置右移 5個位置后向下移一行 0278 7878 0000 行結(jié)束 091E 1E1E1E1E1E1E1E1E1E 0001 編碼圖象結(jié)束 行程編碼 簡介：真彩色圖像以行為單位，按色面存放 128字節(jié)的文件頭 圖像數(shù)據(jù) 調(diào)色板 行程編碼 ? 圖像數(shù)據(jù)以字節(jié)為單位進行編碼 ? 按行進行壓縮 ? 長度在前，灰度值在后 ? 單像素沒有長度值 ? 以最高兩位作為判斷是重復(fù)數(shù)還是原像素。 最高兩位為 1（ B0除外），說明是重復(fù)數(shù)，否則，說明是原像素值 行程編碼 ?重復(fù)像素長度最大值為 261 = 63，如果遇到大于63的情況，則分為小于 63的幾段，分別處理。 ?如果遇到不重復(fù)的單個像素 P： ? 如果 P 00（ 192） 直接存入該像素值， ? 否則先存入長度 1，再存入像素值 ? （ 192255之間的單像素圖像不減反增） 行程編碼 例 0X150X15 0X5