羅志灶，周贏武，鄭忠楷

（閩江學(xué)院物理與電子信息工程系，福建 福州350108）

基于數(shù)組型并查集的連通域標(biāo)記算法

羅志灶，周贏武，鄭忠楷

（閩江學(xué)院物理與電子信息工程系，福建 福州350108）

常用的二次掃描算法存在某些缺陷，即共同連通域的合并主要是通過(guò)重復(fù)遍歷共同連通域標(biāo)號(hào)數(shù)組，修改相應(yīng)的共同連通域標(biāo)號(hào)完成的．重復(fù)遍歷嚴(yán)重影響算法的性能．?dāng)?shù)組型并查集算法利用樹(shù)型數(shù)據(jù)結(jié)構(gòu)特點(diǎn)實(shí)現(xiàn)連通域合并，以取代重復(fù)遍歷．實(shí)驗(yàn)表明數(shù)組型并查集算法更具優(yōu)勢(shì)．

二值圖像；連通域；像素掃描；標(biāo)記

0 引 言

連通域標(biāo)記是是介于圖像預(yù)處理和目標(biāo)識(shí)別之間的重要步驟．連通域標(biāo)記是指將圖像中符合某種連通規(guī)則［1］（4－鄰域連通、8－鄰域連通或m－鄰域）的像素標(biāo)識(shí)為同一目標(biāo)［2］，并用唯一的標(biāo)號(hào)標(biāo)記連通域內(nèi)的像素點(diǎn)［3］．通常圖像的目標(biāo)是由一個(gè)或多個(gè)連通域組成，因此，可根據(jù)連通域的屬性，例如面積、二階矩等，計(jì)算目標(biāo)的特征值，以達(dá)到識(shí)別目標(biāo)的目的．連通域標(biāo)記是對(duì)掃描圖像標(biāo)記目標(biāo)的過(guò)程，其運(yùn)算量相當(dāng)大．優(yōu)化連通域標(biāo)記算法可極大提高數(shù)字圖像處理系統(tǒng)的性能．

影響連通域標(biāo)記算法性能［3－4］的因素主要有：1）圖像掃描的次數(shù)及連通域標(biāo)號(hào)沖突處理的方法；2）內(nèi)存訪問(wèn)的方法等．通常提高連通域標(biāo)記算法性能的方法也是基于這兩方面：減少圖像的掃描次數(shù)，盡可能減少回溯掃描；合理設(shè)計(jì)內(nèi)存訪問(wèn)方式，盡量減少連通域信息訪問(wèn)的時(shí)間．

連通域標(biāo)記算法有多種類型［5］，根據(jù)掃描方式可分為像素掃描法［6］、線段掃描即線標(biāo)記法［7］、基于輪廓的標(biāo)記法［8］．像素點(diǎn)掃描方式有順序掃描法［6］、遞歸標(biāo)記法［9］、區(qū)域增長(zhǎng)法［10］等．線段掃描算法主要是基于游程的標(biāo)記算法［11］等．像素掃描法是最常用的標(biāo)記算法，主要是遍歷圖像的像素點(diǎn)，并根據(jù)4－領(lǐng)域或8－領(lǐng)域規(guī)則，將相互連通的像素點(diǎn)用同一標(biāo)號(hào)標(biāo)記．基于游程的標(biāo)記算法［11］是逐行掃描圖像，并記錄每行連通域的起始位置和終止位置，然后與下一行的游程比較，確定是否屬于同一連通域．該算法占用內(nèi)存少，適用于嵌入式系統(tǒng)．基于輪廓的標(biāo)記算法［8］，是遍歷圖像的輪廓，并將在閉合的輪廓內(nèi)的像素點(diǎn)標(biāo)記為同一目標(biāo)．該算法運(yùn)算時(shí)間與圖像的復(fù)雜度有關(guān)，因此應(yīng)用不多．文獻(xiàn)［5］分析了對(duì)連通域算法的進(jìn)展及類別．

