摘要
为解决预定义参数化模型的特征匹配方法通用性较低且鲁棒性较差的问题，根据正确匹配和误匹配的空间分布具有显著差异的现象，提出一种局部密度差异引导的特征匹配(RFM-LoDD)算法。首先，将假定特征匹配转换为能够表征特征匹配性质的空间样本点，并引入概率距离计算样本点的局部密度。其次，在随机选取的40幅涉及不同变换模型的图像对上测试算法的最优参数设置，确定了具有全局最优的密度阈值和其他参数。最后，将样本点的局部密度与密度阈值进行比较，当样本点的局部密度大于密度阈值，则认为该样本点代表的假定匹配为正确匹配，否则，就认为其代表的假定匹配为误匹配。在代表图像对和公开数据集上进行的实验表明，RFM-LoDD算法在各种匹配场景下都能够保持良好的鲁棒性，特别是在内点率较低的Retina数据集和AdelaideRMF数据集上相比于先进的算法均取得了领先的F分数。此外，RFM-LoDD算法具有准线性的时间复杂度，在4个公开数据集上的平均运行时间约为40 ms，时间成本相比于经典的随机抽样一致性（RANSAC）算法降低了两个数量级。
Abstract
To address the low generalization and poor robustness in feature matching methods that rely on pre-defined parameterized models, based on the observation that the spatial distribution of correct match and mismatch has significant differences, a feature matching algorithm guided by local density difference (RFM-LoDD) is proposed. Firstly, the putative feature matches are converted into spatial sample points that can characterize the nature of the feature matches, and the probabilistic distance is introduced to calculate the local density of the sample points. Secondly, the optimal parameter settings of the algorithm are tested on 40 randomly selected image pairs involving different transformation models，determining the globally optimal density threshold and other parameters. Finally, the local density of the sample points is compared with the density threshold. When the local density of a sample point is greater than the density threshold, the putative feature match represented by the sample point is considered to be a correct match, otherwise, it is a mismatch. Experiments conducted on representative image pairs and public datasets demonstrate that the RFM-LoDD algorithm maintains good robustness in various matching scenarios. Notably, it achieves leading F-scores on the Retina dataset and AdelaideRMF dataset with low inlier rates compared to advanced algorithms. Additionally, the RFM-LoDD algorithm has quasi-linear time complexity, with an average run time of about 40 ms on the four public datasets, significantly reducing time cost by two orders of magnitude compared to the classical random sample consensus (RANSAC) algorithm.
Keywords
图像特征匹配旨在建立参考图像与目标图像特征点之间的可靠对应关系，已被广泛应用于许多计算机视觉任务[1]，例如智能感知[2]，医学成像[3]、遥感[4]、即时定位与地图构建[5]、图像配准与融合[6]等。特征匹配一般包括粗匹配和精匹配两个步骤。粗匹配基于特征描述符信息判断匹配关系，从而建立假定特征匹配。然而，由于特征描述符存在不确定性，尤其是当参考图像与目标图像之间涉及非刚性变换时，假定匹配中除了正确匹配（内点）外，还包含大量的错误匹配（外点），因此需要通过精匹配进一步剔除假定匹配中的误匹配。
现有精匹配方法按照理论框架一般可以分为参数化方法和非参数化方法。参数化方法通常需要预定义图像变换模型，如投影变换、极线几何、非刚性变换[7]等。随机采样一致性（random sample consensus，RANSAC）算法、极大后验样本一致性（maximum a posteriori sample and consensus，MAGSAC[8]）及其改进算法MAGSAC++[9]等，是目前广泛使用的参数化方法。RANSAC算法遵循假设和验证策略。首先，在假定匹配中随机选取一组能拟合给定图像变换模型的匹配关系，如拟合投影变换模型需要4对匹配；然后，根据匹配关系拟合模型，并根据其他假定匹配验证模型的可靠性；最后，若符合该模型的特征匹配数量超过设定的阈值，则认为模型可靠且符合该模型的特征匹配为正确匹配。否则，重新采样拟合模型并重复验证步骤，直至拟合出可靠的模型。
非参数化方法不依赖图像变换模型，而是基于理论假设研究正确特征匹配的局部邻域结构来剔除误匹配。Bian等[10]提出基于网格的运动统计（grid-based motion statistics，GMS）算法，将匹配图像划分为不重叠的网格，通过统计同一对网格内的匹配对数量实现了快速误匹配剔除。Ma等[11]提出局部保持匹配（locality preserving matching，LPM）算法，基于匹配对的局部邻域结构设计目标函数，并对目标函数的项进行量化从而大幅降低了算法的时间成本。Jiang等[12]提出一种基于局部图结构的特征匹配方法，通过研究正确匹配的局部邻域相似性设计了一个保持几何拓扑的图结构，从而在图匹配的框架下解决了特征匹配问题。Xia等[13]提出局部引导的全局保持优化（locality-guided global-preserving optimization，LOGO）算法，设计了一种基于图匹配的目标函数，并引入了定点渐进方法优化图目标函数，提高了算法对大量外点的鲁棒性。 Ma等[14]提出一种基于空间聚类的特征匹配（robust feature matching based on spatial clustering algorithm with noisy samples，RFM-SCAN）算法，根据假定匹配构建空间聚类样本，设计了一种自适应参数估计方法和迭代聚类策略，提高了数据严重退化下的匹配性能并实现了准线性的时间复杂度。
虽然目前已经提出了许多精匹配的方法，但在应对较为复杂的匹配场景时，现有方法仍存在许多挑战。一方面，在许多计算机视觉任务中，如可变形物体识别，匹配图像间的变换模型通常无法预知[15]，而参数化特征匹配方法由于需要预定义图像变换模型不再适用，因此需要设计一种通用的特征匹配算法；另一方面，当假定匹配中外点数量较多或者匹配图像对涉及复杂的非刚性变换时，现有特征匹配方法的鲁棒性和匹配效率会显著降低[16]。
为解决上述问题，本文提出一种局部密度差异引导的特征匹配（robust feature matching based on local density difference，RFM-LoDD）算法。根据假定特征匹配中正确匹配具有运动一致性，而误匹配的空间分布具有任意性这一现象，将假定匹配转换为空间样本点，引入概率距离[17]计算样本点的局部密度，并将其与预先设定的密度阈值进行比较从而判断假定匹配的正确性。本文算法不需要预定义匹配图像间的变换模型，相比于参数化方法具有更广泛的应用场景。基于此本文在各种图像数据上的实验表明，该算法在复杂匹配场景下仍然能够保持良好的鲁棒性和较高的匹配效率，整体匹配性能优于先进的特征匹配算法。
1 特征匹配方法
1.1 局部密度计算
如前所述，两个近邻的正确匹配具有相似的运动特性，如运动矢量的方向和长度，而误匹配的空间分布具有任意性。因此，由假定匹配构成的空间样本点通常呈现为一个或多个运动一致的簇和若干分散的离群点，可以通过样本点之间的局部密度差异剔除误匹配。
假设通过尺度不变特征变换（scale-invariant feature transform，SIFT）算法从两幅图像中获得了H对假定特征匹配。其中，xi、yi分别为两个对应特征点的图像坐标的二维向量。令mi=xi-yi表示假定匹配（xi，yi）的运动矢量。将假定匹配S转换为样本集D，转换规则为
(1)
式中pi为假定特征匹配性质的样本点。为了增强正确匹配间的运动一致性，参考文献[14]中的加权距离表示如下：
(2)
其中
式中: ωi，j为权重参数，φ（·）为距离函数，文中采用欧氏距离; γ为正数，用以增强运动一致性。
引入概率距离计算样本点的局部密度。相关定义如下。
定义1（k近邻集合） 给定样本点p和任意正整数k，样本点p的k近邻集合由距离p最近的k个样本点组成，表示为Nk（p）。
定义2（概率距离） 给定样本点p∈D，p与其k近邻集合Nk（p）的概率距离记为pdist（p，Nk（p）），表示为
(3)
其中
定义3（局部密度） 样本点p的局部密度定义为p与集合Nk（p）的概率距离的倒数，记为pdens（p），表示为
(4)
计算每个样本点的局部密度值，并与预先设定的密度阈值pd比较。当样本点的局部密度大于pd时，则认为该样本点代表的假定匹配为正确匹配，否则就认为其代表的假定匹配为误匹配。因此，内点集I由下式确定
(5)
为了验证内点和外点的局部密度存在显著差异，随机选取40幅具有不同变换模型的图像对，将通过SIFT算法获得的假定特征匹配按照上述规则转换为样本点，并计算样本点的局部密度。样本点的局部密度统计结果见图1。从图1中可以看出，内点和外点的局部密度具有显著差异。内点的局部密度通常较高，绝大多数内点的局部密度大于0.8，而外点的局部密度普遍较小，通常小于0.8，因此可以通过设置密度阈值对内点和外点进行区分。
图140幅图像对的假定匹配样本点局部密度统计分布
Fig.1Statistical distribution of local density of putative feature matching sample points of 40 image pairs
1.2 最优参数估计
在求每个样本点的k近邻集合时，参数k决定了样本点的邻域规模，其最优值应该取决于样本集D的基数。假设参数k的最优值由集合D的基数H和一个百分比Rpct决定，即k=[H·Rpct]，其中[·]表示舍入运算。此外，为了提高鲁棒性，将k的取值限制在BL和BU之间，即
(6)
式中，根据经验设置BL=3，BU=30。因此，确定参数k的最优值就被转换为了确定Rpct的最优值。
为了确定参数Rpct、γ和pd的最优值，测试了不同参数设置下RFM-LoDD算法在随机选取的40幅图像对上的平均F分数，结果见图2，分别固定{Rpct，γ，pd}中的一个参数并改变另外两个参数以找到最优设置。从图2中可以看出，不同参数设置下的平均F分数整体都呈现为先上升后下降的趋势，固定参数pd，γ，Rpct得到的最优参数设置分别为： {Rpct=0.03，γ=5}，{pd=0.7，Rpct=0.03}，{γ=5，pd=0.7}，3组结果具有一致性，即Rpct=0.03，γ=5，pd=0.7，RFM-LoDD算法取得了最优的平均F分数，这也是本文的最佳参数设置，而参数λ决定了样本点局部密度的对比度。本文算法根据经验设置λ=3。
RFM-LoDD算法的具体步骤描述如下。
输入：假定特征匹配S，参数λ，Rpct，γ，pd。
输出：内点集I。
1）根据式（1）构建样本集D。
2）根据式（6）和参数Rpct确定参数k。
3）根据式（2）加权距离、参数k以及定义1确定样本点的k近邻集合。
4）根据定义2和定义3计算样本点的局部密度。
5）根据式（5）确定内点集I。
1.3 计算复杂度
RFM-LoDD算法主要涉及两个步骤，包括每个样本点的k近邻集合的计算以及每个样本点的局部密度的计算。通过k-d树算法求每个样本点的k近邻集合，时间复杂度近似为O（NlogN）。计算每个样本点的局部密度的时间复杂度近似为O（N），因此时间复杂度总计为O（N（1+logN））。由于需要存储每个样本点的k近邻集合，所以RFM-LoDD算法的空间复杂度为O（kN）。通常情况下，，因此本文算法的时间复杂度和空间复杂度可以分别近似为O（NlogN）和O（N）。
图2不同参数设置下RFM-LoDD在40幅图像对上的平均F分数
Fig.2Average F-score of RFM-LoDD with different parameter settings on 40 image pairs
2 实验与分析
本文首先测试RFM-LoDD算法在代表图像对上的特征匹配结果，并与RANSAC、LPM[11]、RFM-SCAN[14]、LOGO[13]算法的匹配结果进行了统计比较和直观对比。然后，在以下4个公开数据集上全面比较RFM-LoDD算法和上述4种算法的性能。最后，测试了RFM-LoDD算法在不同外点率下的鲁棒性。
2.1 VGG数据集[18]
VGG数据集共包括40对图像，涵盖旋转缩放、角度变化、亮度变化等。图像对的变换模型为投影变换。
2.2 Retina数据集[11]
Retina数据集共包括65对视网膜图像，图像对涉及非刚性变换。
2.3 AdelaideRMF数据集[19]
AdelaideRMF数据集由38个图像对组成。其中，前19个图像对的变换模型为投影变换，后19个图像对的变换模型为极线几何变换。且大部分图像对符合多运动变换，即图像场景中存在多个具有不同运动的物体。
2.4 RS数据集[11]
RS数据集由156对遥感图像组成，包括彩色红外、合成孔径雷达和全色照片。
上述4个数据集中图像对的假定特征匹配以及正确匹配关系均来自文献[1]的公开数据。使用MATLAB代码实现RFM-LoDD算法，实验配置为AMD Ryzen 5 2500U CPU和8 GB内存的笔记本电脑。
2.5 代表图像对实验结果
使用8个代表图像对进行测试，变换模型包括多运动变换、分段线性变换和非刚性变换等，特征匹配结果见图3。 8个测试对的内点率分别为64.00%、68.48%、60.62%、83.70%、73.06%、13.73%、48.51%、27.17%。对于每组结果，左边图像对直观地显示了特征匹配关系，右边运动场中每个矢量的头部和尾部分别是左边图像对中两个对应特征点的位置。从结果可以直观地看出，RFM-LoDD算法在所有图像对中只保留了极少数的误匹配，表明其对不同匹配场景具有较强的鲁棒性。
图3RFM-LoDD在8个代表图像对上的特征匹配结果
Fig.3Feature matching results of RFM-LoDD on 8 representative image pairs
对RFM-LoDD算法和RANSAC、LPM、RFM-SCAN、LOGO算法在8幅代表图像对上的匹配结果进行比较。对比算法的特征匹配结果基于公开代码实现，将特征匹配准确率、召回率和F分数作为算法性能评价指标，统计结果如图4所示，横坐标表示累计图像对数量占总图像对数量的百分比，纵坐标分别表示准确率、召回率和F分数，图中曲线上坐标为（x，y）的一点分别表示有（100×x）%的图像对的准确率、召回率和F分数不超过y。从图中结果可以看出，RFM-LoDD算法的召回率高达99.48%，领先第2名1.77%。同时能够取得97.72%的准确率，仅落后于RANSAC算法。并且，RFM-LoDD算法在8幅代表图像对上具有最高的平均F分数，表明RFM-LoDD算法取得了最优的准确率-召回率权衡。
为了直观地对比RFM-LoDD算法与上述4种算法的特征匹配结果，选取图3中两个图像变换相对复杂的图像对进行实验，特征匹配结果见图5。
图4RFM-LoDD、RANSAC、LPM、RFM-SCAN、LOGO在图3中8个代表图像对上的特征匹配准确率、召回率、F分数的累计分布
Fig.4Cumulative distribution of feature matching precision, recall, and F-score for RFM-LoDD, RANSAC, LPM, RFM-SCAN, and LOGO on eight representative image pairs in Fig.3
图5RFM-LoDD、RANSAC、LPM、RFM-SCAN、LOGO的特征匹配结果直观对比
Fig.5Intuitive feature matching results of RFM-LOF, RANSAC, LPM, RFM-SCAN and LOGO
图5中第1组图像对之间存在多运动变换，4个不同的物体在两幅图像中分别产生了不同的运动，且图像中存在大片空白背景。第2组图像对涉及极线几何变换，且图像内容存在相似的纹理，如建筑物的窗户。从匹配结果可以直观地看出，相比于其他4种算法，本文RFM-LoDD算法面对复杂的特征匹配场景具有更强的鲁棒性。
2.6 图像数据集实验结果
在VGG、Retina、AdelaideRMF、RS这4个公开数据集上对RFM-LoDD算法和RANSAC、LPM[11]、RFM-SCAN[14]、LOGO[13]算法进行全面比较。4个数据集中假定匹配的平均数量分别为693.17、69.03、341.68、445.34。初始内点率、准确率、召回率、F分数以及运行时间的统计分布见图6。
图6VGG，Retina，AdelaideRMF，RS数据集的内点率累计分布以及RFM-LoDD，RANSAC，LPM，RFM-SCAN，LOGO在4个数据集上的准确率、召回率、F分数和运行时间的累计分布
Fig.6Cumulative distribution of inlier ratio for VGG, Retina, AdelaideRMF, RS datasets and cumulative distribution of precision, recall, F-score, run time for RFM-LoDD, RANSAC, LPM, RFM-SCAN, and LOGO on four datasets
从图6结果中可以看出，RANSAC算法的准确率非常稳定，在VGG、AdelaideRMF和RS数据集上均获得了领先的准确率。但是，在内点率较低的Retina和AdelaideRMF数据集上RANSAC的召回率较低，平均召回率仅为37.27%和33.02%，显著低于其他算法。虽然可以通过增加迭代次数提高RANSAC算法的召回率，但会大幅增加算法的时间成本。LPM算法在Retina、AdelaideRMF和RS数据集上的准确率和召回率都比较稳定。但在VGG数据集上，LPM的召回率相比其他算法较低。RFM-SCAN算法总体上比较稳定，在准确率和召回率之间取得了较好的平衡。LOGO算法的准确率较为稳定，但在内点率较低的Retina数据集上其召回率与其他算法的差距较大。RFM-LoDD算法的表现十分稳健，准确率都保持在92%以上，召回率都保持在93%以上，特别是在内点率较低的Retina数据集和AdelaideRMF数据集上都获得了最高的平均F分数，表明RFM-LoDD算法具有良好的综合性能，且对大量外点和涉及非刚性变换的匹配场景具有很强的鲁棒性。此外，RFM-LoDD算法非常高效，综合匹配效率仅落后于LPM算法，通常只需要几十毫秒就可以完成数百个假定匹配的误匹配剔除。
2.7 鲁棒性测试实验结果
为了测试RFM-LoDD算法在外点率极高情况下的鲁棒性，选择图5中的两个图像对，通过随机剔除或添加外点的方式使其外点率以0.05的间隔从0.05递增至0.95。重复实验20次，并以算法在不同外点率时的平均准确率、平均召回率和平均F分数为评价指标，统计结果见图7。图中横坐标表示外点率，纵坐标分别表示准确率、召回率和F分数。从图7中可以看出，所有方法的性能整体上都随着外点率的增加而下降，但RFM-LoDD算法在准确率和召回率之间取得了最佳的平衡，在两个图像对中均获得了最佳的平均F分数，并且领先第2名2.5%以上。这表明，RFM-LoDD算法相比于其他4种先进的算法在外点率较高的匹配场景下具有更高的鲁棒性。
图7RFM-LoDD，RANSAC，LPM，RFM-SCAN和LOGO的鲁棒性测试
Fig.7Robustness test of RFM-LoDD, RANSAC, LPM, RFM-SCAN and LOGO
3 结论
1）本文将假定特征匹配转换为空间样本点，引入概率距离计算样本点的局部密度。统计结果表明：正确匹配和误匹配的局部密度具有显著差异，可以通过设置合适的密度阈值剔除误匹配。
2）在随机选取的40幅涉及不同变换模型的图像对上测试算法的最优参数设置，确定了具有全局最优的密度阈值和其他参数。将样本点的局部密度与密度阈值进行比较，从而剔除误匹配。
3）在代表图像对和公开数据集上的实验结果表明，本文算法能够处理各种复杂的特征匹配场景，综合匹配性能优于先进的算法。并且，本文算法具有准线性的时间复杂度，能够适用实时性匹配任务。
