基于連通區域標記的區域填充算法

苗龍元，于正林，王震

（長春理工大學 機電工程學院，長春 130022）

隨著科技的發展，數字圖像處理在各個領域占有越來越重要的地位。區域填充作為計算機圖形學中的一項重要研究內容，被廣泛運用于數字圖像處理[1-7]和圖形軟件[8，9]中。在數字圖像處理過程中，經常會出現由于圖像采集過程中存在光線干擾、背景選用等問題，導致所要提取的目標圖形在經過二值化等運算后存在缺失。為保證圖像處理的最終效果，降低圖像后續處理的難度，提高圖像的處理效率，就必須對丟失區域進行填充。常見的區域填充算法有種子填充算法和掃描線填充算法等[10]。種子填充算法首先通過確定需要填充區域內部的一個起始點，然后利用4連通或8連通法檢測其相鄰位置的點是否為邊界點，若不是則填充此點并繼續檢測其相鄰點，直至檢測完區域內的所有點完成區域填充。掃描線填充算法首先通過計算掃描線與邊界的交點并對其進行排序，然后按照順序對交點進行配對分類，最后填充奇數對兩點之間掃描線覆蓋的區域的所有像素點。掃描線填充算法雖然處理速度較快，但對填充交點分類較為復雜，面對含有復雜邊界的區域時容易造成填充不完善，影響處理效果。種子填充算法雖然可以填充邊界較為復雜的區域，但存在種子尋找困難、重復判斷和占用較大存儲空間等問題，從而導致效率降低。隨著研究的深入，一些改進算法被相繼提出。余臘生等提出的掃描線種子填充算法的改進[1]，通過修改入棧數據結構使填充速度得到較大提高，但堆棧操作仍然十分頻繁。巨志勇給出一種新的基于鏈碼的填充算法[2]，利用Freeman鏈碼表示邊界，提出一種新的邊界分類準則，并利用邊界上的左右端點對柵欄與交點間的像素取反進行填充，雖然不需要標記邊界點且釋放了大量內存，但對于某些圖形（如圖5b），此算法失效導致填充不完備。譚利等提出的新的連通域標記方法及其在醫學圖像中的應用[3]，雖然將連通域標記運用于區域填充提高了區域填充的速度和效率，但仍需對邊界進行跟蹤和標記造成效率降低。文獻[4-6]提出的算法雖有改進，但依然存在由于邊界限定導致的效率降低。劉海峰等提出的基于區域外接矩形的自動化孔洞填充算法[7]，雖放棄使用固定邊界改以使用矩形的邊界，但使用外接矩形容易導致處理圖像質量下降。

考慮到正確的區域填充結果中各個填充部分必將是被閉合的外邊界所包圍，反之可以推出錯誤填充的部分中的部分像素點必定在圖像的最大行（列）、最小行（列）上。由于連通區域標記可以對不同區域進行標記，并且每個區域產生固定的標號可用于對填充區域的判斷。因此，本文提出將連通區域標記運用到區域填充中，提出基于連通區域標記的區域填充算法。通過連通區域標記對二值圖進行標記，檢測標記矩陣L的最大、最小行（列）上所含有的標號，并對標號相對應的區域進行取反，從而完成最終的填充。

1 算法原理

區域填充的最終目的是填充圖像中閉合區域內的部分。然而由于區域填充的外形輪廓是任意且難以預知的，所以從輪廓的角度出發對區域進行填充必然會造成算法的復雜化，對于算法未涉及到的外形輪廓無法保證填充效果。但是由于區域填充中大部分區域具有一定的連通性，并且所需填充區域的外形輪廓必定是閉合的。所以，可以考慮從區域內部出發簡化算法，提高填充效率同時實現對任意圖形的填充。利用連通區域標記算法對取反后的二值圖中的區域進行劃分，其中在圖片四條邊界上出現的區域必然被認定為填充錯誤的部分。因此，連通區域標記算法將作為本算法的重要一環，綜合考慮本文選用bwlabel[11]連通區域標記算法用于本文對二值圖像進行分區標記。

1.1 bwlabel連通區域標記步驟

1）利用游程編碼對輸入圖像進行標記。

2）掃描連續的團（run），在等價表中對其設定初始標記并記錄等價對。

3）解析等價類。

4）在解析等價類的基礎上對團（run）進行重新標記完成連通區域標記。

1.2 bwlabel連通區域標記分類

