基于連通區(qū)域標(biāo)記的區(qū)域填充算法

苗龍?jiān)?，于正林，王?/p>

（長(zhǎng)春理工大學(xué) 機(jī)電工程學(xué)院，長(zhǎng)春 130022）

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

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

1 算法原理

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

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

1）利用游程編碼對(duì)輸入圖像進(jìn)行標(biāo)記。

2）掃描連續(xù)的團(tuán)（run），在等價(jià)表中對(duì)其設(shè)定初始標(biāo)記并記錄等價(jià)對(duì)。

3）解析等價(jià)類。

4）在解析等價(jià)類的基礎(chǔ)上對(duì)團(tuán)（run）進(jìn)行重新標(biāo)記完成連通區(qū)域標(biāo)記。

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

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

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

圖1 4鄰域

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

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

圖2 8鄰域

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

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

2 算法的步驟

1）對(duì)圖4（a）進(jìn)行二值化處理得到二值圖4（b），并對(duì)圖4（b）取反得到圖4（c）。

圖4 提出算法處理過程

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

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

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

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

3 實(shí)驗(yàn)結(jié)果對(duì)比

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

圖5 算法填充對(duì)比

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

圖6 提出算法對(duì)復(fù)雜圖像填充的案例

圖7 算法運(yùn)行內(nèi)存對(duì)比

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

圖8 交互式復(fù)雜圖像填充案例

4 結(jié)論

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