零件的角点提取及匹配定位

高礼圳，刘书桂，韩振华

(天津大学 精密测试技术及仪器国家重点实验室，天津 300072)



零件的角点提取及匹配定位

高礼圳，刘书桂*，韩振华

(天津大学 精密测试技术及仪器国家重点实验室，天津 300072)

摘要：本文基于三坐标测量机(CMM)设计了一套视觉检测系统，该系统能够对零件实际空间特征信息进行比较全面地提取。针对位于CMM平台上带有角点的零件，利用Harris算子提取从CMM三个不同方位获取的零件图像的角点。对于Harris算子提取到的角点，本文提出一种八链码搜索法和SUSAN区域法相结合的伪角点剔除方法，最后基于立体视觉的原理，提出“距离空间图”匹配算法，将以上3幅图像一一建立匹配关系。实验中多次改变零件在CMM中姿态时，多次实验数据表明本文的角点提取精度与真实角点间仅存在1～2像素的偏差，零件的定位误差为1～3 mm。通过实验验证，角点匹配和定位的稳定性和精度满足要求，具有一定的抗干扰性和实用性。

关键词:三坐标测量机；Harris算子；角点匹配；立体视觉；距离空间图

1引言

在防碰撞系统[1-2]中，零件位姿的判定和定位是进行智能路径规划和自动检测的前提和基础[3-4]，而对于有角点的零件，利用角点信息在零件姿态判定中极其重要，因此角点提取和匹配定位在防碰撞系统中是必不可少的。

角点一般是指图像中亮度变化剧烈的像素点或者指图像中梯度值和梯度变化率都很高的像素点，它反映了图像的局部特征。角点检测是图像处理中的一个关键预处理步骤，常用于图像匹配、运动物体跟踪以及目标识别等方面[5]。现有的特征点提取方法可分为基于模板的特征点检测、基于边缘的特征点检测和基于亮度变化的特征点检测。基于模板的特征点检测算法需要设计复杂的模板，对于复杂图像不适用；基于边缘的特征点检测算法对边缘检测的依赖性很大；而基于亮度变化的特征点检测方法已成为研究热点，Harris、SUSAN和SIFT算法等都属于该类算法[6]。

文献[5]中提出利用双掩膜进行非极大值抑制方法提取角点，但是掩膜设计成为一大难点。文献[7]中利用全局和局部边缘的曲率特性提取角点，对边缘检测要求很高。文献[8]中利用多尺度Harris算法需要在多个尺度上检测角点，但是计算量比传统算法大大增加。目前用于图像匹配的方法主要有两大类[9]:一是基于灰度相关的匹配方法，该方法是对2幅图像的灰度相似度进行计算估计，尽管该算法简单，匹配准确率高，但不适合于光轴之间夹角很大的多个相机间的匹配，且计算量大；另一种是基于图像特征的方法，该方法主要有点匹配、线匹配和面匹配，由于线特征为一维特征，面特征为二维特征，其匹配算法要考虑到的方向、尺度位置等因素受噪声、 遮挡影响较大。而点特征包含图像中丰富的信息，其提取算法是计算机视觉中比较成熟且经典的技术,如Harris算法，SUSAN算法。角点是最常用的目标特征之一，它们常用于图像单尺度下的角点检测。但是实际中由Harris提取到的角点包含很多杂乱无章且包含无用信息的伪角点，这些伪角点主要是由光照和零件上的毛刺所引起的。对于所获得的角点，利用现有的匹配算法[9-12]无法直接建立匹配关系。

针对以上问题，本文提出了八链码搜索法和SUSAN区域法相结合的伪角点剔除方法。该方法利用八链码搜索法删除图像的内部伪角点后，再利用SUSAN 区域法删除位于轮廓上的伪角点，最后基于立体视觉原理，提出“距离空间图”的匹配算法，对留下的角点进行匹配和定位。通过实验证明，本文的伪角点剔除方法和匹配定位算法有较高的精度，具有一定的实用性。

2角点提取和剔除

实验中为避免外部环境的干扰，先用位于CMM[14]3个不同方位的相机分别获取放零件前的背景图像，然后再获取放零件后的零件图像，两图像相减后得到去除背景后的零件图像。对于相减后的图像，经预处理后采用Harris算法[15]提取图像特征点。该方法使用图像的一阶差分来计算每个像素处的平均平方梯度矩阵M，如式(1)。通过特征值分析，如式(2)，给出角点响应。该方法原理简单、运算量小、使用方便。实验中发现可检测性、定位性、稳定性都满足要求，运算速度也较快[5]，但是同时也会检测到很多伪角点。对于所获得的角点，利用现有的匹配算法无法直接建立匹配关系。因此，在匹配前应该把这种伪角点删除，下面将通过以下两个步骤来删除伪角点。

