二值图像中目标物体边界跟踪的一种快速算法及其应用

陈 旺，郭庆胜，范 伟，张 航，周贺杰

(武汉大学 资源与环境科学学院，湖北 武汉 430070)

二值图像中目标物体边界跟踪的一种快速算法及其应用

陈 旺，郭庆胜，范 伟，张 航，周贺杰

(武汉大学 资源与环境科学学院，湖北 武汉 430070)

对比分析传统的二值图像边界跟踪算法，并在此基础上提出一种只根据邻近两个栅格的图像状态控制轮廓走向的新算法。实验结果表明，新算法搜索次数少，轮廓识别准确，且很好地解决了岛洞问题，最后在应用中验证了算法的有效性。

二值图像；边界追踪；地理信息系统；栅格数据；模式识别

边界跟踪作为图像处理和模式识别的基础算法，一直是研究的热点和难点。边界轮廓的确定对于研究物体的形状特征有着不言而喻的意义，在医学图像、工业断层扫描图像等二维图像处理领域中应用广泛[1]，甚至可以说是很多进一步研究的前提。另外在地理信息系统(GIS)数据处理的栅格数据向矢量数据转换的过程中，边界追踪也有着重要作用[2-3]。

边界跟踪算法的难点与关键就在于如何确定下一步的跟踪方向[4]，经典的算法有虫随法、光栅法等。而这些算法有可能反复跟踪局部区域，使程序陷入死循环。另外，对于可能存在的岛或者洞，并没有提供一个解决方案。文献[5]中的目标邻域跟踪算法是在虫随法上改进而来，一次循环就可得到结果，但搜索精度和速度上仍有待提高。文献[6]采用的算法思想是基于文献[5]的算法思想，并根据上一点的边界位置判断轮廓走向，减少了搜索次数，但精确度并不太高，也没有解决岛和洞的问题。文献[7]提出的基于动态权值的边界跟踪法在搜索速度和准确度上都有所提升，并较好地过滤掉二值化引起的边界噪声，但存储空间开销大，对于复杂的图像，效率不高。本文提出的算法可以根据邻近两个栅格的图像状态控制轮廓走向，极大地减少了搜索次数，并较好地解决了岛和洞存在的问题，实际应用价值较高。

1 已有的典型算法

虫随法是一种常见方法，它的基本思路是：一只理想的小虫从背景区域向目标区域前进，当由背景区域跨入目标区域时向左转，当由目标区域跨入背景区域时向右转，直到回到起点，便得到目标物体的轮廓结果(见图1)。

图1 虫随法跟踪边界

虫随法概念明确，算法简单，适合于四连通区域[8]，但却存在小虫易“迷路”而陷入死循环，最终回不到起点的问题，而且该方法中边界定义与出发点有关，受到了较大的限制。

光栅扫描法通过选定的阈值，按照固定的扫描线和规定的扫描顺序进行扫描。先从荧光屏左上角开始，向右扫一条水平线，然后迅速地回扫到下一行的位置，再扫第二条水平线，照此固定的路径及顺序扫下去，直到最后一条水平线，即完成了整个图像的扫描，得到边界轮廓。

但是光栅法需要不断调整阈值，对扫描方向有很大依赖性，而且需要多次进行行扫描和列扫描，工作量大，得到的轮廓也不太准确[9]。

2 改进后的算法

2.1 算法说明

本文提出的算法结合了虫随法和光栅扫描法的优点，并做了相应的改进，使得搜索的速度大大提高，并针对岛和洞提出了解决方法。算法思路如下：首先对目标图像从左上角点开始进行逐行逐列地搜索，直到搜索到像素值为1的栅格，将该栅格的左上角点定为边界的起始点，边界前进方向向右，然后按照以下跟踪规则进行跟踪，直到跟踪的边界回到起始点为止。

跟踪规则：如图2所示，P为当前栅格，箭头所指为当前边界前进方向，P1、P2为共享沿着当前前进方向下一单位距离线段的两个栅格。如果在前进方向右侧的P1为0，则前进方向改为当前前进方向顺时针旋转90°所指的方向；如果P1为1，而在前进方向左侧的P2为0，则前进方向不变；如果P1、P2都为1，则前进方向改为当前前进方向逆时针旋转90°所指的方向。

图2 跟踪规则判定

对于岛和洞，则将它们归类，然后对每种不同情况分别进行跟踪，具体跟踪方法见算法实现部分。

2.2 算法编程实现

1)备份一个相同的二值图像，接下来算法中所有对图像的修改操作都将在“备份图”上进行，而原图的作用仅仅是在确定下一个边界点的过程中，用来比对，以明确搜索规则。

2)将“备份图”中完全内部的值为1的栅格(四邻域中的内部栅格)置为0，如图3(a)所示。

