抽样一致性及其改进算法综述

魏若岩 金雅素

摘 要：抽样一致性算法（Random Sample Consensus，RANSAC）是一种稳健的模型估计方法，该方法广泛应用于机器视觉领域。针对图像匹配模型的鲁棒估计问题，首先分析了RANSAC改进算法，然后对RANSAC、Optimal-RANSAC、NAPSAC、Mapsac以及RANSAC-Tdd等算法进行了对比实验，最后通过实验结果分析了各种改进算法的优缺点。

关键词： RANSAC;模型估计;图像匹配;机器视觉

【Abstract】 RANSAC is a robust method for model estimation，this method has been widely used in machine vision.For the problem of estimating image matching model，this paper firstly analyzes the improved RANSAC algorithm; then，series of comparative experiments are conducted on the algorithms such as RANSAC，Optimal-RANSAC，NAPSAC，Mapsac and RANSAC-Tdd to test their performance; finally， the features analysis of various improved algorithms are given.

【Key words】  RANSAC; model estimation; image matching; machine vision

0 引 言

在機器视觉领域，大量的图像匹配算法被提出[1～3]，其中较为常用的是Fischler等人[2， 4]在1981年提出的RANSAC，其易于实现而且鲁棒性高，但是在准确性、有效性和稳定性方面存在一定的不足，针对这些问题，提出了一些改进算法。对此可展开研究论述如下。

1 RANSAC算法概述

目前，RANSAC算法已广泛应用于机器视觉领域，是经典的模型鲁棒估计算法。该算法通过抽取最小样本计算出可能的模型参数，再将模型参数回带到所有的数据样本并计算相应的内点率，直到迭代次数大于预定次数，或当前最优模型的内点率达到设定的阈值，就把目前最优结果作为最终模型、且停止抽样，否则继续抽样。RANSAC算法的运行步骤详见如下。

Step 1 随机抽取能计算出模型参数的最小数量的样本。

Step 2 从抽取的样本中计算出模型参数。

Step 3 将参数回带到所有数据样本并统计内点率，若当前内点率最大，则将模型定为当前最优模型。

Step 4 若当前最优模型的内点率大于设定的阈值或迭代次数大于预定次数，则迭代停止，否则重复Step 1～Step 3。

Step 5 输出当前最优模型。

2.4 基于优化的方法

2.4.1 LO-RANSAC

LO-RANSAC[22]（Locally optimized RANSAC）算法需要设置一个固定的迭代次数，并从返回的内点集中重新抽样计算模型，最后选取最优的匹配模型作为改进后的结果，从未受污染的最小样本中计算出的模型总是包含大量内点，因此将一个优化步骤插入到RANSAC算法中，以当前的最优解作为优化的起点。

文献[15]指出LO-RANSAC可采用多种优化策略，比如以精度换取效率，可以执行一个inner-RANSAC过程;采用迭代方法，首先选择误差小于Kt的所有数据点，这里的K是预定义尺度因子，t是误差阈值，然后用所有选定的点来估计新模型，降低阈值比例因子并将继续迭代此过程，直到阈值达到t为止。两种策略组合比较常见，其中inner-RANSAC中的每个（非最小）样本都受迭代精化过程的制约，这种组合通常会减少RANSAC的迭代次数，使其与理论预期数一致。

2.4.2 OPTIMAL-RANSAC

OPTIMAL-RANSAC[23]类似于LO-RANSAC算法，可对一组初始值进行多次重采样，再对模型进行迭代估计并给出相应的内点数。分析可知，此算法与LO-RANSAC存在差异，对此可表述如下：

（1）当发现一组具有5个以上暂定变量的集合时，就会执行优化，对于低内点率的集合很重要。

（2）集合大于当前最大的暂定内点集合时，从该集合开始重采样，不断迭代直至找到最大集合。

（3）迭代重估计和取心使用相同的公差，即集合将不断增长，直到集合停止变化，迭代停止，即找到最优集合的概率很高。

（4）以较低的公差进行修剪以保留最好的内点，在每一步中使用剩余内点重新计算。

该算法的缺点主要是当图像包含多个平面时，不能保证找到最优集，因为可以有多个次优集以给定的公差完成转换。在任何情况下，该算法都能有效地找到次优集，但是无法保证每次都会找到相同的次优集。OPTIMAL-RANSAC具有较好的性能，该方法能处理外点率高于95%的样本。

3 实验分析

本节将从2个方面来做研究探讨。其一，是利用模拟数据对上述算法进行对比实验并得出结论;其二，是利用真实图像对上述算法进行对比实验并得出结论。由于资源有限，本文只对部分算法进行实验，分别为：RANSAC、OPTIMAL-RANSAC、Mlesac、Mapsac、NAPSAC、RANSAC-Tdd。对此研究可做详尽表述如下。

3.1 基于模拟数据的对比实验

模拟数据由1 000个匹配点构成，设置内点率从0.2到0.8，0.05为步长，假设经过数据过滤后有n个匹配点，则参数信息见表2。

