Fixing the RANSAC Stopping Criterion

• URL: http://arxiv.org/abs/2503.07829v1
• Date: Mon, 10 Mar 2025 20:18:54 GMT
• Title: Fixing the RANSAC Stopping Criterion
• Authors: Johannes Schönberger, Viktor Larsson, Marc Pollefeys,
• Abstract summary: The main contribution of this paper lies in addressing a long-standing error baked into virtually any system building upon the RANSAC algorithm.<n>An approximation to the sampling probability was originally derived by the paper in 1981 in support of adaptively stopping RANSAC.<n>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.
• Score: 69.59335489157175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Controllable RANSAC-based Anomaly Detection via Hypothesis Testing [7.10052009802944]
  We propose a novel statistical method for testing the anomaly detection results obtained by RANSAC (controllable RANSAC) The key strength of the proposed method lies in its ability to control the probability of misidentifying anomalies below a pre-specified level. Experiments conducted on synthetic and real-world datasets robustly support our theoretical results.
  arXiv  Detail & Related papers  (2024-10-19T15:15:41Z)
• A sparse PAC-Bayesian approach for high-dimensional quantile prediction [0.0]
  This paper presents a novel probabilistic machine learning approach for high-dimensional quantile prediction. It uses a pseudo-Bayesian framework with a scaled Student-t prior and Langevin Monte Carlo for efficient computation. Its effectiveness is validated through simulations and real-world data, where it performs competitively against established frequentist and Bayesian techniques.
  arXiv  Detail & Related papers  (2024-09-03T08:01:01Z)
• More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling [41.21199687865359]
  We propose an algorithmic framework that incorporates different approximate sampling methods with the recently proposed Feel-Good Thompson Sampling (FGTS) approach. Our regret analysis yields the best known dependency of regret on dimensionality, surpassing existing randomized algorithms. Our algorithms achieve performance that is either better than or on par with other strong baselines from the deep RL literature.
  arXiv  Detail & Related papers  (2024-06-18T03:32:10Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
  Multi-armed bandit algorithms like Thompson Sampling can be used to conduct adaptive experiments. We present simulations for 2-arm experiments that explore two algorithms that combine the benefits of uniform randomization for statistical analysis.
  arXiv  Detail & Related papers  (2021-12-15T22:11:58Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• DPER: Efficient Parameter Estimation for Randomly Missing Data [0.24466725954625884]
  We propose novel algorithms to find the maximum likelihood estimates (MLEs) for a one-class/multiple-class randomly missing data set. Our algorithms do not require multiple iterations through the data, thus promising to be less time-consuming than other methods.
  arXiv  Detail & Related papers  (2021-06-06T16:37:48Z)
• On Efficient and Robust Metrics for RANSAC Hypotheses and 3D Rigid Registration [51.64236850960365]
  This paper focuses on developing efficient and robust evaluation metrics for RANSAC hypotheses to achieve accurate 3D rigid registration. We analyze the contributions of inliers and outliers, and then proposing several efficient and robust metrics with different designing motivations for RANSAC hypotheses.
  arXiv  Detail & Related papers  (2020-11-10T02:22:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.