The random cluster model for robust geometric fitting

Abstract

Random hypothesis generation is central to robust geometric model fitting in computer vision. The predominant technique is to randomly sample minimal subsets of the data, and hypothesize the geometric models from the selected subsets. While taking minimal subsets increases the chance of successively "hitting" inliers in a sample, hypotheses fitted on minimal subsets may be severely biased due to the influence of measurement noise, even if the minimal subsets contain purely inliers. In this paper we propose Random Cluster Models, a technique used to simulate coupled spin systems, to conduct hypothesis generation using subsets larger than minimal. We show how large clusters of data from genuine instances of the model can be efficiently harvested to produce accurate hypotheses that are less affected by the vagaries of fitting on minimal subsets. A second aspect of the problem is the optimization of the set of structures that best fit the data. We show how our novel hypothesis sampler can be integrated seamlessly with graph cuts under a simple annealing framework to optimize the fitting efficiently. Unlike previous methods that conduct hypothesis sampling and fitting optimization in two disjoint stages, our algorithm performs the two subtasks alternatingly and in a mutually reinforcing manner. Experimental results show clear improvements in overall efficiency.