改进FAST-SURF算法在卷烟包件识别定位中的应用

张 毅，王彦博，高奇峰，杨德伟，魏 博

1.重庆邮电大学 先进制造工程学院，重庆400065

2.重庆邮电大学 自动化学院，重庆400065

1 引言

工业机器人广泛用于物流分拣、码垛等工业任务[1]，而拾取和放置目标物体是工业机器人的重要任务之一。大部分工业机器人的抓取仍停留在预先描点后重复工作的层次。这样的工作方式对环境的稳定性要求极高，不能应对突发的变化。而在烟草物流的码垛装配中，由于客户订单的复杂性和随机性会导致数量不同的条烟包装成形状不同的卷烟包件，卷烟行业要针对不同条数的卷烟包件有着一套特殊的码放规则以利于码放的稳定性同时避免条烟的损坏，因此对卷烟包件码垛系统的实用性、智能化要求较高。凭借视觉系统对卷烟包件进行识别与定位，从而提高系统的鲁棒性和实时性来应对突发的情况。近年来，视觉识别定位在工业上的应用也越来越广泛。机器视觉识别在工业机器人在抓取和放置功能等方面仍面临着时效性不够的问题[2]。在这一问题上，很多人做出了成果。2016年，陈剑虹，韩小珍提出结合FAST-SURF和改进k-d树最近邻查找的图像配准[3]，匹配精度有一定提高，但时效性稍低。2017年，储蓄对基于改进SURF算法图像匹配方法研究，提高了SURF算法检测的速度[4]，但在后续定位中处理较为复杂，难以达到时效性。本文在前人工作的基础上，提出采用改进的FAST-SURF算法，以双目立体视觉[5]的方式对目标卷烟包件进行识别然后定位。首先通过改进的FAST算法检测可能的特征点，而后将特征点通过Haar小波生成特征向量，FLANN算法搜索待匹配特征点[6-7]，欧式距离匹配[8]，RANSAC算法剔除误匹配对，实现对目标物体的匹配[9]。根据图像匹配的结果与标定得到的内外参进行定位。与基于SURF特征的目标识别相比，本文提出的方法更能满足卷烟包件码垛系统实时性的要求，实验结果证明了本文方法在目标物体匹配定位中的可行性。

2 基于SURF特征的目标识别

SURF算法[10]是一种高鲁棒性的局部特征点检测器，是由Herbert Bay等人在2006年提出的。SURF特征具有尺度、旋转等不变特性，因此常用于图像拼接、三维建模、视频跟踪、目标识别等。该算法采用积分图像和近似的Hessian矩阵运算提高运算速度，使用Haar小波变换增加鲁棒性。

2.1 Hessian矩阵提取特征点

SURF算法通过计算图像像素点的Hessian矩阵提取图像特征点，这需要图像和高斯函数做卷积运算。根据卷积运算性质，图像与高斯函数的卷积可以转化为积分图像与高斯二阶倒数模板的卷积运算。

SURF算法采用盒子滤波器近似高斯二阶偏导数，最终获得了近似的Hessian矩阵，通过改变盒子滤波器的模板大小建立尺度图像金字塔。Hessian矩阵的行列式的局部最大值点即为特征点[11]。

2.2 Haar构建特征描述符

对提取到的特征点，建立特征向量对其进行描述，SURF算法在特征点圆形区域内同构Haar小波响应确定一个主方向，使特征向量具有旋转不变性，再以特征点为中心，构建正方形区域，经过Haar小波响应最终生成一个64维的特征向量。

2.3 最近邻域特征匹配

对于参考图像与待匹配图像特征点的匹配，SURF算法采用最近邻域匹配方法[12]，首先计算待匹配图像上的特征点特征向量到参考图像上所有特征点特征向量的欧氏距离[13]，得到一个距离集合，其次通过对距离集合进行比较运算得到最小欧氏距离d1和次最小欧氏距离d2，即：

式（1）中，T为设定阈值，一般为0.6。当最小欧式距离d1和次最小欧式距离d2的比值小于该阈值时，认为特征点与对应最小欧式距离的特征点是匹配的，否则没有点与该特征点相匹配。

3改进的FAST-SURF算法

改进前的流程图对比和改进后的流程图对比如图1所示。

图1 流程图对比

3.1 改进的FAST检测

FAST算法主要包含非特征点检测、特征点检测、非极大值抑制三个步骤：

