Network Principles for SfM: Disambiguating Repeated Structures with Local Context

Kyle Wilson, Noah Snavely


Repeated features are common in urban scenes. Many objects, such as clock towers with nearly identical sides, or domes with strong radial symmetries, pose challenges for structure from motion. When similar but distinct features are mistakenly equated, the resulting 3D reconstructions can have errors ranging from phantom walls and superimposed structures to a complete failure to reconstruct. We present a new approach to solving such local visibility structure of such repeated features. Drawing upon network theory, we present a new way of scoring features using a measure of local clustering. Our model leads to a simple, fast, and highly scalable technique for disambiguating repeated features based on an analysis of an underlying visibility graph, without relying on explicit geometric reasoning. We demonstrate our method on several very large datasets drawn from Internet photo collections, and compare it to a more traditional geometry-based disambiguation technique.


--- Update 2 May 2017 --- Bugfix: The k-cover code implementation now conforms to the algorithm description in the paper. Thanks to Derek Hoiem for noticing the discrepancy! ---

--- Update 27 July 2014 --- The dataset files below have been updated to include missing README files, and to replace all EG.txt files. These were included for possible reference and are not required to run our code. They were previously miscomputed, but are now correct. ---

The datasets in the paper are available in two downloads: the matches and tracks used as input for disambiguation and reconstruction, and the original images. The images are not necessary to run the code.
Full Paper ICCV2013
PDF (13MB)
Poster ICCV2013
PDF (13MB)
MATLAB code used to generate results in the paper.
Matches and tracks for Seville
tar.gz (71MB)
Images for Seville
tar.gz (1.6GB)
Matches and tracks for SacreCoeur
tar.gz (263MB)
Images for SacreCoeur
tar.gz (3.1GB)
Matches and tracks for Louvre
tar.gz (37MB)
Images for Louvre
tar.gz (3.5GB)
Matches and tracks for NotreDame
tar.gz (898MB)
Images for NotreDame
tar.gz (8.0GB)

BibTeX entry

   Title = {Network Principles for SfM: Disambiguating Repeated Structures with Local Context}
   Author = {Kyle Wilson and Noah Snavely},
   booktitle = {Proceedings of the International Conference on Computer Vision ({ICCV})},
   Year = {2013},

Acknowledgments.This work was supported in part by the National Science Foundation under IIS-1149393, IIS-1111534, and IIS-0964027, and a grant from Intel Corporation. We would also like to thank Chun-Po Wang and Robert Kleinberg for their valuable discussions.