基于Ｍａｘ－ｔｒｅｅ的連通區(qū)域標(biāo)記新算法

(電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院 計(jì)算智能實(shí)驗(yàn)室， 四川 成都 610054）

摘 要：采用灰度圖像創(chuàng)建Max tree的基本思想，提出一種新的二值圖像連通區(qū)域標(biāo)記算法。該算法主要采用8 鄰域搜索及排序隊(duì)列方式實(shí)現(xiàn)，通過一次掃描二值圖像即可完成連通區(qū)域標(biāo)記。提出一種新的8 鄰域搜索策略，可以將鄰域搜索次數(shù)由八次減少到平均四次以下，從而提高了系統(tǒng)效率。此外，還給出一種排序隊(duì)列的快速實(shí)現(xiàn)方法，并將其應(yīng)用到標(biāo)記算法中。而且，該算法的運(yùn)行時(shí)間僅與待標(biāo)記圖像的大小有關(guān)，與連通區(qū)數(shù)目和圖像內(nèi)容無關(guān)。該算法已應(yīng)用于海藻圖像識(shí)別，實(shí)驗(yàn)結(jié)果表明該算法是快速、高效的。

關(guān)鍵詞： Max tree； 連通區(qū)域標(biāo)記； 8 鄰域搜索； 排序隊(duì)列

中圖法分類號(hào)： TP391 文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)： 1001 3695(2006)08 0168 03



Connected Component Labeling Algorithm Based on Max tree



ZHANG De wei， PU Xiao rong， ZHANG Yi

(Computational Intelligence Laboratory，College of Computer Science Engineering， UEST of China， Chengdu Sichuan 610054， China)

Abstract: Based on the theory of Max tree， a new connected component labeling algorithm is proposed in this paper.The proposed algorithm can labelthe connected components by scanning the binary image on time.By improving the traditional algorithm of 8 Neighbor Searching， the average Neighbor Searching times can be reduced from eight to four. An efficient implementation of ordered queue is also introduced in this paper. The experiments on diatom images identification have been done to test the performance of the proposed algorithm， which show that the new algorithm has better performance than the traditio nal ones.

Key words: Max tree; Connected Component Labeling; 8 Neighbor Searching; Ordered Queue



二值圖像指僅包含背景像素和目標(biāo)像素的數(shù)字圖像；二值圖像連通區(qū)域標(biāo)記指將圖像中符合某種連通規(guī)則的目標(biāo)像素點(diǎn)用相同的標(biāo)號(hào)表示出來。通常使用的連通規(guī)則包括4 鄰域連通或8 鄰域連通兩種。其中，后者的應(yīng)用更廣泛。在模式識(shí)別等許多圖像處理應(yīng)用中，灰度圖像經(jīng)過預(yù)處理轉(zhuǎn)變?yōu)槎祱D像以后，常常需要對不同的連通區(qū)域（即目標(biāo)）進(jìn)行標(biāo)記，以便單獨(dú)分析每一個(gè)目標(biāo)的特征[11～13]。此外，二值圖像標(biāo)記算法本身也可以作為圖像預(yù)處理步驟，為后續(xù)處理提供依據(jù)[1]。

到目前為止，先后研究出了許多二值圖像連通區(qū)域標(biāo)記方法。這些方法大致可以分為以下幾類：

(1)兩次掃描法[2]。第一次掃描時(shí)，將臨時(shí)標(biāo)號(hào)存儲(chǔ)在一個(gè)與圖像大小一樣的二維數(shù)組中并形成等價(jià)對。掃描結(jié)束時(shí)，通過某種搜索方法合并等價(jià)標(biāo)號(hào)；第二次掃描時(shí)，用等價(jià)標(biāo)號(hào)中最小的標(biāo)號(hào)值賦予所有等價(jià)標(biāo)號(hào)對應(yīng)的像素點(diǎn)。

(2)雙向反復(fù)掃描法[3]。第一次掃描時(shí)，將每個(gè)目標(biāo)像素點(diǎn)標(biāo)記為一個(gè)唯一的標(biāo)號(hào)。然后，通過正向和反向反復(fù)掃描標(biāo)號(hào)圖像，并在每個(gè)像素的鄰域內(nèi)傳播最小標(biāo)號(hào)，直到?jīng)]有標(biāo)號(hào)變化時(shí)為止。

(3)區(qū)域增長法[4]。依次掃描二值圖像的每一個(gè)像素點(diǎn)。當(dāng)找到某個(gè)未標(biāo)記的目標(biāo)像素點(diǎn)時(shí)，將其壓入堆棧并從該點(diǎn)開始反復(fù)標(biāo)記其鄰域，直到堆棧為空。

