Abstract
How best to efficiently establish correspondence among a large set of images or video frames is an interesting unanswered question. For large databases, the high computational cost of performing pair-wise image matching is a major problem. However, for many applications, images are inherently sparsely connected, and so current techniques try to correctly estimate small potentially matching subsets of databases upon which to perform expensive pair-wise matching. Our contribution is to pose the identification of potential matches as a link prediction problem in an image correspondence graph, and to propose an effective algorithm to solve this problem. Our algorithm facilitates incremental image matching: initially, the match graph is very sparse, but it becomes dense as we alternate between link prediction and verification. We demonstrate the effectiveness of our algorithm by comparing it with several existing alternatives on large-scale databases. Our resulting match graph is useful for many different applications. As an example, we show the benefits of our graph construction method to a label propagation application which propagates user-provided sparse object labels to other instances of that object in large image collections.
Chapter PDF
Similar content being viewed by others
References
Snavely, N., Seitz, S.M., Szeliski, R.: Photo tourism: exploring photo collections in 3D. ACM TOG (Proc. SIGGRAPH) 25, 835–846 (2006)
Raguram, R., Wu, C., Frahm, J.M., Lazebnik, S.: Modeling and recognition of landmark image collections using iconic scene graphs. IJCV 95(3), 213–239 (2011)
Heath, K., Gelfand, N., Ovsjanikov, M., Aanjaneya, M., Guibas, L.J.: Image webs: computing and exploiting connectivity in image collections. In: Proc. IEEE CVPR, pp. 3432–3439 (2010)
Gammeter, S., Bossard, L., Quack, T., Gool, L.V.: I know what you did last summer: object-level auto-annotation of holiday snaps. In: Proc. ICCV, pp. 614–621 (2009)
Zheng, Y.T., Zhao, M., Song, Y., Adam, H., Buddemeier, U., Bissacco, A., Brucher, F., Chua, T.S., Neven, H.: Tour the world: building a web-scale landmark recognition engine. In: Proc. IEEE CVPR, pp. 1085–1092 (2009)
Kennedy, L., Naaman, M.: Generating diverse and representative image search results for landmarks. In: Proc. WWW, pp. 297–306 (2008)
Agarwal, S., Snavely, N., Simon, I., Seitz, S.M., Szeliski, R.: Building Rome in a day. In: Proc. ICCV (2009)
Tompkin, J., Kim, K.I., Kautz, J., Theobalt, C.: Videoscapes: exploring sparse, unstructured video collections. ACM TOG (Proc. SIGGRAPH) 68, 1–12 (2012)
Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: Proc. ICCV, pp. 1470–1477 (2003)
Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press (2004)
Philbin, J., Sivic, J., Zisserman, A.: Geometric latent Dirichlet allocation on a matching graph for large-scale image datasets. IJCV 95(2), 138–153 (2011)
Weyand, T., Leibe, B.: Discovering favorite views of popular places with iconoid shift. In: Proc. ICCV, pp. 1132–1139 (2011)
Hays, J., Efros, A.A.: IM2GPS: estimating geographic information from a single image. In: Proc. IEEE CVPR, pp. 1–8 (2008)
Kleban, J., Moxley, E., Xu, J., Manjunath, B.S.: Global annotation on georeferenced photographs. In: Proc. CIVR, pp. 1–8 (2009)
Serdyukov, P., Murdock, V., van Zwol, R.: Placing flickr photos on a map. In: Proc. SIGIR, pp. 484–491 (2009)
Crandall, D.J., Backstrom, L., Huttenlocher, D., Kleinberg, J.: Mapping the world’s photos. In: Proc. WWW, pp. 761–770 (2009)
Kunegis, J., Lommatzsch, A.: Learning spectral graph transformations for link prediction. In: Proc. ICML, pp. 561–568 (2009)
Backstrom, L., Leskovec, J.: Supervised random walks: predicting and recommending links in social networks. In: Proc. WSDM, pp. 635–644 (2011)
Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., Luca, E.W., Albayrak, S.: Spectral analysis of signed graphs for clustering, prediction and visualization. In: Proc. ICDM, pp. 559–570 (2010)
Lü, L., Zhou, T.: Link prediction in complex networks: a survey. arXiv:1010.0725v1 (2011)
Lowe, D.G.: Distinctive image features from scale-invariant keypoints. IJCV 60(2), 91–110 (2004)
Lazebnik, S., Schmid, C., Ponce., J.: Beyond bags of features: spatial pyramid matching for recognizing natural scene categories. In: Proc. IEEE CVPR, pp. 2169–2178 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, K.I., Tompkin, J., Theobald, M., Kautz, J., Theobalt, C. (2012). Match Graph Construction for Large Image Databases. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds) Computer Vision – ECCV 2012. ECCV 2012. Lecture Notes in Computer Science, vol 7572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33718-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-33718-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33717-8
Online ISBN: 978-3-642-33718-5
eBook Packages: Computer ScienceComputer Science (R0)