MIT Electrical Engineering and Computer Science EECS Event

Structure from Motion without Correspondence

Frank Dellaert
Carnegie Mellon University

Monday, April 2, 2001
4:15 PM (refreshments 4:00)
Room NE43-518
EECS Special Seminar

Abstract

"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 can arise in such diverse fields as target tracking, computational biology, and data mining.