Overview
RANSAC handles outliers by testing many minimal hypotheses and scoring each by how many data points agree with it.
CoreSource checked
RANSAC
Fits a model by repeatedly sampling small subsets and keeping the model with the most inliers.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Robust Estimation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Random Sample Consensus
Core Concepts
random subsetmodel hypothesisinlier thresholdoutlier rejection
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(sample cost)
Average
O(iterations * n)
Worst
O(iterations * n)
Space
O(n)
When to Use
- Use when tuning model parameters needs random subset.
- Use when the input matches the assumptions behind robust Estimation.
When Not to Use
- Avoid when the objective is cheap and convex enough for a simpler exact solver.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Fits a model by repeatedly sampling small subsets and keeping the model with the most inliers
- Uses random subset and model hypothesis to guide the work.
- Produces best candidate.
Use Cases
- Tuning model parameters
- Searching design spaces
- Fitting models to noisy data
Inputs
- Objective function
- Initial candidate or population
- Stopping rule
Outputs
- Best candidate
- Objective value
- Search history
Key Formulas (1)
RANSAC iteration count
N = log(1 − confidence) / log(1 − inlierratiosamplesize)
N = log(1 - confidence) / log(1 - inlier_ratio^sample_size)Estimates how many random trials are needed for a desired success probability.
Pseudocode
- 1.Prepare the inputs and state needed for RANSAC.
- 2.Apply the random subset step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return best candidate.
Canonical Example
- Input
- RANSAC input with a small representative case
- Output
- Best candidate
- Explanation
- RANSAC applies random subset to produce best candidate.
Implementation Notes
- Track both best-so-far and current candidate state.
- Keep the random subset step separate enough to test independently.
Common Pitfalls
- Stopping too early can make a poor local result look like convergence.
- Forgetting to check edge cases can make RANSAC look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryPlot candidate points, objective values, and improvement steps across iterations.
Step 1 of 4: Prepare the inputs and state needed for RANSAC.
optimization-mechanismNotes
RANSAC should be used with the assumptions and tradeoffs of robust Estimation in mind.
Sources (1)
What each reference supports for this entry.
Fischler and Bolles 1981
PaperOriginal RANSAC paper for robust model fitting from contaminated data.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toLinear Regression
RANSAC can fit models robustly when outliers would distort ordinary regression.
Related Algorithms
Tags
OptimizationModel FittingRobust EstimationStochastic