(1)

(2)

式(1)中，矩阵M即为每个像素的平均平方梯度矩阵，I表示了点(x,y)处的像素亮度，*是卷积符号，W是一个3×3高斯低通滤波器。式(2)中，det(M)为矩阵M的行列式，tr(M)为矩阵的迹，k为一个经验值，通常被选定为0.04。R为角点响应函数的值，设定一个合理的阈值条件threshold，当R的值大于此阈值时，此时图像点即为感兴趣的特征点。

2.1内部伪角点剔除

八链码搜索如下图1所示，对于由Harris算法提取的角点，首先从八链码的0方向搜索连续两个大于某阈值的像素点，该阈值可以取该角点像素值的一半。如果能搜到满足上面条件的像素点集，那么再从八链码的1方向搜索，直到八链码的8个方向都能搜索到满足条件的点集，那么这个角点属于内部伪角点。否则如果有一个方向不满足搜索条件，那么停止其他方向的搜索，因为该角点一定不属于内部伪角点。

图1　八链码的方向图 Fig.1　Eight-chain-code direction

2.2轮廓上伪角点剔除

SUSAN算法[16]是由牛津大学的S M Smith提出的，同样也是一种基于灰度的特征点获取方法。其基本原理是通过图像中目标与背景的对比度确定阈值，将模板中的各点与核心点(当前点)的灰度值用相似比较函数进行比较，得到与核心点灰度相近的点的集合区域称为核值相似区(Univalue Segment Assimilating Nucleus，USAN)。实验通过对留下的角点利用SUSAN模板进行搜索，其在轮廓上的角点处的USAN区大于在边缘交线上的角点处的USAN区，由此，响应图像中的角点特征。在实际操作时，对于模板内任一像素点R与模板中心像素N，通过给定的阈值t来判断该像素点是否属于USAN区域，其判别函数为:

(3)

那么以N为中心像素点模板内 USAN区域的大小为:

(4)

式中，S(N,r)表示以N为中心，r为半径的圆形模板，表示模板中USAN区域的大小。然后，将n(N,r)与预先给定阈值G进行比较，由此剔除图像中轮廓上的角点[17]。

3特征点匹配

本实验中，3个相机分别位于CMM三个不同的方位，如下图2所示，相机1位于CMM的正前方，相机2位于CMM的横梁上，相机3位于CMM的左方，各相机与CMM之间的坐标关系已标定。其中零件摆放在CMM的工作平台上，且都在3个相机的视场范围内。本文中设计的视觉系统都能够较大限度地提取零件的三维特征信息，由于3个相机的光轴基本相互垂直，相机之间能够互相约束景深尺寸，可以较大限度地减少视觉系统的定位误差。

图2　相机与CMM的方位图 Fig.2　Orientation diagram of camera and CMM

图3　对极几何约束图 Fig.3　Diagram of epipolar geometry

由于特征点提取不够精确，匹配两图中的对应点成为本文最大的困难。理想情况下，对于图像点x和x′的两条反向投影的射线，如果满足对极几何约束x′TFx=0，其中F为基本矩阵，那么这两条射线共面，从而相交于一个三维点X。但是在实际中，非理想测量点x和x′反向投影的射线在三维空间中一般不共面，如下图3(a)所示，测量点不满足对极几何约束[18]。对极线I′=Fx是过x的射线的像，而对极线I=FTx′是过x′的射线的像。因为射线不相交，x′不在I′上，并且x不在I上，如下图3(b)所示。

图4　多视图确定空间点 Fig.4　Multiple views to determine the point

针对上述出现的问题，本文采用一种新的判定方法，考虑到本实验中防碰撞系统实际应用场合和系统所需精度等，将测量点x和x′反向投影的射线之间的异面距离不超过3 mm作为判定条件，若满足这一条件就判定这两点是匹配点。取两射线公垂线的中点作为三维点X。在双目视图中，这种方法会出现多义性，因为一幅图像中的某个点可能会对应另一幅视图中多个点，如图4(a)所示。这是由重构的多义性引起的[18]，但是在三视图中它不具有多义性。若空间一个点在3幅视图中都有对应点，那么两两视图按上述方法确定一个三维点，这样就可以构成一个三角形，将三角形的重心作为三视图中的三维点X，如图4(b)所示。

图5　距离空间图 Fig.5　Diagram of distance space

