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

1,第七章算術編碼,2,7.1 前言,7.2 算術編碼原理 7.3 二元集式算術碼 7.4 JBIG中的改良式算術碼7.5 動態式算術碼 7.7 作業,7.4.1 BACIC,7.4.2 條件熵式,3,假設一字母集，字母集發生機率、和。,圖7.1 字母的機率區間分佈,舉例說明算術編碼原理,7.2 算術編碼原理,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，一開始，令字母集中各個字母的出現次數為1。,圖7.5起始狀態,P 代表主要集(Primary Set)S 代表次要集(Secondary set)F 代表出現次數,6,假設給一輸入字串如下所示 輸入字串=BAAEEAD,(a)B的機率範圍,(b)修正後的主要集,圖7.6 讀入字母B後的變動,(b)修正後的主要集,(a)新的機率範圍,圖7.7 讀入字母A後的變動,首先，我們讀入字母B，接著讀入第二個字母A,7,第三個讀入的字母仍為A，A仍屬於主要集，我們很容易得出圖7.8的相關機率範圍和主要集。第四個讀入的字母為E，同理得出圖7.9的相關機率範圍和主要集。,(a)新的機率範圍,(b)修正後的主要集,圖7.8 讀入第三個字母後的變動,(b)修正後的主要集,(a)新的機率範圍,圖7.9 處理完第四個字母後的變動,8,在實作時，為避免主要集中字母出現的總和過大，我們暫令總和的上限為10，若總和超過10，則進行重新縮小的動作，這裡，我們是將各字母的出現數除以2後，將商再進行四捨五入。接著，第五個讀入的字母為E，各字母出現的新變動如圖7.10所示。,圖7.10 處理完第五個字母後的變動,由圖7.10可知目前主要集中的字母出現總數已超過10，經除以2再取四捨五入後，得到圖7.11的異動。,圖7.11 重新縮小後的結果,(a)新的機率範圍,(b)修正後的主要集,9,在圖7.11中，我們將字母出現次數為2次以上的留在主要集中，ESC也仍留在主要集中。其餘的字母移到次要集中，我們因此得到圖7.12。,圖7.12 新產生的主要集和次要集,第六個讀入的字母為A。,(a)縮小後的主要集,(b)新產生的次要集,圖7.13 處理完第六個字母後的狀態,(a)機率範圍,(b)主要集,(c)次要集,10,再來模擬一次下個字母D。因為字母D不在主要集內，故先輸出ESC，然後在次要集內將字母D移進主要集中。如此一來，我們得到圖7.14的狀態。,圖7.14 新的主要集和次要集,在處理第七個符號D時，由於在主要集中找不到D，我們輸出ESC，ESC的機率範圍介於 到 之間。又已知D在次要集中的機率範圍介於 到 之間。所以處理完七個符號後的機率範圍介於 到 之間。,11,(a)三列式,BACIC的全名為Block Arithmetic Coding for Image Compression，BACIC主要是針對黑白影像的壓縮而設計的，其效能並不輸JBIG(Joint Bilevel Image Experts Group)。當我們在對目前符號編碼時，會參考到前面處理過的部分符號。,7.4 JBIG中的改良式算術碼7.4.1 BACIC,(b)五列式,圖7.15 二種常用的模組(Template),12,對任一模組而言，共有12個位元被納入考慮。12個位元共有212=4096種組態，例如：000000000000以註標0代表，000000000001以註標1代表，111111111111以註標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+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),14,假設BACIC的碼表樹中葉子個數為K=16，而掃描五個黑色像素的機率序列為 以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所示。,圖7.18 建置完成的編碼樹,假若我們掃描到的二元字串為11110，則在圖7.18中所對應到的路徑為圖中的粗體線所示。利用定長碼來編葉子點。例如，令圖7.18的葉子數量為16個，則每個葉子只需四個位元來編，如此一來，二元字串11110可編碼成0001。,16,結合JBIG1而設計的另一種算術編碼器。如何將高灰階影像轉換成黑白影像：,7.4.2 條件熵式,1.給一 高灰階影像，假設其中所有的灰階值皆為25。2.若我們選用散亂式的抖動矩陣(Disperse Dither Matrix)來當作門檻矩陣。3.則輸入影像經由圖7.20會轉換為圖7.21，經由圖7.22會轉換為 圖7.23。4.在圖7.21，圖7.23中的黑像素代表原輸入影像的灰階值小於抖 動矩陣中同位置的門檻。如此一來，高灰階影像就可轉換為黑白影像了。,17,圖7.20 散亂式的抖動矩陣,圖7.21 所得的黑白影像,圖7.22 叢聚式的抖動矩陣,圖7.23 經圖7.22作用後的結果,18,雖然以上的輸入影像為 的小例子，但從較巨觀的角度來看，若輸入的影像大小為一般的數百乘以數百的大小時，則經上述程序所得的黑白影像之效果還是不錯的。給一F16高灰階影像如圖7.24所示，經圖7.20的散亂式抖動矩陣作用後，我們得圖7.25的黑白影像。,圖7.24 輸入的F16高灰階影像,圖7.25 經圖7.20作用後的結果,19,JBIG1用的是十點式的參考模組。利用散亂式抖動矩陣所得的黑白影像之黑白像素分佈，我們可知黑白像素呈現交錯分佈的樣式。基於這個特性，我們可將參考模組設計如圖7.27所示。,圖7.26 JBIG1的十點式模組,圖7.27 新的參考模組,20,7.5 動態式算術碼,假設字母集 S=A,B,C,D,E且目前字母出現的總次數為40。,圖7.28 目前的隱式二元樹,出現次數最高的字母為C且將其放置在樹根。出現次數次高的字母為B且依廣先搜尋(Breadth First Search)的次序將其放置在C的左孩子處。1到5的註標也是依廣先搜尋放置的。,在這隱式二元樹上，有一些性質值得我們注意：,21,陣列式的資料結構 COUNT i：記錄註標i之下符號為POS_TO_SYM i的出現次數。TREE_CN i：記錄符號為POS_TO_SYM i為樹根的左子樹之 符號總出現次數。SYM_TO_POS i：得到符號SYM的位置。POS_TO_SYM i：得到註標為何符號SYM。,圖7.29 圖7.28 的陣列表示,22,假設接下來讀到的字母串為DAAA 首先讀入字母D，記錄字母出現總數的變數加1得到 T=41(=40+1)。因為字母D的次數加1了，自然也影響了字母B和字母C的TREE_CN 的值，字母B和字母C的 TREE_CN 的值得加1。,圖7.30 處理完字母D後的陣列表示,23,處理完二個A後，A的總數增為12。圖7.31為處理完AA後的陣列表示。因為字母A所在的節點為右子樹且無祖母節點，故不調整TREE_CN。,圖7.31 處理完AA後的陣列表示,24,處理最後一個字母A，處理完A後，A的總數變為13，這會破壞在隱式二元樹進行廣先搜尋所得的數列之遞減性的。這時，我們將字母A和字母B做適當的對調。圖7.32為對調後的結果。除了符號A的左子樹個數要改外，存字母出現總和的變數也得改為44。,圖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編碼。,