蔣偉達(dá)

（河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇 南京 211100）

1 引 言

二值圖像的連通域標(biāo)記處理操作是從白色像素（通常用“0”來表示）和黑色像素（通常用“1”來表示）組成的一幅點陣圖像中將互相鄰接（本文研究的是4鄰域、8鄰域，m鄰域暫不討論）的目標(biāo)“1”值像素標(biāo)識為同一目標(biāo)。該處理過程是圖像處理和分析中一個非常重要的基礎(chǔ)操作，有廣泛的應(yīng)用領(lǐng)域［1］。

傳統(tǒng)的標(biāo)記方法如二次掃描法主要通過2次掃描確定各個不同的連通區(qū)域。第1次掃描逐行逐列掃描像素，通過判斷像素之間的鄰域關(guān)系對屬于同一連通區(qū)域的像素賦予相同的連通標(biāo)志。這樣可能造成同一連通區(qū)域中不同子區(qū)域被賦予不同的值，因此要執(zhí)行第2次掃描消除重復(fù)標(biāo)記，以合并子區(qū)域。這種方法的效率不高，尤其是在重復(fù)性標(biāo)記發(fā)生率高時，效率更低［2］。

眾所周知，走迷宮時若一直沿著左側(cè)邊緣前進(jìn)，則一定可以到達(dá)終點；若不從出口出去，繼續(xù)沿著左側(cè)邊緣前進(jìn)，必將回到起點。這就可以順時針遍歷整個迷宮道路的左沿邊界。受破解迷宮方法啟發(fā)，本文提出了一種基于對象的連通區(qū)域標(biāo)記方法。

2 算法描述

不同于傳統(tǒng)方法，本文算法基于對象，一次掃描即可將所有連通子區(qū)標(biāo)記為同一連通區(qū)域，無需進(jìn)行二次掃描。算法主要實施步驟如下。

（1）首先，從左到右、從上至下進(jìn)行逐行逐列掃描，找到一個未標(biāo)記的連通區(qū)域內(nèi)的一點（該點在連通區(qū)域中實際位置對本算法實現(xiàn)無影響）設(shè)為第1點。探索該像素左側(cè)和上側(cè)像素點是否有標(biāo)記，若有則以此為本連通子區(qū)的標(biāo)記值，若無則自動分配標(biāo)記值。

（2）標(biāo)記該像素，根據(jù)標(biāo)記符數(shù)值按一定順序探索同一連通區(qū)域的下一個像素，并重設(shè)標(biāo)記符。每當(dāng)標(biāo)記符tag值為2時（即向下前進(jìn)時）直接向左依次標(biāo)記連通區(qū)域內(nèi)未標(biāo)記的像素。

（3）循環(huán)步驟（2）直至返回步驟（1）中首先標(biāo)記的第1點，則一個連通區(qū)域（或連通子區(qū)）的標(biāo)記結(jié)束。

（4）繼續(xù)步驟（1），標(biāo)記下一個連通區(qū)域，直至標(biāo)記完整幅圖像。

在步驟（2）中，本文引入了一個標(biāo)記符tag（值在0到3之間，0表示上，1表示右，2表示下，3表示左），這個標(biāo)記符是用來記錄探索像素時前進(jìn)方向的，初始值為1（即向右探索）。

探索順序與標(biāo)記符tag的值有關(guān)，如下。

①tag＝1時，按上、右、下、左的順序探索四鄰域內(nèi)像素。

②tag＝2時，按右、下、左、上的順序探索四鄰域內(nèi)像素。

③tag＝3時，按下、左、上、右的順序探索四鄰域內(nèi)像素。

④tag＝0時，按左、上、右、下的順序探索四鄰域內(nèi)像素。

同時，根據(jù)探索前進(jìn)方向重新為tag賦值，即向上前進(jìn)tag＝0，向右前進(jìn)tag＝1，向下前進(jìn)tag＝2，向左前進(jìn)tag＝3。

3 算法演示及分析

本文以傳統(tǒng)方法標(biāo)記問題最為嚴(yán)重的“U形”、“E形”為例演示并分析此算法推算過程。一般認(rèn)為，這種形狀的對象最易在傳統(tǒng)第1次掃描過程中被判為多個不同的連通區(qū)域。

為了演示本算法標(biāo)記過程，以8×8為例，我們先將每個像素的坐標(biāo)按從左到右，從上到下，從0到63編號。

“U形”、“E形”對象如圖1所示。① 按0～63的順序依次遍歷，直至探索到連通區(qū)的第1點9號像素，標(biāo)記之，此時tag初始值為1。② 按上、右、下、左的探索順序探索到17號像素為連通區(qū)內(nèi)像素，標(biāo)記之，向下前進(jìn)，為tag賦值2。③ 按右、下、左、上順序探索，探索到25號為連通區(qū)內(nèi)像素，標(biāo)記之，向下前進(jìn)，tag賦值為2。④繼續(xù)……標(biāo)記51號，此時tag值為1。⑤ 探索順序為上、右、下、左，繼續(xù)到43號為連通區(qū)內(nèi)像素，標(biāo)記之，向上前進(jìn)，為tag賦值為0……

圖1 一種復(fù)雜度較高的對象

實際具體遍歷順序如圖2所示。

據(jù)陳柏生［2］所述，傳統(tǒng)二次掃描法在最好的情況下時間復(fù)雜度為O（n），而在重復(fù)標(biāo)記較嚴(yán)重的情況下時間復(fù)雜度甚至達(dá)到O（n3）。本算法在針對較復(fù)雜的“U形”、“E形”對象時也只是對連通區(qū)域進(jìn)行了2次遍歷，即使在更為復(fù)雜的情況下，本算法也只會對每一個像素進(jìn)行2次4鄰域探索，其時間復(fù)雜度為O（2n）。

圖2 像素遍歷順序示意圖

4 結(jié) 語

本文主要提供了一種基于對象的連通區(qū)域標(biāo)記算法。因篇幅所限，本文只提供了四連通區(qū)域的標(biāo)記方法。八連通區(qū)域的標(biāo)記需修改步驟（2）中探索順序，且此種算法在標(biāo)記過程中可以利用鏈表等數(shù)據(jù)結(jié)構(gòu)儲存對象邊界所經(jīng)過的像素坐標(biāo)，有助于進(jìn)一步進(jìn)行柵格圖像向矢量對象的轉(zhuǎn)換工作。

［1］ 李歡，楊捷.求解二值圖像連通域的改進(jìn)算法［J］.計算機與現(xiàn)代化，2005，（4）：11－13.

［2］ 陳柏生.一種二值圖像連通區(qū)域標(biāo)記的新方法［J］.計算機工程與應(yīng)用，2006，42（25）：46－47.

［3］ 葛春平.一種二值圖像連通區(qū)域標(biāo)記的簡單快速算法［J］.價值工程，2012（28）：242－243.

［4］ 高紅波，王衛(wèi)星.一種二值圖像連通區(qū)域標(biāo)記的新算法［J］.計算機應(yīng)用，2007（11）：168－169，177.