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

Frank Dellaert, Steven M. Seitz, C. Thorpe, and Sebastian Thrun

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.

Paper available in postscript (gzipped) and PDF.

@ARTICLE{Dellaert00c,
  AUTHOR         = {Dellaert, F. and Seitz, S.M. and Thorpe, C. and Thrun, S.},
  TITLE          = {{EM}, {MCMC}, and Chain Flipping for Structure 
                    from Motion with Unknown Correspondence},
  JOURNAL        = {Machine Learning},
  VOLUME         = {50},
  NUMBER         = {1-2},
  YEAR           = {2003}
}