（1）传统的FAST检测从图片中选取一个像素点P为圆心，半径为3像素的离散化的Bresenhan圆，圆的边界有16个像素，如图2所示。本文改进的FAST检测算法如图3所示。

图2 FAST特征点示意图

图3 待检测点示意图

由图2可以看出，传统的SURF检测是IP与周围16个像素点进行比较（IP为P点灰度值）。因像素点较多，检测对比的时间较长。因此本文利用图3的阴影区域（编号1～12）的内部像素点进行检测，能达到检测的效果，也减少了检测的时间。t为阈值，检测原则是连续9个像素点都比Ip+t大或者比Ip-t小，则该像素点为特征点候选点。

（2）待检测的点周围的一圈像素的灰度值与候选的点的灰度值差别够大，可以认为这个候选点是一个特征点，在二维图像中的任意一点圆心坐标( x,y)。特征点描述算法公式如下：

式（2）中，t为阈值，其中定义圆周上任意一点的灰度为Ix，圆心的灰度为Ip。当中心像素的灰度值IP小于周围圈点x处像素灰度值Ix+t时，则认为该灰度像素属于更暗的，则SP→x=d；以此类推相似的s和更亮的灰度像素点b。这样在一个以候选特征点p为圆心的圆形区域边缘就找到了三种类型的灰度像素点d、s和b。统计d或b的次数，如果大于n（当分割测试点数目为9时，即Ix的个数的3/4），则认为该点为候选特征点。然后通过固定半径圆上像素的灰度值进行比较获得候选特征点。利用ID3分类器，根据12个特征，判断此候选特征点是否为特征点。将上面的步骤获得d、s、b的记为Pd、Ps、Pb，计算得到的SP→x必定对应式（2）的某种情况。令IP为特征点时kp=true，否则false，从而判定某个像素是否为特征点。

（3）最后，对特征点进行非极大值抑制，得到特征点输出。

关于本算法中阈值t的值取为55，取值论证在实验部分描述。

3.2 改进FAST-SURF算法

正本文将得到的FAST检测子进行主方向的选取。首先，以特征点为圆心做一个半径为6s的圆形邻域（s即特征点的尺度值），然后计算区域内像素点的水平方向和垂直方向的加权Haar小波响应[14]。

如图4所示，左侧为Haar小波在x方向上的响应，右侧为Haar小波在y方向上的响应。将高斯权重系数赋予响应值，令越靠近特征点的Haar小波响应的权值越大，然后用一个60°的扇形模板遍历整个圆形区域，得到多个Haar响应的构成的累加矢量，矢量最长的方向即为特征点主方向[15]。最后计算每个特征点，获得所有特征点的主方向。

图4 Haar小波响应

沿着特征点方向构造以特征点为中心，边长为20s的正方形区域。如图5所示，然后对该区域实现等间隔采样（采样间隔为s），并将其化为成4×4=16个子区域，在每个子区域采样5×5个点。计算所有子区域的Haar小波响应。

图5 特征描述符生成过程

将每个子区域的d x、d y、| d x|、| d y|相加，其中d x、d y分别表示Haar小波在x和y方向的相应。获得四维特征描述向量V：

将16个子区域的V组合在一起，获得16×4=64维特征描述向量，即生成了SURF描述符。对于参考图像与待匹配图像特征点的匹配，SURF算法采用最近邻域匹配方法，得到的结果较准确，但搜索速度慢。本文采用基于FLANN算法进行特征搜索。通过最近欧式距离和次近欧式距离的比值同给定的阈值T来判定是否匹配。阈值T通常取0.4～0.8，阈值越大匹配点数越多，但匹配正确率会降低，本文取0.6。

3.3改进RANSAC算法

经过欧式距离匹配后的匹配点对仍会存在错误匹配的情况，在本视觉系统中提出了一种改进的RANSAC算法用以消除。利用准确匹配点间相对斜率相同的关系来剔除误匹配点。设(Ai,Aj)和(Bi,Bj)是处理后的图像A和待匹配的模板图像B两两正确的匹配对。那么Ai和Bi的绝对斜率k(Ai,Bi)应该相等于Aj和Bj的绝对斜率k(Aj,Bj)。基于以上原理，利用参考图像A中的Ai与它自身中所有的特征点Aj的斜率关系和待匹配图像B中的Bi与它自身中所有的特征点Bj的斜率关系的相似性评价两点对应关系，提出如下的评价函数：

