Pour retrouver les similitudes entre une image et celles d'une vaste base de données, l'Inria a mis au point un algorithme étonnamment efficace. Baptisé PQ Codes, il réduit une image à un nombre très faible de caractéristiques, qui finissent par ne plus occuper que quelques octets. L’objectif de ce comparateur d'images est de gagner du temps de calcul pour afficher les résultats le plus rapidement possible.

au sommaire

    Caractéristique du moteur de comparaison d'images PQ Codes : au lieu de chercher à comparer des pixels, l’image est analysée puis ses zones caractéristiques sont transformées en vecteurs, qui sont ensuite regroupés en un seul supervecteur afin d’alléger au maximum la charge de travail du processeur et l’occupation en mémoire. © Inria Rennes

    Caractéristique du moteur de comparaison d'images PQ Codes : au lieu de chercher à comparer des pixels, l’image est analysée puis ses zones caractéristiques sont transformées en vecteurs, qui sont ensuite regroupés en un seul supervecteur afin d’alléger au maximum la charge de travail du processeur et l’occupation en mémoire. © Inria Rennes

    Pour repérer des montages photo, on peut utiliser les services d'un comparateur d'images. Ce type de moteur ne permet pas de retrouver un document à l'aide de mots clés, mais de chercher toutes les copies et les modifications d'une image publiées sur le Web à partir de celle-ci. Un tel système est le rêve de tout photographe professionnel qui souhaite débusquer les contrefaçons de ses clichés, mais aussi des éditeurs audiovisuels traquant le piratage de leurs productions puisque le procédé fonctionne aussi bien avec les vidéos.

    Parmi les comparateurs d'images connus, citons TinEye ou Cydral. Leurs algorithmes se basent sur l'analyse des pixels d'une image pour en extraire ses caractéristiques. Ce système fonctionne même si les couleurscouleurs de l'image ou sa taille ont été modifiés. Mais voilà, les calculs sont plutôt longs et lourds pour les serveurs. Par rapport au déploiement de puissance colossal, les résultats ne sont pas forcément au rendez-vous.

    Le seul frein : le temps de calcul

    Et c'est sur cette question du temps de calcul qu'a planché un chercheur de l'Inria, Hervé Jégou, avec son projet baptisé PQ Codes. Il ne faut que 20 millisecondes pour trouver une photo ou une vidéo semblable à une autre dans une base de 10 millions de fichiers !


      Dans cette démonstration de PQ Codes réalisée par l'Inria, la recherche à partir d'une image dans une base de 10 millions d'images prend environ 20 millisecondes. Chaque image de la base occupe 21 octets. La seule limitation reste le temps d'affichage des résultats. © Inria Rennes

    Comment une telle prouesse est possible ? Contrairement aux systèmes se basant sur l'analyse des pixels, PQ Codes construit une représentation mathématique de l'image. Le programme va donc extraire de l'image un ensemble de valeurs indiquant différentes positions sur des zones caractéristiques. Ces valeurs produisent un certain nombre de vecteurs.

    Et pour aller encore plus loin, les vecteurs d'une même zone sont rassemblés dans un même groupe. L'algorithme choisit le plus représentatif pour constituer un seul supervecteur. Il sera moins précis, mais amplement suffisant pour conserver les caractéristiques de l'image. C'est ce que l'on appelle la quantification vectorielle, une technique très utilisée en reconnaissance de parole, compression de parole, etc.

    PQ Codes : le comparateur d'image avec seulement 20 octets

    Ainsi, les caractéristiques d'une image peuvent être définies avec seulement 20 octetsoctets. Ce qui explique le gain important de calcul. « Si l'on fixe la taille des descripteursdescripteurs à 100 octets par image, la qualité de la recherche est meilleure, au prix d'une recherche plus lente et de 5 fois plus de mémoire. En utilisant 100 octets par image, on peut indexer 1 milliard d'images avec un serveur de 128 giga-octets de mémoire pour héberger la base » explique Hervé Jégou.

    Au final, la comparaison de deux images se résume à celles de deux supervecteurs. Difficile de faire mieux... Avec ce système, comme les pixels et les couleurs ne sont pas du tout pris en compte, même une image qui a été modifiée, ou une vidéo piratée de mauvaise qualité, peut être repérée parmi des millions d'autres.

    Côté applicationapplication concrète, cette technologie pourrait, bien entendu, être intégrée par les moteurs de recherche que nous utilisons au quotidien. Toutefois, souligne Hervé Jégou, le père du projet, « pour le moment, seul un gros industriel a acheté une licence et un autre envisage de le faire. Étant donné sa relative simplicité, plusieurs groupes industriels et de recherche (ETZH, NTTNTT, Xerox...) ont réimplémenté la technique pour leur besoins propres ».