基于改进A*算法的不完整轮廓修复方法

李云青　胡斌梁　彭向前　黄怡静

摘  要：在利用机器视觉对一些冲压、注塑等产品进行产品定位或者检测时，由于产品个体的差异，如模具磨损导致圆角局部过渡平缓等，往往会出现局部轮廓缺失而产生不完整轮廓，导致检测到的产品位置与实际位置存在较大偏差。为了解决局部轮廓缺失引起的位置失准问题，对轮廓修复进行了研究，提出一种极坐标下基于改进的A*算法不完整轮廓修复方法。首先，将轮廓目标转换到极坐标下搜索出断开区域；其次，将完整的轮廓作为先验轮廓，结合先验轮廓与图像灰度特征，改进A*算法的代价函数；最终，对断开区域进行最优轮廓点的搜索，实现了不完整轮廓的修复。实验结果表明，该算法对不完整轮廓修复差异率均不超过8.33%，鲁棒性强。

关键词：定位；不完整轮廓；极坐标；先验轮廓；A*算法；代价函数

中图分类号：TP391    文献标识码：A    文章编号：2096-4706（2023）13-0001-06

Incomplete Contour Repair Method Based on Improved A* Algorithm

LI Yunqing， HU Binliang， PENG Xiangqian， HUANG Yijing

（School of Mechanical Engineering， Hunan University of Science and Technology， Xiangtan  411201， China）

Abstract： In the use of machine vision for product positioning or detection of some stamping， injection molding and other products， due to the differences of individual products， such as mold wear resulting in a smooth local transition of rounded corners， there will often be local contour loss and produce incomplete contour， resulting in a large deviation between the detected product position and the actual position. In order to solve the problem of position misalignment caused by local contour missing， the contour repair is studied and a new incomplete contour repair method based on improved A* algorithm in polar coordinates is proposed. Firstly， the contour targets are converted to polar coordinates to search the disconnection area. Secondly， the complete contour is taken as the prior contour， and the cost function of A* algorithm is improved by combining the prior contour and the image gray feature. Finally， the optimal contour point is searched in the broken area， and the repair of incomplete contour is realized. Experimental results show that the difference rate of incomplete contour repair is less than 8.33%， and the robustness is strong.

Keywords： position; incomplete contour; polar coordinate; prior contour; A* algorithm; cost function

0  引  言

近年來，随着机器视觉技术被广泛地应用在工业检测领域[1]，许多冲压零件、注塑零件也纷纷采用视觉引导下的自动装配技术。但由于冲压件、注塑件的加工精度不一致，导致部分产品的被测轮廓出现退化（实际产品仍为合格品），在用视觉技术对这些产品进行位置检测或定位时，往往会出现局部轮廓缺失的现象，从而导致视觉系统检测到的产品位置与实际产品位置会存在很大的偏差，继而导致出现产品错误装配问题。如图1为某摄像头外形轮廓检测结果图，其中绿色（图1（a）中环线及图2（b）中上方半环线）为检测到的轮廓图，图1（a）为完好产品在进行预处理后得到的正常八边形轮廓检测效果，检测到了完整的八边形轮廓；图1（b）为轮廓退化产品进行相同预处理过程后得到的不完整八边形轮廓效果，只检测到了上半部分轮廓，由此检测到的产品与图1（a）中检测到的中心位置之间出现了很大的偏差。图1（c）为某一方形垫片的检测轮廓，轮廓中心实际应当在中心位置，但在出现轮廓缺失之后，所检测到的中心位置与实际中心位置相比也出现了很大偏差。因此，常规的检测算法如比较经典的Sobel算子、Canny算子等轮廓提取算法[2-4]都不能解决这种由轮廓缺失造成的检测失准问题。

