Computer Science Department
School of Computer Science, Carnegie Mellon University


Monte Carlo EM for Data-Association
and its Applications in Computer Vision

Frank Dellaert

September 2001

Ph.D. Thesis

Keywords: Computer vision, correspondence problem, data association

Estimating geometry from images is at the core of many computer vision applications, whether it concerns the imaging geometry, the geometry of the scene, or both. Examples include image mosaicking, pose estimation, multi-baseline stereo, and structure from motion. All these problems can be modeled probabilistically and translate into well-understood statistical estimation problems, provided the correspondence between measurements in the different images is known.

I will show that, if the correspondence is not known, the statistically optimal estimate for the geometry can be obtained using the expectation-maximization (EM) algorithm. In contrast to existing techniques, the EM algorithm avoids the estimation bias associated with computing a single "best" set of correspondences, but rather considers the distribution over all possible correspondences consistent with the data. While the latter computation is intractable in general, I show that it can be approximated well in practice using Markov chain Monte Carlo sampling. As part of this, I have designed an efficient sampler specifically tuned to the correspondence problem.

Abstract The resulting Monte Carlo EM approach represents the first truly multi-view algorithm for geometric estimation with unknown correspondence. This is especially relevant in the structure from motion domain, where the state of the art relies on robust estimation of two or three-view geometric constraints. In addition, I will show that the probabilistic approach I propose allows for a seamless and principled way of integrating prior knowledge, appearance models, and statistical models for occlusion and clutter.

236 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by