一种八邻域图像边界追踪改进算法

胡晋山，康建荣，张 琪，刘鹏程，朱铭达

(1.江苏师范大学地理测绘与城乡规划学院，江苏 徐州 221116；2.华中师范大学城市与环境科学学院，湖北 武汉 430079；3.江苏师范大学科文学院，江苏 徐州 221116)

利用形态学方法对图像进行边界检测，只是在图像中定位标记出边界点，为了自动提取各边界线的坐标序列，还需要对检测后的边界点进行边界追踪[1]。传统的边界追踪算法主要有Square跟踪算法[2]、摩尔邻域跟踪算法[3]、径向扫描算法[4]等，这些算法主要用于提取环形封闭边界。其中Square跟踪算法适用范围较窄，无法跟踪八邻域图形边界；摩尔邻域边界追踪算法考虑了图形边界的八邻域关系，但由于其停止准则的局限性，无法跟踪大量的图形轮廓；径向扫描算法实质上是一种新的在给定像素点的摩尔邻域内搜索边界点的方法,其边界追踪停止准则与摩尔邻域边界追踪算法相同。边界追踪算法的难点在于如何确定跟踪方向，较为经典的算法有爬虫法、光栅扫描法[1]、八邻域追踪算法[5]。其中爬虫法和光栅扫描法都需要反复追踪图像局部区域，由于无法准确计算重复跟踪图像次数，往往会使程序陷入死循环；八邻域边缘追踪算法虽然能够单次扫描图像获得目标的轮廓，但无法识别较为狭窄的边界重叠状况，容易将多条重叠的边缘线追踪为单条边缘线，或在重叠交叉处将单条边缘线追踪为多条边缘线。当前国内外专家学者们也在不断研究图像边缘线提取方法，石爽等[6]提出了双层边界区域生长的追踪算法，实现对“厚”边界及断点处的边界跟踪，但是该算法时间复杂度较高；戴激光等[7]提出了一种链码跟踪与相位验证相结合的直线提取方法，该方法仅能在噪声较小的光学图像中实现直线的检测；谭凯等[8]用双阈值判别方法来提取地面激光点云图像的非边缘点、边缘点与噪声点；赵丽科[9]等提出基于链码优先级的直线提取算法，实现了图像中物体边界的直线快速提取。上述这些方法多是专门针对某些应用领域而设计的算法，因此有一定的局限性。本文在分析经典的边界追踪算法原理的基础上，改进基于八邻域边界追踪算法，以解决边界追踪过程中边界间断、重叠、相邻等特殊状况，实现图像边界的自动提取。

1 八邻域边界追踪改进算法

1.1 八邻域

当进行边界追踪搜索时，与当前点所有方向相邻接的像素点称为该像素点的8个邻接像素[10]，如图1所示，设定目标C右侧平行点为0邻域点，按逆时针方向将八邻域点分别标号为0、1、2、…、7。

图1 八邻域

1.2 基于八邻域的边界追踪步骤

边界追踪算法包含以下3个基本步骤：①确定追踪边界的起始点[11]；②选取合适的邻接点搜索机理，进行边界线像素点的追踪及提取；③确定边界线追踪终止准则。

1.2.1 确定边界线起点

本文算法对二值图像从顶端开始从左向右、从上至下逐行扫描，检测到的第一个边界点标定为目标边界线的起点，并停止对图像边界线起始点的扫描。

1.2.2 搜索机理

如图2所示，标定当前像素点为C，该像素点的前一边界点为P，连接PC，并作PC的垂线将八邻域分割为两部分，这样将边界点的检索范围缩小了50%。灰色像素点为待检测的八邻域点，依据图2中PC不同的方向，按顺时针方向依次判断其邻域5个像素点是否为目标边界点，若搜索到某一像素点为目标边界点，则记录该点为当前边界线的边界点，并依据当前像素点与前一个边界点的位置关系继续追踪下一个边界点。

1.2.3 终止准则

(1) 环形边界线追踪终止判断依据。如图3所示，从像素值为1的边界起点开始边界线追踪，顺时针沿黑色虚线箭头的灰色像素点的有序集合即为所要提取目标边界线，当追踪到像素值为2点，正确路径应该为①号实线箭头指向，但是，若按②号实线箭头指向追踪，会追踪到另一组边界，因此，本方法约定，当边缘点追踪至目标边界线起点的八邻域范围内或正好回到起始点，且进入方向与边界线追踪走势相同时，停止目标边界线追踪，环形边界追踪完成。

图2 搜索机理

图3 终止准则(1)

(2) 非闭合边界线终止准则。如图4所示，1点为目标边界线起始点，顺时针追踪至2点时，终止当前边界线追踪，并重新返回起始点1，其顺时针方向边界线的第2个边界点设为当前边界起始点的前一边界点，按逆时针方向追踪直至3点时，停止边界线追踪，并设置3点为此边界线新的起点，结束非闭合边界线的追踪。

图4 终止准则(2)

1.3 整幅图像边界拓扑关系处理

当追踪一幅图像中所有边界线时还需要解决3个问题：首先是不同边界线起始点的定位及标记；然后正确追踪边界线，并获得目标边界线的坐标序列及边界线类型；最后还需处理好边界线的拓扑关系，确保不存在边界线漏跟踪和重复跟踪的现象。由于像素是有宽度的，基于像素追踪边界时，需要考虑由像素组成的边界之间的复杂关系，如孤岛[12]、内外边界[13]等情况。

1.3.1 内外边界标定

