Photo Tourism: Exploring Photo Collections in 3D

“Photo Tourism: Exploring Photo Collections in 3D”, by Noah Snavely and Steven Seitz of the University of Washington and Richard Szeliski of Microsoft Research, was presented at SIGGRAPH 2006 and published in ACM Transactions on Graphics. The authors expanded it in “Modeling the World from Internet Photo Collections”, published in the International Journal of Computer Vision in 2008, which adds new reconstructions, a fuller account of the reconstruction algorithm, a discussion of Microsoft’s Photosynth, and a set of research challenges; this article treats the two as one publication and notes where they differ. Together they recovered where each photo of a landmark from Flickr or an image search was taken, along with a sparse 3D model of the scene, and used that geometry to browse the collection in 3D: flying between photos, finding better views of an object, and carrying text annotations to every photo of the same object. The authors described it as the first successful demonstration of structure from motion on internet photo collections. The reconstruction problem as understood today is described in structure from motion.

Problem

The paper starts from browsing. Photo sharing had produced enormous collections of popular sites (a Google image search for Notre Dame Cathedral, the 2006 paper notes, returned over 15,000 photos), but search engines and Flickr presented them as pages of thumbnails. Map-based browsers needed GPS or manual locations, which most photos lacked.

Recovering the cameras from the images meant structure from motion on data it had not been shown to handle. The closest systems, Brown and Lowe’s (2005) reconstruction of unordered image sets and Schaffalitzky and Zisserman’s (2002) multi-view matching, addressed the same problem but, the authors argued, had been tested on much simpler datasets. A typical Photo Tourism collection mixed hundreds of cameras, zoom levels, and resolutions, with different seasons, lighting, weather, and occlusion. The authors cast their system as an automatic way to build something like the 1980 Aspen Movie Map, which had taken a team of over a dozen people a few years.

Contribution

• Robust SfM on uncontrolled photos. An incremental pipeline, close to Brown and Lowe’s, with changes the authors credit for its robustness: initializing each new camera by pose estimation, a different rule for choosing the initial pair, a conditioning check before adding points, and focal lengths from EXIF tags.
• A 3D photo explorer. Photos are shown in place in the reconstructed scene, with transitions that move a virtual camera between them and morph one image into the next.
• Geometric browsing tools. Requests for close-ups, zoom-outs, or what lies to the left of the current photo are answered by projecting the reconstructed points between cameras, and dragging a box around an object finds the best photo of it.
• Annotation transfer. A label attached to a region of one photo appears in every registered photo that sees the same points, at a sensible scale.

Method

Reconstruction

The pipeline is the incremental one described in structure from motion, which also covers the 2006 paper’s camera model, seed-pair rule, and focal-length initialization. In outline, every pair of images is matched by approximate nearest-neighbor search on SIFT descriptors, typically several thousand per image, and verified by a fundamental matrix fitted with RANSAC; pairs left with fewer than twenty inliers are dropped, and the rest are chained into tracks. Cameras are added by the direct linear transform inside RANSAC, and the model is refined by bundle adjustment with Lourakis and Argyros’s sparse bundle adjustment library. For speed and robustness, tracks with a high reprojection error are removed after each optimization, and every camera with at least $0.75M$ matches to existing points is added at once, where $M$ is the best camera’s count.

The reconstruction is defined only up to a similarity, so the user aligns it to an overhead map by rotating, translating, and scaling it interactively, with the vertical direction estimated automatically; for landscapes, the optimization is rerun with an extra term fitting a digital elevation map. A new photo dropped onto the map is matched only to the twenty nearest cameras, and its pose took around ten seconds to optimize.

The journal version gives details the 2006 paper leaves out and changes several steps. Matching uses Lowe’s ratio test with a threshold of 0.6 (the SIFT paper). The seed must have at least 100 matches and the lowest fraction of homography inliers, and its relative pose comes from Nistér’s five-point algorithm. Points are triangulated only if two of their rays meet at more than 2°, the outlier threshold adapts to each image’s distribution of reprojection errors, and each camera gains two regularized radial distortion coefficients.

Photo explorer