其中R(i,j)表示Ai,Bi与各自图像每个兴趣点斜率的相对差异；K(i,j)表示Ai,Bi与各自图像每个兴趣点的评价斜率。

经过改进的RANSAC算法去除误匹配对后，可以看到误匹配点对有明显的消除，这样模板图与目标处理图实现了精确的特征点配对。

4 双目定位

4.1 双目定位理论

双目视觉定位技术的原理是模拟人类双目感知距离，实现对物体三维空间位置的测量，是机器人视觉研究的一个重要内容[16]。首先用两个摄像头对同一物体从不同位置成像，然后从视差中修复距离信息，其中视差是指左、右观测点在观看目标物体时所产生的偏差，视差会受到观测点与被目标物体之间距离的影响[17]。三维空间内的点能否在图像中出现实际上取决于成像过程中的“视线”，如果一个对象被两个视点观测到，首先利用两幅对应的图像，计算出空间点在两幅图像中像素点之间的位置偏差，然后由几何原理计算出目标物体的三维坐标值。本文将两个相同相机平行放置，对卷烟包件进行测量与图像采集。平视双目立体视觉定位原理图如图6所示。

图6 三维重建原理图

在平视双目立体视觉中，两个相机拥有完全相同的内部参数，平行放置且有一对坐标轴共线，因此两个相机的光轴互相平行而且成像平面共面。假设左相机C1的相机坐标系为O1X1Y1Z1，右相机C2的相机坐标系为O2X2Y2Z2，相机焦距均为f，两个相机的光心距离为d。对于任意一个空间点P，在相机坐标系C1和C2中的坐标分别为(x1,y1,z1)、(x2,y2,z2)，P点在左、右相机拍摄到的图片中的图像坐标分别为(u1,v1)、(u2,v2)。可知，在得到空间中点P在双目视觉系统中两个二维图像中的像素坐标，就可以重建P点的三维坐标。

4.2 双目定位

在卷烟包件的智能码垛系统的定位过程中，需要获取的是卷烟包件形心坐标。由于工业场地有限，本系统采集图像的方式是水平拍摄。根据图像匹配的结果与标定得到的内外参，计算获得所有匹配特征点的三维坐标。由于匹配特征点近似均匀分布，所以将所有特征点的三维坐标进行平均运算，得到近似平面形心坐标。卷烟包件的烟包长度已知为270 mm，将获得的近似平面形心坐标的Y轴值加上烟包长度的一半135 mm，即获得卷烟包件的近似形心坐标。

5 实验及结果分析

5.1 相机标定

进行匹配实验之前要先对摄像机进行标定[18]。本实验搭建的双目平台由两摄像机组合而成，1号相机焦距6.764 mm，2号相机焦距6.758 mm，相机距离约195 mm。采用Halcon13、opencv2.4.9等软件作为开发工具。实验电脑参数如下：I5-3210处理器，CPU频率为2.5 GHz，RAM容量为2 GB，64位操作系统。

根据实际场景与实验条件，本实验采用170 mm×170 mm的标定板，如图7所示。

图7 标定

左右摄像机同时采集六组空间位置不同的标定板图像，采用Halcon对双目立体视觉系统进行标定，标定结果如表1所示。

完成相机标定后，对图像进行校准，目的是消除透镜畸变并使双目图像的成像平面在同一平面且严格对齐彼此的行扫描线。

5.2 阈值t的确定

实验对缩小、放大、旋转的情况下，改变本文算法中的阈值，根据三种情况的匹配结果来确定阈值t的值。

实验在缩小（远距离）、放大（近距离）、旋转（顺时针90°）下的情况，各采集两幅图像，在三种不同的情况，对阈值进行讨论实验。实验具体数据如表2所示。从实验数据可以得出结论：在大体上，整个匹配时间随阈值的增大而减小，而正确匹配率随阈值的增大而减小。在阈值t=55时，在缩小、放大、旋转三种情况下，匹配时间较短，且匹配正确率较高。因此，本算法将阈值t的值定为55。

表1 摄像机标定结果

表2 三种情况下阈值变化与时间、正确匹配率的关系

对采集的原图像用Halcon软件进行校准，校准后的图像如图8所示。

图8 校准后的图像

为了验证FAST-SURF方法对目标物体的匹配的可行性，完成摄像机标定和校准后，采用FAST-SURF、SURF、参考文献[3]中的SURF改进算法进行目标匹配。

5.3 目标匹配

在将校准后的图像用三种算法匹配，得到的匹配结果如图9～11所示。

