Random sample consensus¶
Why this mattered¶
RANSAC mattered because it changed model fitting from a problem that assumed mostly reliable measurements into one that could operate when many measurements were simply wrong. Earlier least-squares-style approaches were powerful for small, roughly Gaussian errors, but they were easily dominated by gross outliers from mismatched features, spurious detections, or occlusions. Fischler and Bolles inverted the emphasis: instead of fitting to all data and trying to explain errors afterward, RANSAC repeatedly fit a model from a minimal random subset, then asked how many other observations agreed with it. That made consensus, not average error, the central criterion.
This was a paradigm shift for computer vision because it made geometric inference practical in cluttered, noisy scenes. The paper’s Location Determination Problem showed the point directly: an automated system could recover camera pose from image landmarks even when feature detectors supplied unreliable correspondences. More broadly, RANSAC gave researchers a general recipe for robust estimation whenever a model could be generated from a small number of samples: hypothesize from a minimal set, verify against the data, and keep the hypothesis with sufficient support.
Its influence is visible across later vision and robotics breakthroughs. RANSAC became a standard component in feature matching, homography and fundamental-matrix estimation, structure from motion, visual odometry, SLAM, object recognition, and 3D reconstruction. It helped make pipelines based on local features and geometric verification reliable enough to scale from controlled laboratory scenes to real images. Later variants refined its sampling, scoring, and termination rules, but the core idea remained the same: robust perception can be built by searching for a coherent model inside unreliable evidence.
Abstract¶
A new paradigm, Random Sample Consensus (RANSAC), for fitting a model to experimental data is introduced. RANSAC is capable of interpreting/smoothing data containing a significant percentage of gross errors, and is thus ideally suited for applications in automated image analysis where interpretation is based on the data provided by error-prone feature detectors. A major portion of this paper describes the application of RANSAC to the Location Determination Problem (LDP): Given an image depicting a set of landmarks with known locations, determine that point in space from which the image was obtained. In response to a RANSAC requirement, new results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form. These results provide the basis for an automatic system that can solve the LDP under difficult viewing
Related¶
- enables → Robust principal component analysis? — RANSAC enables robust PCA by establishing the idea that model structure can be estimated despite sparse gross outliers.
- cite ← Robust principal component analysis? — Robust PCA relates to RANSAC through the shared problem of estimating low-dimensional structure in the presence of outliers.