Deterministic Sample Consensus with Multiple Match Hypotheses

RANSAC (Random Sample Consensus) is a popular and effective technique for estimat- ing model parameters in the presence of outliers. Efficient algorithms are necessary for both frame-rate vision tasks and offline tasks with difficult data. We present a determin- istic scheme for selecting samples to generate hypotheses, applied to data from feature matching. This method combines matching scores, ambiguity and past performance of hypotheses generated by the matches to estimate the probability that a match is correct. At every stage the best matches are chosen to generate a hypothesis. This method will therefore only spend time on bad matches when the best ones have proven themselves to be unsuitable. The result is a system that is able to operate very efficiently on ambiguous data and is suitable for implementation on devices with limited computing resources.