1、1第七章第七章算術編碼算術編碼 27.1 前言n7.2 算術編碼原理 n7.3 二元集式算術碼 n7.4 JBIG中的改良式算術碼n7.5 動態式算術碼 n7.7 作業 n7.4.1 BACIC n7.4.2 條件熵式 3假設一字母集 ， 字母集發生機率 、 、 、 和 。 圖7.1 字母的機率區間分佈n舉例說明算術編碼原理7.2 算術編碼原理 54321,aaaaaS 5 . 0)(1aP2 . 0)(2aP1 . 0)(3aP1 . 0)(4aP1 . 0)(5aP00.50.70.80.91.01a2a3a4a5a4若今送方打算送出的訊息為圖7.2 處理完 的機率範圍圖7.3 處理完 的
2、機率範圍圖7.4 處理完 的機率範圍如果用0.175的二進位表示式來代表 這個訊息。現在，收方看到0.175，很容易知道訊息中的第一字母為 ，因為 0.175屬於區間 0, 0.5之中，依此類推， 收方很容易就可以解出原訊息為 。311aaa311aaa0.50.01.00.000.501a1a1a0.250.000.500.0000.250311aaa1a311aaa0.1750.0000.20057.3 二元集式算術碼 PABCDEESCF111111n舉例說明二元集式算術碼 假設一字母集 S = A, B, C, D, E, ESC, EOF， 一開始，令字母集中各個字母的出現次數為1。
3、 SEOFF1圖7.5起始狀態P 代表主要集(Primary Set)S 代表次要集(Secondary set)F 代表出現次數 6n假設給一輸入字串如下所示 輸入字串 = BAAEEAD (a) B的機率範圍P A B C D EESCF121111(b) 修正後的主要集圖7.6 讀入字母B後的變動P A B C D EESCF221111(b) 修正後的主要集(a) 新的機率範圍圖7.7 讀入字母A後的變動n首先，我們讀入字母B ，接著讀入第二個字母A01616261622147n第三個讀入的字母仍為A，A仍屬於主要集，我們很容易得出圖7.8的相關機率範圍和主要集。 n第四個讀入的字母為
4、E，同理得出圖7.9的相關機率範圍和主要集。 (a) 新的機率範圍(b) 修正後的主要集圖7.8 讀入第三個字母後的變動(b) 修正後的主要集(a) 新的機率範圍圖7.9 處理完第四個字母後的變動PABCDEESCF321111PA B C D EESCF3211216121416829611682921637378658n在實作時，為避免主要集中字母出現的總和過大，我們暫令總和的上限為10，若總和超過10，則進行重新縮小的動作，這裡，我們是將各字母的出現數除以2後，將商再進行四捨五入。 n接著，第五個讀入的字母為E，各字母出現的新變動如圖7.10所示。 圖7.10 處理完第五個字母後的變動P
5、 A B C D EESCF321131n由圖7.10可知目前主要集中的字母出現總數已超過10，經除以2再取四捨五入後，得到圖7.11的異動。 P A B C D EESCF211121圖7.11 重新縮小後的結果21637378652160371151202599(a) 新的機率範圍(b) 修正後的主要集9n在圖7.11中，我們將字母出現次數為2次以上的留在主要集中，ESC也仍留在主要集中。其餘的字母移到次要集中，我們因此得到圖7.12。圖7.12 新產生的主要集和次要集n第六個讀入的字母為A。 PAE ESCF221SBCDEOFF1111(a) 縮小後的主要集(b) 新產生的次要集圖7.
6、13 處理完第六個字母後的狀態(a) 機率範圍(b) 主要集(c) 次要集PAE ESCF321SBCDEOFF11112160371151202599216037152216037115120259910n再來模擬一次下個字母D。因為字母D不在主要集內，故先輸出ESC，然後在次要集內將字母D移進主要集中。如此一來，我們得到圖7.14的狀態。 圖7.14 新的主要集和次要集n在處理第七個符號D時，由於在主要集中找不到D，我們輸出ESC，ESC的機率範圍介於 到 之間。又已知D在次要集中的機率範圍介於 到 之間。所以處理完七個符號後的機率範圍介於 到 之間。 PADEESCF3121SBCEOF
7、F11165664243216037115120259942655221603712160371151202599436552216037111(a) 三列式nBACIC的全名為Block Arithmetic Coding for Image Compression，BACIC主要是針對黑白影像的壓縮而設計的，其效能並不輸JBIG (Joint Bilevel Image Experts Group)。n當我們在對目前符號編碼時，會參考到前面處理過的部分符號 。7.4 JBIG中的改良式算術碼7.4.1 BACICx xx xx xx xx xx xx xx xx xx xx xx x？x
8、xx xx xx xx xx xx xx xx xx xx xx x？(b) 五列式圖7.15 二種常用的模組(Template)12n對任一模組而言，共有12個位元被納入考慮。 12個位元共有212 = 4096種組態，例如：000000000000以註標0代表，000000000001以註標1代表，111111111111以註標4095代表 為方便起見用符號 i， ，用來表示註標 。40950 in為了記錄這4096種組態的黑位元之機率，我們用 ri 記錄每個 i其黑點數。 si 記錄每個 i 總點數。 n我們在黑白調色的影像中進行算術編碼時，離目前前後文較遠的相關點數給予較小的加權，例如
9、： ，如此一來就較能反應真實的機率分佈。 95. 013n起始時，si (0) = 2 ri (0) = 1 這裡 ri是記錄編碼黑點的個數，而括弧內的註標代表時間的變數。nri (n+1) 和 si (n+1) 定義如下 ri (n+1) = pi + 0.95 ri (n)si (n+1) = 1 + 0.95 si (n) 上式中，ri (n) 代表在編碼目前像素前，曾編過的黑像素且其模 組為 i 的總個數，而pi代表目前待編的像素。 pi = 0代表目前的像素為白；pi = 1代表目前的像素為黑。 針對模組為i 的組態，時間參數為n+1時，黑像素的機率可估計為 上式中，取很小的數，在實
10、作時可依實驗調整得之。分母項放二倍的，而在分子項放一個是怕高估了p1 (n+1, i) 。)2)(/()(), 1(1nsnrinpii(7.1) (7.2) 14n假設BACIC的碼表樹中葉子個數為K = 16， 而掃描五個黑色像素的機率序列為 n以K=16為樹根，由0.5機率可知其左子樹的加權為8 ，而右子樹的加權也為8。圖7.16為處理完機率0.5後的子樹示意圖。n接下來讀入機率0.6，我們可得到圖7.17的編碼樹。 圖7.16 處理完機率0.5後的子樹圖7.17 處理完機率0.6後的子樹)5 . 016(168801168801530115n同理，讀完0.7、0.4和0.2後，其對應的
11、編碼樹圖如7.18所示。 圖7.18 建置完成的編碼樹n假若我們掃描到的二元字串為11110，則在圖7.18中所對應到的路徑為圖中的粗體線所示。利用定長碼來編葉子點。例如，令圖7.18的葉子數量為16個，則每個葉子只需四個位元來編，如此一來，二元字串11110可編碼成0001。 16880153014101220111011016n結合JBIG1而設計的另一種算術編碼器。n如何將高灰階影像轉換成黑白影像 ：7.4.2 條件熵式1. 給一 高灰階影像，假設其中所有的灰階值皆為25。2. 若我們選用散亂式的抖動矩陣(Disperse Dither Matrix)來當作門檻矩陣。3. 則輸入影像經由
12、圖7.20會轉換為圖7.21，經由圖7.22會轉換為 圖7.23 。 4. 在圖7.21，圖7.23中的黑像素代表原輸入影像的灰階值小於抖 動矩陣中同位置的門檻。如此一來，高灰階影像就可轉換為黑白影像了。 8817圖7.20 散亂式的抖動矩陣圖7.21 所得的黑白影像圖7.22 叢聚式的抖動矩陣 圖7.23 經圖7.22作用後的結果1175212186222592913261030147233198244203115271131162812218622117521261030142592913824420723319311628123115271114781519262518612927313
13、12454310282930231312111620212217192625181478152731312461292829302354310202122171312111618n雖然以上的輸入影像為 的小例子，但從較巨觀的角度來看，若輸入的影像大小為一般的數百乘以數百的大小時，則經上述程序所得的黑白影像之效果還是不錯的。給一F16高灰階影像如圖7.24所示，經圖7.20的散亂式抖動矩陣作用後，我們得圖7.25的黑白影像。 圖7.24 輸入的F16高灰階影像圖7.25 經圖7.20作用後的結果8819nJBIG1用的是十點式的參考模組。n利用散亂式抖動矩陣所得的黑白影像之黑白像素分佈，我們可知
14、黑白像素呈現交錯分佈的樣式。基於這個特性，我們可將參考模組設計如圖7.27所示。圖7.26 JBIG1的十點式模組 x xx xx xx xx xx xx xx xx xx x？圖7.27 新的參考模組 x xx xx xx x？x xx xx xx xx xx xx xx x207.5 動態式算術碼n 假設字母集 S = A, B, C, D, E且目前字母出現的總次數為40。1：C16, 29, 40)3：A30, 40, 40)2：B3, 15, 40)5：E15, 16, 40)4：D0, 3, 40)圖7.28 目前的隱式二元樹1. 出現次數最高的字母為C且將其放置在樹根。2. 出現
15、次數次高的字母為B且依廣先搜尋(Breadth First Search)的次序將其放置在C的左孩子處。3. 1到5的註標也是依廣先搜尋放置的。 在這隱式二元樹上，有一些性質值得我們注意：21n陣列式的資料結構 COUNT i：記錄註標i之下符號為POS_TO_SYM i的出現次數。 TREE_CN i：記錄符號為POS_TO_SYM i為樹根的左子樹之 符號總出現次數。 SYM_TO_POS i：得到符號SYM的位置。 POS_TO_SYM i：得到註標為何符號SYM。 符 號ABCDE註 標 i12345COUNT i13121031TREE_CN i163000SYM_TO_POS i3
16、2145POS_TO_SYM iCBADE圖7.29 圖7.28 的陣列表示22n假設接下來讀到的字母串為DAAA n首先讀入字母D， 記錄字母出現總數的變數加1得到 T = 41( =40 + 1)。因為字母D的次數加1了，自然也影響了字母B和字母C的TREE_CN 的值，字母B和字母C的 TREE_CN 的值得加1。圖7.30 處理完字母D後的陣列表示符 號ABCDE註 標 i12345COUNT i13121041TREE_CN i174000SYM_TO_POS i32145POS_TO_SYM iCBADE23n處理完二個A後，A的總數增為12。圖7.31為處理完AA後的陣列表示。因
17、為字母A所在的節點為右子樹且無祖母節點，故不調整TREE_CN 。圖7.31 處理完AA後的陣列表示符 號ABCDE註 標 i12345COUNT i13121241TREE_CN i174000SYM_TO_POS i32145POS_TO_SYM iCBADE24n處理最後一個字母A，處理完A後，A的總數變為13，這會破壞在隱式二元樹進行廣先搜尋所得的數列之遞減性的。這時，我們將字母A和字母B做適當的對調。圖7.32為對調後的結果。除了符號A的左子樹個數要改外，存字母出現總和的變數也得改為44。 圖7.32 處理完最後一個A後的陣列表示符 號ABCDE註 標 i12345COUNT i13
18、121241TREE_CN i184000SYM_TO_POS i23145POS_TO_SYM iCABDE25定理7.1假設字母集中有 n 個字母。且第 i 個位置， ，所 紀錄的 ，滿足 令 ，則 而言，下式成立證明：(反證法)假設對某個 j 而言， ， 則 故和 矛盾。證明完畢。 ni 1iCOUNT1.2 1 nCOUNTCOUNTCOUNTniTiCOUNT1nj 1jTjCOUNT/jTjCOUNT/TnTTTjCOUNTnj/.2/1niTiCOUNT126定理7.2利用本節介紹的方法，算術碼的編碼工作可在 的時間內完成。這裡n代表字母集的大小；m代表待編訊 息的符號數；d代表
19、輸出的位元數。證明：假設我們已編完 個符號，第i個待編的符號為Si， 令 ，則Si的目前機率可表示為 ，這裡 。 令di為編Si所需的位元數，則 。 利用定理7.1，可得到 對編所有的符號而言，所花時間的上限為 )(dmn_iiSPOSTOSYMPOS iiiTPOSCOUNTP/ njiinjCOUNTT11log1logiiiiPOSCOUNTTPdiiPOSdlog)()()(log) 1(log111dmnOmdmdmPOSPOSmiimiimii) 1( i證明完畢。277.7 作業習題一：假設字母集 ，而各字母的機率為、 和 。假設送方打算送出的訊息為，試利用算術碼的技巧予以編碼後再解碼。 習題二： 假若最後一段的二元字串為1111，請問利用什麼方法仍可在 圖7.18上將1111編碼。321,aaaS 21)(1aP41)(2aP41)(3aP112aaa
