基于游程与轮廓跟踪的连通区域标记改进算法

杨定礼，孙山林，严 石,3，尹晓琦，付成芳，吴天驰，张约骋

(1. 淮阴工学院 电子信息工程学院， 江苏 淮安 223003;2. 北京航空航天大学 仪器科学与光电工程学院，北京 100191；3. 淮阴工学院 成人教育处， 江苏 淮安 223001)



基于游程与轮廓跟踪的连通区域标记改进算法

杨定礼1，孙山林2，严 石1,3，尹晓琦1，付成芳1，吴天驰1，张约骋1

(1. 淮阴工学院 电子信息工程学院， 江苏 淮安 223003;2. 北京航空航天大学 仪器科学与光电工程学院，北京 100191；3. 淮阴工学院 成人教育处， 江苏 淮安 223001)

为了进一步提高连通区域标记的效率，提出了一种改进的基于游程与轮廓跟踪技术相结合的连通区域标记算法。该算法首先判断当前前景像素点是孤立点还是轮廓点，然后判断是外轮廓还是内轮廓，并用相应的轮廓标记算法对其进行标记，最后用游程标记方法对本行中剩余的前景像素进行标记，整个过程无需等价表，耗时较少。实验证明，改进后算法的标记效率提高大约24.5% 。

连通域标记；游程；轮廓跟踪；外轮廓；内轮廓

0 引言

一般将二值图像进行连通区域标记的目的是:首先将二值图像中属于同一连通区域的所有像素检测出来，并将每个连通区域分配唯一的标号。然后根据标号来分割出不同的物体。在分割出不同的物体以后，就可以计算每个连通区域的质心、周长、面积等特征。这些在计算机视觉、模式识别、图像处理等领域有非常重要的作用。目前二值图像连通区域标记算法主要有：像素标记法[1]、游程编码法[2-3]、区域生长法[4-6]、轮廓跟踪标记算法[7]。这些算法都需要处理大量的中间信息，所消耗的时间较多。张云哲等[8]提出了一种新的基于非对称游程和轮廓跟踪技术相结合的连通区域标记算法，该算法避免了上述的缺点。其主要先采用轮廓跟踪技术搜索连通区域的轮廓，然后以游程为单位来标记二值的图像[8]。在用游程标记时，有的采用起始点像素的标记来标记游程[8]，有的采用终点的像素的标记来标记游程。在用终点的像素标记进行标记时，则必须先扫描游程的每个像素点，直到该游程终点的像素，在标记时又需要重新扫描一遍，势必要浪费时间。本文对此进行了改进，无需扫描到游程的终点就可以得到该像素的标记。改进后算法的每一个游程的起始点一定是已经标记过的，如果没有标记则一定是新的轮廓的起始点，则先进行轮廓标记，再进行游程标记。主要改进有这样几个方面。改进一：在处理内轮廓时，用搜索内轮廓的方法进行标记，并用游程的标记方法[8]，但是由于在检测是否是轮廓像素以及在上下两行搜索游程时耗费大量的时间，所以本文提出用当前前景像素点的P5位置的标号来标记较好。P5位置的标号是非常重要的，如果P5位置有前景像素，则其为内轮廓，必须按照内轮廓的标记方法进行标记。如果P5位置没有前景像素，则其为外轮廓，必须按照外轮廓的标记方法进行标记。改进二：对于外轮廓，第一次遇到的，从P0开始搜索，不应该按照从P5开始[8]。对于内轮廓点则要从P5开始搜索。改进三：每个游程的标记都用起始点进行标记，而不是用游程终点进行标记，也不需要搜索上一行的游程或者下一行的游程而浪费时间。

1 连通域标记的算法

在连通区域标记的过程中，不同物体的像素将被标上不同的标号，同一物体的像素则被标上相同的标号。通常的连通性有两种：4连通与8连通。本文主要讨论8连通，并从当前像素点的右侧开始标号，起始标号为P0，按照顺时针方向进行标号，直到P7，如图1所示。目前常用的二值图像连通区域标记算法大致有下面几种方法。

