一种快速的误匹配筛选算法

宋孟良，张国伟，卢秋红，张苏苏

（1.上海电力大学 自动化工程学院，上海200082；2.上海合时智能科技有限公司，上海201100；3.上海太阳能工程技术研究中心有限公司，上海201100）

0 引言

目前，机器视觉发展迅速并广泛应用于各个领域。图像的特征点提取与匹配属于机器视觉的基础组成部分，在图像配准、视觉SLAM、三维重建等多个领域都起着重要的作用[1-3]。特征匹配的结果是下一个环节的输入数据，是其他图像处理的前提和关键[4]。因此，在特征匹配中减少误匹配的数量并提高特征匹配的正确率与效率会对实际应用产生较大的影响。

在SIFT[5]中,作者提出一种基于KNN的比例误匹配筛选方法，但这种方法鲁棒性较差。Fischler等[6]提出基于统计模型的经典方法RANSAC（Random Sample Consensus）,该方法可以在包含“局外点”的数据中，通过迭代有效地得到高精度的数学模型，该方法具有一定的鲁棒性，但是迭代次数没有上限计算时间较长，当数据整体错误率较高时，其计算结果也会有较高的错误率。文献[7]中，将前两种算法相融合，减少了RANSAC的迭代次数并且提高了正确匹配率。文献[8]中，提出了一种改进RANSAC的方法，通过改进损失函数使模型考虑到了不同匹配的误差，相比于传统方法提高了模型的估算精度。文献[9]在文献[8]的基础上使用具有更大概率的“内点”的数据点来指导数据采样，并且在估算单应矩阵时使用这些点作为先验知识，进一步提高了模型估算的精度。文献[10]中，将所有匹配点以先验知识为依据进行排序，将“内点”概率大的点排在前面，有序地进行采样而不是随机进行，进一步提高了算法的运行速度和鲁棒性。文献[11]中，为了解决大比例的误匹配会影响模型精度问题，以一个更好的模型为基础进行局部优化，以克服大比例误匹配对模型精度的影响。

为了兼顾鲁棒性和计算速度，本文在前人的基础上提出了一种快速的误匹配筛选算法，融合使用Otsu算法和RANSAC算法，在保证正确率与充足匹配对的情况下提高了算法的计算速度。最后在TMU数据集上验证了该方法的有效性。

1 误匹配筛选算法

1.1 欧式距离(Euclidean Distance)

在特征匹配中，假设待匹配图像矩阵的个数为n元素值，用个数为n的元素值(x1，x2，…，xn)组成该图像的特征组，特征组构成了n维空间，特征组中的元素值构成了每一维的数值。在n维空间下，待匹配的两张图像的特征点的集合分别记为A与B：

1.2 基于欧氏距离的最大间类方差法（Otsu）

最大类间方差法是由日本学者大津展之[12]于1979年提出的，是一种自适应的阈值确定方法，简称Otsu，该方法的本质上是一种分类算法。

本文将该算法应用于特征点的误匹配筛选，具体算法如下。

假设2张图片特征匹配完成后得到的所有匹配对的数量为N，将匹配对欧式距离映射为d∈［0，255］,欧氏距离等级为d的匹配对的个数为nd，则每个等级的欧氏距离出现的概率为pd=nd/N；假设最佳阈值为t，则根据阈值t将所有匹配对划分为正确匹配与错误匹配2类：

欧氏距离越小则说明匹配对是正确匹配的概率越高，则正确匹配对对应的范围为Right∈（0，T）。

1.3 基于Otsu的初次筛选

图像特征点匹配初次匹配完成后得到的特征点包含大量的错误匹配，本文利用所有特征匹配对的平均欧氏距离进行初次筛选，提高算法的运行效率[13]。在1.2节中基于欧式距离的Otsu算法中，根据式（1）～式（3）可知：

由此可得|μ-μR(t)|-|μ-μW(t)|>0，即表明，特征匹配对的欧氏距离均值μ更接近于错误匹配所对应的欧式距离均值μR(t)，即更接近于错误匹配对应的峰值，则说明Otsu算法的最佳阈值在本算法中处于2个峰值之间的峰谷处，即T∈(0，μ)，μ大于T，表明所有的匹配对中欧氏距离大于μ的匹配对应该剔除。

1.4 随机取样一致（RANSAC）

