基于局部相似性的特征匹配筛选算法

马正见，文志诚，尹欢一

（湖南工业大学 计算机学院，湖南 株洲 412007）

0 引 言

图像匹配是计算机视觉的一个重要研究方向，在人脸识别[1]、遥感图像[2]以及图像分类[3]等方面具有重要作用。现有的图像匹配技术按匹配对象可以分为基于像素、基于特征和基于频域三类[4]。这三类方法中，基于像素的配准方法存在处理效率低、对重叠区域要求高的不足，基于频域的配准方法在面对图像噪声时匹配质量又较差。因此目前主要的研究方向还是基于特征的匹配方式。

在国内外学者的不断研究下，目前已经提出许多基于特征的图像匹配算法。其中由Lowe 提出的SIFT 算法通过构建空间金字塔的方式检测稳定的特征像素点，以特征像素点邻域的梯度直方图为基准对特征像素点进行描述，所形成的特征像素点描述子对图像的尺度以及旋转变化适应性很强，但计算量过大也使该算法在效率上略显不足。为了获得效率上的提升，Bay 等人提出一种利用图像积分检测特征像素点的SURF 算法。该算法相对SIFT 算法在效率上有所提升，在遥感图像[5-6]上也获得了应用。

随着对算法实时性要求的提高，研究者对之前的算法进行了优化[7-9]。同时，Rublee 等人提出更具效率的ORB 算法，算法在实时性上得到进一步提升，但也出现了特征像素点误匹配率高的问题。为剔除误匹配，许多优秀的筛选算法[10-12]被提了出来，其还是基于RANSAC算法的思想，通过不断迭代求解像素点对间最优的线性变换矩阵，再用该矩阵重新对所有像素点对进行筛选。RANSAC 算法在处理平移以及模糊这一类特征像素点满足线性关系的图像时，筛选效果比较好，但对像素点间位置发生偏移的视角变化类图像鲁棒性不强，此外，迭代次数过多也使得筛选过程效率略低。

针对以上两方面的不足，本文通过对非极大值抑制算法进行优化来降低初始误匹配率，并在此基础上提出一种基于局部相似性的筛选算法。通过待筛选像素点局部区域内其他像素点的相似性分布实现对误匹配的筛选，降低了算法对像素点的线性要求，对视角变化的图像具有更高的鲁棒性。同时由于不需要过多的迭代，筛选过程中的效率也得到了提升。

1 ORB 算法

1.1 特征检测

ORB 算法通过比较像素点与其邻域内其他像素点的灰度值来检测特征像素点。对任意位置的一个像素点P，选择以该像素点为圆心，半径为3 的圆上的像素点作为比较像素点。当存在连续的n个像素点的灰度值都大于或小于P点的灰度值时，就认为像素点P为特征像素点。当n取值为12 时，可以先与4 个顶点的像素灰度值相比较。当满足条件的顶点少于3 个时，直接判定中心像素点P不是特征像素点。

此时检测到的特征像素点还不具备方向属性，因此还需要为特征像素点计算方向。这里使用像素的灰度质心描述当前特征像素点的方向，特征像素点的p+q阶几何矩定义为：

其中f(i,j)为图像在坐标点(i,j)处的灰度值。几何矩的质心为：

向量PC的方向即为特征像素点的方向，其值为：

1.2 特征描述子

对特征像素点进行描述时选择一种改进的RBRIEF 算法，改进后算法生成的特征描述子具备旋转不变性。算法以待描述特征像素点为中心，在S×S的邻域窗口内按高斯分布选择256 对像素点对，每对选择的特征像素点对按式（4）进行描述。将所有描述按顺序组合成最终256 维的特征描述子。

生成描述子时选择的坐标系是以被描述的特征像素点为原点，向量PC的方向作为参考坐标系中x轴的正向。为了保证特征像素点描述子的旋转不变性，需要将特征像素点在生成描述子坐标系中的坐标转化至原图像的坐标系中。两个坐标系中的坐标转换公式如式（5）所示：

将式（5）化简有：

进行坐标转换后的特征描述子就具备了旋转不变性。

1.3 特征像素点的匹配

目前特征像素点的匹配主要采用暴力匹配方式，依据特征像素点描述子之间的Hamming 距离进行匹配。对待匹配图像中的任意特征像素点，匹配图像中与它距离最小的特征像素点即为它的匹配点。2 个匹配的特征像素点一起就组成了一对特征像素点对。