3)从上到下，从左到右依次搜寻“备份图”，直到找到第一个值为1的栅格，如果没有找到，则搜索结束，如果有，记录下该栅格的左上角点P0，并判断是否是岛和洞，如果是，转5)。定义向前搜索的方向为Rotation，其中，前进方向向右时，Rotation=0；前进方向向上时，Rotation=1；前进方向向左时，Rotation=2；前进方向向下时，Rotation=3，如图3(b)所示。开始，置Rotation=0。

图3 算法基础定义及设定

4)判断是否回到P0点且搜索到的边界点数目大于1，如果是，此边界搜索完成，转3)，开始下一边界的搜索。如果否，此边界继续向前搜索。对于不同值的Rotation，有如下搜索规则：

a. Rotation=0

i.如图4(a)所示，当前栅格的右侧栅格为0，则将当前栅格置为0，当前节点向右前进一个栅格的距离，并将当前节点添加到该边界中，然后置Rotation=3，转4)；

ii.如图4(b)所示，当前栅格的右侧栅格为1，右上侧栅格为0，则将当前栅格置为0，当前节点向右前进一个栅格的距离，Rotation值不变，转4)；

iii.如图4(c)所示，当前栅格的右侧栅格为1，右上侧栅格为1，则将当前栅格置为0，当前节点向右前进一个栅格的距离，并将当前节点添加到该边界中，然后置Rotation=1，转4)。

b. Rotation=1

将Rotation=0的各种情况分别逆时针旋转90°即可得到对应情况，如图4(d)、图4(e)、图4(f)所示，此处不再赘述。

c. Rotation=2

将Rotation=0的各种情况分别逆时针旋转180°即可得到对应情况，如图4(g)、图4(h)、图4(i)所示，此处不再赘述。

d. Rotation=3

将Rotation=0的各种情况分别逆时针旋转270°即可得到对应情况，如图4(j)、图4(k)、图4(l)所示，此处不再赘述。

图4 确定下一边界点时的各种判定情况

5)对于岛和洞，有如下搜索规则：

a.如图5(a) 所示，岛洞在当前搜索栅格的右侧，则将当前节点向右前进一个栅格的距离，并将当前节点作为新的岛洞边界的起始节点，然后置Rotation=3，转4)；

b.如图5(b) 所示，岛洞在当前搜索栅格(P)的下侧，则将当前节点向下前进一个栅格的距离，并将当前节点作为新的岛洞边界的起始节点，然后置Rotation=3，转4)；

c.如图5(c) 所示，岛洞在当前搜索栅格的左侧，则将当前节点作为新的岛洞边界的起始节点，然后置Rotation=2，转4)；

d.如图5(d) 所示，岛洞在当前搜索栅格的上侧，则将当前节点作为新的岛洞边界的起始节点，然后置Rotation=0，转4)；

e.如图5(e) 所示，岛洞的边界宽度处为一个栅格，且在四邻域上闭合(即该边界的所有栅格在四邻域上有且仅有2个为空)，则取边界的起始栅格的右下角点为新边界线的起始点，置Rotation=3，转4)。

图5 岛和洞的处理

2.3 值得注意的细节问题

1)当追踪到的边界位于整幅二值图像的边缘时，就会发生数组越界的情况，导致追踪的面闭合不了[10]。解决办法：遇到这种情况，就需要扩大二值图像，使其向四周各延伸一个栅格，用0值填充。此时，二值图像的行列数均增加2。

2)当整幅二值图像很大时，追踪结束后，可以统计每个追踪到的多边形包含的栅格数目，如果数目小于一定的阈值(根据不同的研究需要制定)，可以将该多边形视为小图斑或者噪点，予以去除。

图6 特殊情况的处理

3)本文提出的算法虽然能解决大部分的岛洞问题，但是对于一些很特殊的情况(如图6(a) 所示)，追踪出来的边界也不是很理想(如图6(b)所示)，这是因为本算法是基于四邻域的，所以这种情况并不视为岛洞。这就需要在追踪结束后进行一些操作，比如将自相交的点向多边形外边进行一点移位(如图6(c)所示)。

4)本算法最后得到的边界中，普通边界和岛的边界是顺时针构造的，而洞的边界则是逆时针构造的。

3 实验结果及算法应用

本文选用了经过处理的某地区中学分布图和酒店分布图作为实验对象，将其二值化得到二值图像(见图7(a))，然后运用本文的搜索算法搜索出其边界(见图7(b))。

图7 实验对象及实验结果

从图上可以看出，搜索出的边界基本符合原来的轮廓。对于面积特别小的图癍，视为噪点予以去除，且对搜索出的边界进行了光滑处理，可视化效果较好。另外，在搜索次数上与文献[6]提出的算法进行了对比。文献[6]采用的算法共搜索了4 128和5 619次，而本文提出的算法仅搜索了2 548和3 604次，搜索效率提高了38.28%和35.86%，其中文献[6]的搜索数据是通过统计其算法在各种边界点情况下平均搜索次数后与其边界点相乘得到，本文的搜索数据是直接统计搜索次数得到的。

