多種鏈編碼在數字圖像中的標定算法

摘 要：提出了一種基于邊界標定自動機獲得二值圖像Freeman編碼的高效算法，并介紹了基于自動機獲得二值圖像區域的頂點鏈編碼以及邊界碼的算法。實驗證明，基于自動機獲得各種鏈編碼的算法具有高效率、高精確度等優點。

關鍵詞：自動機； Freeman編碼； 頂點鏈編碼； 邊界碼

中圖法分類號：TP391.41文獻標識碼：A

文章編號：1001—3695(2007)02—0160—03

鏈編碼是一種基于二值圖像區域邊界的二值圖像表示方法，這種方法可以把二維圖像轉換為一維數字序列的問題。對于大尺度的圖像，鏈編碼可以大幅度地節省存儲空間并提高處理速度[2—5]，在圖像處理和模式識別中的很多實際應用都使用了鏈編碼技術。H.Freeman在1961年提出了Freeman鏈編碼，之后人們又提出了多種鏈編碼方案[3—5]。圖像的每一種鏈編碼都有它自己的優點和應用背景，如可以從頂點鏈編碼獲得圖像區域的邊界周長、圖像的面積、自動探測掃描文件的傾斜角度等[6]；利用Freeman鏈碼可以計算圖像的一階矩、二階矩；在Merrill鏈編碼中，可以方便地確定某一點是否在區域之中[4]。

鏈編碼在圖像處理中具有十分廣泛的應用，因而如何找到一種方法能夠方便快速地獲得二值圖像的鏈編碼就顯得十分重要。近年來，不少研究者的文章中都探討了鏈編碼的獲得方法[1]。本文對文獻[1]所提出的記錄圖像區域的Freeman編碼算法與本文提出算法的速度進行了比較，實驗表明，本文所提出的方法具有更高的效率。

1 基于自動機的二值圖像頂點鏈編碼獲得方法[6]

為了保證自動機能沿著區域的邊界始終向前行走，文獻[6]設計了如圖2所示的自動機的狀態遷移映射，由于問題的對稱性質，圖中只畫出了狀態1的狀態遷移映射。自動機周圍像素點是否為圖形占據構成了自動機的輸入。經研究可知，對于狀態1，只有六種不同的輸入，而且也可以確定對于這六種輸入下一時刻自動機和邊界點的相對位置，即可確定自動機的狀態映射。不必檢查所有的鄰近像素，這樣可以進一步提高算法的效率。圖2中以圓圈標記的像素表示需要檢查的像素；箭頭右邊即為下一時刻自動機的內部狀態。

區域標定自動機的任務有兩個：①讓它沿區域的邊界走一遍；②給出邊界的頂點鏈編碼。據此可以設計相應的兩個輸出映射。圖2的每個子圖中，右邊括號內的數字是自動機在x方向和y方向的位移。每個子圖方框內的數字串就是輸出編碼子鏈。我們把圖2中表示狀態遷移關系的圖稱為區域標定自動機的基本圖。

由于矩形點陣中自動機和邊界像素相對位置在空間上的對稱性質，把狀態1的狀態遷移圖順時針旋轉90°即可得到狀態2的狀態遷移映射;依次再順時針旋轉90°和180°又可得到狀態3和狀態4的狀態遷移映射。這里不再畫出狀態2—狀態4的狀態遷移和輸出映射。利用基本圖使自動機沿區域邊界行走一周即可生成圖像區域的頂點鏈編碼。

2 基于自動機的二值圖像Freeman鏈編碼獲得方法

2.1 文獻[1]的二值圖像Freeman碼獲得算法

文獻[1]的二值圖像表示算法通過邊界提取、輪廓跟蹤等一系列步驟組成，現將其算法簡要描述如下：

（1）邊界提取。算法假定圖像的前景色為黑色。通過判斷一個目標點的四近鄰像素是否為黑色。若為黑色則說明該目標點在目標圖像的內部，將該點標注為白色，直至將目標圖像內部的像素點全部標注為白色（這里并不是將內部像素變為白色）；其他情況下像素點顏色不變，則完成了目標圖像邊界的提取。

