修正了鲁棒估计中广泛使用的RANSAC停止准则的致命错误。
Fixing the RANSAC Stopping Criterion
- 发现经典RANSAC停止准则基于错误近似，导致采样不足。
- 实验证明该错误在低内点率、高复杂度场景下会完全失效。
- 提出精确计算概率的简单方法，可显著提升模型检测效果。
几十年来，RANSAC一直是计算机视觉及相关领域中最常用的鲁棒估计算法之一。本文的核心贡献在于揭示并修复了一个长期存在于几乎所有基于RANSAC系统的根本性错误。自1981年Fischler与Bolles提出以来，众多RANSAC变体均依赖于随机采样从最小测量子集生成优质假设的原理，并采用1981年论文中推导出的采样概率近似值来实现自适应停止。然而，这一近似从未被后续研究系统性质疑或深入分析。本文通过理论推导与实证表明，该近似会导致严重采样不足，从而无法找到良好模型，尤其在内点比例低、模型复杂度高的挑战性场景中表现尤为明显。我们提出的精确概率计算方法实现极其简单，但效果显著，有望对大量计算机视觉系统产生深远影响。
原文摘要 · Abstract (English)
For several decades, RANSAC has been one of the most commonly used robust estimation algorithms for many problems in computer vision and related fields. The main contribution of this paper lies in addressing a long-standing error baked into virtually any system building upon the RANSAC algorithm. Since its inception in 1981 by Fischler and Bolles, many variants of RANSAC have been proposed on top of the same original idea relying on the fact that random sampling has a high likelihood of generating a good hypothesis from minimal subsets of measurements. An approximation to the sampling probability was originally derived by the paper in 1981 in support of adaptively stopping RANSAC and is, as such, used in the vast majority of today's RANSAC variants and implementations. The impact of this approximation has since not been questioned or thoroughly studied by any of the later works. As we theoretically derive and practically demonstrate in this paper, the approximation leads to severe undersampling and thus failure to find good models. The discrepancy is especially pronounced in challenging scenarios with few inliers and high model complexity. An implementation of computing the exact probability is surprisingly simple yet highly effective and has potentially drastic impact across a large range of computer vision systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。