馮海文 ，牛連強 ，劉曉明

1.沈陽工業(yè)大學(xué) 軟件學(xué)院，沈陽 110023

2.沈陽工業(yè)大學(xué) 電氣工程學(xué)院，沈陽 110023

高效的一遍掃描式連通區(qū)域標(biāo)記算法

馮海文1，2，牛連強1，劉曉明2

1.沈陽工業(yè)大學(xué) 軟件學(xué)院，沈陽 110023

2.沈陽工業(yè)大學(xué) 電氣工程學(xué)院，沈陽 110023

1 引言

二值圖像連通區(qū)域標(biāo)記是指對圖像中不同連通區(qū)域中的像素設(shè)置唯一的標(biāo)號，是計算機視覺、模式識別和圖像處理等領(lǐng)域中眾多算法的基礎(chǔ)[1-4]。例如，在對醫(yī)學(xué)、遙感、視頻等圖像進行處理時，通過連通域標(biāo)記來確定物體的邊緣，以對感興趣的區(qū)域（目標(biāo)）進行標(biāo)記和提??；在電氣行業(yè)的真空斷路器的開斷特性研究中，其基本方法是通過對圖像連通域的查找來確定電弧圖像中電弧面積和直徑的變化規(guī)律，進而確定電弧的運動機理[5-6]。這些算法通常需要處理大量的圖像，連通域標(biāo)記算法的效率是一個關(guān)鍵問題。

目前，存在著多種連通區(qū)域標(biāo)記算法，從處理的對象上主要可分為基于像素的算法和基于游程（塊）的算法；從對像素的處理次數(shù)上，可分為一遍掃描算法、兩遍掃描算法和多遍掃描算法[7-10]。文獻[11-14]是幾種典型的基于像素的算法，其中，文獻[9]利用并查集技術(shù)減少等價信息傳播的時間消耗，文獻[10]采用遞歸方法處理連通域信息，它們對算法效率的改善不大。文獻[13]提出了一種基于輪廓跟蹤的快速標(biāo)記算法，文獻[14]提出了一種實現(xiàn)快速等價性判別的技術(shù)，文獻[8，15]采用決策樹方法減少對當(dāng)前像素的鄰近像素的掃描個數(shù)。這些技術(shù)使基于像素的算法在效率上得到了一定的改善。如果圖像主要以水平線段（稱為“游程”）組成，采用基于游程的算法可能得到更高的效率[16-20]。文獻[16]采用標(biāo)記矯正來減少圖像的掃描次數(shù)，并對標(biāo)記采用RLE游程編碼來提高合并效，但所使用的鏈表結(jié)構(gòu)復(fù)雜且影響了整體的效率。文獻[17-18]利用附加存儲結(jié)構(gòu)合并一個連通分支內(nèi)的游程以減少參與合并的標(biāo)號，使標(biāo)記效率得到較大提高。文獻[19]直接采用并查集來處理游程的標(biāo)號，因為并查集本身可以在近似線性時間內(nèi)合并兩棵子樹，故標(biāo)記效率比采用動態(tài)結(jié)構(gòu)的算法高，但參與比較的游程數(shù)量沒有減少。文獻[20]的主要工作是利用動態(tài)鏈表和遞歸過程解決等價信息的傳播問題，算法效率提高的效果并不明顯。

在處理具有復(fù)雜內(nèi)容的圖像時，基于像素的算法有其獨到的優(yōu)勢，而盡量減少相鄰像素的連通關(guān)系判別和對圖像掃描的次數(shù)是提高算法效率的主要途徑。Suzuki等[14]利用一維表存儲臨時標(biāo)號，并借助像素的位置關(guān)系快速判別其等價性，有效地減少了掃描圖像的次數(shù)，使算法效率有了很大提高。但該算法在掃描中會產(chǎn)生等價信息損失問題，不僅使掃描圖像次數(shù)增加，且次數(shù)無法事先確定。本文通過一個前置遞推過程，將當(dāng)前像素的鄰域最小標(biāo)號在連通域中直接傳播，即將被更新結(jié)點所在連通分支連接到該結(jié)點，以保證等價信息不損失。同時，用最小標(biāo)號更新遞推查找路徑上結(jié)點的臨時標(biāo)號，以減小分支的深度。從而以很小的代價避免了對圖像的重復(fù)掃描，得到了一種高效的一遍掃描算法。

