基于圆弧基元的工件实时定位与匹配方法

周 晴，吉 峰，白瑞林

ZHOU Qing1,JI Feng2,BAI Ruilin1

1.江南大学 轻工过程先进控制教育部重点实验室，信息与控制实验教学中心，江苏 无锡 214122

2.无锡信捷电气股份有限公司，江苏 无锡 214072

1.Key Laboratory of Advanced Process Control for Light Industry（Ministry of Education）,Information and Control Experiment Teaching Center,Jiangnan University,Wuxi,Jiangsu 214122,China

2.Xinje Electronic Co.,Ltd,Wuxi,Jiangsu 214072,China

1 引言

机器视觉定位技术[1]具有非接触，速度快，稳定性好，精度高，抗干扰能力强，易于维护等突出优点，广泛应用于工业缺陷检测、工件定位、产品分拣、机器人视觉引导技术、军事航天等领域中。

L.Gottesfeld[2]等人基于模板与图像之间差值的绝对值的总和或者所有差值的平方和（SAD或SSD）提出了基于灰度的图像匹配算法，基于灰度的模板匹配，算法耗时多，不适于快速匹配定位；Lowe[3]、H.Bay[4]等提出了基元特征点的匹配算法，算法匹配精度高，但是无法满足实时性的要求；Steger等[5]提出一种以边缘为特征的匹配方法；倪健等[6]采用一种以边缘的方向向量为相似度量的匹配方法，该方法对遮挡、混乱等情况有比较好的鲁棒性，但算法耗时相对较多。G.Borgefors等[7]提出了一种基于模板边缘与图像边缘之间的距离的方法来匹配定位，为基于几何基元本身的匹配提供了匹配依据。Chen等[8]提出了一种将模板物体与搜索图像中的轮廓线分割为线段，然后匹配特殊线段的方法来实现匹配定位，然而分割方法没有涉及到圆弧。此外，还有诸多实例利用Hausdorff距离[9-10]、LOG算子[11]、局部不变量[12]等特征，并采用遗传算法、PSO算法[13]等方法来实现匹配定位。

基于上述分析，本文提出了一种基于圆弧基元的工件实时定位与匹配方法。通过递归算法将边缘轮廓多边形近似，通过基元的合并将轮廓分割为线段和圆弧基元。以最长圆弧基元计算模板的刚性变换，通过计算测试图像几何基元与变换后的模板中对应的几何基元之间的距离来实现匹配定位。试验表明，该算法对于单目标或者多目标，目标是否被遮挡，是否具有复杂的背景等情况下都能快速准确地定位出目标。

2 系统方案

基于圆弧基元的工件实时定位与匹配方法的整体过程的系统方案如图1所示。

图1 模板匹配示意图

离线过程制作模板，将工件的轮廓分割为线段基元和圆弧基元，计算得到它们的几何参数，并确定模板的位姿以及各基元之间的关系。在线匹配过程，将实测图像中以相同的算法求得几何基元。匹配算法如图2所示，通过最长圆弧基元的粗定位，以及各基元的角度、相对距离来实现匹配定位。

图2 在线匹配算法

3 模板制作过程

基于圆弧基元的工件实时定位与匹配方法，离线模板制作过程，采用背光照射，使用智能相机采集图像，手动截取工件所在的区域为ROI区域。对ROI区域处理进行Otsu法二值化，提取单像素边缘轮廓，并跟踪边缘轮廓。通过多边形拟合以及合并相邻基元，将边缘轮廓分割成线段基元和圆弧基元，并确定模板方向以及各基元之间的关系。

3.1 轮廓跟踪

图像的轮廓跟踪，即边界跟踪[14]，即在ROI区域的边界像素依次检测并记录下来。将轮廓点坐标存入序列数组 Pi=(ri，ci)，i=1，2，…，n 。为了正确跟踪8-连通域（如图3所示）边界单像素宽度目标的边界，设初始方向dir=5，按8-连通域的顺序搜索边界点，当搜索到边界点之后需要更新搜索的起始方向dir，若当前的dir为斜角方向，则dir=(dir+6)%8（其中%表示取余数），否则，dir=(dir+7)%8。如图4中，p2的搜索起始方向为2。

图3 8连通域示意图

图4 跟踪方向示意图

