Addressing the Correspondence Problem: A Markov Chain Monte Carlo Approach

January 2000

Addressing the Correspondence Problem: A Markov Chain Monte Carlo Approach

Authors:

Frank Dellaert
Technical Report
CMU-RI-TR-00-11

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.
@techreport{Dellaert-2000-7966,
author = {Frank Dellaert},
title = {Addressing the Correspondence Problem: A Markov Chain Monte Carlo Approach},
year = {2000},
month = {January},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-00-11},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.