一種基于對(duì)象的連通區(qū)域標(biāo)記方法

蔣偉達(dá)

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

1 引 言

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

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

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

2 算法描述

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

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

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

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

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

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

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

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

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

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

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

同時(shí)，根據(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)記問(wèn)題最為嚴(yán)重的“U形”、“E形”為例演示并分析此算法推算過(guò)程。一般認(rèn)為，這種形狀的對(duì)象最易在傳統(tǒng)第1次掃描過(guò)程中被判為多個(gè)不同的連通區(qū)域。

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

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

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

實(shí)際具體遍歷順序如圖2所示。

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

圖2 像素遍歷順序示意圖

4 結(jié) 語(yǔ)

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

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

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

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

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