鑒于在邊緣查找等應(yīng)用中均以8-連通規(guī)則來判定，這里的連通域標(biāo)記也采用了8-連通規(guī)則。此時，一個像素的鄰域由8個像素構(gòu)成，包括水平、垂直和兩個對角方向的相鄰像素。

2 相關(guān)工作分析

這里簡要分析Suzuki標(biāo)記算法的機理。設(shè)二值圖像b(x，y)僅由表示前景（目標(biāo)）像素 FO和背景像素 FB組成。Suzuki算法采用一個一維的標(biāo)號連接表T存儲等價標(biāo)號，并定義圖1所示的兩類模板MS。

圖1 由陰影區(qū)表示的8連通區(qū)域標(biāo)記模板MS

算法先對圖像做2.1節(jié)中的初始正向掃描（從前向后）來標(biāo)記每個前景像素；再利用2.2節(jié)的過程逆向（從后向前）和正向交替掃描圖像，計算并傳播最小標(biāo)號。每掃描一個前景像素時，用最小標(biāo)號修改其值及對應(yīng)MS中像素的等價標(biāo)號，直到圖像的所有前景像素的標(biāo)號不再發(fā)生變化為止。

2.1 初始掃描

初始掃描使用圖1（a）模板的正向掃描，初始標(biāo)號m=1。對每個當(dāng)前像素b(x，y)按下式計算其標(biāo)號g(x，y)。

式中的m=m+1表示在設(shè)置一個新標(biāo)號后m值增1。式（1）中的條件1表明b(x，y)為 FB；條件2表明鄰域中僅b(x，y)為FO時應(yīng)賦予新的標(biāo)號m；條件3指在b(x，y)為FO且Ms中含有FO時，計算其最小標(biāo)號。在更新圖像的同時，按式（3）對應(yīng)地更新表T中的臨時標(biāo)號：

2.2 交替掃描

初始掃描僅解決了局部鄰域的標(biāo)號等價性，需要通過逆向和正向交替掃描才能使等價標(biāo)號在整個圖像中傳播。對于每個當(dāng)前像素b(x，y)，按式（4）計算其標(biāo)號g(x，y)，并由式（5）同時更新表T 。

若在某遍掃描時，所有前景像素的標(biāo)號不變，掃描結(jié)束。

導(dǎo)致Suzuki算法效率較低的主要原因如下：

（1）每處理一個像素時，僅在其鄰域模板MS內(nèi)傳播等價信息，需多次掃描才能使等價標(biāo)號傳播到整個連通區(qū)域，且掃描次數(shù)無法事先確定。

（2）對連接表T的更新可能導(dǎo)致中間的等價信息丟失，即已計算出的結(jié)果失效。例如，在圖2中處理前景像素b(2，6)時，由前面的掃描已經(jīng)確定了標(biāo)號5、4和1的等價性。因其鄰域模板內(nèi)的最小標(biāo)號為2，Suzuki算法直接將表1中的T[5]由4改為2，以便在鄰域內(nèi)傳播最小標(biāo)號，但賦值的結(jié)果使標(biāo)號5與4及1的等價關(guān)系失效。因此，需要增加更多的掃描次數(shù)來重新建立起它們之間的等價關(guān)系。

圖2 一個等價信息丟失的實例

表1 初次掃描圖2后的標(biāo)號連接表

3 改進的一遍掃描算法

3.1 最小標(biāo)號的無損失傳播

為避免Suzuki算法中更新連接表T所帶來的等價信息失效問題，本文提出一種直接在更新當(dāng)前像素標(biāo)號的同時，向已建立的部分連通域中進行最小標(biāo)號傳播的標(biāo)記方法，稱為無損失連通信息傳播。該方法能夠防止已建立的等價關(guān)系丟失，僅對圖像執(zhí)行一遍掃描即可完成連通域的快速標(biāo)記。

事實上，任何一個連通域最終在表T中都表現(xiàn)為一棵樹結(jié)構(gòu)。在對圖像執(zhí)行掃描時，如果出現(xiàn)了一個新的序號為k的前景像素，且該像素連接著兩個序號分別為l和r的前景像素，需要將三者合并為一個連通分支。假定T[l]＜T[r]，如果只是簡單地將T[l]填入T[r]，就會導(dǎo)致原來的T[r]分支被從連通域中分離出去，這是Suzuki算法中使等價關(guān)系失效的根本原因。

