第七章 算術編碼

7.1 前言 7.2 算術編碼原理 7.3 二元集式算術碼 7.4 JBIG中的改良式算術碼 7.5 動態式算術碼 7.7 作業 7.1 前言 7.2 算術編碼原理 7.3 二元集式算術碼 7.4 JBIG中的改良式算術碼 7.5 動態式算術碼 7.7 作業 7.4.1 BACIC 7.4.2 條件熵式

7.2 算術編碼原理 舉例說明算術編碼原理 假設一字母集 ， 字母集發生機率 、 、 、 和 。 圖7.1 字母的機率區間分佈

若今送方打算送出的訊息為 圖7.2 處理完 的機率範圍 圖7.3 處理完 的機率範圍 圖7.4 處理完　　　 的機率範圍 如果用0.175的二進位表示式來代表 這個訊息。現在，收方看到0.175，很容易知道訊息中的第一字母為 ，因為 0.175屬於區間 [0, 0.5]之中，依此類推， 收方很容易就可以解出原訊息為 。

7.3 二元集式算術碼 舉例說明二元集式算術碼 假設一字母集 S = {A, B, C, D, E, ESC, EOF}， 7.3 二元集式算術碼 舉例說明二元集式算術碼 假設一字母集 S = {A, B, C, D, E, ESC, EOF}， 一開始，令字母集中各個字母的出現次數為1。 P A B C D E ESC F 1 S EOF F 1 圖7.5　 起始狀態 P 代表主要集(Primary Set) S 代表次要集(Secondary set) F 代表出現次數

首先，我們讀入字母B ，接著讀入第二個字母A 假設給一輸入字串如下所示 輸入字串 = BAAEEAD… 首先，我們讀入字母B ，接著讀入第二個字母A (a) B的機率範圍 (a) 新的機率範圍 P A B C D E ESC F 1 2 P A B C D E ESC F 2 1 (b) 修正後的主要集 (b) 修正後的主要集 圖7.6 讀入字母B後的變動 圖7.7 讀入字母A後的變動

第三個讀入的字母仍為A，A仍屬於主要集，我們很容易得出圖7.8的相關機率範圍和主要集。 第四個讀入的字母為E，同理得出圖7.9的相關機率範圍和主要集。 (a) 新的機率範圍 (a) 新的機率範圍 P A B C D E ESC F 3 2 1 P A B C D E ESC F 3 2 1 (b) 修正後的主要集 (b) 修正後的主要集 圖7.8 讀入第三個字母後的變動 圖7.9 處理完第四個字母後的變動

接著，第五個讀入的字母為E，各字母出現的新變動如圖7.10所示。 P A B C D E ESC 在實作時，為避免主要集中字母出現的總和過大，我們暫令總和的上限為10，若總和超過10，則進行重新縮小的動作，這裡，我們是將各字母的出現數除以2後，將商再進行四捨五入。 接著，第五個讀入的字母為E，各字母出現的新變動如圖7.10所示。 P A B C D E ESC F 3 2 1 (a) 新的機率範圍 (b) 修正後的主要集 圖7.10 處理完第五個字母後的變動 由圖7.10可知目前主要集中的字母出現總數已超過10，經除以2再取四捨五入後，得到圖7.11的異動。 P A B C D E ESC F 2 1 圖7.11 重新縮小後的結果

在圖7.11中，我們將字母出現次數為2次以上的留在主要集中，ESC也仍留在主要集中。其餘的字母移到次要集中，我們因此得到圖7.12。 P A F 2 1 S B C D EOF F 1 (a) 縮小後的主要集 (b) 新產生的次要集 圖7.12 新產生的主要集和次要集 第六個讀入的字母為A。 P A E ESC F 3 2 1 S B C D EOF F 1 (a) 機率範圍 (b) 主要集 (c) 次要集 圖7.13 處理完第六個字母後的狀態

再來模擬一次下個字母D。因為字母D不在主要集內，故先輸出ESC，然後在次要集內將字母D移進主要集中。如此一來，我們得到圖7.14的狀態。 P A D E ESC F 3 1 2 S B C EOF F 1 圖7.14 新的主要集和次要集 在處理第七個符號D時，由於在主要集中找不到D，我們輸出ESC，ESC的機率範圍介於 到 之間。又已知D在次要集中的機率範圍介於 到 之間。所以處理完七個符號後的機率範圍介於 到 之間。