順序掃描法是最常用的算法，其直觀，數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)［6］．順序掃描法有一次掃描法［9］、二次掃描法6和多次掃描法12．二次掃描法的性能及穩(wěn)定性都比較好，是常用的算法．文獻(xiàn)［6］分析了二次掃描法的原理及改進(jìn)的方法．文獻(xiàn)［3］提出等價(jià)標(biāo)號(hào)快速傳遞法，并用決策樹(shù)（decision tree）分析8－鄰域和4－鄰域內(nèi)像素點(diǎn)的遍歷秩序，以減少鄰域內(nèi)的像素點(diǎn)掃描次數(shù)；還提出用并查集（union－find）分析和處理沖突的等價(jià)連通域標(biāo)號(hào)的思路，以提高等價(jià)標(biāo)號(hào)沖突處理的效率．但文［3］中僅分析并查集算法原理，其算法實(shí)現(xiàn)不明晰，并且算法以過(guò)程調(diào)用方式植入連通域標(biāo)記算法，嚴(yán)重影響連通域算法的性能．

在此首先針對(duì)二次掃描算法的缺陷提出改進(jìn)的方法，分析和優(yōu)化數(shù)組型并查集算法，特別對(duì)并查集的平面化算法優(yōu)化，使算法易于實(shí)現(xiàn)，且充分利用數(shù)組直接訪問(wèn)存儲(chǔ)的特點(diǎn)，提高算法的效率．最后，將本文的優(yōu)化算法與文中提出的其它順序掃描法相比較，分析優(yōu)化算法的優(yōu)缺點(diǎn)及適用范圍．該文算法的4－鄰域和8－鄰域?qū)崿F(xiàn)方法類似，將以4－鄰域?yàn)槔M(jìn)行闡述．

1 二次掃描算法優(yōu)化

1．1 常用二次掃描算法

描述算法之前先解釋幾個(gè)變量：BinaryImage（x，y）是二值圖像某像素點(diǎn)（x，y）的灰度級(jí)，0表示背景，1表示目標(biāo)．二維矩陣provisional（x，y）表示某像素點(diǎn)（x，y）的連通域標(biāo)號(hào)，在算法的第一次掃描后，保存的是像素點(diǎn)（x，y）的臨時(shí)連通域標(biāo)號(hào)，二次掃描后，則保存的是目標(biāo)的標(biāo)號(hào)．一維矩陣common（index）表示由臨時(shí)標(biāo)號(hào)index標(biāo)記的子連通域所屬的共同連通域標(biāo)號(hào)．例如，common（provisional（x，y））則表示由像素點(diǎn)（x，y）的臨時(shí)標(biāo)號(hào)provisional（x，y）所指定的共同連通域標(biāo)號(hào)，是最終的、唯一的目標(biāo)標(biāo)號(hào)．二次掃描算法分為2個(gè)掃描階段．

第一階段，對(duì)二值圖像BinaryImage進(jìn)行掃描，按8－鄰域或4－鄰域規(guī)則，用臨時(shí)標(biāo)號(hào)provisional矩陣標(biāo)記所有像素點(diǎn)．此時(shí)，會(huì)有大量的等價(jià)標(biāo)號(hào)存在，即不同的臨時(shí)標(biāo)號(hào)標(biāo)記的連通域?qū)儆谕荒繕?biāo)的子連通域，將此類連通域標(biāo)號(hào)稱為等價(jià)標(biāo)號(hào)．解決等價(jià)標(biāo)號(hào)的方法是：用共同連通域數(shù)組common存儲(chǔ)每個(gè)子連通域所屬的共同連通域標(biāo)號(hào)，共同連通域數(shù)組的下標(biāo)表示子連通域的標(biāo)號(hào)，其值則是目標(biāo)的共同連通域的唯一標(biāo)號(hào)．當(dāng)遇到等價(jià)標(biāo)號(hào)時(shí)，則重復(fù)掃描共同連通域數(shù)組，將等價(jià)標(biāo)號(hào)的共同連通域標(biāo)號(hào)改成一致．

第二階段，掃描臨時(shí)連通域標(biāo)號(hào)矩陣provisional，對(duì)每個(gè)像素點(diǎn)的臨時(shí)連通域標(biāo)號(hào)用最終確定的、唯一的共同連通域標(biāo)號(hào)替換，即實(shí)現(xiàn)連通域的合并．在連通域合并前，按共同連通域標(biāo)號(hào)出現(xiàn)的次序，重新定序，確保目標(biāo)連通域標(biāo)號(hào)有效．合并后，標(biāo)號(hào)矩陣中的像素點(diǎn)連通域標(biāo)號(hào)即是最終所得的目標(biāo)連通域標(biāo)號(hào)．

