基于改进SURF特征点的模板匹配算法

吴清辉

（广州市威控机器人有限公司，广州 511340）

0 引言

随着智能制造技术的发展，机器人的智能性越来越受到关注。目前大多数机器人都是面对固定环境，重复完成固定任务，例如机器人抓取物体等。为了更好地引导机器人完成特定任务，机器视觉技术被越来越多地应用到机器人领域。其中目标识别[1－4]能够帮助机器人检测场景中的待抓取物体，在机器人抓取领域[5]有着重要的应用。目前来说针对图像的目标识别问题算法主要有模板匹配以及图像分割等，而其中由于基于特征点的模板匹配算法[6－9]涉及的参数相对较少，只需要在所获得的图像中搜索到之前已经确定的匹配项就可以识别出目标物体，这种类型的算法不仅简单有效，而且有较强的鲁棒性和可扩展性，运用也相对灵活。而其中SURF算法[10－11]在倾斜场景和缩小场景的提取较为稳定，并且实时性较好，已成为广泛使用的特征点提取算法之一，但其描述子构建在匹配过程中易存在误匹配的问题。基于此本文采用DAISY算法[12－13]构建特征描述符来代替SURF原本构建特征描述符方法，并采用PROSAC算法[14－15]进行误匹配点删除，结合上述两种算法的优点提高匹配过程中目标识别的准确性。

1 基于改进SURF特征点的模板匹配目标识别算法

基于模板匹配完成目标识别的基本思路是在摄像机采集到的图像上找到和之前已经确定的模板相近的对象，大致过程如下：

（1）生成与目标物体对应的模板图像；

（2）采用某种算法对得到的模板图像进行处理和训练，构建出模板图像对应的模型；

（3）根据构建出的模板模型来找出待检测图像，也就是摄像机获得的图像上的与模板相似或者一致的目标。

前两步已经有着较好的实现，而第三步匹配精度仍有待提高。传统的SURF特征点能够在一定程度上缓解这一问题，因此该算法具有大量的应用，然而SURF算法虽然一定程度上兼顾了实时性和稳定性，但是实时性并不是太高，而且由于SURF算法描述子的局限性，在模板匹配过程中存在有一些误匹配的情况，从而对目标识别造成影响，本文采用如下方法对SURF算法进行改进。

首先采用DAISY算法构建特征描述符来代替SURF原本构建特征描述符方法，该算法核心思想是采用一种将原始图像的若干个方向图与数个尺度不一的高斯滤波函数进行卷积的方法，由于高斯滤波函数具有可分离性，因此该方法具有较高的效率；其次在模板匹配过程中利用PROSAC算法进行误匹配点删除，PROSAC算法的核心是将样本集中的点预先进行等级排名，能估计出正确模型的内点有更高的等级，对估计模型起到阻碍作用的外点具有较低的等级，然后选出等级较高的点集来对模型进行估计，这样可以减少算法采样的随机性，提升获得正确模型的成功率，从而降低算法迭代次数。

2 算法说明

2.1 SURF算法

在SURF算法中，生成特征点描述子的过程可由图1所示，在提取出的关键点周围生成一个由4×4共16个矩形块构成的矩形区域，其中每一个矩形块的分辨率为5×5，即由25个像素点构成。将矩形区域旋转至主方向后（主方向为提取关键点过程中计算得到），统计各个子矩形块中像素点相对于主方向的水平方向和竖直方向的haar小波特征[16]，这里的haar小波特征共包含4个方向，分别为水平梯度、竖直梯度、水平梯度绝对值之和以及竖直梯度绝对值之和。经过上述过程后，可以统计得到20×20个像素邻域内的各方向分布，以此作为该关键点的描述子。从上述过程中可以看出由于该过程需要统计每个关键点周围20×20共400个像素点的haar特征，其描述子向量维度一共有400×4＝1 600维，计算量较大，导致SURF算法较为耗时。

图1 SURF算法说明

2.2 DAISY算法

本文提出采用DAISY算法替代SURF算法过程中生成描述子的过程。DAISY算法主要思想如图2所示，对于每一个关键点，以该关键点为中心构建3层半径不同的同心圆，在每一个同心圆上以45°为单位间隔，取8个点作为采样点，这样总共得到了3×8＋1＝25个采样点，针对每一个采样点，取8个不同方向的梯度，这样就能获得25×8＝200维的特征向量来描述该关键点的描述子。从上述过程中，可以看出一方面用于描述关键点的描述子向量维数大大降低了，并且在取采样点的过程中，由于外圈的梯度可以通过内圈的梯度利用高斯卷积推算出来，这使得计算量大大降低了，同时由于采样点均匀分布在同心圆上，描述子具有一定的鲁棒性，不会降低匹配的精度。因此本文采用DAISY算法作为SURF算法的描述子提取过程。

