中图分类号：TN91 文献标识码 A
0 引言
边界是图像中相邻区域的交界点的集合，反映了物体之间的分界。在图像处理领域，边界跟踪是一种从一个边界点出发，根据特定的判别准则和搜索规则逐步寻找下一个边界点的技术，直至完成一个完整的边界闭合过程。这种技术在动态目标跟踪、图像分割、人脸识别、运动分析等应用中具有重要作用。
二值图像处理是边界跟踪中的一种常见方式，其中图像的像素值只有0和1两个灰度级。本文讨论的是针对二值图像的封闭边界跟踪，结果同样适用于灰度图像。对于二值图像，边界可以通过坐标序列或链码来表示，甚至可以直接用边界的序号来表示。在实际应用中，为了实现对边界的准确跟踪，需要定义边界点、外边界和内边界的分类，以及它们之间的拓扑关系。
1 边界跟踪的有关概念
1.1 边界点及判定
二值图像中，1像素点按照4连通或者8连通组成1连通域，0像素则按照相同规则组成0连通域。1连通域和相邻的0连通域的交界线就是二者的边界，边界由1连通域的1像素点组成。
图1 二值图像边界
在边界跟踪的时候，需要根据当前的边界点寻找下一个边界点。方法是以当前边界点为中心，上一个边界点为起点，顺时针或逆时针在八领域或四领域内寻找下一个边界点。对于八领域，如果1点周围的四领域内有0点，则该点为边界点，否则为连通域内部。如图1所示，A、B、C、D四个点，由于其四领域是1点，所以认为是1领域的内部，不算边界点。黑色背景的1组成封闭连续的边界。在边界跟踪的时候，可以使用四领域规则，也可以使用八领域规则。 规则确定以后，就不能变化，否则会有歧义。由于八领域判定边界更为宽泛，本文取八领域规则。
1.2 边界分类及拓扑关系
为了表示和保存边界，需要定义边界的类型和确定边界之间的关系。边界类型可分为外边界和内边界；边界关系关系可分为父边界和子边界。
如图2所示，A1、A3白色部分表示图像中的0像素区域，A2、A4、A5黑色部分表示1像素区域。相邻区域的交界线就是边界。0像素区域包围1像素区域形成外边界，1像素区域包围0像素区域形成内边界。B1、B3、B4为外边界，B2为内边界。外边界的父边界是包围该外边界的内边界，内边界的父边界是包围该内边界的外边界。一个边界和其父边界的类型必然是不同的 。B1是B2父边界，B2是B3和B4的父边界。B1的父边界定义为图像的边框，因为B1是外边界，因此认为图像的边框是内边界。边界关系不可传递，比如，B1是B2的父边界，B2是B3和B4的父边界，B1与B3和B4都是外边界，所以B1不是它们的父边界。
当扫描边界的时候，记录上一个边界和当前边界的类型，也就是内边界还是外边界。如表1所示，根据当前边界与上一个边界的边界类型，可以判断当前边界的父边界。
表1 父边界的判定
图2 二值图像区域和边界关系
2 边界跟踪算法
2.1 八领域寻找边界点算法
搜索二值图像的方法是从上向下、自左向右。如图3所示，按照搜索方向，设置向下为X轴增加方向，向右为Y轴增加方向。设PC为当前边界点，PL为上一个边界点，以PC为中心点，PL为起点，在PC的8领域内寻找下一个边界点。搜索方向可以是顺时针，也可以是逆时针，本文取顺时针方向。
左上角P0点的序号为0，上边P1点的序号为1，依此类推，左边P7点的序号为7。八个领域点的序号依次为0、1、2、3、4、5、6、7。
定义因子weight,当逆时针时取值为-1，顺时针为1。八领域搜索下一个边界点的时候，起始点可取任意一个点，设起始点的序号为start，下一个边界点的序号index，则有关系式：
index = (start + i×weight+8)mod 8
其中i取值为1到7之间的整数。任取start = 3，i = 5，当weight = 1时， index = 0，表示下一个边界点是P0,当weight = -1时，index = 6，表示下一个边界点是P6。
图3 像素点8领域
2.2 边界扫描
如图4所示，黑色矩形是二值图像的边框。要求待搜索的边界位于图像中央位置，也就是边界和图像边框没有共同点。从图像的左上角开始自左向右、自上而下光栅扫描二值图像寻找边界。每一次行扫描，都是从边框开始。图像内一般有多个边界，包括外边界和内边
界。在搜索和记录边界的时候，为了表示方便，需要给边界编号。为了表示边界之间的关系，还需要定义边界的上一个边界的序号。由此，得到边界跟踪的算法步骤：
1、首先定义一个编号为NBD = 1的内边界，表示图像边框；每一行扫描，都是首先寻找一下一个外边界，记录其上一个边界的序号为LNBD = 1。
2、如果扫描到一个边界点的像素值为1，并且前面一个点的像素值为0，则该点是一个新的外边界的起始点，记录该边界的序号为 NBD+1,同时进行边界跟踪。如果扫描到一个边界点的像素值大于1，则该点是已经标记过的外边界，则LNBD取值该像素点的值，然后继续扫描。
3、如果像素点的值大于1，并且右边的值为0。这该点是一个新的内边界的起始点，记录该边界的序号为NBD+1,同时进行边界跟踪。
4、边届跟踪完成之后，记录和保存边界。
图4 光栅扫描
2.3 边界跟踪
在确定边界类型和边界起点之后，首先要跟踪边界，然后要标记边界和保存边界。为了简单起见，在标记边界的时候，直接用边界的序号值对边界像素赋值。如图5所示，两个外边界的序号分别为2和3，在标记的时候，分别把两个边界的像素值记为2和3。
图5 外、内边界标记
边界点的标注，除了方便查看边界的个数之外，对于边界跟踪的起始点的判断，更为重要。根据边界起始点的判断规则，在标注边界点的时候，有如下要求：
1、外边界右边点标注为负的边界序号，其它点标注为边界序号。
2、内边界的左边的标注为负的边界序号，其它点标注边界序号。
这样标注的理由是，外边界的右边点因为是负值，就不再认为是一个内边界的起始点，而外边界的左边点可以认为是一个新的内边界的起始点。内边界的右变点，由于为负值，不等于1，就不会判断为一个外边界的起始点。
3 python实现
3.1 八领域搜索
定义函数find_neighbor(self, center, start, weight=1)，实现八领域下一个边界点判别。其中，center表示当前边界点序号，start表示上一个边界点序号，clock_wise取值为1表示顺时针，-1表示逆时针。该函数实现以当前边界点为中心，从上一个边界点开始，在八领域内寻找下一个边界点。如果
点PC周围的边界点定义为字典neighbors = {0: [-1, -1], 1: [-1, 0], 2: [-1, 1], 3: [0, 1], 4: [1, 1], 5: [1, 0], 6: [1, -1], 7: [0, -1]}。利用for循环，遍历PC周围八领域，对于任意一个网格点坐标[x,y]。
x = neighbors[index ][0] + center[0]
y = neighbors[index ][1] + center[1]
如果点[x,y]处灰度值不等于零，就是下一个边界点。find_neighbor将返回[x,y]的值，如果买有找到边界点，函数返回[-1,-1],表示PC是一个孤立点，孤立点可以看作是一个外边界。
3.2 光栅扫描
定义函数rast_scan(self)实现二值图像扫描。实现的步骤如下：
a) 每一行从图像边框开始扫描，LNBD = 1;
b) 对于每一行像素点，其值grid[i][j]如果大于1，则LNBD = grid[i][j]。
c) 如果grid[i][j]的值为1，grid[i][j-1]的值为0，则grid[i][j]为外边界的起点，其编号为当前编号加1，调用边界跟踪函数，完成一个外边界标注和保存。
d) 如果grid[i][j]的值大于或等于1，grid[i1][j+1]的值为0，则grid[i][j]为内边界的起点，其编号为当前编号加1，调用边界跟踪函数，完成一条内边界标注和保存。
e) 一条边界跟踪完成之后，保存该边界。保存的方法可以是保存起点和序号，也可以保存链码等。
3.3 边界跟踪算法的实现
定义函数board_follow(self, center_p, start_p, mode)实现边界跟踪。实现的步骤如下：
a) 以start_p为起点，逆时针搜索center_p的八领域，查找非零点。如果找不到非零点，函数返回[-1,-1],表示center_p是一个孤立点。孤立点看成是外边界。
b) 如果找到非零点，则该点为边界的终点。以终点为起点，顺时针搜索center_p八领域的下一个边界点nexp_p。然后以center_p为起点，nexp_p为中心点，继续搜索下一个 边界点。依次迭代，最终搜到终点。
c) 不管是外边界，还是内边界，规定向下搜索时，center_p标记为正值，向上搜索时，标记为负值。这标记的目的，是使得外边界的右边为负，内边界的左边为负。这样下一次搜索新边界时，舍去不合适的边界起点。
3.4 python类封装
设计python类封装边界跟踪算法，函数有光栅扫描函数、边界跟踪函数和八领域搜索函数。定义列表存储边界，每一个边界是一个字典，定义如下：
contour = { "NBD": nbd, #当前边界的NBD
"parent": parent, # 父边界的NBD
"contour_type": contour_type, #边界类型：Hole/Outer "start_point": start_point} # 边界起始点
获得边界序列以后，需要打印边界，定义一个函数disp_grid(self)打印结果。在函数中，需要把数字转换为字母。
4 测试及分析
图6 外边界测试结果 图7 内边界测试结果
基于pycharm平台，完成程序算法的测试。如图6所示，一个外边界的跟踪结果。数值2表示外边界的序号为2。左边界点为正2，保证了这些点不再是外边界的起始点，因为起始点的条件是grid[i][j] == 1 并且 grid[i][j-1] = 0。右边界点位-2，保证了
如图8所示，共有9条边界，外、内边界有共同的边界点。由扫描结果可见，对于公共的边界点，后扫描的边界序号不需要覆盖先扫描的边界序号，比如3号内边界只有左边两点值为-3，其上边的序号值没有改变。
如图7所示，3号数字表示内边界序号，和外边界相反，左边数值为-3，保证了下次扫描的时候，这些点不是内边界的起始点，因为内边界起始点的条件是grid[i][j] >= 1并且grid[i][j+1] == 0。点，因为内边界起始点的条件是下次扫描的时候，这些点不是内边界的起始grid[i][j] >= 1并且grid[i][j+1] == 0。
图8 外、内边界测试结果
5 结束语
边界跟踪算法在目标跟踪、自动驾驶等领域中有重要应用。本文对一种基于八领域的连通性边界跟踪算法进行了研究，基于python语言实现了该算法。本算法只适用于连续边界的情况，对于不连续边界，是进一步研究的课题。
参考文献
[1]陈兆学，张奎.一种基于像素标记的二值图像区域围线追踪方法[J] 上海理工大学学报，2019,41(3)：289-292
[2]陈旺,郭庆胜.二值图像中目标物体边界跟踪的一种快速算法及其应用[J],测绘工程,2014,23(12):63–66
[3]韩晓冬,王浩森 ,王硕 ,等 .Python 在图像处理中的应用 [J]. 北京测绘 ,2018,32(3):312-317.
[4] 李雨田,晋小莉.基于图像边界跟踪的顶点矩阵算法[J].计算机工程,2010,36(1):231–232.
[5] 刘相滨，向坚持. 基于八领域边界跟踪标号算法 [J].计算机工程与应用, 2001,37238):125-132
[6] 葛澎．一种快速边缘跟踪与提取新算法［J]，微电子学与计算机2005，22(8) : 14 － 17．
[7] 李西平，王思贤.基于边缘检测技术的字符轮廓线的提取和显示[J].计算机工程与应用,2001, 36(1):52:53-11
[8]崔风魁，张丰收，白露，等． 二值图像目标邻域点法边界跟踪算法［J].洛阳工学院学报: 自然科学版，2001，33( 1) : 24-28．
[9]柳稼航，杨建峰，单新建，等． 一种基于优先搜索方向的边界跟踪算法［J］.遥感技术与应用，2004，19( 3) : 209-213．
[10]王玉琨，魏国军． 图像测量中的边界跟踪算法改进［J］.橡胶工业，2008，55( 9) : 554-556．
