一种基于FAST和改进的RANSAC图像匹配方法

岳港琳，雷志勇

（西安工业大学电子信息工程学院，西安 710021）

0 引言

在靶场测试中，炸点坐标测量对于射击偏差校正［1］具有非常重要的意义。通过双相机交汇测量炸点的坐标中，双目匹配［2］的精度直接影响到炸点定位的准确性。

基于图像特征［3］的匹配方法考虑了点、线、面等图像特征，由于该方法计算量较小，并且对形变、灰度变化和遮挡具有很好的鲁棒性，因此近年来成为图像匹配的研究热点问题。SIFT［4］算法2004 年正式被Lowe 提出，该算法通过引入拉普拉斯算子［5］提取尺度和旋转不变的特征，对透视、噪声的变化和仿射变换在一定程度上保持了稳定性，实现图像的自动匹配。对于有丰富纹理信息的图像，文献［6］提出一种只提取图像的灰度值，并且没有尺度等较复杂运算的更实时的快速检测特征点的算法，因此该算法运行速度非常快，但此算法也存在一定缺陷，如初始匹配时会出现错误的匹配点，导致后续出现物体识别有误或目标跟踪丢失等问题，因此对误匹配点进行剔除尤为重要。对误匹配点进行消除的方法主要包括：NNDR、RANSAC、Hough聚类等［7］。

在现研究基础上，通过FAST 进行特征点检测，SURF 进行特征描述后，采用自适应阈值RANSAC 算法消除匹配结果中错误匹配点，提高匹配的准确率。

1 图像特征匹配

图像特征匹配包括四个方面：检测特征点、特征点描述、对特征点进行匹配和消除误匹配点。本文提出的匹配算法实现过程如图1所示。

图1 图像匹配算法流程

1.1 特征点检测

FAST 检测特征点的核心是确定给定像素为中心的圆上是否有足够数量的连续像素的灰度值大于（小于）该像素点灰度值。如果存在，则表明该像素点是被检测出的特征点，否则作为一个非特征点剔除。主要步骤如下：

（1）选择一个像素p，将其亮度设置为Ip，亮度阈值为T；

（2）以像素p为中心，在半径r=3的圆上选取16个像素点；

（3）假如选取的圆上有连续的N个点的像素灰度值大于（Ip+T）或小于（Ip-T），那么像素p就被认为是特征点；

（4）重复以上三个步骤，对每个像素进行同样的操作；

（5）采用计算角点响应函数的方法，剔除非角点。计算公式见式（1）。

式（1）中，V是角点与其相邻16 个点之间的灰度差值的绝对值之和，Ip是像素p的亮度值，T是像素p的亮度阈值，x为圆上16 个像素点的位置，Sbright，Sdark分别是16 个邻域像素点中灰度值大于（Ip+T）或灰度值小于（Ip-T）的像素点的集合。

1.2 SURF特征描述

1.2.1 主方向确定

SURF 算法以检测到的特征点为中心，半径为6 s（s 为尺度）来构建圆形区域，目的是确定唯一的方向，实现图像的旋转不变性。在π/3的滑动窗口中，利用Harr 小波响应，求出各特征点x、y轴的dx，dy之和，得到一个局部方向向量，求出所有窗口上的最大方向向量，即该特征点的主方向。

1.2.2 生成特征点描述子

SURF 算法是利用特征点周围的正方形区域来构建描述符的，并将其分为4 × 4 个子区域，以保存部分空间信息。在每个子区域中，有5 s×5 s 个像素点，分别求出各子区域内的所有像素点的水平Haar小波响应dx和垂直Haar小波响应dy，然后将Haar 小波响应dx，dy加到高斯权重中（σ=3.3 s），再求出各子区域的dx，dy，| dx|，| dy|之和，由此得到对应的四维向量，从而得到一个64 维的SURF 特征向量，即描述子。

1.3 特征点匹配

1.3.1 双向FLANN匹配

FLANN 匹配算法的核心是要计算出两特征点之间的欧氏距离，根据距离这一特征点的最近欧氏距离和次近欧氏距离之比是否小于设定的阈值T来判断特征点是否匹配。