5674P0321

图1 八连通的表示

1.1 像素标记法

该方法要求对二值图像进行多次扫描，每次扫描以后对属于同一连通区域的像素标号进行更新，直到二值图像中所有像素的标号不再变化，这种方法的效率较低。有研究将当前像素的8个邻域像素进行拆分，拆分为2个子集，一个向前扫描，一个向后扫描，经过多遍的交替扫描，不断调整等价表，最后得到一个不变等价标号表，然后根据等价标号表得到每个像素的最终的标号[9]。这种方法缺点是要多次扫描图像，耗费大量的时间。

1.2 游程编码法

所谓游程是将一行中连续相连的前景像素即一条直线段作为连通区域检测的基本单元，一行中可能有一个游程，也可能有几个游程。游程编码法是对二值处理后的图像进行逐行扫描时，每当扫描出当前行的一条直线段，就和上一行检测出的直线段进行连通性检测，那些满足连通性要求的直线段将被赋予相同的标号[2]。在进行第二次扫描时，应该用等价标记中最小的标号来代替所有等价标号对应的像素点。由于该算法充分利用了区域连通性的结构的特征，与像素标记法相比，产生的等价对个数要减少很多，因而具有更高的效率。不过在工程实践中也遇到不少问题，如当图像较大时利用数组或者链表处理等价对时，占用内存太大，甚至出现溢出问题[2]。

1.3 区域生长法

区域生长法可以弥补像素标记法与游程编码法的多次扫描的缺陷，可以实现一次标记一个连通区域内所有的像素，然后再标记下一个连通区域的像素，直到标记完所有的连通区域内的像素。该方法是以当前像素为种子，用一个新的标号标记当前像素，然后标记与其相邻的前景像素，再把它们压入堆栈，作为种子，继续标记，不断重复这个过程，直到标记完整个连通区域。由于这个方法不需要用等价标记表，不受目标数量与目标图像复杂度的影响，因而具有一定的鲁棒性[2]。但是，当连通区域面积较大时，如果对每个目标像素点进行8邻域的判断，那么所需堆栈会较大，此时它的算法效率反而会下降。

1.4 轮廓跟踪标记算法

轮廓跟踪标记算法在标记时主要分三个步骤。

第一，如果遇到外轮廓起始点时，则用一个新标号来标记外轮廓。

第二，当遇到内轮廓起始点时，要分两种情况：(1) 如果起始点已经标记，则用它的标号标记内轮廓；(2) 如果该起始点没有标记，那么它的左邻P4一定是已经标记的像素点，则用P4的标号标记本行内轮廓。

第三，当遇到已经标记的轮廓点时，用这个轮廓点的标号标记本行中位于其后的所有前景像素[8]。

2 连通区域标记的改进算法

本文在仔细研究文献[8]后，在其基础上提出了改进的方法。改进的方法是用轮廓跟踪技术与游程标记相结合的标记方法来标记二值图像，与文献[8]不同的是本文先进行轮廓跟踪再进行游程标记，而且本文的轮廓跟踪技术是对文献[8]的轮廓跟踪技术的改进。该方法只需要扫描一遍图像，不需要等价对表，耗时较少。主要的改进有以下几个方面。

2.1 外轮廓搜索方法的改进

在处理外轮廓时，通过从左上邻居P5开始按照顺时针方向扫描它的邻居，首先遇到的前景像素就是下一个轮廓点，如果遇到一个新的轮廓点，最上面的第一个轮廓点P5位置是没有前景像素的[8]。一般在P0的位置是有前景像素的，因此本文提出对于外轮廓，第一次遇到的，从P0开始搜索，不应该从P5开始。以后就按照下面的规则进行搜索。该规则是假设下一个轮廓点是当前轮廓点的Pj，则当前轮廓点是下一个轮廓点的邻居 Pi=mod(Pj+4)，那么下次从Pi+2开始按照顺时针的方向来扫描当前轮廓点的邻居，第一个遇到的前景像素就是下一个轮廓点，标记该轮廓点，并按照上面的方法继续搜索下一个轮廓点，直到当前点是起始点，而下一个点是原始第二个点，则轮廓标记程序结束。

