一种新的边界跟踪算法

石 爽，曲仕茹，何 力



一种新的边界跟踪算法

石 爽，曲仕茹，何 力

（西北工业大学自动化学院，陕西西安 710072）

针对提取的图像边缘中存在非单像素和断点的情况，提出了双层边界区域生长的边界跟踪算法。通过对中心点周围里层点和外层点分别进行搜索，然后把里层点和上一层中心点的外层点合并，并将并集中的点分别作为下一步搜索的中心点，循环向下搜索。同时充分考虑了起始中心点单向搜索的情况，并在一次搜索过程中完成了对断点的补齐工作，从而弥补了“记忆爬虫”法和八邻域法在跟踪分支、断点和“厚”边缘过程中存在的不足。实验证明该方法效果较好。

区域生长；边界跟踪；爬虫；八邻域

区域的边缘为图像中灰度变化剧烈的地方，它含有丰富的信息。边缘描述了图像中所包含物体的轮廓，表达了物体之间的关系。边缘在图像高层处理中，如物体的识别、特征提取或者三维重建等都要用到边界信息，边缘处理的好坏直接影响图像处理的结果。边缘处理的前提是必须把边缘组合成有意义的数据链，通过边界跟踪得到边界点序列或边界链码才可以求得物体的周长、宽度、高度、轮廓的凹凸情况。

常用的边界跟踪方法是“爬虫”法（轮廓跟踪法）。文献[5]对“爬虫”法作了改进，采用Freeman对链码及方向的定义，将链码以1、5为对角线分成上下两个部分，这样不必每次都搜索这8个像素点，算法时间复杂度有所降低。文献[6]采用最近点关系准则，即通过计算当前点和其他点间的距离，选择与当前点距离最近的点连接。文献[7]从中心点左上角开始，逆时针对八邻域点进行搜索，先搜索到的点作为下一搜索的中心点。文献[8]为了消除轮廓跟踪过程中断点以及分支点的不利影响，采用遗传算法对待定点进行最优搜索。

1 问题提出

常用的边缘检测算法中，Canny算法提取的边缘效果较好，但其算法的时间复杂度较高，在实时图像处理中很难接受。其它边缘提取算子，例如Roberts算子、Sobel算子、Prewitt算子以及Laplace算子等，时间复杂度较低，但所得到的边缘可能很“厚”，远非理想中的单像素宽，而且无论边缘提取算法多么好，边缘漏检仍是不可避免的。断边和分支点会导致伪边界的生成，噪声和图像灰度值差异也会产生的边缘间断。

文献[9-11]的方法具有各自的局限，只能适用于某一类的图像。光栅扫描跟踪法通过扫描的方式将边缘点连接起来，但很难构成边缘点链。“爬虫”边界跟踪方法对于断裂长度较大的边缘跟踪会失败，“记忆爬虫”能够解决边缘分支问题，但会落入“厚”边缘和断点的“陷阱”中。

在图1(a)中，每个方格代表一个像素点，5、6、7、8点构成“厚”边缘，如果从点1开始搜索，从左上角开始，利用8邻域逆时针搜索，且搜索到一个8邻域点后就更换搜索中心点，那么搜索中心点到达点5后，将会遗漏点6、7、9，搜索结果为1－2－3－4－5－8－10－11－12。如果采用每次都搜索完所有8邻域点，那么以点5为中心点搜索时先搜索到8，接着是7，最后是6，这样虽然不会产生遗漏点，但无法处理断点的情况，如图1(c)中，必须采用24邻域搜索的办法，而且每次必须搜索所有的邻域点。

当边界出现小分支时，如图1(b)所示，利用“爬虫”，从点1开始，同样按8邻域搜索爬行，当搜索到一个8邻域点后就更换搜索中心点，那么搜索结果为1－2－3－4－5－6－7－9－10－11。“爬虫”落入“陷阱”中，遗失边界点12到16。采用“记忆爬虫”可以使其回到点7继续向另一分支“爬行”，但它无法解决断点的情况，如图1(d)中，在8至13间出现断点，“爬虫”无法识别。

图1 边界点图组

可见，以上提到的边缘跟踪算法均没有充分考虑“厚”边缘存在的情况下对分支和断点等各种情况的处理。

