New Conditional Sampling Strategies for Speeded-Up RANSAC

Abstract

RANSAC (Random Sample Consensus) [2] is a popular algorithm in computer vision for fitting a model to data points contaminated with many gross outliers. Traditionally many small hypothesis sets are chosen randomly; these are used to generate models and the model consistent with most data points is selected. Instead we propose that each hypothesis set chosen is the one most likely to be correct, conditional on the knowledge of those that have failed to lead to a good model. We present two algorithms, BaySAC and SimSAC, to choose this most likely hypothesis set. A common use for RANSAC is for estimating the essential matrix describing the relative position of two cameras, which can be computed from stereo matches between two images. Given a set of these stereo correspondences the classic RANSAC sampling algorithm selects random subsets of five points, and for each subset computes all possible essential matrices. Each essential matrix is checked against all correspondences until one compatible with a large number of correspondences is found. RANSAC for essential matrix estimation can be a costly part of realtime Visual Navigation schemes because of the large number of hypothesis sets that must be tried before finding one uncontaminated by outliers. This number may be reduced considerably if outlier probabilities can be estimated, e.g. from stereo correspondence match strengths. PROSAC (Progressive Sample Consensus) [1] ranks data points by prior probability then selects subsets in (approximate) order of prior likelihood. Alternatively Guided-MLESAC [3] selects random subsets where each data-point is selected with probability in proportion to its prior inlier likelihood. These sampling methods fail to take into account is the information gained by testing hypothesis sets and finding them to be contaminated by outliers, unlike the two methods proposed here which are based on the following observation: a hypothesis set leading to a model consistent with few data points probably contains one or more outliers (the alternative possibility is that it contains a degenerate configuration of inliers). Hypothesis sets with one or more data points in common with this set are also now less likely, as they are likely to include the same outlier(s). Ideally at each time we will choose one of the hypothesis set that is most likely to contain no outliers based on the prior probabilities and the history of contaminated samples. This strategy minimises the number of hypotheses that must be tested before finding one consisting entirely of inliers. Unfortunately a closed-form solution for this posterior probability is algebraically intractable. Instead we present two methods of approximating this probability, both of which are shown to work well in practice.