在第一次掃描時(shí)，若在4－鄰域內(nèi)，若出現(xiàn)某像素點(diǎn)BinaryImage（x，y）＝1即屬于目標(biāo)像素點(diǎn)，且它的上鄰域BinaryImage（x，y－1）＝＝1和左鄰域BinaryImage（x－1，y）＝＝1即均屬于目標(biāo)像素點(diǎn)則；若它的上鄰域共同連通域和左鄰域的共同連通標(biāo)號(hào)不一致，即common（provisional（x－1，y））≠common（provisional（x，y－1））時(shí)，則遍歷整個(gè)common數(shù)組，將按如下處理沖突等價(jià)標(biāo)號(hào)，實(shí)現(xiàn)連通域合并：

二次掃描算法中，若出現(xiàn)不一致的等價(jià)標(biāo)號(hào)，則要遍歷整個(gè)共同連通域common數(shù)組，實(shí)驗(yàn)表明，需花費(fèi)大量運(yùn)行時(shí)間重復(fù)遍歷共同連通域數(shù)組．該文1．2節(jié)將介紹采用數(shù)組型并查集算法解決重復(fù)遍歷共同連通域的問(wèn)題，提高算法的性能．

1．2 數(shù)組型并查集（array of union－find）

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，常用于集合的分割和合并，解決判斷兩個(gè)子集是否同屬一個(gè)集合，和把兩個(gè)不屬同一集合的兩個(gè)子集進(jìn)行合并的問(wèn)題．并查集主要是利用樹(shù)型結(jié)構(gòu)存儲(chǔ)和操作等價(jià)標(biāo)號(hào)，并通過(guò)修改節(jié)點(diǎn)的左或上鄰域?qū)崿F(xiàn)連通域的合并．?dāng)?shù)組型并查集的特點(diǎn)是將其樹(shù)節(jié)點(diǎn)以數(shù)組的形式保存，訪問(wèn)節(jié)點(diǎn)不是通過(guò)指針傳遞，而是通過(guò)檢索數(shù)組．這可極大地縮小節(jié)點(diǎn)的訪問(wèn)時(shí)間．

如圖1所示：樹(shù)根節(jié)點(diǎn)的①⑧分別指向節(jié)點(diǎn)本身，表示是共同連通域；子節(jié)點(diǎn)②③指向根節(jié)點(diǎn)①；節(jié)點(diǎn)④⑤⑥⑦可通過(guò)父節(jié)點(diǎn)索引到根節(jié)點(diǎn)①．若樹(shù)的根節(jié)點(diǎn)保存的是共同連通域的標(biāo)號(hào)，則可在第一次掃描圖像后，遍歷所有的并查樹(shù)，并將臨時(shí)標(biāo)號(hào)改為相應(yīng)節(jié)點(diǎn)所指向的根節(jié)點(diǎn)的標(biāo)號(hào)，實(shí)現(xiàn)連通域的合并．

數(shù)組型并查集同時(shí)擁有并查樹(shù)和順序存儲(chǔ)的優(yōu)點(diǎn)，適用于連通域標(biāo)記算法．在二次掃描算法中，數(shù)組型并查集可用于解決連通域標(biāo)號(hào)的訪問(wèn)和合并．在圖像掃描過(guò)程中，若出現(xiàn)某目標(biāo)像素點(diǎn)的左鄰域和上鄰域所指的共同連通域標(biāo)號(hào)不一致時(shí)，可通過(guò)修改其左鄰域或上鄰域的共同連通域標(biāo)號(hào)，完成共同連通域的合并；而不是如上節(jié)所示的遍歷共同連通域數(shù)組．這樣可節(jié)約大量的算法運(yùn)行時(shí)間．

數(shù)組型并查集中的每個(gè)元素可表示某一子連通域，其下標(biāo)是子連通域的臨時(shí)標(biāo)號(hào)，其值是該子連通域所處的共同連通域標(biāo)號(hào)，如圖2所示．由于掃描過(guò)程中的信息不充分，因此子連通域所指的共同連通域通常不是最終的連通域，僅是根據(jù)未完成掃描的信息所得的連通域，是臨時(shí)的、不確定的．因此在算法掃描過(guò)程中經(jīng)常出現(xiàn)某像素點(diǎn)的左鄰域和上鄰域的共同連通域不一致．

在圖像掃描過(guò)程中，若出現(xiàn)某像素點(diǎn)和左、上鄰域都是目標(biāo)像素點(diǎn)，且左、上鄰域的共同連通域標(biāo)號(hào)不一致時(shí)，可利用數(shù)組型并查集實(shí)現(xiàn)它們的共同連通域合并．合并過(guò)程如下：