2.2 内轮廓搜索方法的改进

在处理内轮廓时，如果遇到的第一个点是没有标记的，通过寻找内轮廓上的某个点的左邻P4，该P4一定是已经标记的像素点，然后用P4的标号标记本行内轮廓。该方法由于要先判断是否是内轮廓点，然后寻找标记点，最后再标记，浪费不少时间[8]。本文在处理轮廓时用第一个遇到的轮廓点的P5位置的标号来标记当前像素。如果P5位置没有前景像素，则其为外轮廓，必须按照外轮廓的标记方法进行标记。如其为内轮廓最上面的第一个点，其P5位置一定是有前景像素的。如果P5位置有前景像素，则其为内轮廓，必须按照内轮廓的标记方法进行标记。如图2，首先标记完外轮廓，再用游程标记后，W点上面的前景像素一定是已经标记好的，同时W点左边也是标记好的，当用本文方法游程扫描时，遇到W右边的第一个点时，如果该点没有标记，则检查它的左上角P5位置是否有前景像素，如果有，则用P5位置的标号标记W右边的第一点，然后以此为起始点，第一次是从P5位置开始搜寻，以后就按照下面的规则进行搜索。该规则是假设下一个轮廓点是当前轮廓点的Pj，则当前轮廓点是下一个轮廓点的邻居Pi=mod(Pj+4)，那么下次从Pi+2开始按顺时针方向扫描当前轮廓点的邻居，第一个遇到的前景像素就是下一个轮廓点，标记该轮廓点，并按照上面的方法继续搜索下一个轮廓点，直到当前点是起始点，而下一个点是原始第二个点，则轮廓标记程序结束。

图2 内轮廓的标记方法

2.3 游程的标记方法的改进

在进行游程标记时，通过用起始点的标号或者终止点的标号来标记，尤其是起始点没有标记，而终止点有标记，则用终止点的标记来标记该游程[8]。由于要搜索到终止点才能确定是否有标记，该方法消耗了不少时间，用本文的方法，不需要搜索，直接用起始点的标记来标记游程。如果起始点没有标记，则其必为轮廓，通过判断P5位置有无前景像素，可以判断其为外轮廓还是内轮廓，然后按照外内轮廓的方法进行标记。

2.4 标记的过程

用本文算法进行标记的流程图见图3。标记过程如下：

(1) 首先进行初始化，设置标号label为1，然后按照从上到下，从左到右的顺序对二值图像进行扫描图像。

(2) 当遇到一个前景像素点时，首先看是否已经标记，如果已经标记，则用游程法进行标记。如果没有标记，则转到(3)。

(3) 搜索该点周围的8个点，判断该点是否是孤立点，如果是孤立点则直接将该点设置为背景像素，起到了滤波的作用。如果该点不是孤立点，则认为该点是某轮廓的起始点，可能是外轮廓点，也可能是内轮廓点。

(4) 根据P5位置是否有前景像素，如果没有前景像素，则该点是外轮廓上的一点，进入(5)调用外轮廓标记程序。如果有前景像素，则该点是内轮廓的一点，进入(6)调用内轮廓标记程序。

图3 用改进的算法进行标记的流程图