2 边界跟踪、补齐断点算法

2.1 边界跟踪

采用双层边界区域生长法可以有效地解决上面提出的问题。区域生长(region growing)的基本思想是将具有相似性质的像素集合起来构成区域。具体步骤是：先对每个需要分割的区域找一个种子像素作为生长的起点，然后将种子像素周围邻域中与种子像素具有相同或相似性质的像素合并到这—区域中。将这些新像素当作新的种子像素继续进行上面的过程，直到再没有满足条件的像素可被包括进来。双层指把搜索中心点的24个邻域点按照里层和外层分开，把中心点的8邻域点作为里层，剩下的16邻域点作为外层。对于边界，厚度一般不会超过3个像素，如果超过3个像素，必须经过边缘细化后才能继续下面的工作。从左上角开始，按逆时针分别计算中心点的里层邻域点和外层邻域点，并把里层邻域点和父中心点的外层邻域点取并集，作为下一次搜索的中心点。这样循环下去，直到所有的边界点都被搜索完。

步骤如下：

（1）选择初始中心点CenterPoint；

（2）如果CenterPoin是前3层点，在搜索其周围点时，只要搜索到逆时针第一个点；

（3）否则CtClm＝本层中心点个数，j＝1；

（4）若j

（5）将搜索到的点从去除被搜索点集中去除；

（6）同深度中心点的里层点求并集a，同深度中心点的外层点求并集b；

（7）里层点集和上一深度中心点的外层点集求并集c；j++；

（8）如果某中心点的里层点和其父亲节点外层点并集为空，但该中心点的外层点不为空，则调用补齐断点程序；

（9）若a、b、c同时为空集，则搜索完毕，break；

（10）否则，转至步骤4；

（11）按逆时针顺序排列被搜索到点，计算新层中心点数目CtClm，j＝1；

（12）转至步骤3。

2.2 初始点处理

通常任一边界点的两侧都有点，当设定第一个中心点，并只有按一测边缘走向搜索才能得到顺序边界。而刚开始搜索时，除中心点外其它点均为未知点，利用里层和外层同时搜索会导致边界顺序同时向中心点两侧生长，所以必须对初始搜索方向进行限制。

对初始点的里层点和外层点进行搜索时，从中心点左上角开始，按逆时针，只分别搜索到一个点即可，然后更换中心点继续向下搜索。这样的搜索深度超过3时（此时新的中心点已经超出第一个中心点的24邻域），再按照4的步骤进行搜索。

2.3 补齐断点

在边界序列中，如果不对断点进行修复，将给后续图像分析带来很多麻烦。为了降低时间复杂度，尽可能在对边界点集合的一次排序中完成对断点的修复。设左右和上下的相邻像素间的距离均为1，在边界跟踪的搜索过程中，设同一中心点的里层点和外层点最小距离为，若>2，则认为该处存在断点；若里层点集为空，外层点集不为空，则同样认为该处存在断点。

补其断点采用求平均值法。在存在断点的地方，计算中心点与外层点的坐标算术平均值，再对该平均值取整，结果填入断点处。

3 实验及结论

图2(a)中给出了一个存在断点的物体红外边界图，设网格的最左上角格坐标为(1, 1)，最右下角格的坐标为(20, 20)，以点1为初始中心点（坐标为(5, 3)），使用八邻域法和“记忆爬虫”法进行跟踪，分别得到图2(b)、图2 (c)中的结果，可见，跟踪过程被A处断点终止。而使用双层边界区域生长法进行跟踪，只进行一次搜索就得到图2(d)中边界图像。共跟踪了61个边缘点，其中点4、11、15、19、21、25、42、49、51、55为修复点。

图2 物体红外边界跟踪对比

图2(e)中给出了一个无断点的物体红外边界图。使用八邻域法跟踪结果如图2(f)中所示，跟踪掉入分支B处的“陷阱”中；使用“记忆爬虫”法进行跟踪，虽然解决了分支问题，但需要跟踪完一个分支后才能回到分支处进行下一分支跟踪，这样，在“厚”边缘C、D处的排序结果中变得杂乱无章，结果如图2(g)中所示。而使用双层边界区域生长法进行跟踪，只进行一次搜索就得到图2(h)中边界图像，不仅解决了分支问题，而且对“厚”边缘C、D处的点实现了合理排序。