本文采用双向FLANN 匹配方法以消耗少量时间来提高匹配精度。该算法对于要匹配的两幅图像I1和I2，找出I1与I2之间欧氏距离最近和次近的2个点，计算最近欧氏距离和次近欧式距离之间的比值并与阈值T进行比较来判断特征点是否匹配，阈值T为0.5，得到I1到I2的匹配点集合A。再对图I2进行相同操作，得到I2到I1的匹配点集合B，取A与B中完全相同的匹配点对作为集合C，从而得到初始匹配点集合。

1.3.2 自适应阈值RANSAC算法

通过双向FLANN 匹配可以去除一部分多对一的错误匹配对，但仍然存在着少量的错误匹配。传统的RANSAC 算法基本思想是从粗匹配结果中随机选出一组最小的数据集，估计出模型，然后将数据集中未选到的数据代入模型，根据设定好的阈值，将最新得到的模型与先前最好的模型的内点数做比较，分别记录最大模型的内点及内点数，迭代该过程，最终内点占比例最大的模型就是待求的模型。RANSAC 算法具有很好的鲁棒性，但是使用时它的阈值设置往往需要根据经验来判断，不同的场景设定的阈值不同，结果往往不具有通用性。因此，为解决传统RANSAC 算法在消除误匹配点对时的不足，本文提出自适应阈值RANSAC 算法。在该算法中，阈值的取值基于匹配点与其变换模型之间距离的平均值。

具体步骤如下：

（1）从粗匹配点对中随机选取非线性点对4组，组成集合N；

（2）根据集合N计算出单应性矩阵H，记为模型Q；

（3）计算出匹配点与其对应模型之间的距离，再对得到的距离求得其均值，设为阈值T，匹配点与其变换模型之间距离l及距离的均值ml通过下式进行计算：

式中，n是匹配点对的数量，Pi是对应图像中第i个匹配点，Hi是第i个匹配点对应的单应性矩阵，‖ .‖2是计算欧几里得范数。

（4）在匹配点数据集中计算出模型Q与所有点之间的距离，若小于设定阈值，则将其添加到内点集P中；

（5）若内点集的个数大于当前最优内点数，则更新最优内点集，反之，则不更新；

（6）迭代总次数由当前最优内点数进行更新，若当前迭代次数小于总迭代次数，则返回步骤（1）；反之，则当前模型Q就是最终要求得的模型。

2 实验结果及分析

为了验证算法的有效性，采用灯光模拟炸点并对图像进行处理，从特征点提取数量和时间，匹配正确率（CMR）和匹配时间三个方面进行算法的评价。

图2 炸点双目图像

2.1 实验一

在不同算法中得到的特征点数量和时间结果如表1所示。

表1 不同算法下的特征点数量和时间

由表1 可知，对于相同的图片，与SURF 算法相比，FAST 算法检测出的特征点数量较少，但是它具有检测速度快、时间短的优点。

2.2 实验二

该实验的目的是验证文中所提匹配算法相对于SIFT、SURF 匹配算法的优点，匹配结果如图3、表2所示。

表2 不同算法下的匹配结果和时间

图3 三组匹配结果

匹配正确率（CMR）计算公式如式（4），CMR值越大，匹配效果越好。

式中Pc是正确匹配的特征点数量，P是匹配到的数量。

本文提出的改进算法与SIFT 算法和SURF算法进行比较，通过对两组实验数据的比较可以看出，所提出的算法在保证正确率的前提下，具有匹配效率高的优点。

3 结语

在目前图像匹配研究的基础上，提出一种新的基于FAST 和改进的RANSAC 的图像匹配算法。首先利用FAST 提取出角点，再利用SURF确定特征向量主方向，接着使用双向FLANN 完成特征点粗匹配，根据匹配的结果计算出每个特征点与其变换模型之间的距离的平均值来作为RANSAC 消除误匹配的阈值，进而加快算法运行的速度。通过实验结果可以看出，与传统的SIFT、SURF 对比，所提算法对图像匹配的准确率和效率均有所提高。