苗龍元，于正林，王震

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

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

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

1 算法原理

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

1.1 bwlabel連通區(qū)域標記步驟

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

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

3）解析等價類。

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

1.2 bwlabel連通區(qū)域標記分類

1.2.1 4鄰域連通區(qū)域標記

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

圖1 4鄰域

1.2.2 8鄰域連通區(qū)域標記

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

圖2 8鄰域

通過兩種算法對圖3（a）進行處理的結(jié)果的對比，可知4鄰域連通區(qū)域標記相比8鄰域連通區(qū)域標記對區(qū)域分割的更為精細。如采用8鄰域連通區(qū)域標記對圖3（b）進行處理，圖中區(qū)域?qū)⒈灰暈橐徽糠郑捎趨^(qū)域沒有封閉的邊界將導致下半部分區(qū)域無法填充，而4鄰域連通區(qū)域標記可以對其下半部分進行單獨填充。因此，本文選用4鄰域連通區(qū)域標記用于區(qū)域劃分。

圖3 連通區(qū)域分析

2 算法的步驟

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

圖4 提出算法處理過程

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

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

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

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

3 實驗結(jié)果對比

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

圖5 算法填充對比

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

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

圖7 算法運行內(nèi)存對比

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

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

4 結(jié)論

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