Exploiting descriptor distances for precise image search

Hervé Jégou 1 Matthijs Douze 2, 3 Cordelia Schmid 2
1 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 LEAR - Learning and recognition in vision
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : This report addresses precise image search based on local descriptors. Our approach extends a k-NN voting scheme in several ways. First, we introduce a query-adaptive criterion that is shown effective to weight the descriptor matches. Second, we exploit the distances between SIFT descriptors and the reciprocal neighbors to further refine the similarity measure between descriptors. Each of these two complementary strategies leads to a significant improvement over the usual voting baseline, and significantly outperforms bag-of-features, at the cost of a high computational and memory complexity due to the exact computation of distances and reciprocal nearest neighbors. In order to make our method tractable, we exploit an approximate search method which, in addition to returning nearest neighbors with high probability, provides precise distance estimates without accessing the full raw vectors, which is critical to avoid memory issues. Experimental results show that our method outperforms the state of the art on four challenging datasets. Although our method is not as efficient as bag-of-features, we show that it can handle a database of up to 1 million images with reasonable query times.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download


https://hal.inria.fr/inria-00602325
Contributor : Hervé Jégou <>
Submitted on : Thursday, June 23, 2011 - 12:03:19 AM
Last modification on : Monday, December 17, 2018 - 11:22:02 AM
Long-term archiving on : Sunday, December 4, 2016 - 8:35:31 PM

Files

RA-7656.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00602325, version 2

Citation

Hervé Jégou, Matthijs Douze, Cordelia Schmid. Exploiting descriptor distances for precise image search. [Research Report] RR-7656, INRIA. 2011. ⟨inria-00602325v2⟩

Share

Metrics

Record views

1139

Files downloads

1763