Mode seeking over permutations for rapid geometric model fitting

Abstract

In this paper we show how to exploit the statistics of permutations to perform rapid hypothesis sampling for robust geometric model fitting. The permutations encapsulate data preferences for random model hypotheses, and we demonstrate that such permutations exhibit a clustering based on the membership of inliers to genuine structures in the data. We perform non-parametric mode seeking in the space of permutations, the results of which are used to derive a set of sampling distributions for minimal subset selection. Our method fully takes advantage of the allocated time by using only the most relevant subsets of the input data for hypothesis generation. Moreover it can naturally handle data with multiple structures, a condition that is usually disastrous for other methods that rely on ad hoc inlier probabilities such as keypoint matching scores. Compared to others, our method consistently returns a much lower time-to-first-solution, and median fitting error, given the same run time. © 2012 Elsevier Ltd All rights reserved.