自动光学检测影像处理套装软体设计与实作课件

第七章

算術編碼

1第七章

算術編碼17.1前言7.2算術編碼原理7.3二元集式算術碼7.4JBIG中的改良式算術碼7.5動態式算術碼7.7作業7.4.1BACIC7.4.2條件熵式27.1前言7.2算術編碼原理7.4.1BACI假設一字母集，字母集發生機率、、、和。

圖7.1字母的機率區間分佈舉例說明算術編碼原理7.2

算術編碼原理3假設一字母集若今送方打算送出的訊息為圖7.2處理完的機率範圍圖7.3處理完的機率範圍圖7.4處理完的機率範圍如果用0.175的二進位表示式來代表這個訊息。現在，收方看到0.175，很容易知道訊息中的第一字母為，因為0.175屬於區間

[0,0.5]之中，依此類推，收方很容易就可以解出原訊息為。4若今送方打算送出的訊息為圖7.2處理完的機率範7.3二元集式算術碼

PABCDEESCF111111舉例說明二元集式算術碼

假設一字母集S={A,B,C,D,E,ESC,EOF}，一開始，令字母集中各個字母的出現次數為1。SEOFF1圖7.5起始狀態P代表主要集(PrimarySet)S代表次要集(Secondaryset)F代表出現次數57.3二元集式算術碼PABCDEESCF111111舉假設給一輸入字串如下所示輸入字串

=BAAEEAD…(a)B的機率範圍PABCDEESCF121111(b)修正後的主要集圖7.6讀入字母B後的變動PABCDEESCF221111(b)修正後的主要集(a)新的機率範圍圖7.7讀入字母A後的變動首先，我們讀入字母B

，接著讀入第二個字母A6假設給一輸入字串如下所示(a)B的機率範圍PABCDEE第三個讀入的字母仍為A，A仍屬於主要集，我們很容易得出圖7.8的相關機率範圍和主要集。第四個讀入的字母為E，同理得出圖7.9的相關機率範圍和主要集。(a)新的機率範圍(b)修正後的主要集圖7.8讀入第三個字母後的變動(b)修正後的主要集(a)新的機率範圍圖7.9處理完第四個字母後的變動PABCDEESCF321111PABCDEESCF3211217第三個讀入的字母仍為A，A仍屬於主要集，我們很容易得出圖7.在實作時，為避免主要集中字母出現的總和過大，我們暫令總和的上限為10，若總和超過10，則進行重新縮小的動作，這裡，我們是將各字母的出現數除以2後，將商再進行四捨五入。接著，第五個讀入的字母為E，各字母出現的新變動如圖7.10所示。圖7.10處理完第五個字母後的變動PABCDEESCF321131由圖7.10可知目前主要集中的字母出現總數已超過10，經除以2再取四捨五入後，得到圖7.11的異動。PABCDEESCF211121圖7.11重新縮小後的結果(a)新的機率範圍(b)修正後的主要集8在實作時，為避免主要集中字母出現的總和過大，我們暫令總和的上在圖7.11中，我們將字母出現次數為2次以上的留在主要集中，ESC也仍留在主要集中。其餘的字母移到次要集中，我們因此得到圖7.12。圖7.12新產生的主要集和次要集第六個讀入的字母為A。PAEESCF221SBCDEOFF1111(a)縮小後的主要集(b)新產生的次要集圖7.13處理完第六個字母後的狀態(a)機率範圍(b)主要集(c)次要集PAEESCF321SBCDEOFF11119在圖7.11中，我們將字母出現次數為2次以上的留在主要集中，再來模擬一次下個字母D。因為字母D不在主要集內，故先輸出ESC，然後在次要集內將字母D移進主要集中。如此一來，我們得到圖7.14的狀態。圖7.14新的主要集和次要集在處理第七個符號D時，由於在主要集中找不到D，我們輸出ESC，ESC的機率範圍介於到之間。又已知D在次要集中的機率範圍介於到之間。所以處理完七個符號後的機率範圍介於到之間。PADEESCF3121SBCEOFF11110再來模擬一次下個字母D。因為字母D不在主要集內，故先輸出ES(a)三列式BACIC的全名為BlockArithmeticCodingforImageCompression，BACIC主要是針對黑白影像的壓縮而設計的，其效能並不輸JBIG(JointBilevelImageExpertsGroup)。當我們在對目前符號編碼時，會參考到前面處理過的部分符號。7.4

JBIG中的改良式算術碼

7.4.1

BACIC(b)五列式圖7.15二種常用的模組(Template)11(a)三列式BACIC的全名為BlockArithme對任一模組而言，共有12個位元被納入考慮。12個位元共有212=4096種組態，例如：000000000000以註標0代表，000000000001以註標1代表，111111111111以註標4095代表

為方便起見用符號i，，用來表示註標。為了記錄這4096種組態的黑位元之機率，我們用

ri記錄每個i其黑點數。

si記錄每個i總點數。

我們在黑白調色的影像中進行算術編碼時，離目前前後文較遠的相關點數給予較小的加權，例如：，如此一來就較能反應真實的機率分佈。12對任一模組而言，共有12個位元被納入考慮。為了記錄這4096起始時，si(0)

=2ri(0)

=1這裡ri是記錄編碼黑點的個數，而括弧內的註標代表時間的變數。ri

(n+1)和si(n+1)定義如下ri(n+1)=pi+0.95ri(n)si(n+1)=1

