【文章內(nèi)容簡(jiǎn)介】 0 a b 1 對(duì)已知區(qū)間進(jìn)行再次分割 第二個(gè)為 b，編碼范圍限制在 ～ 0 a b 算術(shù)編碼 a b 0 a b 對(duì)已知區(qū)間進(jìn)行再次分割 第 3個(gè)為 a，編碼范圍限制在 [,)范圍內(nèi) 9 a b 算術(shù)編碼 ?在 [,) 中任選一個(gè)浮點(diǎn)數(shù)來(lái)標(biāo)識(shí)這個(gè)區(qū)間，如 ，即可表示我們要編的消息為“ aba‖ ?把該浮點(diǎn)數(shù)轉(zhuǎn)變?yōu)槎M(jìn)制編碼 : 0010 ?特性： 區(qū)間越窄，說(shuō)明符號(hào)串越長(zhǎng)，二進(jìn)制碼長(zhǎng)越長(zhǎng) 舉例 2 ? 假設(shè)信源符號(hào)為 {00, 01, 10, 11}，它們的 概率分別為 { , , , } ? 對(duì)二進(jìn)制消息序列 10 00 11 00 10 11 01 … 進(jìn)行算術(shù)編碼 算術(shù)編碼 ?初始化： 根據(jù)信源符號(hào)的概率把間隔 [0, 1)分成如表 2 4所示的 4個(gè)子間隔： [0, ), [, ), [, ), [, 1)。其中 [x, y)的表示半開(kāi)放間隔， 即包含 x不包含 y， x稱為低邊界或左邊界， y 稱為高邊界或右邊界 符號(hào) 00 01 10 11 概率 初始區(qū)間 [0, ) [, ) [, ) [, 1) 算術(shù)編碼 ? 確定符號(hào)的編碼范圍 ? 編碼時(shí)輸入第 1個(gè)符號(hào)是 10，找到它的編碼范圍是 [, ] ? 消息中第 2個(gè)符號(hào) 00的編碼范圍是 [0, )，它的間隔 就取 [, )的第一個(gè)十分之一作為新間隔 [, ) ? 編碼第 3個(gè)符號(hào) 11時(shí)，取新間隔為 [, ) ? 編碼第 4個(gè)符號(hào) 00時(shí)，取新間隔為 [, ) ? 依此類推 …… ? 消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù) 算術(shù)編碼 算術(shù)編碼 算術(shù)編碼 算術(shù)編碼 ?算術(shù)編碼 ?長(zhǎng)度為 n的序列的算術(shù)編碼的平均碼長(zhǎng)為： 算術(shù)編碼的效率高：當(dāng)信源符號(hào)序列很長(zhǎng)，平均碼長(zhǎng)接近信源的熵 ? ?? ? ? ?()1 ( ) 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ù)編碼中需要注意的問(wèn)題： ?由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問(wèn)題，但多數(shù)機(jī)器都有 16位、 32位或者 64位的精度，因此這個(gè)問(wèn)題可使用比例縮放方法解決。 ?算術(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)行修改。 ?開(kāi)發(fā)動(dòng)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過(guò)程中估算概率。 帶縮放的算術(shù)編碼 ?編碼器： ? 一旦我們到達(dá) 1. 或 2.，就可以忽略 [0,1)的另一半 ? 還需要告知解碼器標(biāo)識(shí)所在的半?yún)^(qū)間： ? 發(fā)送 0/1 比特用來(lái)指示下上界所在區(qū)間 ? 將標(biāo)識(shí)區(qū)間縮放到 [0, 1): ? E1: [0, ) = [0, 1)。 E1(x) = 2x ? E2: [0. 5,1) = [0, 1)。 E2(x) = 2() ? 注意：在縮放過(guò)程中我們丟失了最高位 ? 但這不成問(wèn)題 —我們已經(jīng)發(fā)送出去了 ?解碼器 ? 根據(jù) 0/1比特并相應(yīng)縮放 ? 與編碼器保持同步 帶縮放的算術(shù)編碼 ? 考慮隨機(jī)變量 X(ai) = 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 Output: 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? ? ? ?? ? ? ?Input: 110001100000 Output: 13 Input: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? ? ? ?? ? ? ?Input: 10001100000 () Output: 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? ? ? ?? ? ? ?Input: 001100000 (左移 ) Input: 0001100000 (左移 ) ( 1 )( 1 )0 (1 0 ) 0 00 (1 0 ) 0 .8 0 .8lu? ? ? ? ?? ? ? ? ?帶縮放的算術(shù)編碼 此時(shí)解碼最后一個(gè)符號(hào) ( 3 )( 3 )2 2 lu? ? ?? ? ?Input: 01100000 (左移 ) ( 3 )( 3 )2 2 lu? ? ?? ? ?Input: 1100000 (左移 ) ( 3 )( 3 )2 2 lu? ? ?? ? ?Input: 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? ? ? ?? ? ? ?Input: 100000 ? ?* 2*1 0 0 0 0 0 0 .5 ,( 0 ) 0 0 .8 ( 1 )XXtF t F??? ? ? ?Output: 1321 ?應(yīng)用背景： 對(duì)于“局部冗余”的特殊類型。 主要應(yīng)用于圖象表達(dá)、處理。 ?原因： ? 數(shù)字化的 image有大量的“局部冗余” ? 占空間大 ? （一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。） 語(yǔ)義依賴 典型： ?行程編碼（ runlength encoding:RLE） ?差異映射 (difference mapping) ?詞典編碼 (Dictionary Encoding) 語(yǔ)義依賴 差異映射： ?算法思想： ? 圖象表示為相鄰像素在亮度 /顏色上的差異陣列，而不是像素本身的亮度 /顏色值 ?例 [Laeser et ] ? 8 bits/pixel (256 brightness)?3 bits/pixel 語(yǔ)義依賴 詞典編碼 ?詞典： ? 全部詞語(yǔ)（ words） ? 常用詞語(yǔ) +詞語(yǔ)結(jié)束符號(hào) ?編碼方法： ? 指向詞典的指針表 ? 指向詞典的指針表（常用詞語(yǔ)） +編碼（不常用詞語(yǔ)） 語(yǔ)義依賴 分解與編碼 ?源信息 ?代碼（長(zhǎng)度）： ? block block ? block variable ? variable block ? variable variable ?例：“ aa bbb cccc ddddd eeeeee fffffffgggggggg” ? ? block block (120) ? Source massage codeword ? a 000 ? b 001 ? c 010 ? d 011 ? e 100 ? f 101 ? g 110 ? space 111 分解與編碼 ?例： aa bbb cccc ddddd eeeeee fffffffgggggggg” ?variable variable (30) ? Source massage codeword ? aa 0 ? bbb 1 ? ccccc 10 ? ddddd 11 ? eeeeeee 100 ? fffffff 101 ? gggggggg 110 ? space 111 分解與編碼 ―定義字”與“自由分解”方法 ?定義字（ definedword）方式 ? 源信息分解的長(zhǎng)度在編碼調(diào)用之前已確定 ?自由分解（ freeparse）方式 ? 編碼算法本身決定源信息分解的長(zhǎng)度（變長(zhǎng)） 分解與編碼 典型算法 ?定義字方式的： ? ShannonFano coding ? Huffman coding ? Universal codes (通用碼 ) ? Arithmetic coding (算術(shù)編碼 ) ?自由分解方式的： ? LempelZiv codes ? Algorithm BSTW 行程編碼 （ RLE） ?基本原理： 它通過(guò)將信源中相同符號(hào)序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。 行程編碼 （ RLE） ?行程編碼 (RLE）算法 : x1, x2, …… xn ( c1 ,l1 ), ( c2,l2 ), …… ( ck,lk )