改进的摩尔邻域图像边缘追踪算法及应用
作者： 葛雷
关键词：摩尔邻域；边界追踪；终止准则；尺寸标注
中图分类号：TP391.9 文献标识码：A
文章编号：1009-3044（2024）28-0034-03
0 引言
随着计算机与人工智能技术的快速发展，人们对图像处理领域的研究愈发深入，针对图像的噪声检测与去除、图像深度恢复、图像增强、图像轮廓的识别和追踪等方面的研究备受关注。近年来，关于图像的自动尺寸标注在生产与生活中的应用也日益增多。例如，宗加飞[1]等提出将尺寸标注技术应用于机械工业生产中，采用计算机视觉进行图像的检测与尺寸的标注，相较单纯地采用人工视觉检测的方法，具有更高的准确性和检测速度，从而有效地提高了生产率。
在图像尺寸标注工作中，一个关键步骤是寻找图像的轮廓，所涉及的算法称为边界追踪算法。目前，主流智能手机中的“测距仪”具备对图像尺寸进行标注的功能，其基本原理是摄像头测量目标两端的距离，手机内置的陀螺仪测量目标两端的角度值，然后运用三角函数计算出目标的长度。然而，这一功能存在两方面的局限：一是该测距功能仅适用于测量近处的物体，如果目标物体距离较远，通过“测距仪”测出的长度误差会较大；二是测距仪需要人工手动校正物体的两端，因此其准确性和精确性与手工校正有较大关联，测量的随机误差较大。
Square追踪算法是近年来备受关注的边界追踪算法之一[2]，它可以实现对简单图形的边界追踪，但其适用范围有限，不能提取边缘变化较多的图形轮廓。本文在分析传统Square追踪算法的基础上，提出了一种改进的基于摩尔邻域的边界跟踪算法，可以解决图像追踪过程中无法提取复杂图案完整外边界的问题，并将其应用于图像的边界处理，进一步实现了图形的自动尺寸标注功能。
1 问题提出
1.1 物体尺寸标注的一般流程
传统的尺寸标注方法采用人工检测的方式，存在检测效率低、精度差的缺点，同时长时间的测量易导致质检员视觉疲劳，测量误差增大。因此，采用计算机视觉通过图像处理的方式对物体尺寸进行自动标注，特别是在大批量物体的尺寸测量中，展现出测量效率高、误差小、成本低的优势，其应用范围广泛。
尺寸标注的一般流程[3]：
1） 使用摄像头采集图像，并通过相应的软件从计算机上读取目标图像。
2） 对读取的图像进行预处理，操作步骤包括：灰度处理、高斯滤波、腐蚀、膨胀、边缘检测等。
3） 在提取图像边缘的基础上寻找图形轮廓。
4） 计算各个轮廓的中心点坐标。
5） 设置参照物，计算实际尺寸与像素尺寸的比例，据此求出实际尺寸，并显示结果。
1.2 传统Square 边界追踪算法
Square追踪算法是提取二值图像中边界信息的基本算法之一[4]，其应用涉及像素点的4邻域，其对图形边界的提取流程如下：对于给定的数字图像（图像由像素组成，这里用像素说明），即在网格上以白像素为背景的一组像素，需要确定一个边界像素起始点（黑色），定位起始像素点有许多方法；在这里，从左下角的像素开始，扫描每行像素，从下往上、从左向右进行直到遇到第一个黑色像素，选定这个像素为起始点。算法将从该起始点出发，展开后续的边界追踪工作，其步骤如下：
1） 若搜索时位于黑色像素点上，则向左进入相邻的像素点。
2） 若搜索时位于白色像素点上，则右转进入相邻的像素点。
3） 搜索过程直到再次遇到起始点时终止。
4） 整个搜索过程中经过的黑色像素所连成的边界即为数字图像的边界。
然而，该追踪算法存在明显的缺陷[5]：不能追踪现实生活中复杂图形的轮廓，其性能存在一定的局限性。原因在于：向左或者向右转时会错过当前像素点对角线侧的像素，即性能上具有只对特殊邻接性图形有效的弱点，Square边界追踪算法对具有8邻域而不是4邻域模式的图形边界无法实现有效的追踪。失败案例如图1所示。
1.3 边界追踪算法步骤
通过对传统Square追踪算法的观察，发现图像尺寸标注工作中一个关键步骤是如何寻找图形轮廓[6]，其涉及的算法为边界追踪算法，首先对图像进行基本的处理：1） 图像灰度化以提高运算速度。2） 图像二值化，二值化过程可以大大减少图形中的数据量，使目标轮廓更加凸显。
边界追踪算法的一般步骤总结为：
1） 确定边界的起始点，并从该点出发展开搜索，搜索方式可以是从左往右、自下而上等。
2） 确定边界点的判别方式以及搜索准则，判别方式用来判断该点是否为边界点，搜索准则用来对下一个边界点展开搜索。
3） 确定终止条件，这将影响边界追踪的结果是否为一个完整的轮廓。
为了提高边界追踪的成功率，在以上下左右四个方向为基础的4邻域上加入对角领域拓展至顺时针8 领域，运用摩尔邻域追踪的思想对原算法进行改进。
2 改进的摩尔邻域追踪算法
对于给定的像素p，其摩尔邻域是一组与原像素共享边或顶点的像素集合，即在原来上、下、左、右的基础上加上了左上、左下、右上、右下4个对角元素，将原来的4邻域扩展至包含对角邻域的8邻域，又被称为间接邻域。
该算法对图形边界提取的流程如下：
1） 确定一个起始像素点，定位起始像素的方式很多，可以从网格的左上角开始，从上而下以及从左往右扫描每一列像素，直到遇到第一个黑色（边界）像素点，将该像素点作为起始像素点。
2） 每次遇到黑色像素，将其设置为边界点。然后原路返回到先前到达的白色像素，以顺时针方向搜索摩尔邻域内的每一个像素，直到遇到下一个黑色像素。
3） 重复步骤2） 的过程，当起始像素被第二次访问时，算法终止，在整个运行过程中经过的黑色像素即是数字图案的边界。
摩尔邻域边界跟踪算法是8邻域搜索过程，对比边界追踪算法的一般步骤，其弱点在于停止准则的选择。参照图2，如果该停止准则选取不当，算法将无法有效对图形的完整轮廓进行追踪。因此，对停止准则的优化会有效提升摩尔邻域边界跟踪算法的整体性能。
我们可以采用以下的优化方式去改进原摩尔邻域边界跟踪算法的停止准则：第二次搜索至起始像素点时，进入该点的方向与第一次相同时停止。图2中的追踪过程虽然再次回到起始点，但过程中遗漏了大部分的边界像素点，其原因在于没有满足停止准则。图3在图2的追踪结果上继续展开边界追踪，直到满足停止准则为止。通过对比图2与图3的结果，改进后的算法有效地提高了摩尔邻域跟踪算法的执行效果。
分析图2与图3区别的原因：摩尔邻域追踪算法在检查当前边界像素点的摩尔邻域时，相比4邻域搜索方式更加全面且有效，能够更准确地找到下一个边界像素点。对于传统Square跟踪算法向左右两边转时忽略了对角侧的像素点问题，摩尔邻域跟踪算法提取到的图案外边界更加完整。因为摩尔邻域为8邻域搜索方式，这将导致其搜索的下一个边界像素点总是位于当前像素点的摩尔邻域内。当算法两次以相同的方向追踪到起始像素点，这表明算法已追踪完图案完整的边界。如果算法没有终止，则会再次重复追踪该像素点。
3 基于改进摩尔邻域的边缘追踪算法实验效果与实际应用
3.1 实验效果
为了进一步验证采用基于改进摩尔邻域的边缘追踪算法与Square追踪算法对不同图像进行轮廓追踪的效果，在Windows 环境下，本文采用PyCharmCommunity Edition 2022.2.2 作为软件工具，选用3 幅图像图4（a）、（b）、（c）展开实验对比验证。
对图4进行以下步骤的处理：
1） 读入彩色图像，并引入gray_img函数实现彩色图像灰度化。
2） 调用get_binary_img函数实现图像二值化。
3） 展开边界追踪，过程中调用了canny边缘检测函数、findcontour轮廓提取函数、drawcontour轮廓绘制函数等。
在原摩尔邻域边界跟踪算法停止准则的优化方面，调用Python中math包的sin（）函数模块。具体步骤如下：
1） 导入math包，使用math.radians（）方法将边界起始点与终止点之间的角度转换为弧度。
2） 计算弧度的正弦值并判断其值是否等于正负1。如果是，则终止搜索；反之，则从该边界点继续展开追踪。
图5 展示了分别对图4 中3 幅不同图像执行Square追踪算法进行轮廓追踪的效果。明显地，图5（e）和（f）的边界追踪存在严重缺失。
图6展示了分别对图4中3幅不同图像执行本文提出的基于改进摩尔邻域的边缘追踪算法进行轮廓追踪的效果。图6中的3幅子图完美保留了原图4中图像的完整外边界轮廓。
3.2 实验结果分析
对比图5和图6的执行结果可以得出：
1） 对于如图4（a）所示的边界清晰、变化简单的图形，Square追踪算法的轮廓提取效果较为理想。
2） 对于轮廓边界变化复杂的图形，如图4（b）、（c），Square追踪算法只能追踪到图形的局部外边界。
3） 本文提出的改进摩尔邻域追踪算法可以提取边界变化复杂图形的完整轮廓。
3.3 算法的实际应用
进一步将改进的摩尔邻域追踪算法运用于实际图片的边界追踪，并进一步实现自动尺寸标注，具体操作步骤如下：
1） 运用基于改进摩尔邻域的边缘追踪算法提取目标图像的边界轮廓。
2） 定义图像中物体所占的像素数与物体实际比例的关系，根据参照物的实际长度与宽度，调用pixel_per_cm函数计算单位长度中的像素个数。
3） 计算被测物体轮廓的最小外接矩形。如果等轮廓是圆，找出与轮廓拟合的中心和最小半径来计算最小外接矩形；如果等轮廓不是圆，在轮廓的顶点上循环，获取当前和前一个顶点的坐标，求这两个顶点的中点，重复此过程将轮廓拟合成圆以计算最小外接矩形，循环过程中调用minAreaRect（）与boxPoints（）函数，并获取4个顶点的坐标。
4） 调用Width与Height函数，根据4个顶点与单位长度中像素的个数，计算测量物体的长度与宽度。图7（a）和（b）是物品原图和运用改进的摩尔邻域追踪算法进一步进行图像自动尺寸标注的结果图。
表1列出了图7（a）中展示的5种物品的真实尺寸与利用本文提出的基于改进的摩尔邻域追踪算法进行边界自动检测并完成尺寸标注的结果，其中相对误差是真实值和测量值的误差与真实值的比值。
分析表1中的尺寸标注结果和相对误差，可以发现自动尺寸标注的结果比较接近真实值，算法有效。个别物品的测量相对误差较大，这与原始图片的清晰度与像素也有关联。
4 结束语
本文提出的改进摩尔邻域边界追踪算法适应当下关于尺寸标注越来越广泛的技术应用现状，针对传统的Square追踪算法在提取复杂图形轮廓方面的局限性，提出由传统以上、下、左、右4个方向为基础的4 邻域拓展至加入对角邻域后的8邻域追踪方式。在此基础上，从优化终止准则入手，着重解决了图像追踪过程中无法提取复杂图形完整外边界的问题，并进一步将算法运用于实际物品的自动尺寸标注中。实验结果表明，本文提出的摩尔邻域改进算法对实际物体图形尺寸能够进行有效的标注。