3.2 多边形近似

轮廓的所有边缘点表示为：Pi=(ri，ci)，i=1，2，…，n，算法将轮廓用一个多边形近似表示。在边缘轮廓上确定一个控制点集：pij，j=1，2，…，m，m≤n，此子集可以非常好地描述该轮廓[15]。

在最大距离位置的轮廓点处，将当前线段分为两条线段。重复上述步骤，直到所有线段满足最大距离约束条件，即得到轮廓的多边形近似。

3.3 线段与圆弧基元的拟合

多边形近似方法仅将轮廓分割为线段，而在应该是圆弧基元处，多边形近似的结果将圆弧基元分割为多段线段基元。因此需要检查彼此相邻的线段，判断是否可以用圆弧来近似这个基元。

将轮廓边缘分割为线段基元和圆弧基元，首先判断当前基元属于线段基元还是圆弧基元，本文通过基元长度作为一个判断，若基元长度大于阈值T1（人工设置），则其为线段基元，不需要合并，使用最小二乘直线拟合算法求得它的几何参数。若小于阈值T1，则合并与它相邻的基元，使用最小二乘圆弧拟合算法求得几何参数。

（1）直线拟合

式（1）、（2）计算得到了线段基元的参数 k，b。

（2）圆弧拟合和合并

取相邻基元，与当前基元合并，得到的新基元使用最小二圆弧乘拟合，求得半径R′，若两个半径大小很接近，则合并这两个基元为一个圆弧基元，取下一个基元重复上述判断。

3.4 创建模板

在离线创建模板的过程中，需要记录模板中各基元的相关信息以用于匹配定位。模板位姿用于计算刚性变换角度，圆弧圆心到各基元的距离是用于匹配定位的判据。

（1）模板位姿

在模板基元中按基元的长度，找到最长圆弧基元，得到圆弧的圆心O(x1，y1)，将圆心位置作为模板的位置。

圆心O(x1，y1)与最长圆弧对应的弦的中点 M(x2，y2)，通过这两点来确定模板的方向θ，与X轴的夹角表示，θ即表示模板的方向。

（2）圆弧圆心到模板各基元的距离

3.5 模板示意图

如图5所示，给出了一个分割边缘轮廓为线段基元和圆弧基元的例子。图5（a）为采集到的灰度图像，图5（b）为经过迭代多边形近似算法将轮廓分割为线段形式，从图中可知，一段圆弧基元被分割成4段线段基元，图5（c）为经过圆弧拟合与合并步骤，4段线段拟合合并为一段圆弧基元，图5（d）显示了该段轮廓的分割结果，由3段线段基元和1段圆弧基元组成。

图5 模板示意图

4 在线匹配过程

基于圆弧基元的工件实时定位与匹配方法，在线匹配过程，首先对实测图像采用同离线过程相同的方法，将边缘轮廓分割为线段基元和圆弧基元；接着利用最长圆弧基元，确定实测图像中的潜在匹配点，并计算模板与实测图的刚性变换，基于这个刚性变换，通过计算实测图像中几何基元与变换后的模板中的几何基元之间的距离来匹配剩余基元。

表1 算法检测结果

4.1 刚性变换

（1）刚性变换角度

实测图中满足条件的圆弧基元，拟合得到它的圆心O′(x3，y3)，以及圆弧对应的弦的中点 M′(x4，y4)。计算实测图中潜在目标的角度θ′，计算方法如下：

通过与模板的比对，计算刚性变换角度Δθ=θ′-θ。

（2）模板的刚性变换

已经计算得到模板图像与实测图像的刚性变换角度Δθ，对于模板中的其他基元需要变换基元的角度。计算公式为：α=θ0+Δθ；其中θ0表示模板图像中基元的角度。

4.2 匹配基元

在实测图像的边缘轮廓中，轮廓被分割为线段基元和圆弧基元，逐基元检查是否有满足基元角度为α的基元；若满足角度条件，则检查该基元相对于实测图像中圆弧圆心的距离，如公式（3）所示。

在模板中的对应基元到模板圆弧圆心的距离d，两者之差在阈值范围（一般为5个像素点）之内，说明当前基元匹配模板中基元。若超出阈值，则当前基元不匹配。

5 试验测试