1.4 特征像素点对的筛选

特征像素点进行匹配后存在许多错误匹配，这里需要对匹配的特征像素点对进行筛选，剔除那些错误匹配的特征像素点对。传统方法采用RANSAC 算法进行筛选，RANSAC 筛选算法步骤为：

1）随机选取多对特征像素点对，这里一般选择4 对；

2）用选出的特征像素点对计算H矩阵；

3）用H矩阵对其他的特征像素点对进行校验，计算其误差，并将误差范围内的点记为内点；

4）统计本次计算中内点的数目；

5）重复以上过程，选取内点数目最多的一次的H矩阵，剔除不满足该H矩阵的特征像素点对。

2 改进算法

2.1 优化非极大值抑制算法

引起特征像素点对误匹配的原因主要有两种：一种是图像噪声之类的外部条件影响，导致特征像素点生成描述子时邻域内有部分像素点对取值错误，使暴力匹配时的距离计算产生误差引起误匹配，这种误匹配难以避免；另一种是对特征像素点进行非极大值抑制时抑制过度引起，这种情况可以通过优化非极大值抑制算法来降低误匹配率。

进行非极大值抑制算法（NMS）的目的是减少特征像素点的数目和让特征像素点分布得更均匀。通过比较特征像素点与范围内其他特征像素点的响应强度值进行抑制。保留的特征像素点Pi需要满足：

式中：f是特征像素点的响应强度函数；U是满足条件的特征像素点集合，它是由以Pi为圆心，r为半径的圆内所有的特征像素点组成代表Pi与P的欧氏距离。

过度抑制指的是准确匹配的特征像素点对中的某一个被错误地抑制。由于检测到的特征像素点大多集中在纹理变化大的地方，因此抑制半径大时就容易发生。过度抑制使留下的那个特征像素点进行暴力匹配时误匹配至其他特征像素点，从而引起连锁反应，增加了初始的误匹配率。

为了尽可能地降低误匹配率，本文对传统非极大值抑制方法进行优化，优化为一种自适应的非极大值抑制方法（SA-NMS）。以生成描述子时的邻域半径作为抑制半径，通过计算范围内特征像素点的数目自动调节抑制的数目，减少过度抑制的出现。此时对于能够保留下来的特征像素点需要满足：

式中NUM(Pi)是抑制区域内特征像素点响应强度值大于中心特征像素点的数目；Pj_NUM 表示抑制区域内除中心外其他特征像素点Pj的总数；V是抑制范围内Pj的集合。

在寻找特征像素点抑制区域即ROI 区域（感兴趣区域）内其他特征像素点时，需要计算它与其他特征像素点之间的欧氏距离。但在ROI 区域内的数目仅占总数很小的比例，这使得每一次确定ROI 区域时有过多无效的距离计算。为了提升抑制算法的效率，这里对查找方法进行优化。

优化后ROI 区域查找过程如图1 所示。将检测到的特征像素点集合映射至x轴，按由小到大的顺序进行排序。对计算的特征像素点按图1b）所示在x轴上寻找ROI 区域，由于已经进行排序，因此可以直接判定边界外的其他像素点不在抑制范围内，减少了无效距离计算。在对下一个特征像素点抑制时，仅需在x轴上进行图1c）这样的边界移动，排序后特征像素点在x轴上靠得很近，因此每次边界移动仅有少数特征像素点变化。确定x轴的界限后计算一次特征像素点在x轴的上下限即可确定如图1d）所示的最终抑制区域，最后将抑制范围内的特征像素点按式（8）进行抑制即可。

由于每次对新的特征像素点进行抑制时仅需要移动x轴边界以及一次y轴的上下限计算，因此相较于传统抑制方法减少了大量的无意义距离计算。同时自动调节抑制数目的方式也减少了因过度抑制引起的高误匹配率问题。优化后算法的伪代码如算法1 所示。

算法1 自适应非极大值抑制算法

图1 抑制区域查找

2.2 基于局部相似性的匹配筛选算法

实验发现，对于准确匹配的特征像素点，它们在图像中的位置都相对固定，在局部范围内与其他准确匹配的特征像素点之间距离远近关系也保持高度相似。而那些误匹配的特征像素点却与它对应的位置相隔较远，因此误匹配的两个特征像素点局部范围内的其他特征像素点几乎完全不同。