从这3幅视图中寻找出对应的匹配点，关键的匹配算法是首先构建“距离空间图”，如图5所示，即3幅视图中的角点两两之间的反向投影射线之间的异面距离构成的三维图。假如视图1、2、3中分别有n1、n2、n3个角点，那么视图1和2之间角点构成的距离关系有n1×n2种，同理视图2和3之间有n2×n3种，视图3和1之间有n3×n1种。然后从“距离空间图”中挑选出距离不大于3 mm的情形。算法首先搜索由3个视图确定一个空间点的情况，接着搜索由两个视图确定一个空间点情况。前面已经验证了由两个视图确定一个点时，会出现多种情形，即一对一、一对多(多对一)的两种情形。图中有标记符的格子表示满足距离不大于3 mm条件的组合。坐标轴上的格子数表示对应视图上的角点数。

本文具体的匹配算法及操作如下所述：

(1)搜索由3个视图确定一个空间点时，搜索方法是在“距离空间图”每一个面上寻找一个标记格，看这3个标记格能否组合成一个闭合通路。若能找到满足闭合通路条件的3个点，说明存在一个空间点在3个视图中都有对应标记点，然后删除这3个格子所对应的行与列，继续重复上述步骤，直到搜索完毕。如下图所示，●符号所表示的是3个视图确定一个空间点的情况。

(2)搜索由两个视图确定一个空间点中的一对一的情况时，只需在“距离空间图”任意两个面中寻找两个标记格，使其满足同行或同列，并且所在的行与列中没有其他标记符，删除这两个标记格所在的行与列，然后重复搜索，直到搜索完为止。■符号对应的是双视图中的一对一的情况。

(3)最后搜索双视图中一对多(多对一)的情况时，搜索方法同一对一的情形类似，只不过一个面中的标记格所在的行或列在另一面中的同行或同列中存在多个标记格，删除满足条件的行与列，然后重复搜索直到搜索完毕。▲符号则是一对多(多对一)的情况。 假如一对多(多对一)的情况有N个，那么会出现2N种组合的解。

4实验结果与分析

实验所用的三坐标测量机为海克斯康制造的Global classic SR 07.10.07。相机1、相机2和相机3的型号为MQ013MG-E2，分辨率为1 280×1 024。相机1和相机3所用镜头型号为VT1614-M2，焦距标注值为16 mm，相机2所用镜头型号为VTS0614-M2，焦距标注值为6 mm。本实验在VS2010平台上用C++语言实现了Harris角点提取，用本文的伪角点剔除方法剔除了内部伪角点和轮廓上的伪角点，并且利用提出的匹配算法成功的实现了特征点之间的匹配。

4.1特征点提取和剔除

实验结果如图6所示。图6(a)、6(b)、6(c)表示Camera 1、2、3得到的零件图像用Harris提取100个角点的图，图6(d)、6(e)、6(f)表示剔除内部伪角点后的角点图，图6(g)、6(h)、6(i)表示剔除轮廓上伪角点后的角点图。从图6中可以看到，最后各视图中的角点定位准确，尽管有些特征点由于遮挡只在一个视图中成像而无法确定该特征点，但这不影响后续的匹配。

图6　角点图像 Fig.6　Corner detection image

4.2角点匹配结果

根据3节中的匹配算法，对处理后的Harris特征点进行匹配，匹配结果如图7所示。

图7　特征匹配结果 Fig.7　Matching result

图7(a)、7(b)、7(c)分别是由Camera 1、2、3拍摄的图片，从图中可以看到，大部分特征点得到正确匹配，但由于有些特征点仅在一个视图中成像，故无法找到这些点的匹配点。多次实验证明，该算法的匹配率达到95%以上。

4.3角点定位

将图7中的四组匹配点①、②、③、④所确定

的角点编号为角点1、2、3、4。表1是各相机的内部参数，(μ0ν0)为主点，f为焦距，k1为径向畸变系数。表2是角点在各视图中的像素坐标(像素大小为0.005 3 mm)，其中“-”表示角点在视图中不存在。表3是各相机与CMM之间的坐标转换关系，α、β、γ分别代表绕X、Y、Z轴旋转，tx、ty、tz分别代表向X、Y、Z方向的平移。对于由两个视图确定的角点，如角点1，将Camera1和Camera3中匹配像点的反向投影射线的公垂线的中点作为三维点X。因此三维点X在CMM中的坐标可通过Camera1和Camera3来求解。对于由3个视图确定的角点，求解可以参考图4(b)。表4是计算得到的角点在CMM中的坐标与用CMM测量得到的坐标。由表4可知，在这4个角点中，x方向最大偏差为1.72 mm，y方向最大偏差为1.88 mm，z方向最大偏差为1.36 mm。定位最大偏差为2.17 mm。