(4)此外，還有基于二值圖像特殊表示方法的標(biāo)記算法，如基于跑長碼表示[14]、基于游程表示[15]、基于四叉樹表示[5]等標(biāo)記方法，以及專用于特殊體系結(jié)構(gòu)的計(jì)算機(jī)的并行標(biāo)記算法[6]等。

本文基于Max tree的思想，提出一種快速連通區(qū)域標(biāo)記方法。該方法通過一次掃描二值圖像即可完成連通區(qū)域標(biāo)記，且處理過程中不需要真正創(chuàng)建Max tree，使得算法簡單有效。為了減少鄰域比較次數(shù)，本文還提出一種新的8 鄰域搜索策略，可以將鄰域搜索次數(shù)由八次減少到平均四次以下，大大提高了搜索效率。此外，本文還給出了標(biāo)記方法及搜索策略的一種快速實(shí)現(xiàn)。

1 連通區(qū)域標(biāo)記

1.1 Max tree

由Salembier等人提出的Max tree數(shù)據(jù)結(jié)構(gòu)被認(rèn)為是一種萬能的圖像表示方法，并且已被成功地應(yīng)用到計(jì)算機(jī)視覺等方面的許多經(jīng)典問題中，如圖像濾波和分割、信息獲取等[7，8]。

灰度圖像的Max tree是一棵有根的樹，數(shù)的深度為圖像的灰度等級。對于二值圖像，樹的深度為2，樹的根節(jié)點(diǎn)代表所有的背景像素，子節(jié)點(diǎn)代表待標(biāo)記的目標(biāo)像素。每一個(gè)子節(jié)點(diǎn)對應(yīng)一個(gè)目標(biāo)像素的連通區(qū)域，如圖1所示。因此，如果我們得到二值圖像的Max tree表示，那么通過Max tree即可獲得二值圖像的連通區(qū)域標(biāo)記圖。

1.2 標(biāo)記算法

對于一般的光柵灰度圖像，Salembier等人給出了創(chuàng)建Max tree的一種簡捷有效的遞歸算法[7，8]。如上所述，如果我們將原始二值圖像轉(zhuǎn)換為Max tree表示，則標(biāo)記過程僅僅為對Max tree子節(jié)點(diǎn)賦予不同標(biāo)號(hào)。實(shí)際上，這樣的標(biāo)記過程由于需要轉(zhuǎn)換圖像表示，導(dǎo)致其效率并不高。因此，本文結(jié)合創(chuàng)建Max tree的思想和標(biāo)記算法的要求，提出一種無須真正創(chuàng)建Max tree的連通區(qū)域標(biāo)記算法。本算法不采用遞歸實(shí)現(xiàn)，因此非常簡捷有效。新算法的實(shí)現(xiàn)步驟如下：

while Que is not empty

p←GetQueHeader( )

L(p)←curLabel*ORI(p)

for each q∈N(p) and L(q)=\"Not Analyze\"

InQue(q)

L(q)←“In the Que”

if ORI(p)=0 and ORI(q)=1

curLabel←curLabel+1

goto 1

DeQue( )

假設(shè)二值圖像中待標(biāo)記的像素值為1，背景值為0。為了不破壞原始圖像，算法需要與原始圖像尺寸大小相同的目標(biāo)標(biāo)記圖像，初始化其值為“Not Analyze”。算法還需要輔助的排序隊(duì)列，初始化時(shí)在隊(duì)列中壓入任意一個(gè)像素點(diǎn)（如圖像最左上角的像素點(diǎn)）并令臨時(shí)變量curLabel的值為該像素灰度值。然后，調(diào)用本算法。算法中GetQueHeader()的功能是取隊(duì)首元素， L(p)表示p 點(diǎn)的標(biāo)記，ORI（ p ）表示 p 點(diǎn)的原始像素值，N（ p ）表示 p 點(diǎn)的鄰域像素點(diǎn)集合，InQue（ q ）表示將 q 點(diǎn)入隊(duì)列，DeQue（）表示隊(duì)首元素出隊(duì)列。算法中使用的排序隊(duì)列采用按像素值降序排列規(guī)則，像素值相同的按照先進(jìn)先出規(guī)則處理。

2 優(yōu)化策略

在本算法中，每個(gè)像素點(diǎn)只需進(jìn)入隊(duì)列一次，因而具有較高的運(yùn)行效率。為了進(jìn)一步提高標(biāo)記效率，本文還分別對算法主要依賴的8 鄰域搜索和排序隊(duì)列提出效率優(yōu)化策略。

2.1 8-鄰域搜索策略

8-鄰域搜索是圖像處理中的一種常用鄰域搜索方式，該方式適合于找出像素及其鄰域像素的某種關(guān)系。但是，8 鄰域搜索策略需要就每個(gè)像素點(diǎn)處理其八個(gè)鄰域像素（圖像邊界像素點(diǎn)除外），導(dǎo)致算法中存在大量的比較操作，因此速度很慢。

