自動(dòng)光學(xué)檢測(cè)影像處理套裝軟體設(shè)計(jì)與實(shí)作課件

第七章

算術(shù)編碼

1第七章

算術(shù)編碼17.1前言7.2算術(shù)編碼原理7.3二元集式算術(shù)碼7.4JBIG中的改良式算術(shù)碼7.5動(dòng)態(tài)式算術(shù)碼7.7作業(yè)7.4.1BACIC7.4.2條件熵式27.1前言7.2算術(shù)編碼原理7.4.1BACI假設(shè)一字母集，字母集發(fā)生機(jī)率、、、和。

圖7.1字母的機(jī)率區(qū)間分佈舉例說(shuō)明算術(shù)編碼原理7.2

算術(shù)編碼原理3假設(shè)一字母集若今送方打算送出的訊息為圖7.2處理完的機(jī)率範(fàn)圍圖7.3處理完的機(jī)率範(fàn)圍圖7.4處理完的機(jī)率範(fàn)圍如果用0.175的二進(jìn)位表示式來(lái)代表這個(gè)訊息?，F(xiàn)在，收方看到0.175，很容易知道訊息中的第一字母為，因?yàn)?.175屬於區(qū)間

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

PABCDEESCF111111舉例說(shuō)明二元集式算術(shù)碼

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

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

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

JBIG中的改良式算術(shù)碼

7.4.1

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

為方便起見(jiàn)用符號(hào)i，，用來(lái)表示註標(biāo)。為了記錄這4096種組態(tài)的黑位元之機(jī)率，我們用

ri記錄每個(gè)i其黑點(diǎn)數(shù)。

si記錄每個(gè)i總點(diǎn)數(shù)。

