High-Dimensional Feature Matching: Employing the Concept of Meaningful Nearest Neighbors
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 1-8
- https://doi.org/10.1109/iccv.2007.4408880
Abstract
Matching of high-dimensional features using nearest neighbors search is an important part of image matching methods which are based on local invariant features. In this work we highlight effects pertinent to high-dimensional spaces that are significant for matching, yet have not been explicitly accounted for in previous work. In our approach, we require every nearest neighbor to be meaningful, that is, sufficiently close to a query feature such that it is an outlier to a background feature distribution. We estimate the background feature distribution from the extended neighborhood of a query feature given by its k nearest neighbors. Based on the concept of meaningful nearest neighbors, we develop a novel high-dimensional feature matching method and evaluate its performance by conducting image matching on two challenging image data sets. A superior performance in terms of accuracy is shown in comparison to several state-of-the-art approaches. Additionally, to make search for k nearest neighbors more efficient, we develop a novel approximate nearest neighbors search method based on sparse coding with an overcomplete basis set that provides a ten-fold speed-up over an exhaustive search even for high dimensional spaces and retains excellent approximation to an exact nearest neighbors search.Keywords
This publication has 17 references indexed in Scilit:
- Automatic Panoramic Image Stitching using Invariant FeaturesInternational Journal of Computer Vision, 2006
- Simultaneous Object Recognition and Segmentation from Single or Multiple Model ViewsInternational Journal of Computer Vision, 2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Matching Widely Separated Views Based on Affine Invariant RegionsInternational Journal of Computer Vision, 2004
- Nearest Neighbors in High-Dimensional SpacesPublished by Taylor & Francis ,2004
- Sparse coding with an overcomplete basis set: A strategy employed by V1?Published by Elsevier ,2003
- Bayesian measures of surprise for outlier detectionJournal of Statistical Planning and Inference, 2003
- Reliable feature matching across widely separated viewsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Local grayvalue invariants for image retrievalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1997
- A simple algorithm for nearest neighbor search in high dimensionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1997