Skeletal Graphs for Efficient Structure from Motion

A few sample photos from a collection of Flickr images of Stonehenge.	An image graph for this photo collection.	Our computed skeletal graph.	A view of the complete reconstruction.

Overview

We address the problem of efficient structure from motion for large, unordered, highly redundant, and irregularly sampled photo collections, such as those found on Internet photo-sharing sites. Our approach computes a small skeletal subset of images, reconstructs the skeletal set, and adds the remaining images using pose estimation. Our technique drastically reduces the number of parameters that are considered, resulting in dramatic speedups. To compute a skeletal image set, we first estimate the robustness of two-frame reconstructions between pairs of overlapping images, then use a graph algorithm to select a subset of images that, when reconstructed, approximates the coverage and robustness of the full set. A final bundle adjustment can then optionally be used to restore any loss of accuracy.

Paper

Noah Snavely, Steven M. Seitz, and Richard Szeliski. Skeletal Graphs for Efficient Structure from Motion. In Proc. Computer Vision and Pattern Recognition (CVPR), 2008. [pdf] [bibtex]
(Note that this paper also goes by the name "Skeletal Sets".)

Results

Reconstruction of the Pantheon (overhead view) from 579 images, with 101 images in the skeletal set	Reconstruction of Piazza dei Miracoli (Pisa; overhead view) from 1130 images, with 298 images in the skeletal set
Trafalgar Square (two views; on the left, looking towards St. Martin-in-the-Fields; on the right, looking towards the Admiralty Arch). This reconstruction was created from 2973 images, with 277 in the skeletal set.

Large-Scale Structure from Motion

For more information on projects related to Internet photos, please visit the BigSFM project page.