我們?cè)诤诎渍{(diào)色的影像中進(jìn)行算術(shù)編碼時(shí)，離目前前後文較遠(yuǎn)的相關(guān)點(diǎn)數(shù)給予較小的加權(quán)，例如：，如此一來(lái)就較能反應(yīng)真實(shí)的機(jī)率分佈。12對(duì)任一模組而言，共有12個(gè)位元被納入考慮。為了記錄這4096起始時(shí)，si(0)

=2ri(0)

=1這裡ri是記錄編碼黑點(diǎn)的個(gè)數(shù)，而括弧內(nèi)的註標(biāo)代表時(shí)間的變數(shù)。ri

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

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

pi

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

=1代表目前的像素為黑。針對(duì)模組為i的組態(tài)，時(shí)間參數(shù)為n+1時(shí)，黑像素的機(jī)率可估計(jì)為

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

(7.2)

13起始時(shí)，si(0)=2ri(n+1)和si(n假設(shè)BACIC的碼表樹(shù)中葉子個(gè)數(shù)為K=16，

而掃描五個(gè)黑色像素的機(jī)率序列為<0.5,0.6,0.7,0.4,0.2>以K=16為樹(shù)根，由0.5機(jī)率可知其左子樹(shù)的加權(quán)為8，而右子樹(shù)的加權(quán)也為8。圖7.16為處理完機(jī)率0.5後的子樹(shù)示意圖。接下來(lái)讀入機(jī)率0.6，我們可得到圖7.17的編碼樹(shù)。圖7.16處理完機(jī)率0.5後的子樹(shù)圖7.17處理完機(jī)率0.6後的子樹(shù)14假設(shè)BACIC的碼表樹(shù)中葉子個(gè)數(shù)為K=16，圖7.16同理，讀完0.7、0.4和0.2後，其對(duì)應(yīng)的編碼樹(shù)圖如7.18所示。

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

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

的小例子，但從較巨觀的角度來(lái)看，若輸入的影像大小為一般的數(shù)百乘以數(shù)百的大小時(shí)，則經(jīng)上述程序所得的黑白影像之效果還是不錯(cuò)的。給一F16高灰階影像如圖7.24所示，經(jīng)圖7.20的散亂式抖動(dòng)矩陣作用後，我們得圖7.25的黑白影像。圖7.24輸入的F16高灰階影像圖7.25經(jīng)圖7.20作用後的結(jié)果18雖然以上的輸入影像為的小例子，但從較巨觀的角JBIG1用的是十點(diǎn)式的參考模組。利用散亂式抖動(dòng)矩陣所得的黑白影像之黑白像素分佈，我們可知黑白像素呈現(xiàn)交錯(cuò)分佈的樣式?；哆@個(gè)特性，我們可將參考模組設(shè)計(jì)如圖7.27所示。圖7.26JBIG1的十點(diǎn)式模組圖7.27新的參考模組19JBIG1用的是十點(diǎn)式的參考模組。圖7.26圖7.277.5動(dòng)態(tài)式算術(shù)碼假設(shè)字母集S={A,B,C,D,E}且目前字母出現(xiàn)的總次數(shù)為40。圖7.28目前的隱式二元樹(shù)出現(xiàn)次數(shù)最高的字母為C且將其放置在樹(shù)根。出現(xiàn)次數(shù)次高的字母為B且依廣先搜尋(BreadthFirstSearch)的次序?qū)⑵浞胖迷贑的左孩子處。1到5的註標(biāo)也是依廣先搜尋放置的。

在這隱式二元樹(shù)上，有一些性質(zhì)值得我們注意：207.5動(dòng)態(tài)式算術(shù)碼假設(shè)字母集S={A,B,C,陣列式的資料結(jié)構(gòu)COUNT[i]：記錄註標(biāo)i之下符號(hào)為POS_TO_SYM[i]的出現(xiàn)次數(shù)。

TREE_CN[i]：記錄符號(hào)為POS_TO_SYM[i]為樹(shù)根的左子樹(shù)之符號(hào)總出現(xiàn)次數(shù)。

SYM_TO_POS[i]：得到符號(hào)SYM的位置。

POS_TO_SYM[i]：得到註標(biāo)為何符號(hào)SYM。

符號(hào)ABCDE註標(biāo)i12345COUNT[i]13121031TREE_CN[i]163000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE圖7.29圖7.28的陣列表示21陣列式的資料結(jié)構(gòu)符號(hào)ABCDE註標(biāo)i12345假設(shè)接下來(lái)讀到的字母串為DAAA首先讀入字母D，記錄字母出現(xiàn)總數(shù)的變數(shù)加1得到T=41(=40+1)。因?yàn)樽帜窪的次數(shù)加1了，自然也影響了字母B和字母C的TREE_CN[]的值，字母B和字母C的TREE_CN[]的值得加1。圖7.30處理完字母D後的陣列表示符號(hào)ABCDE註標(biāo)i12345COUNT[i]13121041TREE_CN[i]174000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE22假設(shè)接下來(lái)讀到的字母串為DAAA圖7.30處理完字母D處理完二個(gè)A後，A的總數(shù)增為12。圖7.31為處理完AA後的陣列表示。因?yàn)樽帜窤所在的節(jié)點(diǎn)為右子樹(shù)且無(wú)祖母節(jié)點(diǎn)，故不調(diào)整TREE_CN[]。圖7.31處理完AA後的陣列表示符號(hào)ABCDE註標(biāo)i12345COUNT[i]13121241TREE_CN[i]174000SYM_TO_POS[i]32145POS_TO_SYM[i]CBADE23處理完二個(gè)A後，A的總數(shù)增為12。圖7.31為處理完AA後的處理最後一個(gè)字母A，處理完A後，A的總數(shù)變?yōu)?3，這會(huì)破壞在隱式二元樹(shù)進(jìn)行廣先搜尋所得的數(shù)列之遞減性的。這時(shí)，我們將字母A和字母B做適當(dāng)?shù)膶?duì)調(diào)。圖7.32為對(duì)調(diào)後的結(jié)果。除了符號(hào)A的左子樹(shù)個(gè)數(shù)要改外，存字母出現(xiàn)總和的變數(shù)也得改為44。圖7.32處理完最後一個(gè)A後的陣列表示符號(hào)ABCDE註標(biāo)i12345COUNT[i]13121241TREE_CN[i]184000SYM_TO_POS[i]23145POS_TO_SYM[i]CABDE24處理最後一個(gè)字母A，處理完A後，A的總數(shù)變?yōu)?3，這會(huì)破壞在定理7.1假設(shè)字母集中有n

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

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