De l’utilité de la factorisation de matrice pour la recherche par similarité grande échelle

We consider the image retrieval problem of finding the images in a dataset that are most similar to a query image. Our goal is to reduce the number of vector operations and memory for performing a search without sacrificing accuracy of the returned images. We adopt a group testing formulation and design the decoding architecture using either dictionary learning or eigendecomposition. The latter is a plausible option for small-to-medium sized problems with high-dimensional global image descriptors, whereas dictionary learning is applicable in large-scale scenario. We evaluate our approach both for global descriptors obtained from SIFT and CNN features. Experiments with standard image search benchmarks, including the Yahoo100M dataset comprising 100 million images, show that our method gives comparable (and sometimes superior) accuracy compared to exhaustive search while requiring only 10% of the vector operations and memory. Moreover, for the same search complexity, our method gives significantly better accuracy compared to approaches based on dimensionality reduction or locality sensitive hashing.Nous considérons le problème de la recherche d’images similaires à une image requête dans une grande base.Notre but est de réduire le nombre d’opérations et l’emprunte mémoire nécessaire sans trop dégrader les performances des recherches approximatives.Nous adoptons une approche inspirée des tests par groupe mariant apprentissage de dictionnaire et décomposition en valeurs propres.La dernière option s’avère adaptée aux bases d’images de taille moyennes avec des descripteurs images grands, alors que la première option concerne les bases d’images à très grande échelle. Nous évaluons notre approche à la fois avec des descripteurs globaux agrégations de descripteurs locaux comme les SIFT, et avec des descripteurs ``réseaux de neurones convolutionnels''. Les expériences réalisées sur des jeux de données standards, notamment la base Yahoo100M contenant 100 millions d’images, montre que notre méthode donne des résultats comparables (et parfois même supérieurs) à la recherche exhaustive tout en consommant dix fois moins de mémoire et de calculs. A complexité donnée, notre méthode donne des résultats meilleurs que les approaches basée réduction de dimensions ou signatures binaires