1.2.1 4鄰域連通區域標記

如圖1所示，4鄰域是對中心點（C）鄰近的0，1，2，3四個位置進行判斷，如果0，1，2，3位置有點則認為C點與0，1，2，3位置點相連。否則，認為C點為孤立點。利用4鄰域連通區域標記對圖3（a）進行標記，得到圖3（c）共有4個區域。

圖1 4鄰域

1.2.2 8鄰域連通區域標記

如圖2所示，8鄰域在4鄰域的基礎上增加了在中心點對角線上的點作為被檢測對象，相比4鄰域，8鄰域連通范圍有所擴大。因此，導致在處理某些圖形時相比4鄰域會得到的區域個數會有所減少。如圖3（d）所示，利用8鄰域連通區域標記對圖3（a）進行標記得到3個區域。

圖2 8鄰域

通過兩種算法對圖3（a）進行處理的結果的對比，可知4鄰域連通區域標記相比8鄰域連通區域標記對區域分割的更為精細。如采用8鄰域連通區域標記對圖3（b）進行處理，圖中區域將被視為一整部分，由于區域沒有封閉的邊界將導致下半部分區域無法填充，而4鄰域連通區域標記可以對其下半部分進行單獨填充。因此，本文選用4鄰域連通區域標記用于區域劃分。

圖3 連通區域分析

2 算法的步驟

1）對圖4（a）進行二值化處理得到二值圖4（b），并對圖4（b）取反得到圖4（c）。

圖4 提出算法處理過程

2）利用4鄰域區域連通標記算法對圖4（c）中的區域進行標記，得到標記矩陣L、分區個數m和各分區的標記值。

3）設數組A=[ ]1:m，使用for循環遍歷矩陣L的最大行（列）、最小行（列）上的每個元素并對其進行檢測。如果檢測到某個分區的標記值為i且A(i)≠0，則將標記值保存在B（數組）中，同時令A(i)=0且n=n+1（n為檢測到的分區的標記值的個數）。否則，跳過此點繼續檢測。

4）檢測完成后，根據n的值遍歷B中元素，令L中標記值等于B中元素值的區域像素點的值置為0，得到圖4（d）。

5）將圖4（b）與圖4（c）相加得圖4e，完成對區域的填充。

3 實驗結果對比

MATLAB作為當今國際上應用最為廣泛，最為著名的數學工具，具有編程簡單、良好的交互環境和自帶大量圖像處理庫函數等優點，可以為使用者驗證算法節省大量的開發時間。為實現本文提出的算法并與其它算法進行比較，本文選擇采用MATLAB R2014a為實驗平臺實現本文所提出的算法。本文通過對同一圖形分別采用一種新的基于鏈碼的填充算法[3]和本文提出的算法進行實驗對比，處理結果如圖5所示：

圖5 算法填充對比

由圖5（a）和5（b）對比可知，巨志勇等[6]提出的算法雖然具有容易實現、節省存儲空間和處理速度快等特點，但對某些復雜的圖形進行填充時，會出現部分區域無法填充的情況，從而大大限制了其算法在圖像填充中的普遍適用性。而本文提出的算法可以對各種具有任意復雜外形輪廓的區域做到精確填充。利用本文算法處理圖6（a）（像素分辨率為1553*745）得到圖6（b），總耗時為0.0560s僅為文獻[2]提出的算法所用時間的15.70%。且由圖7可知，本文提出算法總分配內存為18208Kb，相比文獻[2]提出的算法節約18%的內存。因此，本文提出的算法擁有填充效率高、精度高適用于超大分辨率圖像的處理等特點。

圖6 提出算法對復雜圖像填充的案例

圖7 算法運行內存對比

由于本文提出的算法具有速度快、可填充任意復雜形狀等優點，因此可通過交互式設計運用于圖形設計（CAD等）軟件中。設計結果如圖8所示。

圖8 交互式復雜圖像填充案例

4 結論

根據區域的連通性和閉合區域填充的邊界性，提出基于連通區域標記的區域填充算法。相比掃描線填充算法在填充復雜區域時會出現漏填或過度填充的情況，本文提出的算法可以做到精準填充。與種子填充算法相比，本文算法釋放了較大的內存，提高了處理速度，減少了重復填充的可能。經試驗證明，本文提出的算法可以對任意復雜的圖形做到精準填充，而且具有容易實現、填充精度高、處理速度快、適用于超大分辨率圖像等特點。