(5) 调用外轮廓标记程序过程：首先用label标记该前景像素点，然后从P0开始，按照顺时针方向进行扫描，将遇到的第一个前景像素点作为下一个轮廓点，并标记。假设下一个轮廓点是当前轮廓点的邻居Pj，则当前轮廓点是下一个轮廓点的邻居 Pi=mod(Pj+4)，那么下次从Pi +2开始按顺时针方向扫描下一个当前轮廓点的邻居，第一个遇到的前景像素就是下一个当前轮廓点，标记该轮廓点，并按照上面的方法搜索它的下一个轮廓点，直到当前点是起始点，而下一个点是原始第二个点，则轮廓标记程序结束。并更新标号，将标号label自动加1，即label= label+1。这种标记结果是按照顺时针方向标记外轮廓。

(6) 调用内轮廓标记程序过程：首先用P5位置前景像素的标记标记当前前景像素，然后从P5开始，按照顺时针方向进行扫描，将遇到的第一个前景像素点作为下一个轮廓点，并标记。假设下一个轮廓点是当前轮廓点的邻居Pj，则当前轮廓点是下一个轮廓点的邻居 Pi=mod(Pj+4)，那么下次从Pi +2开始按顺时针方向扫描下一个当前轮廓点的邻居，第一个遇到的前景像素就是下一个当前轮廓点，标记该轮廓点，并按照上面的方法搜索它的下一个轮廓点，直到当前点是起始点，而下一个点是原始第二个点，则轮廓标记程序结束。并更新标号，将标号label自动加1，即label= label+1。这种标记结果是按照逆时针方向标记内轮廓。

(7) 标记完轮廓以后，沿着当前行继续向前扫描，如果遇到前景像素点，则回到(2)。如果扫描到最后一行，最后一列，则结束。

3 实验与分析

在对水果商品品质进行分级时，首先要提取水果的图像，将水果从背景中分割出来，然后进行特征提取，最后进行分级。而要将水果分割出来，必须要进行连通区域的标记。本实验是在MATLAB R2010b软件环境下编程，PC机的配置为 Intel Core I5-5200U CPU@2.2GHz 2.2GHz双核，内存为4.0GB。在HIS颜色空间对含有苹果的图像运用色度阈值进行判断，可得二值图像，见图4(a)。该图中存在噪声，必须去掉噪声，只留下苹果的图像。采用本文的基于游程与轮廓跟踪技术的连通区域标记改进算法可以得到各个连通区域的标记，取含有最大数目像素的标记，可以将苹果从背景中分割出来。图4(b)表示轮廓提取，当搜索到轮廓最上面第一个像素时，就按照轮廓搜索的方法将轮廓提取出来。图4(c)表示游程标记过程，当从左向右搜索的时候，用游程的第一个像素的标记进行其他像素的标记。图4(d)表示标记后的结果，从图中可以看出不同的连通区域具有不同的标记。如果取最大数目像素的标记，就可以将苹果从背景中分割出来。图5与图4类似，只是含有两个苹果，其中第一个苹果已被损坏，含有内轮廓时，演示如何来搜索外轮廓与内轮廓并标记的。

(a)原始的二值图像 (b)轮廓提取

(c)游程标记过程 (d) 标记后的图像

图4 本文方法对单个苹果进行连通区域标记的过程

(a)原始的二值图像 (b)轮廓提取

(c)游程标记过程 (d) 标记后的图像

图5 本文方法对两个苹果进行连通区域标记的过程

为了比较不同方法标记的效果，本文采用方法一：基于区域增长的标记算法、方法二：基于标号等价技术的标记算法，方法三：基于非对称游程和轮廓跟踪的连通区域标记算法，方法四：在方法三基础上提出改进方法。用上述的四种方法对三幅图像进行实验，图像一是含有1个苹果的图像；图像二是含有2个苹果的图像，其中一个苹果坏掉，搜索时有内轮廓的提取；图像三是含有1个梨子的图像，对这三幅图像分别用上述四种方法进行连通区域的标记。每种方法的执行时间如下表所示。从表中可以看出，由于方法一要进行多次扫描图像与等价表，所需时间最多。方法二采用区域增长的标记算法，要不断访问前景像素，如果前景像素在图中所占的比例较大时，其所需要的时间较大。在实验时占用内存最大。方法三与前两种方法相比，所需时间较少，方法四是在方法三的基础上进行的改进，使得执行时间进一步减少。