（2）輪廓跟蹤。從邊界點P0(x0，y0)開始，搜索下一個邊界點P1。下一點按照以下規則進行搜索：首先在P0的四近鄰點中探測邊界點，若存在這樣的點，則選擇優先級最大的點作為P1；若不存在這樣的點，則在P0的四遠鄰點中重復這樣的過程尋找P1。一旦找到了Pk，記錄其Freeman編碼，并將邊界點Pk-1標注為白色，從而將其在Pk+1的搜索中排除。當所有的邊界點被標注為白色后算法終止。

在進行輪廓追蹤時，對于一些包含噪聲的圖像有可能出現這種情況：根據算法檢測的某邊界點在次序上是最后一個點，所以該邊界點的四近鄰點和四遠鄰點都不為黑色，而此時邊界并沒有完全追蹤完。對于這種情況，該算法提出了一種解決方案，即在追蹤邊界點的同時記錄前k個邊界點，若出現上述情況，則反向運行算法，直至找到一個可以連續追蹤邊界的邊界點，然后再次正向運算。這樣做的結果是去除了圖像中一些噪聲的干擾，并避免了噪聲造成的不能追蹤整個邊界的情況。完成了以上兩步后，文獻[1]就完成了對二值圖像的Freeman編碼的表示。然而經過研究發現，如果出現如圖3（a）所示的區域間由單像素連接的情況，那么使用文獻[1]的算法就不能把整個圖像區域的邊界表示出來。將圖3（a）經過邊界提取后獲得如圖3（b）所示的邊界像素，進行輪廓跟蹤產生Freeman編碼步驟時，算法跟蹤A區域邊界到黑圈位置時繼續沿單像素連接邊界跟蹤，跟蹤完連接兩區域的邊界后，繼續沿B區域邊界跟蹤?？梢钥吹?，當算法沿著B區域邊界跟蹤一圈后，由于A，B兩區域間的單像素連接邊界已經被算法標注為白色，算法無法沿連接邊界走回A區域，算法終止，A區域的邊界沒有被完全表示出來。實驗證明，本文所提出的自動機算法能夠解決這個問題。

2.2 基于自動機的二值圖像Freeman鏈編碼獲得方法

圖5是當前位置關系為1時的自動機的狀態遷移圖，圖5的狀態遷移部分表示的是當前光標在此位置時可能出現的三種對自動機走向產生影響的周圍像素值的情況，用灰色標注的像素表示該像素為黑色像素，？表示的是算法中關心的像素，箭頭(←↑→↓)的意義與圖4 相同。圖5獲得的編碼部分表示當自動機處于這種狀態時可以獲得的Freeman編碼。該自動機的主要運行機制是使圖像始終在自動機行走方向的左側。

下面以圖5為例介紹該自動機的工作方式，圖5是當光標點和區域邊界單元格的位置關系為1時的情況。當自動機標定的當前位置處于如圖5（a）中的位置時，自動機下一步判斷該邊界像素右下角的像素是否為黑色，若為黑色，則光標下一步與區域邊界單元格的位置關系變為4，根據八方位Freeman編碼各方位所代表的代碼，獲得鏈編碼為“7”。若其右下角像素為白色，則繼續判斷當前位置的右邊像素是否為黑色，若右邊像素為白色，當前光標轉向，光標與區域邊界單元格的位置關系變為2，獲得鏈編碼為空；若該邊界像素的右邊像素為黑色，則光標下一步與區域邊界單元格的位置關系仍為1，獲得鏈編碼為“0”。

當光標點和區域邊界單元格的位置關系分別為2，3，4時，可以將圖3中的遷移圖逆時針分別旋轉90°，180°，270°，而自動機走向的判斷方式如上所述，獲得的編碼將由于方向的不同而有所不同。

