馮海文 ，牛連強 ，劉曉明

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

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

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

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

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

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

1 引言

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

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

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

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

2 相關工作分析

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

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

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

2.1 初始掃描

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

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

2.2 交替掃描

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

若在某遍掃描時，所有前景像素的標號不變，掃描結束。

導致Suzuki算法效率較低的主要原因如下：

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

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

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

表1 初次掃描圖2后的標號連接表

3 改進的一遍掃描算法

3.1 最小標號的無損失傳播

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

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

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

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

最后，更新當前像素的標號為更新后的T[l]。

3.2 算法實現(xiàn)

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

（1）設T為標號連接表，標號初始值m=1。

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

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

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

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

表2 本文算法一遍掃描圖2后的標號連接表

圖3為表2所對應的樹結構，以及標號連接表后最終得到的樹結構。

圖3 圖像掃描和連接表掃描后的標號樹

4 算法分析

4.1 時間復雜性

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

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

其中，ti為標記一個像素所消耗的時間。對應式（1）的三種情況，有：

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

掃描連接表T的時間為：

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

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

4.2 實驗結果

為了比較算法的效率，利用C++語言編制程序，在C++Builder 6.0環(huán)境下運行，系統(tǒng)配置為Windows XP、Intel 2.5 GHz、4.0 GB內存的PC機。限于篇幅，主要比較了Suzuki算法[14]、文獻[20]算法和本文算法的實際運行時間。測試圖像尺寸為512×512的二值圖像，其中，圖4（a）、（c）～（e）分別來自于東京大學和南加利福尼亞大學（http://sipi.usc.edu/database/、http://www1.cs.columbia. edu/CAVE/software/curet/index.php）開發(fā)的標準圖像庫，圖4（b）為利用圖5的固定模式構造的人工圖像。各圖像的連通域個數(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]算法會遠比本文算法耗時，這是因為得到一個游程要計算其兩端像素，判別游程間的連通性也要從兩端比較，在游程很小時，它們比直接對當前像素與其鄰域像素之間的比較多耗時幾倍，二者所消耗的時間比甚至達到4∶1以上。圖6直觀地顯示了算法所消耗的時間比。

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

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

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

5 結束語

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

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

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

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

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

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

[6]董華軍，趙鴻飛，袁瑞磊，等.短間隙真空開關電弧圖像邊緣提取研究[J].真空科學與技術學報，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ù)組型并查集的連通域標記算法[J].杭州師范大學學報：自然科學版，2011，10（1）：86-91.

[12]徐正光，鮑東來，張利欣.基于遞歸的二值圖像連通域像素標記算法[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]謝宜壯，譚許彬，陳禾.一種新的連通域標記算法[J].北京理工大學學報，2012，32（12）：1273-1278.

[16]張修軍，郭霞，金心宇.帶標記矯正的二值圖像連通域像素標記算法[J].中國圖象圖形學報，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ū)域標記的新算法[J].計算機工程與應用，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ū)域標記算法是圖像處理的一個基本問題。為了提高算法的效率，以Suzuki等人提出的多遍掃描算法為基礎，提出了一種快速的一遍掃描連通域標記算法。算法通過對圖像做一次正向掃描，先計算出每個當前像素所在鄰域內的最小標號，再利用一個遞推過程，查找該連通域中具有較小標號的結點，將被更新結點所在連通分支連接到該結點，以保證等價信息不損失。同時，用最小標號更新遞推查找路徑上結點的臨時標號，以減小分支的深度。通過對連接表的更新使每個結點獲得最終標號。算法不需要動態(tài)數(shù)據結構和遞歸過程的支持，需要的存儲空間較小，算法比原算法速度提高了近2倍，也快于近期提出的一些基于游程的算法。

連通域；標記算法；一遍掃描；標號；二值圖像；標記連接表

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.

國家自然科學基金（No.51377106）。

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

2014-07-28

2014-10-21

1002-8331（2014）23-0031-05

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