Structure from Motion without Correspondence

Frank Dellaert


"Structure from motion" is the problem of recovering the 3D structure of a scene from a set of 2D views. Its applications range from building models of small objects to constructing large scale environment models.

I will address the hard continuous-discrete optimization problem that arises when the correspondence between 2D measurements in the different views is unknown. To attack this problem, I combine tools from optimal estimation with Monte Carlo approximation methods designed to speed up the combinatorial data-association problem. In the talk, I will also discuss an efficient Markov chain sampler, developed by generalizing graph-theoretic algorithms for bipartite graph matching. The final algorithm is intuitive, fast, and works well in practice, as will be demonstrated using results on several real image sequences.

While developed within the context of a computer vision, I conjecture that the methods I describe are more broadly applicable, i.e., whenever a large optimization problem is paired with a hard data-association problem. Such problems commonly arise in such diverse fields as target tracking, computational biology, and data mining.

Papers on this topic can be found at:

Note: this is going to be essentially my academic job talk, wich I'm in the process of refining. I would welcome any comments you might have, especially with regards to how well it would do as a job talk. Also, there will be a lot of redunandcy with an earlier VASC talk, but there is some new stuff as well.

Charles Rosenberg
Last modified: Sat Feb 10 11:22:48 EST 2001