【文章內(nèi)容簡(jiǎn)介】 ( ) 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ù)編碼中需要注意的問題： 由于實(shí)際的計(jì)算機(jī)的精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有 16位、32位或者 64位的精度，因此這個(gè)問題可使用比例縮放方法解決。 算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 [0, 1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。 算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。 算術(shù)編碼 ? 算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。 ?開發(fā)動(dòng)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。 帶縮放的算術(shù)編碼 ?編碼器： ?一旦我們到達(dá) 1. 或 2.，就可以忽略 [0,1)的另一半 ?還需要告知解碼器標(biāo)識(shí)所在的半?yún)^(qū)間： ?發(fā)送 0/1 比特用來指示下上界所在區(qū)間 ?將標(biāo)識(shí)區(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ù)編碼 ? 考慮隨機(jī)變量 X() = i ? 對(duì)序列 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è)碼字長(zhǎng)為 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ù)編碼 此時(shí)解碼最后一個(gè)符號(hào) ( 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)用背景： ? 對(duì)于“局部冗余”的特殊類型。 ? 主要應(yīng)用于圖象表達(dá)、處理。 ?原因： ?數(shù)字化的有大量的“局部冗余” ?占空間大 ?（一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。） 語義依賴 典型： 行程編碼（ ） 差異映射 ( ) 詞典編碼 ( ) 語義依賴 差異映射： 算法思想： 圖象表示為相鄰像素在亮度 /顏色上的差異陣列，而不是像素本身的亮度 /顏色值 例 [ .1986] 8 (256 ) 3 語義依賴 詞典編碼 詞典： 全部詞語（） 常用詞語 +詞語結(jié)束符號(hào) 編碼方法： 指向詞典的指針表 指向詞典的指針表（常用詞語） +編碼（不常用詞語） 語義依賴 分解與編碼 ?源信息 代碼（長(zhǎng)度）： ? ? ? ? ?例：“ ” ? ? (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 分解與編碼 ―定義字 ‖與 ―自由分解 ‖方法 定義字（）方式 源信息分解的長(zhǎng)度在編碼調(diào)用之前已確定 自由分解（）方式 編碼算法本身決定源信息分解的長(zhǎng)度（變長(zhǎng)） 分解與編碼 典型算法 定義字方式的： (通用碼 ) (算術(shù)編碼 ) 自由分解方式的： 行程編碼（） ?基本原理： ? 它通過將信源中相同符號(hào)序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。 ? 行程編碼（） ?行程編碼 (）算法 : ?x1, x2, …… ( c1 1 ), ( c22 ), …… ( ) ? : 亮度 /顏色 ? :第 i行程（相同亮度 /顏色的像素的序列）的長(zhǎng)度 ?不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以；或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。 ?具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱為行程長(zhǎng)度。 行程編碼（） ?例： ?代碼字為： ?（ 0， 8),（ 1， 3),（ 8， 50),（ 1， 4),(0， 8） 行程編碼（） ? 所能獲得的壓縮比 ——主要是取決于圖像本身的特點(diǎn)。 ? 如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。 ? 是無損壓縮技術(shù)。 行程編碼（） 應(yīng)用： 尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。（對(duì)顏色豐富的自然圖像不能單純使用一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。） 商業(yè)數(shù)據(jù)處理（如連續(xù)多個(gè) 0，空格） 行程編碼（） 特點(diǎn)： 利用兩個(gè)字節(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個(gè)字節(jié)組成，第一個(gè)字節(jié)指定使用相同顏色的象素?cái)?shù)目，第二個(gè)字節(jié)指定使用的顏色索引。此外，這個(gè)字節(jié)對(duì)中的第一個(gè)字節(jié)可設(shè)置為 0，聯(lián)合使用第二個(gè)字節(jié)的值表示： 第二個(gè)字節(jié)的值為 0：行的結(jié)束。 第二個(gè)字節(jié)的值為 1：圖象結(jié)束。 第二個(gè)字節(jié)的值為 2：其后的兩個(gè)字節(jié)表示下一個(gè)象素從當(dāng)前開始的水平和垂直位置的偏移量。 行程編碼 ?例如： 0304050602780002050102780000091E0001 ?這些壓縮數(shù)據(jù)可解釋為： 0304 040404 0506 0606060606 0278 7878 00020501 從當(dāng)前位置右移 5個(gè)位置后向下移一行 0278 7878 0000 行結(jié)束 091E 1E1E1E1E1E1E1E1E1E 0001 編碼圖象結(jié)束 行程編碼 簡(jiǎn)介：真彩色圖像以行為單位，按色面存放 128字節(jié)的文件頭 圖像數(shù)據(jù) 調(diào)色板 行程編碼 ? 圖像數(shù)據(jù)以字節(jié)為單位進(jìn)行編碼 ? 按行進(jìn)行壓縮 ? 長(zhǎng)度在前，灰度值在后 ? 單像素沒有長(zhǎng)度值 ? 以最高兩位作為判斷是重復(fù)數(shù)還是原像素。 最高兩位為 1（ B0除外），說明是重復(fù)數(shù)，否則，說明是原像素值 行程編碼 ?重復(fù)像素長(zhǎng)度最大值為 261 = 63，如果遇到大于63的情況，則分為小于 63的幾段，分別處理。 ?如果遇到不重復(fù)的單個(gè)像素 P： ? 如果 P 00（ 192） 直接存入該像素值， ? 否則先存入長(zhǎng)度 1，再存入像素值 ? （ 192255之間的單像素圖像不減反增） 行程編碼 例 0X150X15 0X5