對于文獻[1]中存在的問題，本文的算法在實現時進行以下處理：在自動機標定圖像的黑色區域邊界的同時，將邊界像素的顏色置成不同于黑色（0）和白色（255）的值1，對于同一條邊界進行標定時，本文認為自動機所搜索到的像素值為0和1的像素均為邊界像素；而對于不同的邊界在進行標定時，則認為只有值為0的像素才作為自動機搜索的邊界像素。這樣有效地避免了文獻[1]追蹤邊界時所出現的問題，另一方面，對于同一圖像存在多個對象或一個含孔圖像對象的情況，這樣做避免了重復追蹤同一圖像區域的同一條邊界的情況。

3 基于自動機的二值圖像邊界鏈編碼獲得方法[7]

3.1 邊界鏈編碼

利用邊來標定圖像區域的編碼就是邊界鏈編碼。如圖6所示，采用0，1，2，3四個鏈碼表示右、上、左、下四個方向。從圖像邊界上任意一個像素出發，沿著圖像的邊界像素點按逆時針方向行走，回到起始點結束，記錄邊上的行走方向就構成了一個由方向鏈碼組成的有序鏈，加上起始點坐標，圖像的邊界就可以被唯一地確定下來。圖像的邊界鏈編碼可以表示為{(x₀，y₀)a₀a₁a₂…a_l-1}，其中，(x₀，y₀)為圖像邊界上起始像素點坐標，ai∈{0，1，2，3}是圖像的四方鏈碼，l為鏈的長。

圖6是對一個圖像作離散化后得到的區域，從邊界像素頂點P出發的圖像邊界的邊界鏈碼表示為{(x₀，y₀) 00010101212211232323230302}，(x₀，y₀)為圖像邊界像素頂點P的坐標。

3.2 邊界鏈編碼的獲得

本文僅以八近鄰方式為例對圖像區域進行標定，與四近鄰方式的標定方法類似。我們用箭頭（↑↓← →）表示當前時刻光標的位置，箭頭所指的方向表示行走方向，同時我們規定自動機按逆時針的方向行走。于是自動機的當前位置、行走方向和邊界點之間只有圖7所示的四種位置關系。狀態1—狀態4就是邊界標定自動機的內部狀態集合。對于上面的任何一種位置關系，需要分析當前點周圍五個單元格是否為黑色像素。經研究，我們只需要考慮其中一種位置關系的所有組合即可實現邊界標定。以狀態1為例，只可能出現如圖8所示的六種組合關系，即狀態映射關系。

由于位置關系在空間上的對稱性，把根據第一種位置關系得到的六種狀態映射圖旋轉90°，180°和270°就可以得到第二、三、四種位置關系的狀態映射圖，共有24種狀態映射關系。這樣，當前位置狀態和下一時刻位置狀態構成了一個封閉的集合，為圖像的標定構造了一個有效的映射。因此根據光標周圍單元格的信息，利用狀態圖間的映射即可獲得下一步的位置關系。一直循環直到當前位置與起始點相同為止，這樣就完成了沿區域邊界行走一周的動作要求。把行走的路線以鏈編碼的方式記錄下來，就完成了對區域邊界進行標定的工作。

4 實驗結果

除了實現本文所提出的算法外，本文還實現了文獻[1]所提出的二值圖像的表示算法，并將它們表示二值圖像的時間作了比較，如表1所示。

從表1可以看到，本文所提出的算法對于圖像的表示明顯比文獻[1]所提出的算法要快，這主要是由于文獻[1]所提出的算法在進行圖像表示時首先對圖像進行了邊界提取，降低了算法的效率。

5 結束語

鏈編碼在數字圖像處理中占有十分重要的地位，本文較全面地研究了鏈編碼，并對多種鏈編碼的實現方法作了闡述。在實際應用中，可以選擇對于處理圖像最為有效的編碼方式。事實上，對于這些鏈編碼的相互轉換也是一個眾多研究者研究的課題，邊界鏈編碼、頂點鏈編碼和Freeman鏈編碼可以進行轉換，因此其在數字圖像處理中有著很大的作用。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。