避免連通信息損失的方法是增加一個連通分支的合并過程，以使等價信息在覆蓋之前能夠被傳播出去。記根結(jié)點的序號為γ(r)。首先利用遞推關(guān)系計算出T[r]分支上第一個不大于T[l]的結(jié)點，記其序號為α(r)。不存在這樣的結(jié)點時令 α(r)=γ(r)；其次，按式（6）連接相互等價的分支：

上述更新方式使T[r]所在的連通分支的等價性被保持下來。同時，為了減小樹的平均深度，縮短后續(xù)的查找時間，在用T[l]替換T[a(r)]時，將T[r]到T[a(r)]路徑上的所有結(jié)點的臨時標(biāo)號也更新為T[l]。

最后，更新當(dāng)前像素的標(biāo)號為更新后的T[l]。

3.2 算法實現(xiàn)

改進后的算法按如下步驟實現(xiàn)：

（1）設(shè)T為標(biāo)號連接表，標(biāo)號初始值m=1。

（2）正向掃描圖像，由式（1）和（2）計算每個當(dāng)前像素的標(biāo)號g(x，y)，并按式（7）更新表T中的臨時標(biāo)號：

（3）在 g(x-i，y-j)≠FB時，式（6）能夠保證已建立的連通分支仍維持一個連通的樹結(jié)構(gòu)，并使被連接的分支結(jié)點的深度盡可能小，但這些結(jié)點所得到的臨時標(biāo)號可能不是根的標(biāo)號，即整個樹的最小標(biāo)號。因此，在掃描圖像后，需要增加一次對標(biāo)號表T的掃描，目的是將連通域中所有結(jié)點的臨時標(biāo)號更新為根結(jié)點的標(biāo)號：

上述過程中的M為最大的初始分配序號，即表T的長度。

對于圖2中的連通域，表2顯示了本文一次圖像掃描處理后的結(jié)果。

表2 本文算法一遍掃描圖2后的標(biāo)號連接表

圖3為表2所對應(yīng)的樹結(jié)構(gòu)，以及標(biāo)號連接表后最終得到的樹結(jié)構(gòu)。

圖3 圖像掃描和連接表掃描后的標(biāo)號樹

4 算法分析

4.1 時間復(fù)雜性

本文的連通域標(biāo)記算法所采用的運算主要包括加減法、邏輯判定、賦值和自加（減）運算，分別計其每次所消耗的時間為t1、t2、t3和t4。本文算法消耗時間t由對圖像掃描消耗的時間ts和掃描連接表所消耗的時間tn組成，即t=ts+tn。

記W和H分別為圖像的寬度和高度，掃描圖像時間為：

其中，ti為標(biāo)記一個像素所消耗的時間。對應(yīng)式（1）的三種情況，有：

其中，1≤δ≤4，nl表示式（6）的遞推次數(shù)。

掃描連接表T的時間為：

其中，tj為將表T中的每個臨時標(biāo)號更新為最小標(biāo)號所消耗的時間：

其中，nt表示式（6）中查找結(jié)點a(r)所經(jīng)歷的路徑長度。

4.2 實驗結(jié)果

為了比較算法的效率，利用C++語言編制程序，在C++Builder 6.0環(huán)境下運行，系統(tǒng)配置為Windows XP、Intel 2.5 GHz、4.0 GB內(nèi)存的PC機。限于篇幅，主要比較了Suzuki算法[14]、文獻[20]算法和本文算法的實際運行時間。測試圖像尺寸為512×512的二值圖像，其中，圖4（a）、（c）～（e）分別來自于東京大學(xué)和南加利福尼亞大學(xué)（http://sipi.usc.edu/database/、http://www1.cs.columbia. edu/CAVE/software/curet/index.php）開發(fā)的標(biāo)準圖像庫，圖4（b）為利用圖5的固定模式構(gòu)造的人工圖像。各圖像的連通域個數(shù)分別為164、940、1 500、1 875和1 988，運行時間為執(zhí)行500次所得到的平均時間，單位為ms。

圖4 幾種典型的二值圖像

圖5 組成圖4（b）圖像的模式

