Minimizing the Number of Keypoint Matching Queries for Object Retrieval

To increase the efficiency of interest-point based object retrieval, researchers have put remarkable research efforts into improving the efficiency of kNN-based feature matching, pursuing to match thousands of features against a database within fractions of a second. However, due to the high-dimensional nature of image features that reduces the effectivity of index structures (curse of dimensionality) and due to the vast amount of features stored in image databases (images are often represented by up to several thousand features), this ultimate goal demanded to trade kNN query runtimes for query precision. In this paper we address an approach complementary to indexing in order to improve the efficiency of retrieval by querying only the most promising keypoint descriptors, as this affects kNN matching time linearly. As this reduction of kNN queries reduces the number of tentative correspondences, a loss of query precision is minimized by an additional image-level correspondence generation stage with a computational performance independent of the underlying indexing structure. Our experimental evaluation suggests good performance on a variety of datasets.