7.4 JBIG中的改良式算術碼 7.4.1 BACIC BACIC的全名為Block Arithmetic Coding for Image Compression，BACIC主要是針對黑白影像的壓縮而設計的，其效能並不輸JBIG (Joint Bilevel Image Experts Group)。 當我們在對目前符號編碼時，會參考到前面處理過的部分符號 。 (a) 三列式 (b) 五列式 圖7.15 二種常用的模組(Template)

對任一模組而言，共有12個位元被納入考慮。 12個位元共有212 = 4096種組態，例如：000000000000以註標0代表，000000000001以註標1代表，111111111111以註標4095代表 為方便起見用符號 i， ，用來表示註標 。 為了記錄這4096種組態的黑位元之機率，我們用 ri 記錄每個 i其黑點數。 si 記錄每個 i 總點數。 我們在黑白調色的影像中進行算術編碼時，離目前前後文較遠的相關點數給予較小的加權，例如： ，如此一來就較能反應真實的機率分佈。

起始時，si (0) = 2 ri (0) = 1 這裡 ri是記錄編碼黑點的個數，而括弧內的註標代表時間的變數。 ri (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時，黑像素的機率可估計為 上式中，β取很小的數，在實作時可依實驗調整得之。分母項放二倍的β，而在分子項放一個β是怕高估了p1 (n+1, i) 。 (7.1) (7.2)

假設BACIC的碼表樹中葉子個數為K = 16， 而掃描五個黑色像素的機率序列為 < 0.5, 0.6, 0.7, 0.4, 0.2 > 以K=16為樹根，由0.5機率可知其左子樹的加權為8　　　　 ，而右子樹的加權也為8。圖7.16為處理完機率0.5後的子樹示意圖。 接下來讀入機率0.6，我們可得到圖7.17的編碼樹。 圖7.16 處理完機率0.5後的子樹 圖7.17 處理完機率0.6後的子樹

同理，讀完0.7、0.4和0.2後，其對應的編碼樹圖如7.18所示。 假若我們掃描到的二元字串為11110，則在圖7.18中所對應到的路徑為圖中的粗體線所示。利用定長碼來編葉子點。例如，令圖7.18的葉子數量為16個，則每個葉子只需四個位元來編，如此一來，二元字串11110可編碼成0001。 圖7.18 建置完成的編碼樹

7.4.2 條件熵式 結合JBIG1而設計的另一種算術編碼器。 如何將高灰階影像轉換成黑白影像 ： 7.4.2 條件熵式 結合JBIG1而設計的另一種算術編碼器。 如何將高灰階影像轉換成黑白影像 ： 1. 給一 高灰階影像，假設其中所有的灰階值皆為25。 2. 若我們選用散亂式的抖動矩陣(Disperse Dither Matrix)來當作門檻矩陣。 3. 則輸入影像經由圖7.20會轉換為圖7.21，經由圖7.22會轉換為 圖7.23 。 4. 在圖7.21，圖7.23中的黑像素代表原輸入影像的灰階值小於抖 動矩陣中同位置的門檻。 如此一來，高灰階影像就可轉換為黑白影像了。

圖7.20 散亂式的抖動矩陣 圖7.22 叢聚式的抖動矩陣 圖7.21 所得的黑白影像 圖7.23 經圖7.22作用後的結果 1 17 5 18 6 22 25 9 29 13 26 10 30 14 7 23 3 19 8 24 4 20 31 15 27 11 16 28 12 14 7 8 15 19 26 25 18 6 1 2 9 27 31 24 5 4 3 10 28 29 30 23 13 12 11 16 20 21 22 17 圖7.20 散亂式的抖動矩陣 圖7.22 叢聚式的抖動矩陣 圖7.21 所得的黑白影像 圖7.23 經圖7.22作用後的結果

雖然以上的輸入影像為 的小例子，但從較巨觀的角度來看，若輸入的影像大小為一般的數百乘以數百的大小時，則經上述程序所得的黑白影像之效果還是不錯的。給一F16高灰階影像如圖7.24所示，經圖7.20的散亂式抖動矩陣作用後，我們得圖7.25的黑白影像。 圖7.24 輸入的F16高灰階影像 圖7.25 經圖7.20作用後的結果

利用散亂式抖動矩陣所得的黑白影像之黑白像素分佈，我們可知黑白像素呈現交錯分佈的樣式。基於這個特性，我們可將參考模組設計如圖7.27所示。 JBIG1用的是十點式的參考模組。 利用散亂式抖動矩陣所得的黑白影像之黑白像素分佈，我們可知黑白像素呈現交錯分佈的樣式。基於這個特性，我們可將參考模組設計如圖7.27所示。 圖7.26 JBIG1的十點式模組 圖7.27 新的參考模組

7.5 動態式算術碼 假設字母集 S = {A, B, C, D, E}且目前字母出現的總次數為40。 在這隱式二元樹上，有一些性質值得我們注意： 出現次數最高的字母為C且將其放置在樹根。 出現次數次高的字母為B且依廣先搜尋(Breadth First Search)的次序將其放置在C的左孩子處。 1到5的註標也是依廣先搜尋放置的。 圖7.28 目前的隱式二元樹

COUNT [i]：記錄註標i之下符號為POS_TO_SYM [i]的出現次數。 陣列式的資料結構 COUNT [i]：記錄註標i之下符號為POS_TO_SYM [i]的出現次數。 TREE_CN [i]：記錄符號為POS_TO_SYM [i]為樹根的左子樹之 符號總出現次數。 SYM_TO_POS [i]：得到符號SYM的位置。 POS_TO_SYM [i]：得到註標為何符號SYM。 符 號 A B C D E 註 標 i 1 2 3 4 5 COUNT [i] 13 12 10 TREE_CN [i] 16 SYM_TO_POS [i] POS_TO_SYM [i] 圖7.29 圖7.28 的陣列表示

假設接下來讀到的字母串為DAAA 首先讀入字母D， 記錄字母出現總數的變數加1得到 T = 41( =40 + 1)。因為字母D的次數加1了，自然也影響了字母B和字母C的TREE_CN [ ]的值，字母B和字母C的 TREE_CN [ ]的值得加1。 符 號 A B C D E 註 標 i 1 2 3 4 5 COUNT [i] 13 12 10 TREE_CN [i] 17 SYM_TO_POS [i] POS_TO_SYM [i] 圖7.30 處理完字母D後的陣列表示

處理完二個A後，A的總數增為12。圖7.31為處理完AA後的陣列表示。因為字母A所在的節點為右子樹且無祖母節點，故不調整TREE_CN [ ] 。 符 號 A B C D E 註 標 i 1 2 3 4 5 COUNT [i] 13 12 TREE_CN [i] 17 SYM_TO_POS [i] POS_TO_SYM [i] 圖7.31 處理完AA後的陣列表示

處理最後一個字母A，處理完A後，A的總數變為13，這會破壞在隱式二元樹進行廣先搜尋所得的數列之遞減性的。這時，我們將字母A和字母B做適當的對調。圖7.32為對調後的結果。除了符號A的左子樹個數要改外，存字母出現總和的變數也得改為44。 符 號 A B C D E 註 標 i 1 2 3 4 5 COUNT [i] 13 12 TREE_CN [i] 18 SYM_TO_POS [i] POS_TO_SYM [i] 圖7.32 處理完最後一個A後的陣列表示

定理7.1　假設字母集中有 n 個字母。且第 i 個位置， ，所 紀錄的 ，滿足 　　　 令 　 ，則 而言，下式成立 證明：(反證法)假設對某個 j 而言， ， 則 故和 矛盾。證明完畢。

定理7.2　利用本節介紹的方法，算術碼的編碼工作可在 的時間內完成。這裡n代表字母集的大小；m代表待編訊 息的符號數；d代表輸出的位元數。 證明：假設我們已編完 個符號，第i個待編的符號為Si， 令 ，則Si的目前機率可表示為 ，這裡 。 令di為編Si所需的位元數，則 　　 。 利用定理7.1，可得到 對編所有的符號而言，所花時間的上限為 證明完畢。

7.7 作業 習題一： 假設字母集 ，而各字母的機率為 、 和 。假設送方打算送出的訊息為 ，試利用算術碼的技巧予以編碼後再解碼。 習題二： 　　假設字母集　　　　　 ，而各字母的機率為　　　　、　　　　　　　 和　　　　 。假設送方打算送出的訊息為　　　　　，試利用算術碼的技巧予以編碼後再解碼。 習題二： 假若最後一段的二元字串為1111，請問利用什麼方法仍可在 圖7.18上將1111編碼。