Suzuki算法和本文算法是基于像素的，而文獻[20]是基于游程的算法。表3和圖6說明，對于一般圖像，本文算法的效率比Suzuki算法提高了約2倍，較文獻[20]算法提高了近50%。對于連通區(qū)域較大、游程較長的圖像，如圖4（a）、4（e），本文算法的效率與文獻[20]算法接近，而在組成圖像的模式很瑣碎時，如圖 4（b）～（d），文獻[20]算法會遠比本文算法耗時，這是因為得到一個游程要計算其兩端像素，判別游程間的連通性也要從兩端比較，在游程很小時，它們比直接對當(dāng)前像素與其鄰域像素之間的比較多耗時幾倍，二者所消耗的時間比甚至達到4∶1以上。圖6直觀地顯示了算法所消耗的時間比。

表3 幾種算法的運行時間 ms

圖6 兩種算法與本算法執(zhí)行時間比

在空間使用上，文獻[20]算法需要依賴動態(tài)存儲結(jié)構(gòu)和遞歸過程的支持，比本文及Suzuki算法消耗更多的輔助內(nèi)存。

5 結(jié)束語

本文提出了一種基于像素的快速連通域標(biāo)記算法。算法的主要特點是在利用局部區(qū)域的最小標(biāo)號更新臨時標(biāo)號之前，借助一個遞推過程來保持原有的等價信息不丟失，并盡可能地減小連通域中分支的深度。由于已得到的等價信息在臨時標(biāo)號更新中沒有損失，使得算法只需對圖像做一次掃描，并輔助一個對連接表的掃描即可完成對連通域的標(biāo)記。實驗表明，算法的效率較改進前有大幅度提高，且因為僅對圖像做一次掃描，更適用于不能對圖像進行暫存的場合。

[1]張云哲，趙海，宋純賀，等.一種新的連通區(qū)域標(biāo)記算法[J].計算機應(yīng)用研究，2010，27（11）：4335-4340.

[2]趙菲，張路，張志勇，等.基于硬件加速的實時二值圖像連通域標(biāo)記算法[J].電子與信息學(xué)報，2011，33（5）：1069-1075.

[3]王靜.二值圖像連通域的分段標(biāo)記算法及實現(xiàn)[J].紅外與激光工程，2010，39（4）：761-765.

[4]張二虎，馮江.Blob分析中基于游程鏈的連通區(qū)域標(biāo)記[J].應(yīng)用科學(xué)學(xué)報，2008，26（5）：536-540.

[5]劉教民，李新福.開關(guān)電弧圖像增強算法研究[J].電工技術(shù)學(xué)報，2005，20（5）：20-23.

[6]董華軍，趙鴻飛，袁瑞磊，等.短間隙真空開關(guān)電弧圖像邊緣提取研究[J].真空科學(xué)與技術(shù)學(xué)報，2012，32（2）：155-157.

[7]Hernandez-Belmonte U H，Ayala-Ramirez V，Sanchez-Yanez R E.A comparative review of two-pass connected component labeling algorithms[J].Advances in Soft Computing，2011，7095（12）：452-462.

[8]Wu K，Otoo E，Suzuki K.Optimizing two-pass connectedcomponent labeling algorithms[J].Pattern Anal Applic，2009，12：117-135.

[9]Dillencourt M B，Samet H，Tamminen M.A general approach to connected-component labeling for arbitrary image representations[J].J ACM，1992，39（2）：253-280.

[10]Hecquard J，Acharya R.Connected component labeling with linear octree[J].Patten Recog，1991，24（6）：515-531.

[11]羅志灶，周贏武，鄭忠楷.基于數(shù)組型并查集的連通域標(biāo)記算法[J].杭州師范大學(xué)學(xué)報：自然科學(xué)版，2011，10（1）：86-91.

[12]徐正光，鮑東來，張利欣.基于遞歸的二值圖像連通域像素標(biāo)記算法[J].計算機工程，2006，32（24）：186-189.

[13]Chang Fu，Chen Chunjen.A component-labeling algorithm using contourtracing technique[C]//Proceedings of the 7th International Conference on Document Analysis and Recognition（ICDAR 2003），2003：741-745.

[14]Suzuki K，Horiba I，Sugie N.Linear-time connectedcomponent labeling based on sequential local operations[J].Computer Vision and Image Understanding，2003，89（1）：1-23.