综上所述，双层边界区域生长法有效地对存在“厚”边界和断点的边界进行跟踪，并在一次跟踪中完成对边界的修复。此外，该算法还可以扩展到中心点的48邻域，以适应更大的断点。但该方法也存在一些不足，例如它的时间复杂度要高于八邻域法，而且在跟踪的过程中不能完成边缘细化的工作。这些问题将在今后的研究中致力解决。

[1] ZHANG Yujin. Image processing and analysis [M]. Beijing: Tsinghua University Press, 1999. 179-180.

[2] 刘相滨, 向坚持, 阳 波. 基于八邻域边界跟踪的标号算法[J]. 计算机工程与应用, 2001, 37(23): 125-132.

[3] Sobel L. Neighborhood coding of binary images for fast contour following and general binary array processing [J]. Computer Graphics Image Process, 1978, 8(1): 127-135.

[4] [美]Castleman K R著. 数字图像处理[M]. 朱志刚,等译. 北京: 电子工业出版社, 1998. 70-72.

[5] 葛 澎. 一种快速边缘跟踪与提取的新算法[J]. 微电子学与计算机, 2005, 22(8): 14-17.

[6] 李西平, 王思贤. 基于边缘检测技术的字符轮廓线的提取和显示[J]. 计算机工程与应用, 2001, 36(1): 52-53.

[7] Donoho D L. De-noising by soft thresholding [J]. IEEE TransInform Theory, 1995, 41(3): 613-626.

[8] 夏 涛, 陈海清, 黄士科. 基于局部灰度分析的红外图像轮廓跟踪算法[J]. 红外与激光工程, 2006, 35(2): 216-221.

[9] DEEMTER J H, DUBUF J M H. Simultaneous detection of lines and edges using compound Gabor filters [J]. International Journal of Pattern Recognition and Artificial Intelligence, 2000, 14(6): 757-777.

[10] 杜 奇, 向健勇, 袁胜春. 基于边缘强度的红外图像阈值分割方法研究[J]. 红外与激光工程, 2004, 33(3): 288-291.

[11] WANG Hongbo, ZHUANG Zhihong, ZHANG Qingtai. Infrared image segmentation algorithm in imaging guidance [J]. Infrared and Laser Engineering, 2003, 32(3): 234-238.

[12] 胡学龙, 许开宇. 数字图像处理[M]. 北京: 电子工业出版社, 2006. 145-146.

[13] 林世毅, 苏广川, 陈 东, 等. 基于二步法的边缘细化算法研究[J]. 仪器仪表学报, 2004, 25(4): 682-684.

[14] 刘明艳, 赵景秀, 孙 宁.用Prewitt算子细化边缘[J]. 光电子技术, 2006, 26(4): 259-263.

[15] 陈庆虎, 赵 云, 刘鸿翔.一种简单高效的二值图像并行细化算法PABIT[J]. 武汉理工大学学报, 2004, 28(2): 270-273.

A New Algorothm for Boundary Tracing

SHI Shuang, QU Shi-ru, HE Li

( Department of Automatic Control, Northwestern Polytechnical University, Xi’an Shaanxi 710072, China )

For the shortcoming of non-single pixels and broken points in the obtained image boundary, a new algorithm for boundary tracing of dual layer boundary region growing is proposed, to search inner-points and outer-points around center-points, to combine the inner-points with upper outer-points, to conduct continuous tracing with the combined points as the center-points in next search. The algorithm takes into account the one-way search from initial points, and can fill the broken points in one tracing process. Thus, it effectively makes up the defects of memory reptile method and eight neighborhood method in tracing embranchment, broken point and thick boundary. The experiments prove its effectiveness.

region growing; boundary tracing; reptile; eight neighborhood

TP 391

A

1003-0158(2011)03-0052-05

2009-03-03

陕西省工业攻关资助项目（2008KD7-14）

石 爽（1978-），男，安徽泗县人，博士研究生，主要研究方向为交通运输工程、图像处理。