高效的一遍扫描式连通区域标记算法

冯海文 ，牛连强 ，刘晓明

1.沈阳工业大学 软件学院，沈阳 110023

2.沈阳工业大学 电气工程学院，沈阳 110023

高效的一遍扫描式连通区域标记算法

冯海文1，2，牛连强1，刘晓明2

1.沈阳工业大学 软件学院，沈阳 110023

2.沈阳工业大学 电气工程学院，沈阳 110023

1 引言

二值图像连通区域标记是指对图像中不同连通区域中的像素设置唯一的标号，是计算机视觉、模式识别和图像处理等领域中众多算法的基础[1-4]。例如，在对医学、遥感、视频等图像进行处理时，通过连通域标记来确定物体的边缘，以对感兴趣的区域（目标）进行标记和提取；在电气行业的真空断路器的开断特性研究中，其基本方法是通过对图像连通域的查找来确定电弧图像中电弧面积和直径的变化规律，进而确定电弧的运动机理[5-6]。这些算法通常需要处理大量的图像，连通域标记算法的效率是一个关键问题。

目前，存在着多种连通区域标记算法，从处理的对象上主要可分为基于像素的算法和基于游程（块）的算法；从对像素的处理次数上，可分为一遍扫描算法、两遍扫描算法和多遍扫描算法[7-10]。文献[11-14]是几种典型的基于像素的算法，其中，文献[9]利用并查集技术减少等价信息传播的时间消耗，文献[10]采用递归方法处理连通域信息，它们对算法效率的改善不大。文献[13]提出了一种基于轮廓跟踪的快速标记算法，文献[14]提出了一种实现快速等价性判别的技术，文献[8，15]采用决策树方法减少对当前像素的邻近像素的扫描个数。这些技术使基于像素的算法在效率上得到了一定的改善。如果图像主要以水平线段（称为“游程”）组成，采用基于游程的算法可能得到更高的效率[16-20]。文献[16]采用标记矫正来减少图像的扫描次数，并对标记采用RLE游程编码来提高合并效，但所使用的链表结构复杂且影响了整体的效率。文献[17-18]利用附加存储结构合并一个连通分支内的游程以减少参与合并的标号，使标记效率得到较大提高。文献[19]直接采用并查集来处理游程的标号，因为并查集本身可以在近似线性时间内合并两棵子树，故标记效率比采用动态结构的算法高，但参与比较的游程数量没有减少。文献[20]的主要工作是利用动态链表和递归过程解决等价信息的传播问题，算法效率提高的效果并不明显。

在处理具有复杂内容的图像时，基于像素的算法有其独到的优势，而尽量减少相邻像素的连通关系判别和对图像扫描的次数是提高算法效率的主要途径。Suzuki等[14]利用一维表存储临时标号，并借助像素的位置关系快速判别其等价性，有效地减少了扫描图像的次数，使算法效率有了很大提高。但该算法在扫描中会产生等价信息损失问题，不仅使扫描图像次数增加，且次数无法事先确定。本文通过一个前置递推过程，将当前像素的邻域最小标号在连通域中直接传播，即将被更新结点所在连通分支连接到该结点，以保证等价信息不损失。同时，用最小标号更新递推查找路径上结点的临时标号，以减小分支的深度。从而以很小的代价避免了对图像的重复扫描，得到了一种高效的一遍扫描算法。

鉴于在边缘查找等应用中均以8-连通规则来判定，这里的连通域标记也采用了8-连通规则。此时，一个像素的邻域由8个像素构成，包括水平、垂直和两个对角方向的相邻像素。

2 相关工作分析

这里简要分析Suzuki标记算法的机理。设二值图像b(x，y)仅由表示前景（目标）像素 FO和背景像素 FB组成。Suzuki算法采用一个一维的标号连接表T存储等价标号，并定义图1所示的两类模板MS。

图1 由阴影区表示的8连通区域标记模板MS

算法先对图像做2.1节中的初始正向扫描（从前向后）来标记每个前景像素；再利用2.2节的过程逆向（从后向前）和正向交替扫描图像，计算并传播最小标号。每扫描一个前景像素时，用最小标号修改其值及对应MS中像素的等价标号，直到图像的所有前景像素的标号不再发生变化为止。

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内传播等价信息，需多次扫描才能使等价标号传播到整个连通区域，且扫描次数无法事先确定。

（2）对连接表T的更新可能导致中间的等价信息丢失，即已计算出的结果失效。例如，在图2中处理前景像素b(2，6)时，由前面的扫描已经确定了标号5、4和1的等价性。因其邻域模板内的最小标号为2，Suzuki算法直接将表1中的T[5]由4改为2，以便在邻域内传播最小标号，但赋值的结果使标号5与4及1的等价关系失效。因此，需要增加更多的扫描次数来重新建立起它们之间的等价关系。

