羅志灶，周贏武，鄭忠楷

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

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

羅志灶，周贏武，鄭忠楷

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

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

二值圖像；連通域；像素掃描；標記

0 引 言

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

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

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

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

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

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

1．1 常用二次掃描算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）當遇到孤立新目標點時，添加臨時標號，及新建樹根節(jié)點．

2）當目標像素點與其左鄰域或上鄰域其中之一連通時，將其相鄰鄰域的臨時連通域標號賦予目標像素點的臨時標號．

3）當目標像素點與其左鄰域及上鄰域均連通，且左鄰域和上鄰域的共同連通域一致時，則僅需將其中一個鄰域的臨時連通域標號賦予目標像素點的臨時標號．

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

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

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

2 實驗分析

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

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

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

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

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

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

3 結(jié) 論

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

［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］章毓晉．圖像工程（圖像處理和分析）：上冊［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］徐正光，鮑東來，張利欣．基于遞歸的二值圖像連通域像素標記算法［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］．中國圖象圖形學(xué)報，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］宋斌．一種新的圖像連通域快速標號算法［J］．電子測量技術(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

福建省重點學(xué)科項目（閩教高［2006］48號）．

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