如图5所示，图5(a)为原始图像，目视该区域有两条边界，一条为外边界，一条为内边界。图5(b)是在不标定内外边界情况下，基于上文追踪机理获取的边界，其中P1为外边界追踪起点，标定为A的边界线为外边界；因此，当从像素点P2点开始追踪内边界时，只能检测出孤点P2。为此本文借鉴了文献[14]中依据3×3模板划分边界点类型，如图6所示，像素值0、1与X分别表示非目标区域点、目标区域点及未知区域点，边界点C分为三类，分别为：左端点(图6(a))，右端点(图6(b))，尖点(图6(c)行尖点、图6(d)列尖点)。右端点和尖点均有可能成为内边界起始点，因此需要判定边界点被检索的次数。

图5 内外边界标定

本算法约定：①所有边界起始点均标识为未检索点，此种情况只能检索出一条外边界线，如图5(b)所示，忽略外边界线内的孤立点；②所有未被检索过的右端点均可被默认为内边界的起始点；③为避免尖点区域可能出现边界重叠现象，标志可检索2次；④给予每条边界不同的检索标志，若出现重复检索且在不同边界上，判定重叠，同一点检索不能超出两次，以此减少漏追踪、重复追踪现象。

1.3.2 孤 岛

如图7所示，图7(a)为原始图像；图7(c)为正确的边界追踪方式，其中P1为边界A的起始点，P2为边界B的起始点；图7(b)是基于上文边界搜索机理追踪的边界线，在追踪至灰色像素点A时，边界追踪走势出现错误，将两条边界检索为一条边界，这种由于细小像素点连接的区域重叠称为“孤岛效应”。

图7 “孤岛”

为解决孤岛效应，本算法基于Freeman链码进行判别[15]。为每条边界设置特定的边界标志，当一个像素点在同一条边界追踪过程中被追踪2次，首先判定此点是否为起始点，若非起始点，则需判定点类型，若为尖点则可能出现为孤岛现象；然后，依据尖点类型确定处理方式，若为行尖点，则回归该像素点在该边界出现的首次位置，并记录其与前一边界点的走向，若由左向右，则掩去该点的1、2、3邻域点，从右向左则剔除该点的5、6、7邻域的边界点(如图1所示)，继续检索；若为列尖点，同样回归该像素点首次出现的位置，记录其与前一像素点的位置关系，并依据位置关系剔除相应邻域点，从该像素点开始重新检索。该方法从重叠点处断开被检索边界线，依据边界线走向掩膜去掉部分干扰像素，进而达到分离两个边界的目的。

2 试验验证

2.1 算法精度验证

试验选取MPEG7-CE(moving picture experts group)图形库中的4幅图像(如图8所示)进行边界提取测试，将本文算法与摩尔邻域边界追踪算法所得结果进行比较，并将两种结果分别视为2个随机矩阵，求解这2个矩阵的相关系数，结果见表1。从表1可以看出，相关系数接近于1，说明本文提出的算法是正确的。另外由于试验所选4个测试图像相对简单，本文算法计算效率稍高于摩尔邻域边界追踪算法，时间效率差别为毫秒级。

图8 MPEG7-CE图形库模板中的4幅图像

表1 两种算法结果比较

2.2 大范围图像边界提取

本文选取美国国家冰雪数据中心免费提供的北半球2014年9月14日的雪冰产品，空间分辨率为4 km的ASCII数据，时间分辨率为1 d，投影方式为极地方位投影，北极点为投影中心点。鉴于北地群岛区域岛屿较多，冰块与海岸、冰块与冰块之间的距离较短，边缘线的拓扑关系较为复杂，因此本次试验以北地群岛作为目视判别区域，裁剪得到图像网格数量为181×181像素，如图9(a)所示。

图9 北地群岛区域海岸线提取

2.2.1 北地群岛区域海岸线提取

利用形态学边缘检测模型生成以陆地及陆地上积雪为前景色的水陆二值图像(如图9(b)所示)，然后运用本文基于八邻域边界追踪改进算法提取了海岸线(如图9(c)所示)，将图9(c)与图9(a)叠加，从目视解译及边界融合状况发现与实际图像一致，说明改进后的八邻域边缘追踪方法适用于大范围具有复杂拓扑关系的图像边界提取。

2.2.2 北地群岛区域海冰边界线提取

将图9(a)中北地群岛区域图像的冰作为前景色，得到该区域的海冰二值图像，然后运用本文算法追踪海冰边界线。本次试验共提取出13条海冰边界线，如图10(a)所示，13条边界线中有3条孤立的边界线，其余边界线之间拓扑关联。分别将图10(a)中具有代表性的两个边界区域局部放大。其中箭头①指向位置为海冰边界线重叠部位有一个公共点，即为本文所述的“孤岛”现象；箭头②指向位置为海冰边界重叠处的内、外边界标定提取结果。

利用海冰二值图像提取出的边界线只是海冰的包络线，而对于北极通航，往往需要获取北极海冰区域与开阔水域之间的边界，因此还需去除海岸线的影响，将图10(a)海冰边界线与图9(c)海岸线相重叠的部分去除，即忽略为数不多的细碎海冰，最终得到北地群岛海冰边缘线，如图10(b)所示。

图10 北地群岛海水边缘线提取

3 结 语

本文在分析现有边界追踪算法的基础上，提出了基于八邻域边界追踪改进算法，采用Visual C++语言进行编程实现，可以一次性追踪出二值图像目标的准确轮廓线，且能够很好地解决孤岛、边界重叠及内外边界的提取等问题，最后应用试验验证了该算法的正确性，并用实例进行了大范围图像边界线提取的有效性验证。