Skip to content. | Skip to navigation

Emergences

Lettre d'information n° 16

Image emergences pour impression
Personal tools
You are here: Home 2011 Lettre d'information n° 16 Un logiciel pour fouiller dans les grandes bases d'images
Document Actions

Un logiciel pour fouiller dans les grandes bases d'images

PQ Codes permet de comparer une image à des millions d'autres avec une rapidité inégalée. Sa performance résulte d'une nouvelle méthode pour estimer la similarité entre les descripteurs vectoriels, comme l'explique Hervé Jégou, le chercheur Inria à l'origine de ces travaux.

PQ Codes permet de comparer une image à des millions d'autres avec une rapidité inégalée. Sa performance résulte d'une nouvelle méthode pour estimer la similarité entre les descripteurs vectoriels, comme l'explique Hervé Jégou, le chercheur Inria à l'origine de ces travaux.

20 millisecondes.” C'est le temps nécessaire au système de recherche utilisant PQ Codes pour comparer et trouver une photo ou une vidéo qui ressemblerait à une autre dans une base de 10 millions de fichiers. Il ne s'agit pas ici de retrouver un document à l'aide de mots clés comme peut le faire un moteur de recherche textuel dans une photothèque. L'objectif est plutôt d'exploiter une représentation mathématique de l'image à base de descripteurs vectoriels capables de mettre en chiffres toutes les géométries d'un visuel. Ce qui ouvre la porte à de véritables comparaisons automatisées d'images à grande échelle. Les éditeurs audiovisuels demandent de tels outils, en particulier pour protéger leur catalogue des contrefaçons et autres piratages. Mais jusqu'à présent, le procédé exigeait des temps de calculs rédhibitoires.

C'est ce verrou qui vient de tomber grâce à la méthode mise au point par des chercheurs de l'Inria (1). Présentée à la conférence CVPR 2011 (2), pour de la recherche d’images, la technique est générique et s’applique à d’autres types de médias. Elle a d'ailleurs été utilisée avec succès pour indexer des bandes audio, à TRECvid, une compétition organisée par l'Institut américain de standardisation (Nist). La méthode a en outre été récemment ré-implémentée par l'École polytechnique fédérale de Zurich (ETHZ) ainsi que le laboratoire japonais KKDI R&D Lab.

 À Rennes, dans le contexte du programme européen Quaero, le groupe Technicolor sera le premier industriel à tester en conditions réelles de production le logiciel né de ces travaux. Un chercheur Inria en disponibilité à Technicolor, Patrick Pérez, contribue d'ailleurs à ces recherches. “Photographies, vidéos ou sons, la technique de comparaison est indépendante du média, explique Hervé Jégou. Dès lors, elle s'applique à de multiples contextes. Elle peut intéresser aussi bien un Nokia qu'un Google. Nous avons effectué par exemple une démonstration en temps réel sur une base de 100 millions d'images, en lien avec Exalead", une filiale du groupe Dassault Systèmes.

 Objectif : le milliard d'images

Comment expliquer de tels gains de temps ? “Nous partons d'un premier constat : dans le fond, cela ne sert à rien de représenter tous les points d'une image et de les comparer à tous ceux d'une autre. Gérer tous ces points ou stocker tous leurs descripteurs est impossible pour 1 milliard d’images, qui est la quantité d’images que nous souhaitons pouvoir traiter sur un serveur. Nous travaillons sur le compromis entre la précision de la recherche et la complexité. À titre d’illustration, nul besoin par exemple de connaître une position à la décimale près. La valeur arrondie suffit amplement. Selon le même principe, plusieurs valeurs peuvent être représentées par une seule valeur approximative. C’est ce que l’on appelle la quantification vectorielle (3). Elle constitue l’un des modules habituels de la compression. Dans notre cas, les techniques de compression sont utilisées pour approcher la description de l’image. Elles permettent de représenter l’image avec 20 octets, soit nettement moins que la taille d’un SMS (160 caractères).

Toute la subtilité consiste ensuite à manipuler les objets directement dans le domaine compressé, ce qui apporte un gain de calcul considérable. “Si nous avons un vecteur sur un axe, nous le découpons par exemple en 10 tranches.  L'intérêt ? Manipuler des segments de valeurs sans avoir à reconstruire explicitement le vecteur. Ainsi, nous effectuons les calculs de distance dans le domaine compressé. De cette façon, nous économisons une grande quantité d'opérations.  Et ce n'est pas tout : “Nous pouvons aussi convertir des milliers de vecteurs pour créer un super-vecteur. Certes, il est plus gros. Mais il nous épargne beaucoup de multiplications. La comparaison de deux images s'opère alors simplement à travers deux super-vecteurs.” La méthode s'avère intéressante si la vitesse prime sur la précision. Avec le gain de performance, “c'est maintenant l'affichage des résultats qui a du mal à suivre.

 Notes :

(1) Hervé Jégou (équipe-projet Texmex, Inria Rennes - Bretagne Atlantique, commune entre l'Inria, le Cnrs, l'université de Rennes 1 et l'Insa de Rennes), Matthijs Douze et Cordelia Schmid (équipe-projet Lear, Inria Grenoble Rhône Alpes). Tous trois ont publié : Product quantization for nearest neighbor search, dans la revue IEEE Transactions on Pattern Analysis and Machine Intelligence, en janvier 2011.

(2) Hervé Jégou, Matthijs Douze, Cordelia Schmid, Patrick Pérez (Technicolor). Aggregating local descriptors into a compact image representation, dans la conférence Computer Vision and Pattern Recognition, en juin 2011.

(3) En anglais :  product quantization. La quantification vectorielle est une technique de compression où l'on remplace des valeurs d'un espace vectoriel par des valeurs d'un sous-espace plus petit.