表1　相机内部参数

表2　角点在各视图中的像素坐标

表3　相机与CMM之间的坐标转换关系

表4　定位精度检测

造成表4中数据误差的的主要因素有以下两个：

(1)角点提取不准确

由于光照不均匀和零件本身存在毛刺等因素导致提取到的角点可能与真实角点存在1～2个像素的偏差。

(2)标定误差

本实验中，相机与CMM之间的关系是间接地借助光笔来标定的，先建立光笔与CMM之间的关系，然后建立光笔与相机之间的关系，这种标定方法精度不是特别高，这是测量数据中最主要的误差来源。

5结论

针对Harris算法提取的角点，本文提出了一种八链码搜索法和SUSAN区域法相结合的伪角点剔除方法，利用八链码搜索法剔除内部伪角点和SUSAN区域法剔除位于轮廓上的伪角点。最后在本文提出的“距离空间图”匹配算法下成功实现了匹配，同时对利用角点信息来判定和定位零件的位姿误差进行了分析。实验数据显示，本文提取的角点与真实角点间存在1～2个像素的偏差，且定位误差在1～3 mm范围内。基本满足实验中防碰撞系统提出的误差要求。该方法与其它角点提取和匹配算法相比具有简单、直接、高效等特点。但是该方法只能针对具有明显角点的零件，不适合于像球、圆柱体等具有自由曲面的零件。

参考文献：

[1]马一凡.防碰撞系统中零件识别研究[D].天津：天津大学，2014.

MA Y F. Research on recognition of parts in anti-collision system[D]. Tianjin:Tianjin University,2014.(in Chinese)

[2]王怀瑜.防碰撞系统中体素相交检测算法的研究[D].天津：天津大学，2014.

WANG H Y. Research on an algorithm of primitive intersection detection in an anti-collision system[D]. Tianjin:Tianjin University,2014.(in Chinese)

[3]刘书桂,赵金才,李建苹,等.智能坐标测量系统中零件位姿自动识别[J].天津大学学报,2006,39(10):1241-1246.

LIU SH G,ZHAO J C,LI J P,etal.. Automatic recognition for position and orientation of parts in intelligent coordinate measuring system[J].J.TianjinUniversity,2006,39(10):1241-1246.(in Chinese)

[4]马新辉,张国雄,王建利,等.智能三坐标测量机中零件位置自动识别系统[J].仪器仪表学报,2003,24(2):165-170.

MA X H,ZHANG G X,WANG J L,etal.. Autamatic recognition for the position and orientation of parts in intelligent CMM[J].ChineseJ.ScientificInstrument,2003,24(2):165-170.(in Chinese)

[5]房超,王小鹏,牛云鹏,等.基于改进Harris算法的角点检测[J].计算机与数字工程,2011,39(5):142-144.

FANG CH,WANG X P,NIU Y P,etal.. Corner detection based on an improved Harris algorithm[J].ComputerandDigitalEngineering,2011,39(5):142-144.(in Chinese)

[6]乔警卫,胡少兴.三维重建中特征点提取与匹配算法研究[J].系统仿真学报,2008,20:400-403.

QIAO J W,HU SH X. Research on feature point extraction and matching in 3D reconstruction[J].J.SystemSimulation,2008,20:400-403.(in Chinese)

[7]黄凤山,刘恩福,方忆湘,等.基于智能三坐标测量机的零件位姿单目立体视觉识别[J].光学 精密工程,2013,21(5):1326-1332.

HUANG F SH,LIU E F,FANG Y X,etal.. Single camera stereo vision recognization for parts pose based on intelligent three coordinate measuring machine[J].Opt.PrecisionEng.,2013,21(5):1326-1332.(in Chinese)

[8]许佳佳.结合Harris与SIFT 算子的图像快速配准算法[J].中国光学,2015,8(4):574-581.

XU J J. Fast image registration method based on Harris and SIFT algorithm[J].ChineseOptics,2015,8(4):574-581.(in Chinese)

[9]高晶,吴育峰,吴昆,等.基于角点检测的图像匹配算法[J].仪器仪表学报,2013,34(8):1717-1725.

GAO J,WU Y F,WU K,etal.. Image matching method based on corner detection[J].ChineseJ.ScientificInstrument,2013,34(8):1717-1725.(in Chinese)

