The generation of random numbers is too important to be left to chance. — R. R. Coveyou

We present a novel variant of the RANSAC algorithm that is much more efficient, in particular when dealing with problems with low inlier ratios. Our algorithm assumes that there exists some grouping in the data, based on which we introduce a new binomial mixture model rather than the simple binomial model as used in RANSAC. We prove that in the new model it is more efficient to sample data from a smaller numbers of groups and groups with more tentative correspondences, which leads to a new sampling procedure that uses progressive numbers of groups. We demonstrate our algorithm on two classical geometric vision problems: wide-baseline matching and camera resectioning. The experiments show that the algorithm serves as a general framework that works well with three possible grouping strategies investigated in this paper, including a novel optical flow based clustering approach. The results show that our algorithm is able to achieve a significant performance gain compared to the standard RANSAC and PROSAC.
Matching problems with low inlier ratios can be very hard, e.g. a lot of repetitve textures.

Local heuristic measures are often unreliable.

Typically, there is some grouping of the data. Key Idea: Fewer groups are better ! Any sample invoving outlier groups is wrong.

For camera resectioning, group by the parent images of the 3D points.