图2 DAISY算法说明

2.3 PROSAC算法

在特征点匹配过程中，由于存在外点（无法适应该匹配模型的数据），如果两帧图像的外点匹配上，那么会引入大量噪声，对后续任务造成较大影响。传统方法主要采用RANSAC算法[17]，其算法流程如下：

（1）首先根据两幅图像中提取的特征点生成匹配点对，从中随机选取4个匹配点对；

（2）利用4个匹配点对计算出这两幅图像的变换矩阵H；

（3）利用变换矩阵H对所有的特征点做变换，如果变换后的特征点与第二帧图像中对应的特征点距离小于一定阈值，则将其加入到满足一致集合C中，即内点集合；

（4）如果当前的一致集合元素个数大于最优的一致集合元素个数，更新当前最优一致集合；

（5）重复（2）～（4）过程，直至迭代终止，迭代终止条件为迭代次数达到最大迭代次数k，计算如下：

式中：p表示置信度，通常取0.995；w表示内点比例；m为取的匹配点对数，取4。

从上述步骤可以看出RANSAC算法忽略了匹配点对的优劣性，由于匹配点对集合中有着匹配度契合的点对，也有匹配度较差的点对，如果在集合中随机采样，如果取得了较差的匹配点对，那么将会浪费很多时间。因此本文采用了PROSAC算法，PROSAC算法相较于RANSAC算法改进有两个方面，首先对匹配点对的优劣性进行排列，取匹配度高于一定阈值的点对作为假设生成集，在假设生成集中进行随机采样。这样针对匹配过程中的PROSAC算法过程则是在RANSAC算法过程中进行了一步预处理操作，即多了一步生成假设生成集的过程。有了该过程的加入后，可以避免匹配度低的点对的计算量，大大提高了该算法的计算过程。并且，由于是在较优的匹配点对中选取，可以使得模型整体匹配效果大大提升，避免了噪声及局外点对匹配模型的影响。

3 实验结果对比

根据上述两种算法的优点，本文在SURF的基础上，改用DAISY算法来生成描述子能够进一步提高算法的实时性，然后再通过PROSAC算法进行匹配提纯，改进算法与基于SURF算法的匹配对比如图3所示，其实时性对比如表1所示，可以发现经过改进之后的算法在旋转、缩小、放大、过亮、过暗场景中均有效去除了误匹配点对，并且也提高了实时性。例如在旋转场景中，可以看出书的上半部分与书的下半部分较为相似（均为大块白色区域），都有着很大一部分的白色区域，因此可以看到在书的上边缘提取出的SURF特征点很容易就匹配上了书下半部分的SURF特征点，导致匹配点对不对应。但采用了DAISY算法以及PROSAC算法后，由于DAISY算法取了不同尺度下的高斯卷积，多尺度描述子的获得使其关键点描述不再局限于局部（可以获得更大范围内的灰纹理区域），配合PROSAC算法提供的高鲁棒性匹配，大量的误匹配点对被滤除，因此匹配效果大大提升了，而且实时性也有一定的提升。此外，值得一提的是，虽然在倾斜场景中改进算法提升的效果并不明显，因为倾斜场景下书对应的描述子区域在DAISY算法下与SURF算法下相差无几，因此区分度较低，故没有明显的提升效果，然而其实时性大大提升了，从每帧图像耗时0.634 s提升至每帧图像耗时0.615 s。

图3 改进算法（右）与基于SURF算法（左）在不同场景的匹配效果对比

表1 改进算法与基于SURF算法在不同场景所耗时间对比

4 结束语

本文在SURF模板匹配方法基础上进行了改进。包括使用DAISY算法构建描述子以提高效率，并使用PRO⁃SAC算法进行匹配提纯，最后通过实验证了改进算法在旋转、倾斜、放大、缩小、过亮、过暗场景中的有效性，并且相较于SURF模板匹配方法有效剔除了误匹配点对，并且一定程度上提高了模板匹配算法的实时性。但本文工作仍存在不足，本文中模板图像只是取了目标物体某一面的信息，对于同一物体换一个面就无法识别，所以本文中所述方法只是针对采集到的物体的可见表面进行识别与重建，缺少物体的完整信息，后续可以考虑对物体进行多视角的图像采集，建立完整的图像信息库，或构造物体的三维模型作为模板，实现对目标更全面、可靠、可靠地识别。