图9 FAST-SURF算法

通过三种不同算法的匹配实验，可以得到实验结果。匹配结果对比表明：本文算法表现良好，速度快，正确率高；SURF算法匹配效果稍差，速度略慢，且正确匹配率相对较低；他人算法匹配效果良好，但是匹配速度和正确率不如本文算法。实验的具体数据如表3所示。

图10 文献[3]算法

图11 本文算法

表3 三种算法结果比较

5.4 目标定位

对于卷烟包件，其长度（即条烟的长度）和宽度（即五条烟的宽度之和）是固定的。得到的不规则卷烟包件平面中心点的三维坐标就可以得到不规则卷烟包件整体的三维坐标，得到的三维坐标与实际三维坐标对比分析如表4所示。

从以上数据可以得出，在烟包条数不同的情况下，本文算法误差在8 mm以内，平均定位时间约0.7 s，优于FAST-SURF算法和SURF-RANSAC算法，而且本文算法误差的波动范围小，适用于卷烟包件的智能码垛系统中。

表4 算法对比定位结果

5.5 鲁棒性测试

在鲁棒性实验中，主要测试了旋转形变、噪声干扰及亮度变化这三个方面的影响。所有测试的图像集均是相同的，最后通过获取的匹配点数量和匹配点对的正确匹配率来评估各算法的鲁棒性。

5.5.1 旋转不变性

图12（a）所示为旋转不变性测试曲线图，可以看出：本文改进的FAST-SURF算法和SURF-RANSAC算法在图像旋转中具有一定的鲁棒性，且两种算法对几乎全部旋转图像都能够获取较多的匹配点，而文献[3]中的FAST-SURF算法虽然也具备一定的鲁棒性，但对于部分图像获得的匹配点较少。所以，在图像旋转匹配的鲁棒性测试中，本文算法和SURF-RANSAC算法更具优势，且本文算法更加稳定。

5.5.2 干扰鲁棒性

图12（b）、（c）所示分别为高斯噪声鲁棒性测试曲线图和光照强度变化的鲁棒性测试曲线图。可以看出三种算法对于噪声干扰和光照变化均具有强鲁棒性，而且本文算法即使在各种干扰较为严重的情况下，仍然可以获取一定数量的匹配点对。因此，本文算法在鲁棒性测试中相对于另两种算法有一定改进。

除此，本文根据差错率曲线描述算法匹配率的横坐标，查全率描述为算法匹配率的纵坐标来论证各算法的鲁棒性，查全率及差错率定义如下：

图12 FAST-SURF算法

图13 算法性能对比

图13（a）～（c）分别为旋转变换、噪声干扰以及光照变化条件下差错率与查全率曲线图，可以看出各项结果与图12接近，在旋转变换中，本文算法和FAST-SURF算法查全率相当但优于SURF-RANSAC算法，匹配的精度也更高。在噪声干扰下，本文算法与SURF-RANSAC算法相似但好于FAST-SURF算法，这是因为本文算法对图像的缩放保持不变性。图13（c）为亮度变化条件下的图像匹配，可以看出三种算法很接近且对非线性光照变化不敏感。

由于本文算法以Harr描述符的特征方向为参考方向对其采样点进行坐标变换，使其对图像旋转具有较好的不变性。并优化FAST算法，快速提取图像重复率较高的特征点。最后，通过改进的RANSAC算法，剔除误匹配点对，提高匹配精度。因此，本文算法在鲁棒性测试中更具优势。

图14分别给出了图像匹配鲁棒性实验的匹配实例。结果表明本文算法的鲁棒性较强，可以很好地满足码垛系统中的应用。

图14 鲁棒性测试匹配效果图

6 结语

本文针对卷烟包件在智能码垛中的识别定位问题，提出了一种基于改进的FAST-SURF算法的双目目标识别定位方法。通过将FAST的16个点降低为12个点进行比较，减小了FAST的检测时间，采用FLANN算法搜索特征点进行粗搜索，与最近邻算法相比，搜索精度略微降低，但速度更快，利用欧式距离匹配后，用改进RANSAC算法来剔除FLANN算法粗搜索带来的误匹配，实现了左右图像的优质匹配，并利用卷烟包件形状规则和其匹配特征点近似均匀分布的规律计算得到不规则卷烟包件的形心位置。本文在卷烟包件识别定位的速度和正确率上都有一定提高且具有良好的鲁棒性，实验验证了本文方法的可行性，具有一定的实用价值。