Exploiting descriptor distances for precise image search - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Exploiting descriptor distances for precise image search

Résumé

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.
Ce rapport considère le problème de la recherche d'image à partir de descripteurs locaux. Notre approche étend un système de vote par k plus proches voisins de plusieurs manières. Tout d'abord, nous introduisons un critère adaptatif, dérivé des distances associés aux plus proches voisins, afin de pondérer la qualité des appariemments. Nous exploitons ensuite les plus proches voisins réciproques et les distances associées pour améliorer la similarité entre chaque descripteur SIFT requête et ses voisins. Chacune de ces deux méthodes apporte un gain significatif par rapport à la référence du système de vote initial, et fournit des résultats supérieurs à une approche par sac-de-mots. Cependant, elle nécessite le calcul coûteux, en mémoire et en CPU, des distances et du graphe des plus proches voisins associé à la base. Afin de rendre notre méthode utilisable à une plus grande échelle, nous utilisons une méthode de recherche approximative récente qui estime les distances entre les vecteurs requêtes et ceux de la base, sans avoir à stocker en mémoire la représentation pleine de descripteurs. Nos expériences montrent que cette méthode approchée dépasse largement l'état de l'art sur 4 jeux de données couramment utilisés en recherche d'image. Bien qu'elle ne soit pas aussi efficace qu'une approche par sac-de-mots, nous montrons qu'elle reste utilisable pour une base comprenant jusqu'à 1 million d'images.
Fichier principal
Vignette du fichier
RA-7656.pdf (1.18 Mo) Télécharger le fichier
Vignette du fichier
nndistances.png (72.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

inria-00602325 , version 1 (22-06-2011)
inria-00602325 , version 2 (23-06-2011)

Identifiants

  • HAL Id : inria-00602325 , version 2

Citer

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

Partager

Gmail Facebook X LinkedIn More