The explorer draws photos as frusta against the reconstructed points, or uses a non-photorealistic mode that projects blurred photos onto planes fitted to each camera’s points. Moving between photos interpolates the camera and morphs the images, by default by projecting both onto a plane fitted to their shared points, which the authors preferred to a triangulated mesh because its artifacts were less objectionable. The browsing tools need only which points each camera sees: a photo counts as a detail, similar view, or zoom-out of the current one by the relative size of the projected shared points, and a selected object is scored in every image by visibility, viewing angle, and apparent size. An annotation transfers to another photo that sees at least one annotated point when the annotation covers between 5% and 80% of that image.

Results

The 2006 paper reported two personal collections, each taken by one person with one camera and lens: Prague, 197 photos of the Old Town Square, and Great Wall, 120 photos of which 82 were registered. Four collections came from Flickr searches, and the system registered one connected component of each:

Collection	Photos downloaded	Photos registered
Notre Dame	2,635	597
Yosemite (Half Dome)	1,882	325
Trevi Fountain	466	360
Trafalgar Square	1,893	278

The average reprojection error was 1.516 pixels, on images averaging 1,611 by 1,128 pixels. SfM took from a few hours for Great Wall to about two weeks for Notre Dame, dominated by bundle adjustment, which slowed as photos were added and as more cameras observed the same points. As a demonstration, the authors aligned the Half Dome model to an elevation map and registered Ansel Adams’s 1960 photograph “Moon and Half Dome” to estimate where he had stood.

The journal paper reported eleven collections, eight from the internet, timing the complete pipeline on 3.80 GHz Pentium 4 processors, with feature detection and matching run in parallel on ten of them and SfM on one. Notre Dame registered 598 of 2,635 photos with 305,535 points in 12.7 days and a mean reprojection error of 0.616 pixels; the fastest internet set, Trevi Fountain, registered 370 of 466 photos in 20.5 hours. Its new sets included Mount Rushmore, the Sphinx, St. Basil’s, and the Colosseum, where only the outside was reconstructed. It attributes the run time to pairwise matching, quadratic in the number of photos but parallelizable, and incremental bundle adjustment.

Impact

In a press release of 1 August 2006, the week the paper was presented at SIGGRAPH, Microsoft announced Photosynth, the first prototype from Microsoft Live Labs, based on the paper. The journal paper describes the Photosynth technology preview as using the same camera positions and points with a different interface: photos are suggested as the cursor moves over the scene, and image data is streamed at the resolution needed.

Snavely released the reconstruction code as Bundler, version 0.1 dated 10 August 2008; its page says an earlier version of the system was used in Photo Tourism, and describes a typical pipeline that feeds Bundler’s cameras to Furukawa’s PMVS2 multi-view stereo software. When Schönberger and Frahm (2016) presented COLMAP, they compared it with Bundler, the state-of-the-art open-source incremental system, and reported COLMAP more than 50 times faster on their internet collections. The project page also offers several image collections with reconstructions, and, it states, a database of corresponding image patches that Simon Winder and Matthew Brown built from the project’s data.

Limitations

The 2006 paper names these limitations:

• Run time. SfM slowed as more cameras were registered.
• No metric guarantee. Without ground control points, the reconstruction was not guaranteed to be metric, and low-frequency drift could prevent alignment to a map by a similarity transformation.
• No lens distortion. The camera model ignored it, at a cost in accuracy; the journal version added radial distortion.
• Hard scenes. Repeating structures and scenes without strong features were difficult.
• One component. Only one connected component of the photos was reconstructed. Unregistered photos mostly showed other parts of the scene, but some were too blurred, noisy, dark, or isolated in viewpoint to match.
• Interface. Large collections filled the view with frusta, and the authors wanted better morphing and view interpolation.

The journal paper adds that the initial-pair rule occasionally chose a pair with too short a baseline, which was then specified by hand, and that photos the camera model could not represent, such as fisheye images and montages, had to be identified by hand.

What Came After

The journal paper closed with challenges for the field, led by scale (reconstructing from millions of photos) and variability (matching across large changes in appearance, such as ground and aerial views or historical and modern photos). The same group took up scale. Skeletal graphs (Snavely et al., 2008) reconstruct a small subset of images chosen to approximate the accuracy of the full set and add the rest afterwards, close to the better registration order the 2006 paper had proposed, and Building Rome in a Day (Agarwal et al., 2009) combined skeletal sets with distributed matching and Photo Tourism’s incremental algorithm to reach city scale. The structure from motion article follows this line to COLMAP, global methods, and learned reconstruction.