在实际生活中，经常遇到选址问题，例如，已经有某个地区的所有学校的位置数据，现在需要根据教育情况划定几个教育集中区域，以期落实教育改革情况或者建设基础设施以改善教学质量。基于此，本文提出一种应用模式。

首先根据这些离散点的位置，计算出整个区域的核密度估计(核密度估计是在概率论中用来估计未知的密度函数，属于非参数检验方法之一[11]。由于核密度估计方法不利用有关数据分布的先验知识, 对数据分布不附加任何假定, 是一种从数据样本本身出发研究数据分布特征的方法, 因而, 在统计学理论和应用领域均受到高度的重视)，如图8所示。如果这些离散点有属性上的重要与非重要之分，则赋予不同的权重再计算。之后根据核密度估计的不同，选定一定的阈值，将整个区域二值化，再根据本文提出的边界追踪算法提取所需的区域，最后进行一定的后期处理，如平滑边界，去除噪点等，就得到了最终的结果，如图7所示。不难看出，筛选出的区域都是目标点集中的区域(重点区域)，且算法追踪出的区域边界光滑，解决了岛和洞的问题，在实际应用中效果较好。

图8 原始点数据及核密度处理结果

这种应用模式可以应用到各个行业中，如抢险救灾中确定重灾区，先行救援；工业生产中确定技术密集区，加大扶持投资；日常生活中划定商业娱乐中心，完善基础设施建设等。

4 结束语

边界追踪是数字图像处理、模式识别的重要内容，也是地理信息系统中栅格数据向矢量数据转换的重要保证。本文提出的算法减少了搜索次数，加快了搜索速度，搜索效率有较大程度提高，同时针对岛洞问题提供了较好的解决方案，最后根据实际问题，提出了自己的应用方法。实验表明，该算法切实可行，同时希望该应用方法能为政府部门、商业机构在解决一些调控、选址问题时提供一定的参考。

[1]何丽，李嘉，郑德华，等.基于栅格的点云数据的边界探测方法[J].测绘工程,2013,22(3):69-73.

[2]CASTLEMANKR. Digital Image Processing[M]. [S.1.]:Prentice Hall,1996:309- 312.

[3]张孝灿, 潘云鹤. GIS中基于“栅格技术”的栅格数据矢量化技术[J].计算机辅助设计与图形学学报,2001,13(10):895-900.

[4]周凌焱，刘成龙，张强，等.基于深度和广度优先算法相结合的闭合环自动搜索方法研究[J].测绘工程,2014，23(5)：24-28.

[5]崔凤魁,张丰收,白露,等.二值图像目标邻域点法边界跟踪算法[J].洛阳工学院学报,2001,22(1):28-34.

[6]王福生,齐国清.二值图像中目标物体轮廓的边界跟踪算法[J].大连海事大学学报,2006(1):62-64.

[7]周丰乐，徐向民，肖跃,等. 一种新的二值图像目标轮廓跟踪算法[J].微计算机信息,2007(6):259-261.

[8] PRATTK.数字图像处理[M].邓鲁华,张延恒,译.北京:机械工业出版社,2005:397-398.

[9]柳稼航,杨建峰,单新建,等.一种基于优先搜索方向的边界跟踪算法[J].遥感技术与应用,2004(19):209-213.

[10]谢顺平,都金康,王杰臣.实现栅格图形和图像数据矢量化提取的游程轮廓追踪法[J].遥感学报, 2004,8(5):465-470.

[11]李存华, 孙志挥, 陈耿, 等. 核密度估计及其在聚类算法构造中的应用[J].计算机研究与发展2004,41(10):21-28.

[责任编辑：刘文霞]

A rapid algorithm on tracing edge of binary image and its application

CHEN Wang, GUO Qing-sheng, FAN Wei, ZHANG Hang, ZHOU He-jie

(School of Resource and Environmental Sciences, Wuhan University, Wuhan 430070 , China)

The traditional tracing edge algorithms of binary image are compared with and analysed, and a new algorithm which can control the direction of the image’s outline is proposed only based on two neighboring grids. The experimental results show that in the algorithm the number of searching is fewer, identification of contour is accurate, and the problem of ‘island and hole’ is solved well. Finally, its application verifies the effectiveness of the algorithm.

binary image; tracing edge; GIS; raster data; pattern recognition

2013-12-23；补充更新日期：2014-09-20

国家863计划资助项目(2012AA12A402)；国家自然科学基金资助项目(41071289，41171350)

陈 旺(1991-)，男，硕士研究生.

TP75

：A

：1006-7949(2014)12-0063-04