图1给出了3组原始数据与过滤后数据的对比图像。图1（a）为原始数据，其内点率分别为0.2、0.5、0.8;图1（b）为对应的过滤后的数据。由图1可知内点率越高，过滤的效果越好，模型越准确。

图2给出了部分算法在不同内点率下的完成时间。各算法在每个内点率上运行20次后求其平均时间。从图2中可以看出，所有算法的运行时间与数据内点率的上升成反比例关系，OPTIMAL-RANSAC在各个内点率下所使用的時间最少，其余算法在内点率0.1～0.2内需较长的时间，当内点率大于0.3时，NAPSAC、OPTIMAL-RANSAC、Mapsac的运行时间接近。

图3～图4给出了6个算法在不同迭代次数下的内点查全率。由图3～图4可以看出，无论内点率是0.1还是0.3，所有算法的内点查全率随着迭代次数的增加均呈增长趋势，当内点率为0.1时，迭代次数在100～800之间时，OPTMAL-RANSAC的优势明显。当内点率为0.3时，OPTIMAL-RANSAC、RANSAC、NAPSAC的内点查全率较为接近。

3.2 基于真实图像的对比实验

有7组真实图像见表3，依次为：Building、Wall、Graft、Book、Boat1、Boat2、Asteroid。其中，Building、Wall与Graft体现了图像间的透视变化，其余图像体现了图像间的水平旋转变化。所有算法实验的最大迭代次数均为5 000，在匹配过程中使用SIFT特征点和描述方式，选取4个指标分别为：查找到的内点数I、算法的迭代次数t、每个模型所需检测的次数vpm（number of verification per model）、算法运行时间times（/s）。研究中得到的上述指标的比较结果见表4。所有算法在每对图像上均运行20次，而后计算出每个指标的平均值，通过分析可发现以下特点：

在查找内点数I方面，OPTIMAL-RANSAC具有较好的性能，尤其在Graft和Wall两对图像中查找到的内点数较多;在迭代次数t与运行时间times上，OPTIMAL-RANSAC显然要胜过其它算法，这是因为OPTIMAL-RANSAC是一种优化算法，每次迭代都要计算出一个数据核，并且在数据核中再进行抽样和模型检验，因此必然增大了每次迭代的时间成本;在模型的整体检测次数上，RANSAC-Tdd具有明显的优势，主要原因在于RANSAC-Tdd选取远小于匹配点数目的d个匹配点作为测试点，只有当d个匹配点都符合当前匹配模型时再对剩余的匹配点进行测试，否则抛弃当前模型，这就必然会减少每个模型的验证次数。

4 结束语

本文先是分析了RANSAC算法的缺点，然后研究了4类改进算法，并论证了各自的性能。总地来说，基于模型求解的方法，其中的M估计和LMedS当内点率大于50%时，不能得到理想模型，Mlesac和Mapsac对于较高外点率的数据能估计出理想模型，但是当外点率大于80%时，效果急剧下降;而针对基于样本预检验的方法，其中的RANSAC-Tdd在样本内点率较高时能得到较为理想的效果，但是当内点率很低时，就会陷入无限次抽样与检验中，Bail-out Test与RANSAC相比，性能提高2～7倍;与此同时，针对基于样本选择的方法，其中的PROSAC主要依赖于样本特征点的相关描述，NAPSAC却依赖于内点的聚集性，GROUPSAC则综合了PROSAC和NAPSAC算法的优缺点，抽样效率很高;此外，针对基于优化的方法，其中的OPTIMAL-RANSAC能处理外点率高于95%的样本。

所以，RANSAC及其改进算法有待从如下方面加以研究，对此可表述为：

（1）完善外点的过滤策略，提高内点在算法迭代中的权重。

（2）提高算法对各种图像的适应性及时效性。

（3）将多个算法进行融合来克服单个算法的缺点，以提高算法的准确性。

参考文献

[1]CHOI S，KIM T，YU W. Performance evaluation of RANSAC family[C]//British Machine Vision Conference，BMVC 2009.London，UK： Dblp，2009：1-13.

[2]RAGURAM R，CHUM O，POLLEFEYS M，et al.USAC： A universal framework for random sample consensus[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，35（8）：2022-2038.

[3]魏若岩，阮晓钢，于乃功，等.基于Skinner操作条件反射的抽样一致性算法[J].控制与决策，2015，30（2）：235-240.

[4]FISCHLER M A，BOLLES R C. Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the ACM，1981，24（6）： 381-395.

[5]CHEN J H，CHEN C S，CHEN Y S.Fast algorithm for robust template matching with M-estimators[J].IEEE Transactions on Signal Processing，2003，51（1）：230-243.

[6]CHUM O，WERNER T，MATAS J.Epipolar geometry estimation via RANSAC benefits from the oriented epipolar constraint[C]// Proceedings of the 17th International Conference on Pattern Recognition， ICPR 2004.Cambridge， UK：IEEE，2004，1：1-4.