Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration
By Marius Muja, David G. Lowe. 2009
3,299 citations recorded by the source corpus.
For many computer vision problems, the most time consuming component consists of nearest neighbor matching in high-dimensional spaces. There are no known exact algorithms for solving these high-dimensional problems that are faster than linear search. Approximate algorithms are known to provide large speedups with only minor loss in accuracy, but many such algorithms have been published with only minimal guidance on selecting an algorithm and its parameters for any given problem. In this paper, we describe a system that answers the question, “What is the fastest approximate nearest-neighbor algorithm for my data?” Our system will take any given dataset and desired degree of precision and use these to automatically determine the best algorithm and parameter values. We also describe a new algorithm that applies priority search on hierarchical k-means trees, which we have found to provide the best known performance on many datasets. After testing a range of alternatives, we have found that multiple randomized k-d trees provide the best performance for other datasets. We are releasing public domain code that implements these approaches. This library provides about one order of magnitude improvement in query time over the best previously available software and provides fully automated parameter selection.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Trevor Darrell
- Luc Van Gool
- Yoshua Bengio
- Andrew Zisserman
- Cordelia Schmid
- Quoc V. Le
- Bernt Schiele
- Mohit Bansal
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Andrew Zisserman
- Ming-Hsuan Yang
- Trevor Darrell
- Yi Yang
- Xiaogang Wang
- Jitendra Malik
In Information Retrieval & Search
- Herv'e J'egou
- Ondřej Chum
- Jingdong Wang
- Matthijs Douze
- Qi Tian
- Yannis Avrithis
- Cordelia Schmid
- Giorgos Tolias
In Signal Processing
- Kristen Grauman
- Andrea Vedaldi
- Jingdong Wang
- Ivan Laptev
- Cordelia Schmid
- Josef Sivic
- Herv'e J'egou
- Jiri Matas
Citations in the corpus
- Aggregating Local Image Descriptors into Compact Codes (2012, methodology): “However, these approaches and the one of Muja and Lowe [37] are memory consuming, as multiple hash tables or trees are required.”
- Product Quantization for Nearest Neighbor Search (2011, methodology): “An evaluation of the parameters of our approach and a comparison with the state of the art is given in Section V. II.”
- Vehicle localization using mono-camera and geo-referenced traffic signs (2015, methodology): “In this paper, SIFT(Scale Invariant Feature Transform) algorithm is chosen to detect and describe the key points [28] and FLANN (Fast Library for Approximate Nearest Neighbors) [29] is used to speed up corresponding point searching.”
- Fast image-based localization using direct 2D-to-3D matching (2011, methodology): “In order to demonstrate this potential, we perform the following systematic experiment: To establish 2D-to-3D correspondences, we use the kd-tree based approach proposed by Lowe [17], based on the FLANN library [18].”
- Segmentation-Driven 6D Object Pose Estimation (2018, background): “Over the years, much effort has been invested in designing local feature descriptors that are invariant to various transformations [27, 40, 41, 42, 34, 32], so that they can be matched more robustly [29, 30, 14].”
- FAST SEMANTIC SEGMENTATION OF 3D POINT CLOUDS WITH STRONGLY VARYING DENSITY (2016, methodology): “We use the method of (Muja and Lowe, 2009) to automatically select and configure the most suitable k D-tree ensemble for our problem.”
- Scale Invariant Feature Transform (2012, methodology): “In later work (Muja and Lowe 2009), this approach has been furthered to hierarchical k means trees and randomized kd trees.”
- Image Retrieval for Image-Based Localization Revisited (2012, methodology): “To compute the visual word assignments, we use a single kd-tree built using the FLANN library [20] and stop the search for the closest word after visiting at most 10 leaves.”
- Tutorial: Point Cloud Library: Three-Dimensional Object Recognition and 6 DOF Pose Estimation (2012, methodology): “Finally, efficient approximated matching schemes are deployed to speed up the matching stage: in particular, the fast approximate NN (FLANN) algorithmwas used [15].”
- Energy-Based Geometric Multi-model Fitting (2012, methodology): “In principle, it is possible to replace exhaustive search with ”smarter” methods as in [1,23].”
- Appearance-Based Loop Closure Detection for Online Large-Scale and Long-Term Operation (2013, background): “Neverthe-less, processing time for each image acquired still increases with the number of key images.”
- Searching with quantization: approximate nearest neighbor search using short codes and distance estimators (2009, methodology): “However, for real data, LSH is outperformed by heuristic methods [7], which exploit the distribution of the vectors better.”
- Hough Transform and 3D SURF for Robust Three Dimensional Classification (2010, methodology): “To reduce the dimensionality of feature matching and limit the effects of noise, we quantize the SURF features to a vocabulary of visual words, which we define as the cluster centers of an approximate K-means algorithm (see Muja et al. [ 18 ]).”
- Object discovery in 3D scenes via shape analysis (2013, methodology): “Efficient k-nearest-neighbor algorithms such as FLANN [31] can be used to further speed up the retrieval process.”