第七章 算術編碼.

Presentation on theme: "第七章 算術編碼."— Presentation transcript:

1 第七章 算術編碼

2 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 作業 BACIC 條件熵式

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

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

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 代表出現次數

6 首先，我們讀入字母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後的變動

7 第三個讀入的字母仍為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 處理完第四個字母後的變動

8 接著，第五個讀入的字母為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 重新縮小後的結果

9 在圖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 處理完第六個字母後的狀態

10 再來模擬一次下個字母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在次要集中的機率範圍介於 到 之間。所以處理完七個符號後的機率範圍介於 到 之間。

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

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

13 起始時，si (0) = 2 ri (0) = 1 這裡 ri是記錄編碼黑點的個數，而括弧內的註標代表時間的變數。 ri (n+1) 和 si (n+1) 定義如下 ri (n+1) = pi ri (n) si (n+1) = si (n) 上式中，ri (n) 代表在編碼目前像素前，曾編過的黑像素且其模 組為 i 的總個數，而pi代表目前待編的像素。 pi = 0代表目前的像素為白；pi = 1代表目前的像素為黑。 針對模組為i 的組態，時間參數為n+1時，黑像素的機率可估計為 上式中，β取很小的數，在實作時可依實驗調整得之。分母項放二倍的β，而在分子項放一個β是怕高估了p1 (n+1, i) 。 (7.1) (7.2)

14 假設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後的子樹

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

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

17 圖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作用後的結果

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

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

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

21 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 的陣列表示

22 假設接下來讀到的字母串為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後的陣列表示

23 處理完二個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後的陣列表示

24 處理最後一個字母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後的陣列表示

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

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

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