1）檢索該像素點(diǎn)的左鄰域和上鄰域在并查集樹(shù)的根節(jié)點(diǎn)．由于從葉節(jié)點(diǎn)到根節(jié)點(diǎn)的層次一般僅為2～3層，因此相對(duì)較快．

2）比較兩子樹(shù)的根節(jié)點(diǎn)的值，修改值較大的子樹(shù)根節(jié)點(diǎn)，使其指向根節(jié)點(diǎn)值較小的子樹(shù)的根．實(shí)驗(yàn)發(fā)現(xiàn)，在圖像的掃描中，使較大根節(jié)點(diǎn)值的子樹(shù)合并到根節(jié)點(diǎn)值較小的子樹(shù)可有效地避免合并過(guò)程中形成網(wǎng)絡(luò)的趨勢(shì)．

當(dāng)掃描某目標(biāo)像素點(diǎn)時(shí)，其左鄰域的連通關(guān)系如圖1a，其上鄰域連通關(guān)系如圖1b所示．兩個(gè)樹(shù)分別表示某像素點(diǎn)的左鄰和上鄰域的連通域的邏輯關(guān)系．若其左鄰域的共同連通域是②、上鄰域的共同連通域是⑧，當(dāng)掃描到該像素點(diǎn)時(shí)，判斷出其左、上鄰共同連通域標(biāo)號(hào)不一致，則對(duì)其進(jìn)行合并．合并結(jié)果如圖3所示，合并僅修改較大根節(jié)點(diǎn)值的子樹(shù)的根節(jié)點(diǎn)值．

圖2表示合并前的某像點(diǎn)的左鄰域和上鄰域的連通關(guān)系，圖4則是合并后的連通域關(guān)系，由圖可知，合并僅是修改根節(jié)點(diǎn)值較大的子樹(shù)的根節(jié)點(diǎn)的值，即將圖中的⑧節(jié)點(diǎn)的值改為指向①．

1．3 數(shù)組型并查集（array of union－find）算法

通常數(shù)組型并查集算法旨在解決某目標(biāo)像素點(diǎn)的左鄰域和上鄰域的共同連通域不一致時(shí)，連通域合并的問(wèn)題．算法的復(fù)雜度體現(xiàn)在連通域的合并．在介紹算法前先假設(shè)一維并查集數(shù)組UF，初始化為0．該數(shù)組大小與臨時(shí)標(biāo)號(hào)的數(shù)量相同．臨時(shí)連通域標(biāo)號(hào)矩陣provisional，大小及維數(shù)與二值圖像相同，用于保存每個(gè)像素點(diǎn)的連通域標(biāo)號(hào)，在算法的第一階段保存臨時(shí)連通域標(biāo)號(hào)，算法第二階段保存像素點(diǎn)的最終目標(biāo)標(biāo)號(hào)．二值圖像矩陣BinaryImage．

算法的第一階段，掃描二值圖像，用provisional保存像素點(diǎn)的連通域臨時(shí)標(biāo)號(hào)，對(duì)可能出現(xiàn)的情況按如下處理：

1）當(dāng)遇到孤立新目標(biāo)點(diǎn)時(shí)，添加臨時(shí)標(biāo)號(hào)，及新建樹(shù)根節(jié)點(diǎn)．

2）當(dāng)目標(biāo)像素點(diǎn)與其左鄰域或上鄰域其中之一連通時(shí)，將其相鄰鄰域的臨時(shí)連通域標(biāo)號(hào)賦予目標(biāo)像素點(diǎn)的臨時(shí)標(biāo)號(hào)．

3）當(dāng)目標(biāo)像素點(diǎn)與其左鄰域及上鄰域均連通，且左鄰域和上鄰域的共同連通域一致時(shí)，則僅需將其中一個(gè)鄰域的臨時(shí)連通域標(biāo)號(hào)賦予目標(biāo)像素點(diǎn)的臨時(shí)標(biāo)號(hào)．

4）當(dāng)目標(biāo)像素點(diǎn)與其左鄰域及上鄰域均連通，且左鄰域和上鄰域的共同連通域不一致時(shí)，則分別索引左鄰域和上鄰域的連通子樹(shù)的根節(jié)點(diǎn)，比較根節(jié)點(diǎn)的值，將較大值的根節(jié)點(diǎn)指向較小值的根節(jié)點(diǎn)．

