Overview
RANSAC homography estimation repeatedly samples small correspondence sets, fits a homography, and counts inliers under a reprojection threshold. The best model is refit from its inliers.
CoreSource checked
RANSAC Homography Estimation
Estimates a planar homography while rejecting mismatched feature correspondences.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Image Processing
- Difficulty
- Intermediate
- Family
- Robust Estimation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
image registrationrobust estimationrandom samplingfeature matchingimage processing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when many correspondences may be outliers but the scene is approximately planar.
- Use when a geometric inlier threshold can be chosen from image noise and scale.
When Not to Use
- Avoid when the scene is not well modeled by a single homography.
- Avoid when there are too few nondegenerate correspondences.
What It Does
- Samples minimal point-correspondence sets
- Fits candidate homographies
- Keeps the model with the strongest inlier support
Use Cases
- Image stitching and panorama alignment
- Planar object localization
- Filtering feature matches between two views
Inputs
- Putative 2D point correspondence pairs (x_i, x'_i) containing outliers
- Inlier reprojection threshold ε and iteration count N
Outputs
- Best-fit 3x3 projective homography matrix H
- Consensus inlier mask separating true matches from outliers
Pseudocode
- 1.Repeat for a fixed number of trials or confidence target
- 2.Sample four nondegenerate correspondences
- 3.Fit a candidate homography
- 4.Count matches whose reprojection error is below the threshold
- 5.Keep the candidate with the largest inlier set
- 6.Refit the homography from all inliers and return it
Canonical Example
- Input
- matched points between a poster image and a camera image, with some false matches
- Output
- homography mapping poster coordinates into the camera image
- Explanation
- RANSAC tries many four-point fits and keeps the transform with the most low-error matches.
Implementation Notes
- Normalize point coordinates before fitting when using linear solvers.
- Reject degenerate samples and require enough spatially spread inliers.
- Refit the final homography from all inliers rather than using the sampled model directly.
Common Pitfalls
- Collinear sample points produce degenerate homographies.
- A threshold tuned for one image scale may fail at another scale.
- Stopping too early can miss the correct model when the outlier rate is high.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow sampling point correspondences and fitting the homography with most inliers on a small image registration example.
Step 1 of 6: Repeat for a fixed number of trials or confidence target
image-processing-mechanismNotes
The inlier threshold is a modeling choice, not a universal constant.
Sources (2)
What each reference supports for this entry.
RANSAC
PaperOriginal RANSAC paper supporting robust model fitting under outliers for homography estimation.
Open sourceComputer Vision: Algorithms and Applications
BookComputer-vision reference covering RANSAC Homography Estimation model fitting, restoration, segmentation, or geometric image-analysis workflow.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageRelated Algorithms
Tags
Image ProcessingRandomnessGraph