
CMUCS00144
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS00144
EM, MCMC, and Chain Flipping for Structure from
Motion with Unknown Correspondence
Frank Dellaert, Steven M. Seitz, Charles E. Thorpe, Sebastian
July 2000
CMUCS00144.ps
CMUCS00144.pdf
Keywords: Computer vision, 3D scene analysis, strcutre from motion,
correspondence, data association, probabilisitic algorithms,
expectationmaximization, 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
Mstep, and develop an efficient Markov chain Monte Carlo sampling
method called "chain flipping", to calculate these statistics in
the Estep. 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