[10]程德志,李言俊,余瑞星.基于改进SIFT算法的图像匹配方法[J].计算机仿真，2011,28(7):285-289.

CHENG D Z,LI Y J,YU R X. Image matching method based on improved SIFT algorithm[J].ComputerSimulation,2011,28(7):285-289.(in Chinese)

[11]全燕鸣,黎淑梅,麦青群.基于双目视觉的工件尺寸在机三维测量[J].光学 精密程,2013,21(4):1054 -1061.

QUAN Y M,LI S M,MAI Q Q. On-machine 3D measurement of workpiece dimensions based on binocular vision[J].Opt.PrecisionEng.,2013,21(4):1054-1061.(in Chinese)

[12]田浩南,张叶.基于边缘及特征点匹配的立体图像质量评价[J].液晶与显示,2015,30(4):666-672.

TIAN H N,ZHANG Y. Quality evaluation of stereo image based on edge and characteristic point matching[J].ChineseJ.LiquidCrystalsandDisplays,2015,30(4):666-672.(in Chinese)

[13]刘书桂,余飞,韩振华.基于OpenCasCade的虚拟三坐标测量机碰撞检测方法[J].纳米技术与精密工程,2016.

LIU SH G,YU F,HAN ZH H. Collision detection of virtual coordinate measuring machine based on OpenCasCade[J].NanotechnologyandPrecisionEngineering,2016.(in Chinese)

[14]张国雄.三坐标测量机[M].天津:天津大学出版社,1999.

ZHANG G X.CoordinateMeasuringMachine[M]. Tianjin:Tianjin University Press,1999.(in Chinese)

[15]HARRIS C G,STEPHENS M. A combined corner and edge detector[C]. Proceedings of the 4thA Ivey Vision Conference,Manchester,UK,1988:147-151.

[16]SMITH S M. Feature based image sequence understanding[D]. Oxford,UK:Oxford University, 1992.

[17]王付新,黄毓瑜,孟 偲,等.三维重建中特征点提取算法的研究与实现[J].工程图学学报,2007,3:91-96.

WANG F X,HUANG Y Y,MENG C,etal. Research and realization of the feature point extraction algorithm in 3D reconstruction[J].J.EngineeringGraphics,2007,3:91-96(in Chinese)

[18]HARTLEY R,ZISSERMAN H.计算机视觉中的多视图几何[M].安徽:安徽大学出版社，2002,8:216-217,178-179.

HARTLEY R,ZISSERMAN H.MultipleViewGeometryinComputerVision[M]. Anhui:Anhui University Press, 2002,8:216-217,178-179.(in Chinese)

收稿日期:2016-04-05；

修订日期:2016-04-26

基金项目：天津市自然科学基金重点资助项目(No.13JCZDJC34500)

文章编号2095-1531(2016)04-0397-08

中图分类号：TH744.3

文献标识码:A

doi:10.3788/CO.20160904.0397

作者简介：

髙礼圳(1991—)，男，江西吉安人，硕士研究生，主要从事图像处理和计算机视觉方面的研究。E-mail：gaolz1002@163.com

刘书桂(1954—)，男，湖南人，教授，博士，博士生导师，主要从事智能坐标测量技术、自动测量与控制技术方面的研究 。E-mail：sgliu@tju.edu.cn

Corner extraction and matching location of parts

GAO Li-zhen, LIU Shu-gui*, HAN Zhen-hua

(StateKeyLaboratoryofPrecisionMeasuringTechnologyandInstruments,TianjinUniversity,Tianjin300072,China)*Correspondingauthor,E-mail:sgliu@tju.edu.cn

Abstract:In this paper, a set of visual inspection system is designed based on three coordinate measuring machine(CMM), and the new visual system can extract the actual spatial feature information of the parts. For the parts with corner which is on the platform of CMM, the Harris operator is used to extract corners in the images obtained from three different orientation of the CMM. For the corner points extracted by the Harris operator, this paper proposes a method of eliminating the false corners, which combines eight-chain-code false corner search method and SUSAN method. Finally, based on the principle of stereo vision, the “Distance spatial map” matching algorithm is put forward, and then the three images are matched one by one. Although the position and orientation of parts are changed for many times in the experiment, the experiment results show that there are 1-2 pixels difference between extracted corners and the real corner points, and the position error of parts is 1-3 mm. Through the experiment, the accuracy and stability of corner matching and positioning can meet the requirements, and with anti-interference and practicability as well as.

Key words:CMM;Harris operator;corner matching;stereo vision;distance spatial map

Supported by Key Project of Natural Science Foundation of Tianjin City(No.13JCZDJC34500)