如果在處理當(dāng)前像素時(shí)，記住其搜索路徑，則對當(dāng)前像素的8-鄰域像素點(diǎn)而言，其中某些像素必定是此前已經(jīng)搜索過的，無須再處理。設(shè)具有公共邊的兩個(gè)像素的相鄰方式稱為邊相鄰，只有公共點(diǎn)的兩個(gè)像素的相鄰方式稱為角相鄰。使用數(shù)字0～7代表從某點(diǎn)訪問其鄰域像素的方向（圖2），每個(gè)像素均有一個(gè)代表其以前搜索路徑的方向值，且算法始終按照圖2所示的方法指定每個(gè)像素點(diǎn)的方向值。不難發(fā)現(xiàn)，方向值為偶數(shù)的點(diǎn)是邊相鄰方式，方向值為奇數(shù)的點(diǎn)是角相鄰方式，如 P0，P2，P4，P6與點(diǎn)P為邊相鄰，而P1，P3，P5，P7與點(diǎn)P 則為角相鄰。

假設(shè) P為初始點(diǎn)，則P的鄰域即P0~P7將被搜索并加入到隊(duì)列，并將每個(gè)點(diǎn)的下標(biāo)值標(biāo)志為其對應(yīng)的方向值。當(dāng)處理像素為P的邊相鄰像素點(diǎn)P6時(shí)，P6的鄰域即P7，P0，P，P4，P5，P54，P55，P61將被搜索，并加入到隊(duì)列。事實(shí)上，此前，P7，P0，P，P4，P5已經(jīng)被搜索過了，因此對于P6的鄰域只需要搜索P54，P55，P61即可。同樣，對于P的角相鄰像素點(diǎn)P5，由于其鄰域像素點(diǎn)P6，P，P4已經(jīng)搜索過了，因此其鄰域只需搜索P51，P52，P53，P54，P55即可。 

由此可以看出，邊相鄰的點(diǎn)在后續(xù)處理中只需搜索其三個(gè)鄰域點(diǎn)，而角相鄰的點(diǎn)在后續(xù)處理中需要搜索其五個(gè)鄰域點(diǎn)。因此，當(dāng)隊(duì)列中某個(gè)待處理的像素點(diǎn)既有角相鄰，又有邊相鄰時(shí)，優(yōu)先選擇邊相鄰方式，這樣可以進(jìn)一步減少鄰域搜索次數(shù)。

2.2 排序隊(duì)列的實(shí)現(xiàn)

Petr Felkel等人提出了兩種基于IFT算法的排序隊(duì)列的快速實(shí)現(xiàn)方法[9]。本文采用類似的方法來提高排序隊(duì)列的訪問效率，即采用兩個(gè)獨(dú)立的隊(duì)列來實(shí)現(xiàn)。其中，一個(gè)隊(duì)列處理背景像素點(diǎn)，另一個(gè)隊(duì)列處理目標(biāo)像素點(diǎn)（圖3），節(jié)點(diǎn)中的 Dir 表示本像素的方向值。本文采用靜態(tài)的排序隊(duì)列來實(shí)現(xiàn)，該方法可以很方便地?cái)U(kuò)展到動(dòng)態(tài)排序隊(duì)列中[9]。

3 實(shí)驗(yàn)結(jié)果

本文將該新算法應(yīng)用到海藻圖像在線檢測與識(shí)別系統(tǒng)中。海藻圖像在線檢測與識(shí)別處理過程復(fù)雜，步驟較多，對時(shí)間性能要求很高[10]。該系統(tǒng)首先對形態(tài)學(xué)梯度處理后的二值圖像進(jìn)行連通區(qū)域標(biāo)記，為形態(tài)學(xué)分水嶺算法提供標(biāo)記圖像，以便檢測出圖像所包含的目標(biāo)海藻，并加以識(shí)別。本文提出的新算法能提高系統(tǒng)處理中相關(guān)部分的處理效率。

本文將該新標(biāo)記算法的運(yùn)行效率與三種傳統(tǒng)標(biāo)記算法的運(yùn)行效率進(jìn)行了比較。新算法的運(yùn)行效率與三種傳統(tǒng)標(biāo)記算法的運(yùn)行效率比較結(jié)果如表1所示。所有算法均運(yùn)行在P4/2.6GHz/256MB DDR的PC計(jì)算機(jī)環(huán)境中。