在特征匹配完成后，待匹配的2张图像之间特征带点的对应关系确定。此时图片A与图片B之间存在对应关系A=H·B，矩阵H是一个3×3的最佳单应性矩阵，通常令h33归一化矩阵。

式中：S为图像尺度参数；(x′，y′)为图像A角点位置；(x，y)为图像B角点位置。

假设样本数（即特征匹配对的总数）为M，从数据集中随机抽取m个样本，因为单应性矩阵H中共有8个未知数，至少需要8个线性方程组求解，所以m≥4，根据样本计算得到的模型后将满足该模型的特征匹配对的个数与重投影误差，通过多次迭代使得重投影误差最小的模型即为所求。

虽然RANSAC具有较强的鲁棒性，但是该算法的迭代次数没有上限算法，运行时间较长，限制迭代次数可能会导致无法得到最优模型。为了进一步提高RANSAC的算法运行速度与模型精度，我们采用文献[10]中的算法思想，将2次筛选后的特征匹配对根据欧式距离从大到小依次排序后，对RANSAC进行优化。

1.5 基于欧氏距离的误匹配筛选算法

为了解决图像特征带点误匹配筛选算法鲁棒性较差、耗时较长等问题，本文提出了基于欧氏距离的特征匹配对误匹配筛选算法。首先，使用欧氏距离作为图像特征匹配对的置信度，特征匹配对的欧氏距离越小则说明特征匹配对的置信度越高，然后在欧氏距离的基础上构建Otsu算法，通过平均欧式距离进行初次筛选，然后通过迭代计算得到最佳阈值T，在二次筛选完成后将剩余匹配对根据欧氏距离排序，最后通过RANSAC算法迭代计算出最优模型。

2 实验与分析

为了验证本文提出的误匹配算法的有效性，在德国慕尼黑大学TUM数据集中进行实验，实验平台采用Windows10操作系统、AMD Ryzen 2600 Six-Core Processor(3400 MHz)、16GB DDR4 RAM，不使用GPU加速，编程环境为Visual Studio2017。

为了验证算法的有效性，我们分别对Otsu算法及基于Otsu的阈值筛选算法进行实验。选取图像为ORBSLAM中使用的TMU数据集。该数据集是汽车行驶中的实际路况，图像分辨率为800×900，采样频率为10 fps，两张图像之间的时间间隔为18 ms以上，提取的特征匹配对的数量为500。

图2 平均欧氏距离的筛选结果

由实验结果可以观察到，在Otsu算法筛选后仍然存在一些误匹配，并不能直接使用得到的结果，因此需要与RANSAC算法融合进一步筛选。

图3 传统RANSAC筛选结果

图4 本文算法筛选结果

表1 算法性能对比

由图1、图2中实验结果可知，本文提出的基于欧氏距离的Otsu筛选算法及平均欧氏距离筛选算法的有效性，可以筛选掉大量的错误匹配。

由图3、图4及表1中的结果可知，本文提出的融合算法可以有效地进行误匹配筛选，并且能够保留较多的特征匹配对，算法得到的筛选结果正确率较高，与传统RANSAC算法相对比，本文算法的运行速度大幅度上升，筛选结果正确率也有所提高。与传统RANSAC算法相比，本文算法筛选后的匹配对数量有所下降，但是比其他种类的算法保留的匹配对数量要多，并且斜率较为固定，具有良好的自适应性。与传统RANSAC算法相比，本文算法运行时间大幅度减小，对筛选数据进行排序，提升了算法的运行速度。由表1中实验结果可知，本文算法在处理500个匹配对时运行时间基本在5 ms左右，能够满足实时性要求，与其他算法相比，本文算法的正确率较高。

3 结论

针对传统的特征匹配对误匹配筛选算法鲁棒性差、效率低等问题，本文提出了一种快速的特征点误匹配筛选算法。在特征匹配对的欧氏距离基础上，引入Otsu算法对数据进行初次筛选和二次筛选，大大提升了算法的筛选效率，不仅快速得到了筛选结果，而且保证了充足的匹配对数量，提升了算法的鲁棒性；另外，进一步提升了RANSAC的运行速度和算法精度，对筛选后数据进行排序。在TUM数据集上进行实验，实验表明本文算法比传统算法具有更好的鲁棒性和实时性。