针对轮廓缺失引起的不完整轮廓检测问题，兰传琳[5]将目标轮廓的几何形状先验生成轮廓模板，然后匹配初步检测到的不完整轮廓和轮廓模板的关键点，最后根据相应的关键点的坐标对轮廓模板进行优化，得到完整的轮廓，但对于小面积区域经常检测不到轮廓；雷靖[6]利用Y事件生成算法，采用了两类Y事件来分别修复轮廓缺失，但是对于非水平方向上大范围的轮廓事件缺失的处理结果还不理想。尹高飞[7]在目标识别后采用加入形状先验知识的主动轮廓模型对目标进行轮廓恢复，能有效地修正目标提取结果中的轮廓缺失，但是需要足够的先验形状库来保证轮廓恢复的精确性。

为了进一步解决轮廓缺失引起的不完整轮廓下检测不准确的问题，本文提出一种极坐标下的基于改进A*算法轮廓修复方法。首先将图像轮廓转换到极坐标下，检测其中的局部轮廓断开位置；其次，建立先验轮廓模型，将完整的轮廓作为先验轮廓，结合先验轮廓与图像灰度特征对A*算法进行改进；最后，对断开区域进行最优轮廓点的搜索，对节点的邻域点进行代价比较，取代价最小的邻域点作为新的节点，将节点置为轮廓点，并继续对新节点的邻域点进行代价比较，直到搜索完断开区域；最终，连接所有的轮廓点，实现了不完整輪廓的修复。

1  算法原理

首先，将图像坐标转化为极坐标[8]，在极坐标系下判断目标轮廓有无断开，搜索出断开区域；然后，使用完整轮廓建立先验轮廓，由于本文研究的应用场景在工业检测中，每类产品检测中光照环境基本不变，待检目标放置固定，故不需要太多先验轮廓，只需确定1个完整轮廓作为先验轮廓即可，这样也降低了算法复杂度，提高了检测效率；其次，在A*算法[9]的基础上，结合图像灰度信息和先验轮廓改进A*算法的代价函数，并搜索断开区域的最优轮廓点，将断开区域的起点作为节点，对节点的5个邻域点进行代价比较，取最小代价的邻域点作为新的节点，继续对节点的邻域点进行代价比较，更新节点直到搜索完断开区域；最后，将节点作为轮廓点，连接所有的轮廓点，修复断开区域的缺失轮廓。

1.1  极坐标转换

极坐标系相较于笛卡尔坐标系，可以将旋转部分转移为平移部分，如图2所示，经极坐标转化[10]之后，图像轮廓由原来的环形转化为一条直线。

笛卡尔坐标转化极坐标式如下：

式中：PDi（xi，yi）表示以图像中点为原点的笛卡尔坐标系下的轮廓点，Pi（ρi，θi）表示PDi（xi，yi）

转化的极坐标，ρi表示极径，θi表示极角。

轮廓点在笛卡尔坐标系下，横坐标与纵坐标形成不了单一的映射关系，而在极坐标下将轮廓点映射到[0，2π]上，极径与极角形成了单一的映射关系，且灰度值没有发生变化[11]，可实现从上往下遍历图像，简化了闭合轮廓的计算过程；在笛卡尔坐标系下，环形边缘的灰度梯度变化以法线方向为主，与

X，Y方向存在角度差，极坐标系下环形边缘附近的梯度变化可直接以ρ方向为主，减小了计算量[12]。

如图3所示，根据图像目标像素尺寸461×485，目标径向长度在200像素左右，在转化后的极坐标系，以0.5°为一角度单元，对极坐标图进行扫描，如果某个区域Jl（ ρ ∈（ρl1，ρl2），θ ∈（θl1，θl2））没有搜索到连续的轮廓点，那么则判定该区域为轮廓缺失区域，区域Jl的两端点分别为Pl1（ρl1，θl1），Pl2（ρl2，θl2）。

1.2  基于改进的A*算法的轮廓修复

A*算法是启发式算法中的一种，主要由实际代价和估计代价两部分构成，通过总代价最低在两点之间选择一个最优路线[13，14]。如图4所示，检测对象虽然存在轮廓缺失，但是在边缘附近的灰度变化明显且图像具有网格化，将缺失区域的两个端点作为起点和终点，在先验轮廓和缺失区域的灰度特征的基础上改进A*算法的代价函数。