雙向反復(fù)掃描法由于掃描次數(shù)過多，導(dǎo)致時(shí)間效率不高；區(qū)域增長法不但對目標(biāo)像素需要掃描兩次，目標(biāo)像素點(diǎn)的鄰域比較次數(shù)也較多，而且需要較多的堆棧操作時(shí)間；兩次掃描法對于階梯形的連通區(qū)域由于等價(jià)對太多因而效率很低。本文提出的算法只需要對圖像掃描一次，且每個(gè)像素點(diǎn)只進(jìn)入隊(duì)列一次，這樣，鄰域的比較次數(shù)大大減少，像素點(diǎn)進(jìn)出隊(duì)列的操作時(shí)間也得到了優(yōu)化，因而算法的效率得到很大提高。

4 總結(jié)

本文提出一種新的二值圖像連通區(qū)域標(biāo)記算法和鄰域搜索策略及算法的一種快速實(shí)現(xiàn)。該算法依據(jù)灰度圖像創(chuàng)建Max tree的思想而提出，通過一次掃描待標(biāo)記圖像即可完成連通區(qū)域的標(biāo)記，過程中無須真正創(chuàng)建Max tree。針對該算法提出了優(yōu)化的8-鄰域搜索策略，可以將鄰域搜索次數(shù)由八次減少到平均四次以下。另外，采用改進(jìn)的排序隊(duì)列來實(shí)現(xiàn)該算法，從而提高了系統(tǒng)效率。該算法的運(yùn)行時(shí)間僅與待標(biāo)記圖像的大小有關(guān)，與連通區(qū)數(shù)目和圖像內(nèi)容無關(guān)。

通過適當(dāng)改進(jìn)算法，可以方便地實(shí)現(xiàn)連通區(qū)幾何特征的統(tǒng)計(jì)，如連通區(qū)面積、中心點(diǎn)坐標(biāo)等。

參考文獻(xiàn)：

[1] R A Lotufo， A X Falcao，F(xiàn) Zampirolli. IFT Watershed from Gray Scale Marker[C]. Proceedings of the 15th Brazilian Symposium Computer Graphics and Image Processing， 2002.146-152.

[2] A Rosenfeld， John L Pfaltz.Sequential Operations in Digital Picture Processing[J].Journal of the ACM，1966，13(4):471-494.

[3] Haralick R M， Shapiro L G. Computer and Robot Vision[M].Addison Wesley， 1992.

[4] Glassner A. Fill′ Er Up![J]. IEEE Computer Graphics and Applications， 2001，21(1):78-85. 

[5] Hanan Samet. Connected Component Labeling Using Quadtrees[J]. Journal of the ACM， 1981，28(3):487-501.

[6] P Bhattacharya. Connected Component Labeling for Binary Images on a Reconfigurable Mesh Architectures[J]. Journal of Systems Architecture， 1996，42(4):309－313.

[7] P Salembier， A Oliveras， L Garrido. Anti extensive Connected Ope rators for Image and Sequence Processing[J]. IEEE Transactions on Image Processing，1998，7(4):555-570.

[8] Luis Garrido Ostermann. Hierarchical Region Based Processing of Ima ge and Video Sequences:Application to Filtering，Segmentation and Information Retrieval[D].Barcelona， Spain：Department of Signal Theory and Communications， Universitat Politecnica de Catalunya，2002.

[9] Petr Felkel， et al . Implementation and Complexity of the Water shed from Markers Algorithm Computed as a Minimal Cost Forest[J]. Computer Graphics Forum，2001，20(3)：C26 C35.

[10] A C Jalba， M H F Wilkinson，J B T M Roerdink. Automatic Segmentation of Diatom Images for Classification[J].Microscopy Research and Technique， 2004，65(1 2):72-85.

[11] 李青，等.計(jì)算機(jī)圖形分離算法研究及實(shí)現(xiàn)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16(8):1040-1044.

[12] 牟少敏，等.昆蟲圖像的自動(dòng)計(jì)數(shù)方法的研究[J].儀器儀表學(xué)報(bào)，2003，24(4期增刊):426-429.

[13] 范鋼鋒，李金伴.機(jī)動(dòng)車輛牌照自動(dòng)定位算法研究[J].江蘇大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，23(2):46-49.

[14] 張桂林.基于跑長碼的連通區(qū)域標(biāo)記算法[J].華中理工大學(xué)學(xué)報(bào)，1994，22(5):11-14.

[15] 王鐵生，施鵬飛.二值圖像的快速標(biāo)記方法及其應(yīng)用[J].微型電腦應(yīng)用，2004，20(6):6-8. 

作者簡介：章德偉(1977-)，男，四川中江人，碩士研究生，主要研究方向?yàn)橛?jì)算智能、模式識(shí)別；蒲曉蓉(1969-)，女，四川射洪人，講師，博士研究生，主要研究方向?yàn)橛?jì)算智能、生物特征模式識(shí)別；章毅(1963 )，男，四川邛崍人，教授，博導(dǎo)，主要研究方向?yàn)橛?jì)算智能、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)挖掘。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。