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.

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.