表1 四种不同算法的执行时间 /s

由表1中最下面的两行数据可以得到改进的方法比方法三提高的效率，效率的公式为:

(1)

上式可以得到表2，从表2中可知改进的方法的效率比方法三的效率平均提高了大约24.5%。

表2 效率提高表

4 结论

本文在仔细研究已有文献的基础上，提出一些改进方法。主要改进有三个方面。第一，是在处理内轮廓时，提出用当前前景像素点的P5位置的标号来标记较好。第二，在处理外轮廓时，第一次从P0开始搜索，不应该从P5开始。对于内轮廓点则要从P5开始搜索。第三，每个游程的标记都用起始点进行标记，而不是用游程终点进行标记，也不需要搜索上一行的游程或者下一行的游程而浪费时间。实验证明改进后算法的标记效率得到了提高。

[1] 蔡世界,于强.基于游程编码的连通区域标记算法优化及应用[J].计算机应用,2008(12):3150-3153．

[2] 刘奇琦,龚晓峰. 一种二值图像连通区域标记的新方法[J].计算机工程与应用,2012 (11):178-180.

[3] 牛连强,彭敏.利用游程集合的标号传播实现快速连通域标记[J].计算机辅助设计与图形学学报,2015(1):128-135.[4] 沈乔楠,安雪晖.基于游程递归的连通区域标记算法[J].计算机应用,2010(6):616-618.

[5] 曹长虎,李亚非.一种二值图像连通区域标记快速算法[J].科学技术与工程,2010(33):8168-8171.

[6] 高红波,王卫星.一种二值图像连通区域标记的新算法[J].计算机应用,2007(11): 2776- 2777.

[7] REN M W, YANG J Y, SUN H. Tracing boundary contours in a binary image[J].Image and Vision Computing,2002(3):125-131.

[8] 张云哲,赵海,宋纯贺,等.一种新的连通区域标记算法[J].计算机应用研究,2010(11): 4335-4337.

[9] Suzuki K, Horiba I, Sugie N. Linear-time connected-component labeling based on sequential local operations[J].Computer Vision and Image Understanding,2003(1): 1-23.

(责任编辑：孙文彬)

Improved Algorithm of the Connected Component Labeling Based on the Run Length and Contour Tracking

YANG Ding-li1, SUN Shan-lin2, YAN Shi1,3, YIN Xiao-qi1, FU Cheng-fang1, WU Tian-chi1, ZHANG Yue-cheng1

(1. Faculty of Electronic Information Engineering, Huaiyin Institute of Technology; Huai'an Jiangsu 223003,China; 2.School of instrumentation Science and Opto-electronics Engineering, Beihang University, Beijing 100191,China; 3. College of Extended Education, Huaiyin Institute of Technology, Huai'an Jiangsu 223001, China)

In order to further improve the efficiency of the connected component labeling, an improved algorithm of the connected component labeling based on the run length and contour tracking technology is proposed. Firstly, the current foreground pixel is determined by whether it is the contour point or isolated point. Then, it is determined by whether it is the outer contour or inner contour. It is marked with the corresponding contour marking algorithm. Finally, the remaining foreground pixels on this row are marked with run length marking method. There is no need of equivalence table during the whole process and the elapsed time is less. Experiments show that the efficiency of the improved algorithm is increased by 24.5%.

connected component labeling; run length; contour tracking; outer contour; inner contour

2016-06-27

国家青年基金项目(61401173)；淮安市工业项目(HAG2013064)；淮阴工学院基金项目(HGB1202)

杨定礼(1973-)，男，江苏淮安人，副教授，硕士，主要从事数字信号处理、图像处理、模式识别和DSP的开发研究。

TP391.41

A

1009-7961(2016)05-0001-05