针对各种类型工件图像进行仿真试验，算法满足工业现场实时、准确的要求。下面以一组图像为例，算法的运行环境为Intel Pentium®CPU E6700 3.2 GHz/2 GB内存。

算法使用的模板图像为图5（d），待检测的图像如图6所示，对应的检测结果如图7所示。

图6 待检测图像

图7 匹配结果

如图6（a）所示，具有单个目标，且目标背景复杂，有干扰物体，如图7（a）显示，本文提出的算法检测到了模板中的3个线段基元和1个圆弧基元，该算法能够准确定位出工件的位置以及相对模板的旋转角度；如图6（b）所示，具有多个目标，且目标的部分被遮挡，还具有无关物体的干扰等外界影响，本文提出的算法能够准确定位出实测图像中的2个目标，如图7（b）所示，其中一个目标的一个线段基元被部分遮挡，该算法能准确定位出未被遮挡的部分。如图6（c）所示，在图6（a）的基础上加上高斯噪声，如图7（c）显示，本文提出的算法依然能检测到模板中的3个线段基元和1个圆弧基元。算法测试的结果如表1所示，并与文献[6]提出的方法进行比较，匹配过程所用时间没有包括边缘跟踪耗时。

6 结论

本文提出了一种具有圆弧几何基元的实时定位与匹配方法，在模板图像中，提取图像的轮廓边缘并进行多边形近似，并分割成线段或者圆弧基元，拟合出它们的几何参数，通过最长的圆弧确定模板的位姿。在实测图像中，通过检查最长的圆弧，得到潜在匹配位置，减少了搜索次数；以模板图像与实测图像中基元之间的距离来匹配定位对应的基元。通过大量对比分析，本文方法不仅匹配定位准确，而且时间较少，在实时应用方面具有较大的意义。

[1]Steger C，Ulrich M，Wiedemann C.机器视觉算法与应用[M].杨少荣，吴迪靖，段德山，译.北京：清华大学出版社，2008：238-345.

[2]Brown L G.A survery of image registration techniques[J].ACM Computing Surveys，2004，24（4）：325-367.

[3]Lowe D G.Distinctive image features from scale invariant keypoints[J].International Journal of Computer Vsion，2004，60（2）：91-110.

[4]Bay H，Ess A，Tuytelaars T，et al.Surf：Speeded up robust features[J].Computer Vision and Image Understanding，2008，110（3）：346-359.

[5]Steger C.Similarity measures for occlusion，clutter，and illumination invariant object recognition[C]//Radig B，Florczyk S.Proc of Pattern Recognition，23rd DAGM-Symposium，2001：148-154.

[6]倪健，白瑞林，李英，等.采用轮廓向量特征的嵌入式图像匹配方法[EB/OL].（2012-10-11）.http：//www.cnki.net/kcms/detail/11.2127.TP.20121011.1019.023.html.

[7]Borgefors G.Hierarchical chamfer matching：a parametric edge matching algorithm[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1988，10（6）：849-865.

[8]Chen J M，Ventura J A.Segmentation of planar curves into circular arcs and line segments[J].Image and Vision Computing，1996，14（1）：71-83.

[9]张文景，许晓鸣，苏键锋，等.基于Hausdorff距离的2D形状匹配改进算法[J].中国图象图形学报，2000，5（2）：106-109.

[10]王红涛，傅卫平，康业娜，等.工件图像识别的边缘匹配方法研究[J].仪器仪表学报，2008，29（5）：986-991.

[11]王民钢，王超，樊英平，等.基于LOG算子的小信息量图像匹配算法[J].计算机工程与应用，2012，48（29）：191-195.

[12]吴文欢，李骞，江泽涛，等.基于局部不变特征的图像匹配算法[J].计算机工程与应用，2012，48（14）：168-170.

[13]Liu X，Jiang W，Xie J，et al.An image template matching method using particle swarm optimization[C]//PACIIA’09，2009：83-86.

[14]刘相滨，邹北冀，孙家广.基于边界跟踪的快速欧式距离变换算法[J].计算机学报，2006，29（2）：317-323.

[15]Ramer U.An iterative procedure for the polygonal approximation of plane curves[J].Computer Vision Graphics and Image Processing，1972，1（3）：244-256.