Computer Science Department
School of Computer Science, Carnegie Mellon University


EM, MCMC, and Chain Flipping for Structure from
Motion with Unknown Correspondence

Frank Dellaert, Steven M. Seitz, Charles E. Thorpe, Sebastian

July 2000

Keywords: Computer vision, 3D scene analysis, strcutre from motion, correspondence, data association, probabilisitic algorithms, expectation-maximization, Markov processes, Markov chain Monte Carlo

Learning spatial models from sensor data often raises a challenging data association problem of relating parameters in the model to individual measurements. This paper proposes an algorithm based on EM, which simultaneously solves the model learning and the data association problem. The algorithm is developed in the context of the the structure from motion problem, which is the problem of learning a 3D scene model from a collection of image data. To accommodate the spatial constraints in this domain, we introduce the notion of "virtual measurements" as sufficient statistics to be used in the M-step, and develop an efficient Markov chain Monte Carlo sampling method called "chain flipping", to calculate these statistics in the E-step. Experimental results show that we can solve hard data association problems when learning models of 3D scenes, and that we can do so efficiently. We conjecture that this approach can be applied to a broad range of model learning problems from sensor data, such as the robot mapping problem.

31 pages

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

This page maintained by