Frank Dellaert

Monte Carlo EM for Data Association and its Applications in Computer Vision Degree Type: Ph.D. in Computer Science
Advisor(s): Charles Thorpe, Sebastian Thrun
Graduated: December 2001

Abstract:

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.

Thesis Committee:
Charles E. Thorpe (Co-Chair)
Sebastian Thrun (Co-Chair)
Takeo Kanade
Richard Szeliski

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Computer vision, correspondence problem, data association