Shape indexing using approximate nearest-neighbour search in high-dimensional spaces

TLDR

Shape indexing links image features to object models, but high‑dimensional features needed for discrimination make nearest‑neighbour search inefficient, and prior hash‑table methods only work in low dimensions. The paper proposes a k‑d tree variant that enables practical indexing in high‑dimensional spaces. The Best Bin First (BBF) algorithm approximates nearest neighbours, accurately retrieving most queries and close matches for the rest. When integrated into a recognition system, the method detects complex objects in cluttered scenes within seconds.

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.