The Random Sample Consensus (RANSAC) algorithm

In this work, we present a technique for robust estima-tion, which by explicitly incorporating the inherent uncer-tainty of the estimation procedure, results in a more ecient robust estimation algorithm. In addition, we build on re-cent work in randomized model veri®cation, and use this to characterize the `non-randomness ' of a solution. The combination of these two strategies results in a robust esti-mation procedure that provides a signi®cant speed-up over existing RANSAC techniques, while requiring no prior in-formation to guide the sampling process. In particular, our algorithm requires, on average, 3-10 times fewer samples than standard RANSAC, which is in close agreement with theoretical predictions. The eciency of the algorithm is demonstrated on a selection of geometric estimation prob-lems