算法的第一階段主要是完成臨時(shí)連通域標(biāo)記和并查樹(shù)數(shù)組的建立，此時(shí)保存在并查樹(shù)中的根節(jié)點(diǎn)是共同連通域標(biāo)號(hào)，其它節(jié)點(diǎn)是臨時(shí)連通域標(biāo)號(hào)．共同連通域標(biāo)號(hào)是斷續(xù)的，且不是按掃描順序排列的．因此需要第二階段對(duì)其進(jìn)行重新定序．

算法的第二階段，主要是調(diào)整共同連通域標(biāo)號(hào)，使之按掃描順序出現(xiàn)，用共同連通域標(biāo)號(hào)標(biāo)記像素點(diǎn)的連通域標(biāo)號(hào)．首先，遍歷并查集數(shù)組UF，將所有的根節(jié)點(diǎn)（UF（i）＝＝i）按根節(jié)點(diǎn)出現(xiàn)的順序重新編號(hào)，且取為負(fù)數(shù)；同時(shí)對(duì)非根節(jié)點(diǎn)檢索其根節(jié)點(diǎn)，并將根節(jié)點(diǎn)值賦予非根節(jié)點(diǎn)．然后，將所有并查集數(shù)組的標(biāo)號(hào)取為正數(shù)．最后遍歷臨時(shí)連通域矩陣provisional，用臨時(shí)連通域所指的共同連通域標(biāo)號(hào)替換臨時(shí)連通域標(biāo)號(hào)，完成連通域標(biāo)記．標(biāo)記后的目標(biāo)連通域標(biāo)號(hào)是順序的、唯一的，按掃描中出現(xiàn)的次序標(biāo)記目標(biāo)．為后續(xù)處理帶來(lái)極大的方便．

2 實(shí)驗(yàn)分析

選取復(fù)雜度不同的圖像，并將本文算法（基于數(shù)組型并查集連通域標(biāo)記算法）與改進(jìn)前的二次掃描算法［6］、多次掃描算法［12］、改進(jìn)型多次掃描算法［12］、基于游程算法［11］、基于鏈表算法［13］等進(jìn)行比較．

選取不同結(jié)構(gòu)的圖像（512×512），在Matlab環(huán)境下，比較各算法的執(zhí)行時(shí)間．鏈表型算法，采用模擬指針?lè)椒ǎ∕atlab不支持指針）．實(shí)驗(yàn)結(jié)果如表1所示．表1表示每幅圖像（512×512）標(biāo)記所用時(shí)間．多數(shù)情況下，二次掃描算法遠(yuǎn)優(yōu)于其于算法，基于并查集的二次掃描算法是對(duì)二次掃描算法的優(yōu)化，表2數(shù)據(jù)表明，基于并查集的二次掃描算法比二次掃描算法明顯地減少了算法執(zhí)行的時(shí)間．但任何算法均有其局限性，對(duì)于表1中的7．1．02．pgm圖像，當(dāng)目標(biāo)過(guò)多且小時(shí)，基于并查集算法和二次掃描算法的反而不如多次掃描算法及改進(jìn)型多次掃描算法．

算法的穩(wěn)定性計(jì)算按如下方式進(jìn)行：

將512×512圖像按16＊n×16＊n劃分為32幅不同尺寸圖像，以分析不同尺度圖像的各算法的執(zhí)行時(shí)間，并隨機(jī)抽取其中一組數(shù)據(jù)，結(jié)果如圖5、圖6所示．圖5將6種算法進(jìn)行比較，圖6則是將圖5中相對(duì)執(zhí)行時(shí)間較少的4種算法集中進(jìn)行比較．由于Matlab計(jì)時(shí)不夠精確，所以當(dāng)執(zhí)行時(shí)間很少時(shí)，會(huì)有圖像更大時(shí)間反而更少的現(xiàn)象，但這不影響對(duì)算法執(zhí)行時(shí)間的整體分析．圖5、圖6表明：在不同尺度圖像下，基于并查集的二次掃描算法運(yùn)行時(shí)間均少于其它算法，且隨圖像尺度的變化，基于并查集二次掃描算法呈線性變化，算法較穩(wěn)定；與改進(jìn)前的二次掃描算法相比，算法的平均運(yùn)行時(shí)間減少約50%；從算法運(yùn)行時(shí)間的一階矩和二階矩上看，穩(wěn)定性也有相應(yīng)的提高．