+0.95si(n)上式中，ri(n)代表在編碼目前像素前，曾編過的黑像素且其模組為i的總個數，而pi代表目前待編的像素。

pi

=0代表目前的像素為白；pi

=1代表目前的像素為黑。針對模組為i的組態，時間參數為n+1時，黑像素的機率可估計為

上式中，β取很小的數，在實作時可依實驗調整得之。分母項放二倍的β，而在分子項放一個β是怕高估了p1(n+1,i)。(7.1)

(7.2)

13起始時，si(0)=2ri(n+1)和si(n假設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後的子樹14假設BACIC的碼表樹中葉子個數為K=16，圖7.16同理，讀完0.7、0.4和0.2後，其對應的編碼樹圖如7.18所示。

圖7.18建置完成的編碼樹假若我們掃描到的二元字串為11110，則在圖7.18中所對應到的路徑為圖中的粗體線所示。利用定長碼來編葉子點。例如，令圖7.18的葉子數量為16個，則每個葉子只需四個位元來編，如此一來，二元字串11110可編碼成0001。15同理，讀完0.7、0.4和0.2後，其對應的編碼樹圖如7.1結合JBIG1而設計的另一種算術編碼器。如何將高灰階影像轉換成黑白影像：7.4.2條件熵式1.給一高灰階影像，假設其中所有的灰階值皆為25。2.若我們選用散亂式的抖動矩陣(DisperseDitherMatrix)來當作門檻矩陣。3.則輸入影像經由圖7.20會轉換為圖7.21，經由圖7.22會轉換為圖7.23。

4.在圖7.21，圖7.23中的黑像素代表原輸入影像的灰階值小於抖動矩陣中同位置的門檻。如此一來，高灰階影像就可轉換為黑白影像了。16結合JBIG1而設計的另一種算術編碼器。7.4.2條件熵圖7.20散亂式的抖動矩陣圖7.21所得的黑白影像圖7.22叢聚式的抖動矩陣圖7.23經圖7.22作用後的結果117521218622259291326103014723319824420311527113116281221862211752126103014259291382442072331931162812311527111478151926251861292731312454310282930231312111620212217192625181478152731312461292829302354310202122171312111617圖7.20散亂式的抖動矩陣圖7.21所得的黑白影像圖雖然以上的輸入影像為

的小例子，但從較巨觀的角度來看，若輸入的影像大小為一般的數百乘以數百的大小時，則經上述程序所得的黑白影像之效果還是不錯的。給一F16高灰階影像如圖7.24所示，經圖7.20的散亂式抖動矩陣作用後，我們得圖7.25的黑白影像。圖7.24輸入的F16高灰階影像圖7.25經圖7.20作用後的結果18雖然以上的輸入影像為的小例子，但從較巨觀的角JBIG1用的是十點式的參考模組。利用散亂式抖動矩陣所得的黑白影像之黑白像素分佈，我們可知黑白像素呈現交錯分佈的樣式。基於這個特性，我們可將參考模組設計如圖7.27所示。圖7.26JBIG1的十點式模組圖7.27新的參考模組19JBIG1用的是十點式的參考模組。圖7.26圖7.277.5動態式算術碼假設字母集S={A,B,C,D,E}且目前字母出現的總次數為40。圖7.28目前的隱式二元樹出現次數最高的字母為C且將其放置在樹根。出現次數次高的字母為B且依廣先搜尋(BreadthFirstSearch)的次序將其放置在C的左孩子處。1到5的註標也是依廣先搜尋放置的。

在這隱式二元樹上，有一些性質值得我們注意：207.5動態式算術碼假設字母集S={A,B,C,陣列式的資料結構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[i]13121031TREE_CN[i]163000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE圖7.29圖7.28的陣列表示21陣列式的資料結構符號ABCDE註標i12345假設接下來讀到的字母串為DAAA首先讀入字母D，記錄字母出現總數的變數加1得到T=41(=40+1)。因為字母D的次數加1了，自然也影響了字母B和字母C的TREE_CN[]的值，字母B和字母C的TREE_CN[]的值得加1。圖7.30處理完字母D後的陣列表示符號ABCDE註標i12345COUNT[i]13121041TREE_CN[i]174000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE22假設接下來讀到的字母串為DAAA圖7.30處理完字母D處理完二個A後，A的總數增為12。圖7.31為處理完AA後的陣列表示。因為字母A所在的節點為右子樹且無祖母節點，故不調整TREE_CN[]。圖7.31處理完AA後的陣列表示符號ABCDE註標i12345COUNT[i]13121241TREE_CN[i]174000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE23處理完二個A後，A的總數增為12。圖7.31為處理完AA後的處理最後一個字母A，處理完A後，A的總數變為13，這會破壞在隱式二元樹進行廣先搜尋所得的數列之遞減性的。這時，我們將字母A和字母B做適當的對調。圖7.32為對調後的結果。除了符號A的左子樹個數要改外，存字母出現總和的變數也得改為44。圖7.32處理完最後一個A後的陣列表示符號ABCDE註標i12345COUNT[i]13121241TREE_CN[i]184000SYM_TO_POS[i]23145POS_TO_SYM[i]CABDE24處理最後一個字母A，處理完A後，A的總數變為13，這會破壞在定理7.1假設字母集中有n

個字母。且第i個位置，，所紀錄的，滿足令，則而言，下式成立證明：(反證法)假設對某個j而言，，則

故和矛盾。證明完畢。25定理7.1假設字母集中有n個字母。且第i個位置，定理7.2利用本節介紹的方法，算術碼的編碼工