Addressing the Correspondence Problem: A Markov Chain Monte Carlo Approach

Abstract

Many vision and AI techniques assume that some form of the infamous correspondence problem has been solved. Typically, a best mapping between sets of features is found either as a pre-processing step or as a side-effect of applying the technique. In this paper we argue that it is incorrect to insist on a single 'best' mapping between features in order to estimate a property that depends on this correspondence. Instead, one should take into account the posterior distribution over all possible mappings, given the measured feature data. The estimate thus obtained can differ substantially from the one where a best mapping is first singled out. The main contribution in this paper is to show how Markov Chain Monte Carlo methods can be used to efficiently sample the correct distribution over correspondences, and how this sample can subsequently be used to estimate a property of interest. We will show examples and results for several applications, including pose estimation and structure from motion. The method we propose can be used in any application where the correspondence problem is a central component.