Fixing the RANSAC Stopping Criterion

几十年来，RANSAC 一直是计算机视觉及相关领域中许多问题最常用的鲁棒估计算法之一。本文的主要贡献在于解决了一个几乎存在于所有基于 RANSAC 算法系统的长期错误。自1981年由 Fischler 和 Bolles 提出以来，基于相同原始思想的 RANSAC 算法提出了许多变体，这些变体依赖于随机抽样有很高的可能性从最小的测量子集中生成一个好的假设。1981年的论文推导了一个用于自适应停止 RANSAC 的抽样概率近似值，因此这一近似值被当今绝大多数 RANSAC 变体和实现所采用。自那时以来，这一近似值的影响未曾在后续的研究中受到质疑或深入研究。在本文中，我们从理论上推导并实际证明了这一近似值会导致严重欠采样，从而无法找到好的模型。在具有少量内点和高模型复杂度的挑战性场景中，这种差异尤为明显。计算精确概率的实现方法非常简单但效果显著，并且可能对广泛的计算机视觉系统产生重大影响。

该论文试图解决自1981年RANSAC算法提出以来，几乎所有基于该算法的系统中存在的一贯错误。具体来说，论文质疑并研究了原始RANSAC论文中关于采样概率的近似计算方法，指出这种方法在实际应用中可能导致严重欠采样，特别是在面对少量内点和高模型复杂度的情况时。

论文的关键思路在于重新审视并理论推导出RANSAC算法中采样概率的确切计算方法，而非依赖于以往的近似值。通过精确计算采样概率，可以显著提高找到优质模型的概率，尤其是在挑战性较大的场景下。这一改进虽然简单，但对计算机视觉领域的影响可能是巨大的。

论文不仅从理论上证明了现有近似方法的问题，还通过实验证明了精确计算采样概率的有效性和必要性。实验设计涵盖了多种不同复杂度的模型和不同比例的内点情况，确保结果的广泛适用性。此外，作者提供了开源代码，使得其他研究人员能够复现实验结果，并进一步探索相关问题。未来的研究可以集中在将这一改进应用于更多类型的计算机视觉任务中。

近年来，在RANSAC及其变种算法方面有许多相关研究。例如，《Probabilistic Model Fitting with Outliers using the Truncated L2 Norm》探讨了另一种处理异常值的方法；《P-NET: A Probabilistic Point Registration CNN for Localization and Environment Perception》则尝试结合深度学习与RANSAC进行点云配准；《Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography》是RANSAC算法的原始论文，奠定了该领域的基础。