Spectral Partitioning for Structure from Motion

Drew Steedly      Irfan Essa      Frank Dellaert

GVU Center, College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280, USA

To appear in: International Conference on Computer Vision 2003

We present a novel partitioning method for large-scale optimization problems, specifically structure from motion, inspired by spectral partitioning. In the structure from motion domain, partitioning methods can be used to convert the problem into smaller and better conditioned subproblems which can be efficiently optimized. We propose a partitioning method that uses only the Hessian of the reprojection error and its eigenvectors. We show that partitioned systems that preserve the eigenvectors corresponding to small eigenvalues result in lower residual error when optimized. We create partitions by clustering the entries of the eigenvectors of the Hessian corresponding to small eigenvalues. This is a more general technique than used in methods relying on domain knowledge and heuristics such as bottom up structure from motion approaches. Simultaneously, it also takes advantage of more information than generic matrix partitioning algorithms.


Pillar Sequence

A few images from a 37 sec (1108 total images) video sequence circumnavigating a pillar. The estimated point position is drawn as a green circle. The measured point position in the image is drawn as a red cross. The measurement tracks from the previous five images are shown as red trails

(Click on images for larger views)

A view of the 3D reconstruction from above and behind the first/last cameras. On the left, the camera trajectory is shown in red and the 3D points are plotted in blue. On the right, the results of partitioning are shown by color coding the cameras based on partition assignment. The camera traveled in a counter clockwise direction.

A VRML of the 3D reconstruction. For clarity, only 56 of the 1108 cameras are drawn. Cameras are drawn as small pyramids. The camera center is at the tip of the pyramid and the camera axis is perpendicular to the pyramid base. Points are drawn as green dots. Some VRML viewers have trouble displaying the points. If you cannot see them, try the latest version of the Cortona viewer.