图2 一个等价信息丢失的实例

表1 初次扫描图2后的标号连接表

3 改进的一遍扫描算法

3.1 最小标号的无损失传播

为避免Suzuki算法中更新连接表T所带来的等价信息失效问题，本文提出一种直接在更新当前像素标号的同时，向已建立的部分连通域中进行最小标号传播的标记方法，称为无损失连通信息传播。该方法能够防止已建立的等价关系丢失，仅对图像执行一遍扫描即可完成连通域的快速标记。

事实上，任何一个连通域最终在表T中都表现为一棵树结构。在对图像执行扫描时，如果出现了一个新的序号为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]所在的连通分支的等价性被保持下来。同时，为了减小树的平均深度，缩短后续的查找时间，在用T[l]替换T[a(r)]时，将T[r]到T[a(r)]路径上的所有结点的临时标号也更新为T[l]。

最后，更新当前像素的标号为更新后的T[l]。

3.2 算法实现

改进后的算法按如下步骤实现：

（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）的递推次数。

扫描连接表T的时间为：

其中，tj为将表T中的每个临时标号更新为最小标号所消耗的时间：

其中，nt表示式（6）中查找结点a(r)所经历的路径长度。

4.2 实验结果

为了比较算法的效率，利用C++语言编制程序，在C++Builder 6.0环境下运行，系统配置为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）开发的标准图像库，图4（b）为利用图5的固定模式构造的人工图像。各图像的连通域个数分别为164、940、1 500、1 875和1 988，运行时间为执行500次所得到的平均时间，单位为ms。

图4 几种典型的二值图像

图5 组成图4（b）图像的模式

Suzuki算法和本文算法是基于像素的，而文献[20]是基于游程的算法。表3和图6说明，对于一般图像，本文算法的效率比Suzuki算法提高了约2倍，较文献[20]算法提高了近50%。对于连通区域较大、游程较长的图像，如图4（a）、4（e），本文算法的效率与文献[20]算法接近，而在组成图像的模式很琐碎时，如图 4（b）～（d），文献[20]算法会远比本文算法耗时，这是因为得到一个游程要计算其两端像素，判别游程间的连通性也要从两端比较，在游程很小时，它们比直接对当前像素与其邻域像素之间的比较多耗时几倍，二者所消耗的时间比甚至达到4∶1以上。图6直观地显示了算法所消耗的时间比。

表3 几种算法的运行时间 ms

图6 两种算法与本算法执行时间比

在空间使用上，文献[20]算法需要依赖动态存储结构和递归过程的支持，比本文及Suzuki算法消耗更多的辅助内存。

5 结束语

本文提出了一种基于像素的快速连通域标记算法。算法的主要特点是在利用局部区域的最小标号更新临时标号之前，借助一个递推过程来保持原有的等价信息不丢失，并尽可能地减小连通域中分支的深度。由于已得到的等价信息在临时标号更新中没有损失，使得算法只需对图像做一次扫描，并辅助一个对连接表的扫描即可完成对连通域的标记。实验表明，算法的效率较改进前有大幅度提高，且因为仅对图像做一次扫描，更适用于不能对图像进行暂存的场合。

[1]张云哲，赵海，宋纯贺，等.一种新的连通区域标记算法[J].计算机应用研究，2010，27（11）：4335-4340.

[2]赵菲，张路，张志勇，等.基于硬件加速的实时二值图像连通域标记算法[J].电子与信息学报，2011，33（5）：1069-1075.

[3]王静.二值图像连通域的分段标记算法及实现[J].红外与激光工程，2010，39（4）：761-765.

[4]张二虎，冯江.Blob分析中基于游程链的连通区域标记[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]罗志灶，周赢武，郑忠楷.基于数组型并查集的连通域标记算法[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]刘奇琦，龚晓峰.一种二值图像连通区域标记的新算法[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

二值图像的连通区域标记算法是图像处理的一个基本问题。为了提高算法的效率，以Suzuki等人提出的多遍扫描算法为基础，提出了一种快速的一遍扫描连通域标记算法。算法通过对图像做一次正向扫描，先计算出每个当前像素所在邻域内的最小标号，再利用一个递推过程，查找该连通域中具有较小标号的结点，将被更新结点所在连通分支连接到该结点，以保证等价信息不损失。同时，用最小标号更新递推查找路径上结点的临时标号，以减小分支的深度。通过对连接表的更新使每个结点获得最终标号。算法不需要动态数据结构和递归过程的支持，需要的存储空间较小，算法比原算法速度提高了近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—），女，博士，教授，主要研究方向为现代电器理论设计、高电压及绝缘技术研究。E-mail：fhw19770704@sina.com

2014-07-28

2014-10-21

1002-8331（2014）23-0031-05

◎理论研究、研发设计◎