Paper Info
Title
Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces
Abstract
Shape indexing is a way of making rapid associations between features detected in an image and object models that could have produced them. When model databases are large, the use of high-dimensional features is critical, due to the improved level of discrimination they can provide. Unfortunately, finding the nearest neighbour to a query point rapidly becomes inefficient as the dimensionality of the feature space increases. Past indexing methods have used hash tables for hypothesis recovery, but only in low-dimensional situations. In this paper, we show that a new variant of the k-d tree search algorithm makes indexing in higher-dimensional spaces practical. This Best Bin First, or BBF, search is an approximate algorithm which finds the nearest neighbour for a large fraction of the queries, and a very close neighbour in the remaining cases. The technique has been integrated into a fully developed recognition system, which is able to detect complex objects in real, cluttered scenes in just a few seconds.
Year
DOI
Venue
1997
10.1109/CVPR.1997.609451
CVPR
Keywords
Field
DocType
nearest neighbour,best bin first,k-d tree search algorithm,shape indexing,past indexing method,close neighbour,high-dimensional spaces,cluttered scene,approximate nearest-neighbour search,large fraction,complex object,approximate algorithm,feature detection,object recognition,indexing,computer vision,indexation,object model,search algorithm,feature extraction,hash table
Feature vector,Tree traversal,Pattern recognition,Best bin first,Computer science,Search engine indexing,Feature extraction,Curse of dimensionality,Artificial intelligence,Cognitive neuroscience of visual object recognition,Hash table
Conference
Volume
Issue
ISSN
1997
1
1063-6919
ISBN
Citations 
PageRank 
0-8186-7822-4
376
73.39
References 
Authors
17
2
Search Limit
100376
Name
Order
Citations
PageRank
Jeffrey S. Beis139774.92
D. G. Lowe2157181413.60