首先，构造A*算法在本文轮廓修复中的代价函数：

式中：F表示估价函数；点Kb （，）表示K（ρk，θk）的5个邻域点之一；G（Kb）表示起点Pl1到Kb的实际代价函数；H（Kb）表示Kb到终点Pl2的估计代价函数，Pi（ρi，θi）为先验轮廓曲线C上的点；gray（K）表示节点K的灰度值，gray（Kb）表示节点K的邻域点Kb的灰度值；设定一条直线L经过Kb与终点Pl2，P0表示过Kb垂直于直线L与先验轮廓曲线C的交点。

式（2）为估价函数，需要将实际代价G（Kb）（即起点Pl1到点Kb的代价）和估计代价H（Kb）（即点Kb到终点Pl2的代价）相加作为估价F，对节点K的5个邻域点Kb计算估价F并取最小值作为最终的估价F。

式（3）为实际代价函数，边缘处往往灰度值变化较大[15]，为了使找到的轮廓点更符合目标实际轮廓，引入灰度梯度，梯度越小表示越接近边缘即实际代价趋近最优。

式（4）为估计代价函数，传统的A*算法采用曼哈顿距离作为估计代价，为了使修复的轮廓点变化更符合先验轮廓的曲率，如图5所示，以点Kb表示垂足，作垂直于直线L的垂线交于先验轮廓上的P0，为了尽可能利用先验轮廓的特征，故设步距为1对先验轮廓取点，将P0与Pl2范围内的先验轮廓点Pi到直线L的距离和作为估计代价，距离和越小表示点Kb越接近先验轮廓，即估计代价最小。

由图3中完整轮廓极坐标图和不完整轮廓极坐标图可知，极径和极角属于单一映射关系，从断开区域的起点到终点的搜索方向为从左向右，对节点K周围8邻域点中左上、左、左下三个方向的搜索属于无效搜索，故只取图6中的5个方向进行搜索。将断开区域的起点Pl1作为算法搜索的第一个节点K，取其中估价值最小的邻域点Kb作为新的节点K，继续计算节点K的5个邻域点并取估价F最小的邻域点Kb作为新的节点K，继续计算节点K的5个邻域点并取估价F最小的邻域点Kb作为新的节点K，直到断开区域的终点Pl2作为新的节点K。搜索完断开区域后，将节点作为最优轮廓点并连接所有的节点，最终修复整个目标的轮廓。

2  实验效果

通过实验来验证本文算法效果，本文算法采用C++语言编程，Visual Studio 2017编译器编译，基于运行内存12 GB，Windows 10 X64平台下运行。对不同角度轮廓缺失的摄像头模组外壳的冲压件进行检测，结果如图7所示。

从修复不同角度区域不完整轮廓的实验结果看，如表1所示，本文算法能修复缺失的轮廓，对各个角度区域具有较强的适应性，修复轮廓与先验轮廓相比曲率差异率最大不超过8.33%，表明修复的轮廓接近先验轮廓，由于在估计代价部分结合了先验轮廓信息，轮廓较平滑，节点突出较少，估计代价函数设计效果较好。

对方形垫片（图8（a））进行外围轮廓检测，方形垫片左下部分较亮而右上部分较暗，从垫片的二值图（图8（b））可看出，最外围轮廓缺失了大部分，无法检测到完整的轮廓；在使用本文算法之后，从效果图（图8（c））可看出，修复的轮廓贴近其真实轮廓，曲线无突出节点，效果较好。

对三角形的目标（图9（a））进行检测，直接进行轮廓提取之后，检测出的三角形中心位置出现了较大偏差（图9（b））；使用本文算法之后，即使在断开区域角度范围较大的情況下也能较好的修复轮廓（图9（c））。

