Optimal Randomized RANSAC
Optimal Randomized RANSAC
复制标题
DOI：
10.1109/tpami.2007.70787
复制
发表时间：
2008-08-01
影响因子：
23.6
通讯作者：
Matas, Jiri
中科院分区：
文献类型：
--
作者：
Chum, Ondrej;Matas, Jiri
提出了一种RANSAC的随机模型验证策略。所提出的方法发现，像RANSAC，一个解决方案，是最佳的用户指定的概率。该解决方案在时间上接近于最短的可能性，并且优于任何确定性验证策略的上级。一个可证明的最快的模型验证策略的设计（理论）的情况下，已知的离群值的数据污染。在这种情况下，该算法是保证解决方案的置信度的所有随机化RANSAC算法中最快的可能（平均）。最优性的推导是基于Wald的序贯决策理论，特别是一种改进的序贯概率比检验（SPRT）。接下来，介绍了具有SPRT算法的R-RANSAC。该算法消除了对离群值分数的先验知识的要求，并在线估计数量。我们的实验表明，在标准的测试数据，该方法的性能接近理论上的最优，是2到10倍的速度比标准的RANSAC，是4倍的速度比以前公布的方法。
A randomized model verification strategy for RANSAC is presented. The proposed method finds, like RANSAC, a solution that is optimal with user-specified probability. The solution is found in time that is close to the shortest possible and superior to any deterministic verification strategy. A provably fastest model verification strategy is designed for the (theoretical) situation when the contamination of data by outliers is known. In this case, the algorithm is the fastest possible (on the average) of all randomized RANSAC algorithms guaranteeing a confidence in the solution. The derivation of the optimality property is based on Wald's theory of sequential decision making, in particular, a modified sequential probability ratio test (SPRT). Next, the R-RANSAC with SPRT algorithm is introduced. The algorithm removes the requirement for a priori knowledge of the fraction of outliers and estimates the quantity online. We show experimentally that on standard test data, the method has performance close to the theoretically optimal and is 2 to 10 times faster than standard RANSAC and is up to four times faster than previously published methods.