魏若岩 金雅素
摘 要:抽样一致性算法(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.