基于以上特性，本文提出以特征像素点局部范围内其他特征像素点分布的相似程度作为筛选标准的LSD筛选算法。算法分为两个阶段：第一阶段从粗匹配中提取准确率高的点对作为参照对象，并通过局部相似性验证从而确保准确性；第二阶段利用反向局部相似性筛选剩余匹配点对。

首先定义特征像素点P的K近邻特征像素点Pk为：

式中d(P,k)为特征像素点P和Pk的欧氏距离。定义特征像素点P的局部区域NNk(P)为：

将特征像素点P到局部区域内其他特征像素点的距离按由小到大的顺序组成距离向量DP：

通过距离向量就可以计算特征像素点对的局部相似度。对某特征像素点对进行计算时，对于两个距离向量内匹配的距离项，计算这两个距离项在距离向量里的索引差值。在这里匹配的距离项指的是这两个距离项对应的另一对匹配的特征像素点的距离。对不存在匹配距离项的，则默认索引差值为距离向量的总项数。将单个距离向量计算出的所有索引差值相加即为特征像素点对的局部相似性度S，越小说明这两个特征像素点局部范围内特征像素点的分布越相似，该像素点对准确匹配的几率越高。

算法的第一阶段需要从粗匹配中提取匹配准确率高的特征像素点对。实验发现，粗匹配中Hamming 距离越小的特征像素点对的匹配准确率越高。因此第一个阶段将粗匹配按距离由小到大的顺序进行排序，挑出排列靠前的n对特征像素点对。这里n的取值依据粗匹配的数目确定。

为了确保挑出特征像素点对的准确率，需要对它们进行校验。如图2 所示，以正确匹配的T1，T2和误匹配的F1为例，当局部范围的k取值为3 时，T1的局部相似度计算的值为5（1+1+3），T2计算的值为0（0+0+0），而F1的值为9（3+3+3）。误匹配的特征像素点对计算出的局部相似度值明显要高于准确匹配，此时设定一个阈值就可以轻松地区分误匹配。用以上方法对所有挑出的特征像素点对进行校验，剔除超过阈值的误匹配像素点对。虽然这一阶段挑出的像素点对本身就有很高的准确率，但进行一次校验仍是非常有必要的。

图2 特征像素点对校验

在完成第一阶段特征像素点对的挑选后，接下来就要对剩余部分进行第二阶段的筛选。由于第一阶段经过校验的特征像素点对的准确率远远高于第二阶段，因此这一阶段选择反向局部相似性的筛选方法。同时考虑到距离对筛选结果的影响，在计算反向局部相似度时设定如下影响权重：

正在筛选特征像素点对局部区域内的特征像素点Pj的反向相似度因子为代表Pj认为正在筛选的特征像素点P准确匹配的程度，它的值为Pj距离向量里特征像素点P与Pj距离的索引差值。此时反向局部相似度RSP的计算公式如下：

按距离由小到大的顺序每次选择一对剩余的特征像素点对进行筛选。每次筛选进行以下操作：

按距离由小到大的顺序每次选择一对剩余的特征像素对进行筛选。每次筛选进行以下操作：

1）计算两个特征像素点的局部区域；

2）计算局部区域内其他特征像素点的距离向量；

3）依据距离向量计算每个特征像素点的反向相似度因子；

4）将计算得到的所有相似度因子相加得到反局部相似度；

5）反局部相似度低于阈值则保留，否则剔除。

基于局部相似性筛选算法伪代码如算法2 所示。

算法2 基于局部相似性筛选算法

3 实验分析与比较

本文采用K.Mikolajczyk 和C.Schmid 所创建的标准开源数据集中的图像进行测试。测试数据集包含图像模糊、旋转以及光照变化等8个系列，每个系列各含有6张图像，对应同一场景受影响程度不同的图像。在测试图像集上进行仿真实验，并将本文算法与传统算法的实验结果进行对比分析。

3.1 实验环境

笔记本电脑处理器为IntelⓇCoreTMI5-4200U，主频1.60 GHz，内 存 4 GB，64 位 Win7 操 作 系 统 ，Visual Studio 2015 和 OpenCV 3.1.0。

3.2 自适应非极大值抑制实验分析