[15]謝宜壯，譚許彬，陳禾.一種新的連通域標(biāo)記算法[J].北京理工大學(xué)學(xué)報，2012，32（12）：1273-1278.

[16]張修軍，郭霞，金心宇.帶標(biāo)記矯正的二值圖像連通域像素標(biāo)記算法[J].中國圖象圖形學(xué)報，2003，8（2）：198-202.

[17]He Lifeng，Chao Yuyan，Suzuki K.A run-based two-scan labeling algorithm[J].IEEE Transactions on Image Processing，2008，17（5）：749-756.

[18]He Lifeng，Chao Yuyan，Susuki Kenji.Fast connectedcomponent labeling[J].Pattern Recognition，2009，42（9）：1977-1987.

[19]Wang Hongtao，Luo Changzhou，Wang Yu，et al.New algorithm forbinary connected-componentlabeling based on run-length encoding and union-find sets[J].Journal of Beijing Institute of Technology，2009，19（1）：71-75.

[20]劉奇琦，龔曉峰.一種二值圖像連通區(qū)域標(biāo)記的新算法[J].計算機工程與應(yīng)用，2012，48（11）：178-180.

FENG Haiwen1，2,NIU Lianqiang1,LIU Xiaoming2

1.School of Software,Shenyang University of Technology,Shenyang 110023,China
2.School of Electrical Engineering,Shenyang University of Technology,Shenyang 110023,China

How to label connected components of a binary image is a basic problem in image processing field.To improve efficiency,a fast one-scan algorithm to label connected components is presented in this paper on the base of the multiplescans algorithm proposed by Suzuki et al.The algorithm runs a forward scan to the object image only once.The node with the minimum label in the mask of the object pixel is calculated.The node with smaller label is searched in the connected component by an iterative process,and the connected branch including the note to be updated is linked to it.This technique can guarantee no loss to the equivalent information.At the same time,the provisional labels in iterative search path are updated by the minimum label in order to decrease the depth of the branch.The final labels of all nodes are obtained by scanning the connected table.Dynamic data structure and recursive procedure are not needed in this algorithm,and only less memory is required.Experiments and analysis show that the algorithm is about 2 times faster than the original one, and is also faster than some run algorithms proposed recently.

connected component;labeling algorithm;one-scan;label;binary image;label connected table

二值圖像的連通區(qū)域標(biāo)記算法是圖像處理的一個基本問題。為了提高算法的效率，以Suzuki等人提出的多遍掃描算法為基礎(chǔ)，提出了一種快速的一遍掃描連通域標(biāo)記算法。算法通過對圖像做一次正向掃描，先計算出每個當(dāng)前像素所在鄰域內(nèi)的最小標(biāo)號，再利用一個遞推過程，查找該連通域中具有較小標(biāo)號的結(jié)點，將被更新結(jié)點所在連通分支連接到該結(jié)點，以保證等價信息不損失。同時，用最小標(biāo)號更新遞推查找路徑上結(jié)點的臨時標(biāo)號，以減小分支的深度。通過對連接表的更新使每個結(jié)點獲得最終標(biāo)號。算法不需要動態(tài)數(shù)據(jù)結(jié)構(gòu)和遞歸過程的支持，需要的存儲空間較小，算法比原算法速度提高了近2倍，也快于近期提出的一些基于游程的算法。

連通域；標(biāo)記算法；一遍掃描；標(biāo)號；二值圖像；標(biāo)記連接表

A

TP391.41

10.3778/j.issn.1002-8331.1407-0409

FENG Haiwen,NIU Lianqiang,LIU Xiaoming.Efficient one-scan algorithm for labeling connected component. Computer Engineering and Applications,2014,50（23）：31-35.

國家自然科學(xué)基金（No.51377106）。

馮海文（1977—），男，博士生，講師，主要研究方向為圖形圖像算法、計算機仿真；牛連強（1965—），男，教授，主要研究方向為圖形圖像算法、計算機仿真；劉曉明（1968—），女，博士，教授，主要研究方向為現(xiàn)代電器理論設(shè)計、高電壓及絕緣技術(shù)研究。E-mail：fhw19770704@sina.com

2014-07-28

2014-10-21

1002-8331（2014）23-0031-05

◎理論研究、研發(fā)設(shè)計◎