综合以上实验结果，在检测不完整轮廓的目标时，本文算法能较好地修复目标完整轮廓，能适应不同断开区域的角度范围，即使断开区域较小也能修复成功，鲁棒性较强，能修复不同形状的目标轮廓。

3  结  论

为了解决局部轮廓缺失引起的位置失准问题，本文提出一种极坐标下基于改进的A*算法不完整轮廓修复方法，该方法先将目标轮廓转化到极坐标下并搜索断开区域，将完整轮廓作为先验轮廓，利用先验轮廓与断开区域的灰度特征改进A*算法，在断开区域中搜索节点并将节点作为轮廓点，搜索完成之后连接所有轮廓点，最终修复断开区域的轮廓。实验结果表明，该算法能修复不同角度缺失的目标轮廓，对不同形状的目标轮廓也有较好的修复效果，但本文算法针对边缘外凸的环形目标轮廓修复，只对5个方向进行轮廓点的寻优，虽然节省了计算量，但是有些角度范围会出现盲区，后续在研究中会进一步完善。

参考文献：

[1] 刘明.基于机器视觉的漆包线点焊定位及焊点质量检测研究 [D].广州：华南理工大学，2021.

[2] 韦德鹏，陈继清，罗天，等.基于改进八方向Sobel算子的图像轮廓提取方法 [J].现代电子技术，2022，45（19）：54-58.

[3] YANG Y，WEI L. Grey Relevancy Degree and Improved Eight-Direction Sobel Operator Edge Detection [J].信号与信息处理：英文，2021（2）：012.

[4] RONG W，LI Z，WEI Z，et al. An improved Canny edge detection algorithm [C]// IEEE International Conference on Mechatronics & Automation. IEEE，2014.

[5] 兰传琳，方佩章，何楚.基于先验模型优化的无人机遥感图像中几何轮廓目标检测方法 [J].电视技术，2019，43（1）：5-10+65.

[6] 雷靖，张平，徐江涛，等.一种基于AER图像传感器的目标完整轮廓提取方法 [J].南开大学学报：自然科学版，2020，53（2）：62-67.

[7] 尹高飞，肖鹏峰，吴桂平，等.基于先验形状的人工目标识别与轮廓恢复 [J].遥感信息，2011（6）：8-12.

[8] 张国敏，殷建平，祝恩，等.基于极坐标区间运算的2D形状匹配 [J].计算机研究与发展，2008（S1）：286-290.

[9] WANG R L，LU Z Z，JIN Y F. Application of A* algorithm in intelligent vehicle path planning [J]. Mathematical Models in Engineering，2022，8（3）：82-90.

[10] XIE E，WANG W，DING M，et al. PolarMask++： Enhanced Polar Representation for Single-Shot Instance Segmentation and Beyond [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2022，44（9）：5385-5400.

[11] 欧锁阳，冯琦，张堃.一种融合对数极坐标映射和归一化割的图像分割算法 [J].计算机应用研究，2012，29（10）：3990-3992.

[12] 丛军，张辉宇，谢建，等.基于对数极坐标变换的X射线焊缝缺陷图像识别算法 [J]焊管，2022，45（2）：39-43.

[13] 陈晓宏，储飞黄，方胜良，等.基于剖分网格改进A*算法的航迹规划研究 [J].电光与控制，2022，29（7）：17-21.

[14] 王卫翼，张秋菊，陈中杰.基于图像处理和改进A*算法的激光切割路径生成方法[J].现代制造工程，2014（10）：95-99.

[15] 张金波.灰度图像的边缘检测算法研究 [D].南京：东南大学，2019.

作者简介：李云青（1998—），男，汉族，安徽宣城人，硕士研究生在读，研究方向：图像处理与视觉定位；通讯作者：彭向前（1980—），男，汉族，湖南双峰人，讲师，博士，主要研究方向：机器视觉和图像处理。

收稿日期：2023-02-13

基金项目：国家自然科学基金（61572185）；湖南省教育厅重点资助项目（19A170）