为验证优化后的自适应非极大值抑制算法与传统非极大值抑制算法在抑制效果和效率上的差异，在相同的实验环境下，分别使用两种算法对测试图像集进行实验。

表1 是两种非极大值抑制算法的运行结果。通过表1 比较可以看出，优化后的自适应非极大值算法相较于传统算法能保留更多的特征像素点，有利于特征像素点的匹配。从效率上来看，传统方法每处理500 个特征像素点平均用时35 ms，而优化后算法仅需18 ms，总体上提升了50%左右。这也证明左右界限标记的方式能够有效地减少距离计算，在效率上优化后的算法更佳。

表1 非极大值抑制结果

图3 展现的是测试图像经过传统非极大值抑制算法与本文抑制算法后的特征像素点匹配时的误匹配率。可以看到用优化后的非极大值抑制算法所产生的误匹配率均略低于传统方法。尤其是在bikes、leuven 这一类纹理变化比较大的图像上效果更为明显。

图3 非极大值抑制后的误匹配率

3.3 基于局部相似性筛选实验

为对比本文提出的LSD 筛选算法与RANSAC 算法对误匹配特征像素点对的筛选性能，用图像测试集中光照变化、模糊变化、视角倾斜以及旋转变化系列进行4组特征像素点对筛选实验，以剔除的特征像素点对的数目衡量算法筛选能力，同时记录筛选算法的运行时间。

特征像素点对数目在筛选过程中的变化如表2 所示。其中由于wall、boat 图像有方向上的旋转，因此许多特征像素点对不能很好地满足RANSAC 计算的H矩阵，所以在这两组实验中RANSAC 算法剔除的特征像素点对数目较多。而本文提出的LSD 算法减弱了特征点坐标的线性要求，因此方向旋转对剔除的数目影响不大，并且由于本文提出的LSD 算法避免了过多的迭代，故在效率上也更高。

表2 匹配筛选实验结果

3.4 对视角变化图像鲁棒性实验

由于本文提出的筛选算法主要考虑匹配点对的局部相似性，因此可以用于视角变化这类图像的筛选。以基准开源数据集中6 个不同视角拍摄的涂鸦（graf）图像作为测试图像，将测试图像集中每2 张图像分为一组，用LSD 算法进行实验，得到的结果如表3 所示。

表3 视角变化图像匹配筛选结果

由表3 分析可以得到以下两个结论：一是视角变化下图像的粗匹配产生的误匹配比其他类型多，这点可以从被筛选的数目看出来；二是用本文提出的筛选算法对小视角变化图像仍具备良好的筛选效果，筛选的效率以及筛选后的准确率都能达到其他类型图像的标准，对视角变化的图像具有鲁棒性。

部分视角变化图像筛选后的结果如图4 所示。

可以看到：图4 两幅图像中匹配的特征像素点并不满足线性关系，此时用RANSAC 算法并不能计算出特征像素点间的线性变化H矩阵；而使用本文提出的筛选方法对视角有变化的图像筛选后仍能保留大量准确匹配的特征点对，这也验证了本文提出的LSD 筛选算法对视角变化的图像的鲁棒性。

图4 视角变化图像匹配筛选

当视角变化的程度不断增大时，特征像素点的检测也变得越来越难，同时描述特征像素点时它邻域内的像素也发生了变化，使得特征像素点间变得难以匹配。对graf 图像系列不同程度视角变化图像进行实验的结果如图5 所示。

图5 视角变化程度对算法的影响

可以看到，随着视角变化的程度增大，图像间匹配到的特征像素点对越来越少。在变化较小时还能保留较多的特征像素点对。一旦变化程度加大，特征像素点的描述子描述的信息区域发生改变，导致粗匹配能匹配到的特征点对迅速减少，虽然用本文提出的筛选算法还能保留少量匹配的点对，但筛选的效果也并不够好。经过两次的视角变化后，再进行筛选效果也不明显。

4 结 语

针对传统ORB 算法误匹配率高、迭代速度慢的缺点，本文提出了一种基于局部相似性的特征筛选算法。为降低特征点粗匹配的误匹配率，本文还对传统的非极大值抑制方法进行了优化。实验结果表明，优化后的自适应非极大值算法有更高的效率和更低的误匹配率。此外，本文提出的特征筛选算法在保持高准确率的同时还减少了迭代计算，对视角变化的图像也展示出了更强的鲁棒性。