表1 不同圖像特性及各算法性能

表2 二次掃描算法和基于并查集算法比較

3 結(jié) 論

利用并查集數(shù)組替代共同連通域數(shù)組，可減少處理等價(jià)標(biāo)號(hào)沖突的時(shí)間．算法直觀，易于代碼實(shí)現(xiàn)．在優(yōu)化二次掃描算法的基礎(chǔ)上，提出基于并查集的二次掃描優(yōu)化算法，利用并查集適用于分類與歸并的特點(diǎn)，并結(jié)合二次掃描算法的優(yōu)點(diǎn)．與改進(jìn)前的二次掃描算法相比，該文提出的基于并查集的二次掃描算法的性能較其它連通域算法有很大的提高．參考文獻(xiàn)：

［1］Gonzalez R C，Woods R E．Digital image processing［M］．2th ed．北京：電子工業(yè)出版社，2006．

［2］Sonka M，Hlavac V，Boyle R．Image processing，analysis and machine［M］．2th ed．北京：人民郵電出版社，2003．

［3］Wu K，Otoo E，Kenji S．Optimizing two－pass connected－component labeling algorithms［J］．Pattern Anal Applic，2009，12（2）：117－135．

［4］Luigi di Stefano，Bulgarelli A．A simple and efficient connected components labeling algorithm［C］／／10th International Conference on Image Analysis and Processing．Venice，Italy：IEEE Computer Society，1999：322－327．

［5］Costantino G，Borghesani D，Cucchiara R．Connected component labeling techniques on modern architectures［J］．Image Analysis and Processing，2009，5716：816－824．

［6］Samet H，Tamminen M．An improved approach to connected component labeling of images［C］／／Proc of CVPR．Washington DC：IEEE Computer Society，1986：312－318．

［7］章毓晉．圖像工程（圖像處理和分析）：上冊(cè)［M］．北京：清華大學(xué)出版社，1999：205－206．

［8］Fu Chang，Chen ChunJen，Lu ChiJen．A component－labeling algorithm using contour tracing technique［J］．Computer Vision and Image Understanding，2003，93：206－220．

［9］徐正光，鮑東來(lái)，張利欣．基于遞歸的二值圖像連通域像素標(biāo)記算法［J］．計(jì)算機(jī)工程，2006，32（24）：186－225．

［10］Reddy B S，Chatterjib N．A FFT－based technique for translation rotation and scale invariant image registration［J］．IEEE Transactions on Image Processing，1996，5（8）：1266－1271．

［11］朱云芳，葉秀清，顧偉康．視頻序列的全景圖拼接技術(shù)［J］．中國(guó)圖象圖形學(xué)報(bào)，2006，11（8）：1150－1155．

［12］Kenji S，Horiba I，Sugie N．Linear－time connected－component labeling based on sequential local operations［J］．Computer Vision and Image Understanding，2003，89（1）：1－23．

［13］宋斌．一種新的圖像連通域快速標(biāo)號(hào)算法［J］．電子測(cè)量技術(shù)，2009，32（9）：67－73．

Abstract：The usual two－scans algorithms has some defects that common connected components are mainly merged via repeating to scan the label array of common connected components，and modifying relevant field of the array．The way seriously affects the performance of the algorithm．The algorithm based on array of union－find，which makes full use of the specialty of tree data structure to merge common connected components，can instead of the repeating scans．The experiments show that the algorithm based on array of union－find has more advantages than the algorithm which repeats to scan the label array of common connected components．

Key words：binary images；connected components；scanning by pixels；labeling

Labeling Connected Components Algorithm Based on Array of Union－Find

LUO Zhi－zao，ZHOU Ying－wu，ZHENG Zhong－kai
（Department of Physics ＆Electronic Information Engineering，Minjiang University，F(xiàn)uzhou 350108，China）

TP391

A

1674－232X（2011）01－0086－06

10．3969／j．issn．1674－232X．2011．01．017

2010－09－08

福建省重點(diǎn)學(xué)科項(xiàng)目（閩教高［2006］48號(hào)）．

羅志灶（1971—），男，福建三明人，講師，碩士，主要從事數(shù)字圖像和嵌入式系統(tǒng)設(shè)計(jì)與開(kāi)發(fā)研究．E－mail：lzz＠m(xù)ju．edu．cn