Brevet FR3041794A1 — publié le 20170331

PROCÉDÉ ET SYSTÈME DE RECHERCHE D'IMAGES SIMILAIRES QUASI-INDÉPENDANT DE L'ÉCHELLE DE LA COLLECTION D'IMAGES DESCRIPTION DOMAINE TECHNIQUE Le domaine de l'invention est celui de la fouille de données, et plus particulièrement celui de la recherche d'image par le contenu pour laquelle on souhaite retrouver des images similaires à une requête purement visuelle prenant la forme d'une image dite image requête. ÉTAT DE LA TECHNIQUE ANTÉRIEURE En l'absence d'annotations textuelles, la recherche d'images peut être réalisée au moyen d'images requête qui sont utilisées afin de retrouver des images similaires au sein d'une collection d'images de référence. Ce processus de recherche par similarité visuelle comprend deux phases principales, l'indexation de la collection d'images, qui est réalisée hors ligne, et le requêtage, qui doit être réalisé en ligne. L'indexation a pour but de transformer le contenu « pixelique » des images en des représentations vectorielles par caractéristiques (feature extraction), généralement de taille fixe. L'étape de requêtage a pour but d'extraire une représentation vectorielle du contenu de l'image requête et de la comparer aux représentations des images de la collection afin de retrouver les éléments les plus similaires. Les représentations vectorielles des caractéristiques visuelles incluent : les représentations qui agrègent des descripteurs locaux au sein d'un vecteur de taille fixe (i.e. sacs de mots visuels, vecteurs de Fisher, réseaux neuronaux convolutionnels, etc.) ; les représentations qui encodent des caractéristiques globales (i.e. histogrammes de couleurs, descriptions de textures, etc.) ; 3041794 2 les représentations sémantiques qui sont obtenues par l'agrégation de classificateurs intermédiaires et qui donnent des probabilités d'apparition de concepts individuels dans l'image. Un problème important en recherche d'images par similarité est la 5 rapidité de la recherche qui doit être effectuée « en ligne ». Ce problème devient même central lorsqu'il s'agit de traiter des collections à large échelle (i.e. milliards d'images). Il existe trois solutions principales qui permettent l'accélération du processus de recherche par similarité : la réduction de la taille des représentations vectorielles en utilisant des techniques 10 comme l'analyse en composantes principales, l'analyse discriminante linéaire, la quantification vectorielle, etc. ; l'utilisation d'arbres de recherche (kd-trees, k-means trees, fôret d'arbres décisionnels) qui fonctionnent en partitionnant l'espace de recherche défini par les vecteurs représentatifs des images et permettent ainsi d'accélérer le processus 15 de recherche d'images ; la représentation par fichiers inversés qui s'inspire de la recherche de documents textuels et est efficace si les vecteurs représentant les images de la collection sont creux (parcimonieux). Ce type de structure associe à chaque dimension de l'espace de représentation un ensemble de documents et, au vu du caractère 20 creux des représentations, les documents similaires sont retrouvés plus efficacement en comparant toutes les dimensions non-nulles du vecteur représentant le document requête avec les documents de la collection associés à ces dimensions. Malgré leur efficacité améliorée par rapport à des comparaisons 25 exhaustives des vecteurs représentatifs, l'utilisation de ces méthodes de recherche accélérée nécessite toujours la réalisation d'un ensemble d'opérations mathématiques pour réaliser des calculs de similarité entre le vecteur représentant l'image requête et les vecteurs représentant mes images de la collection. La recherche d'images similaires demeure donc complexe, et cette complexité augmente avec la taille de la collection. 3041794 3 EXPOSÉ DE L'INVENTION L'invention vise une technique de recherche d'image par le contenu qui soit plus simple à mettre en oeuvre sans pour autant perdre en pertinence, et qui permette d'être appliquée à des collections de référence de très grande taille sans pour 5 autant que le temps de recherche ne devienne exorbitant. A cet effet, l'invention propose un procédé de recherche d'images similaires à une image requête dans une collection d'images, procédé exploitant une représentation de l'image requête par un vecteur de caractéristiques associant un poids à chacune des caractéristiques, et comprenant une étape d'interrogation d'un index inversé 10 mettant en correspondance chacune des caractéristiques avec des images de la collection. L'étape d'interrogation de l'index inversé comprend une opération d'intégration à une liste d'une ou plusieurs images de la collection mises en correspondance dans l'index inversé avec une première caractéristique sélectionnée en fonction du poids qui lui est associé dans le vecteur représentant l'image requête. 15 L'opération d'intégration à la liste est répétée pour une autre caractéristique sélectionnée en fonction du poids qui lui est associé dans le vecteur représentant l'image requête tant que le nombre d'images de la collection intégrées à la liste n'a pas atteint un nombre cible. Certains aspects préférés mais non limitatifs de ce procédé sont les 20 suivants : l'étape d'interrogation de l'index inversé débute par une opération d'intégration à la liste ayant pour première caractéristique la caractéristique de poids le plus élevé dans le vecteur représentant l'image requête, et se poursuit tant que le nombre d'images intégrées à la liste n'a pas atteint le nombre cible en répétant 25 l'opération d'intégration à la liste avec pour autre caractéristique la caractéristique de poids immédiatement plus faible dans le vecteur représentant l'image requête ; l'opération d'intégration à la liste est réalisée de manière à intégrer une image de la collection mise en correspondance avec une caractéristique dans l'index inversé uniquement si ladite image n'est pas déjà intégrée à la liste ; 3041794 4 il comprend une étape de détermination, à partir du nombre cible d'images dans la liste, et pour chaque caractéristique, d'un nombre maximal d'images pouvant être intégrées à la liste parmi les images mises en correspondance avec ladite caractéristique dans l'index inversé ; 5 il comprend une étape préalable d'indexation de la collection d'images, comprenant : pour chaque image de la collection, l'extraction de caractéristiques de l'image pour représenter l'image sous la forme d'un vecteur de caractéristiques associant un poids à chacune des caractéristiques ; 10 pour chaque caractéristique, l'ordonnancement des images de la collection en fonction de leur poids associé à la caractéristique pour créer une liste d'images ordonnées par poids décroissant ; la création de l'index inversé en venant mettre en correspondance chacune des caractéristiques avec un nombre prédéfini d'images de la 15 collection correspondant aux premières images dans la liste d'images ordonnées associée à la caractéristique. les caractéristiques sont des caractéristiques relatives à la présence de concepts visuels dans une image, le vecteur représentant une image ayant pour poids associé à chacune des caractéristiques une probabilité d'apparition d'un concept 20 visuel dans l'image ; il comprend en outre une étape de classement des images intégrées à la liste, ladite étape de classement comprenant, pour chacune des images intégrées à la liste, une mesure de similarité avec l'image requête ; la mesure de similarité d'une image intégrée à la liste avec l'image requête 25 comprend une comparaison de caractéristiques bas-niveau, respectivement haut- niveau, extraites de l'image requête et de caractéristiques bas-niveau, respectivement haut-niveau, extraites de l'image intégrée à la liste ; il comprend une étape de reformulation du vecteur représentant l'image requête consistant à modifier le poids associé à une ou plusieurs caractéristiques pouvant 30 être confondues avec d'autres caractéristiques. 3041794 5 L'invention porte également sur un produit programme d'ordinateur comprenant des instructions de code de programme permettant d'effectuer les étapes du procédé lorsque ledit programme est exécuté sur un ordinateur. Elle s'étend en outre à 5 un système de recherche d'images similaires à une image requête dans une collection d'images configuré de manière à mettre en oeuvre le procédé selon l'invention. BRÈVE DESCRIPTION DES DESSINS D'autres aspects, buts, avantages et caractéristiques de l'invention apparaîtront mieux à la lecture de la description détaillée suivante de formes de 10 réalisation préférées de celle-ci, donnée à titre d'exemple non limitatif, et faite en référence à la figure 1 annexée qui illustre le schéma global d'un mode de réalisation possible du procédé selon l'invention. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS L'invention porte sur un procédé de recherche de documents parmi les 15 documents d'une collection au moyen d'une représentation d'une requête et des documents de la collection par un vecteur de caractéristiques associant un poids à chacune des caractéristiques. On prendra dans ce qui suit l'exemple d'une collection d'images, sans que cela ne soit pour autant limitatif, l'invention visant tout type de document multimédia et pouvant être mise en oeuvre dès lors qu'une représentation par 20 vecteur de caractéristiques des documents multimédia est accessible. L'invention porte ainsi notamment, mais non exclusivement, sur la recherche d'images similaires à une image requête parmi une collection d'images qui comprend généralement des milliers d'images, voire des millions d'images. Le procédé a en particulier pour objectif de créer une liste d'images de la collection similaires à l'image 25 requête dont le nombre d'images similaires correspond à un nombre cible prédéterminé x. Il exploite une représentation de l'image requête par un vecteur de caractéristiques associant un poids à chacune des caractéristiques, et comprend une étape d'interrogation d'un index inversé mettant en correspondance chacune des caractéristiques avec des images de la collection. 3041794 6 Le procédé se décompose en deux phases principales : une première phase dite d'indexation généralement effectuée « hors-ligne », et une deuxième phase de requêtage généralement effectuée « en ligne », c'est-à-dire en temps réel pendant la recherche d'images similaires proprement dite. 5 On a représenté sur la figure 1 un schéma global du procédé selon l'invention. Sur cette figure, les lignes en traits pleins illustrent les étapes réalisées « hors-ligne » tandis que les lignes en traits pointillés illustrent les étapes réalisées « en ligne ». Sur cette même figure, les données et les résultats des traitements sont représentés dans des rectangles aux coins arrondis, les différentes étapes de traitement des données étant 10 présentées dans des rectangles. Sur cette figure, on a par ailleurs séparé les étapes et données de la phase d'indexation hors ligne HL des étapes et données de la phase de recherche en ligne EL. Chacune des première et deuxième phases HL, EL comporte une étape d'extraction de caractéristiques « EX-CR » (feature extraction en anglais) d'une image 15 pour représenter l'image sous la forme d'un vecteur de caractéristiques associant un poids à chacune des caractéristiques d'un ensemble de caractéristiques d'image. Lors de la phase d'indexation HL, l'extraction de caractéristiques EX-CR est mise en oeuvre pour l'ensemble des images de la collection stockées dans une base de données BdB. Lors de la phase de recherche en ligne EL, l'extraction de caractéristiques 20 EX-CR est mise en oeuvre pour l'image requête Ir. Les images de la collection et l'image requête sont ainsi décrites par un vecteur de même nature. Dans un mode de réalisation possible de l'invention, l'extraction de caractéristiques d'une image EX-CR comprend une extraction de caractéristiques bas-niveau « EX-BN » qui permet d'associer un vecteur de taille fixe à l'image, suivie d'une 25 extraction de caractéristiques haut-niveau « EX-S » à partir des caractéristiques bas- niveau. Les caractéristiques bas-niveau sont typiquement des caractéristiques peu interprétables, là où les caractéristiques haut-niveau sont généralement compréhensibles pour l'homme. Les caractéristiques bas-niveau sont par exemple des sacs de mots 30 visuels (BoVW pour Bag of Visual Word), des histogrammes de gradient orienté (HOG 3041794 7 pour Histogram of Oriented Gradients), des noyaux de Fisher, des couches totalement connectées (dites « de classification ») de réseaux neuronaux convolutionnels, etc. Ces caractéristiques bas-niveau peuvent être stockées dans un index direct ID associant à chacune des images de la collection lt, lp, lq le vecteur de taille fixe 5 résultant de l'extraction de caractéristiques bas-niveau de l'image. Les caractéristiques haut-niveau sont par exemple des caractéristiques visuelles permettant de former une représentation sémantique de l'image. Il peut s'agir d'une représentation sémantique intermédiaire (les caractéristiques étant par exemple les sorties de la couche finale d'un réseau 10 convolutionnel) ou d'une représentation sémantique proprement dite (les caractéristiques sont alors relatives à la présence de concepts visuels dans l'image, le vecteur représentant une image ayant pour poids associé à chacune des caractéristiques une probabilité d'apparition d'un concept visuel dans l'image). Une telle représentation sémantique est typiquement obtenue par l'agrégation des sorties d'un banc de 15 classificateurs visuels qui fournissent des probabilités d'apparition de concepts individuels dans l'image. Elle rend possible la recherche d'images similaires à une requête formulée avec des concepts textuels de l'espace de représentation à la place d'images requête. On relèvera que lorsque la collection de référence inclut des images d'un domaine précis, il est possible d'adapter l'espace de représentation en venant 20 éliminer des caractéristiques qui ne sont pas pertinentes dans le contexte. Après extraction des caractéristiques d'une image, on dispose d'une représentation compacte de l'image sous la forme d'un vecteur de taille fixe qui peut s'écrire comme D= {(v i, p1), (y2, P2), (va, Pn)} où y, sont les dimensions de l'espace vectoriel de représentation et p, 25 sont les poids associés à ces dimensions pour l'image considérée. Les y, peuvent ainsi représenter un ensemble de concepts visuels, pi étant la probabilité de présence du concept visuel y, dans l'image. Sous l'intuition que seulement un nombre réduit de concepts visuels est reconnaissable dans une image et devrait donc être actif dans le vecteur représentant 30 une image, on peut chercher à obtenir une représentation parcimonieuse (ou « creuse ») 3041794 8 de l'image comprenant un nombre réduit de dimensions non nulles dans le vecteur représentant l'image. Pour ce faire, le vecteur D représentatif d'une image est modifié de manière à ce que seulement un petit sous-ensemble k des poids pi restent non-nuls. Typiquement on a k REVENDICATIONS1. Procédé de recherche d'images similaires à une image requête (Ir) dans une collection d'images, procédé exploitant une représentation de l'image requête par un vecteur de caractéristiques associant un poids à chacune des caractéristiques, et comprenant une étape d'interrogation (LTU) d'un index inversé (11) mettant en correspondance chacune des caractéristiques (C1-05) avec des images de la collection (1118), caractérisé en ce que l'étape d'interrogation de l'index inversé comprend une opération d'intégration à une liste d'une ou plusieurs images (16-18) de la collection mises en correspondance dans l'index inversé avec une première caractéristique (C3) sélectionnée en fonction du poids qui lui est associé dans le vecteur représentant l'image requête, l'opération d'intégration à la liste étant répétée pour une autre caractéristique (C1) sélectionnée en fonction du poids qui lui est associé dans le vecteur représentant l'image requête tant que le nombre d'images de la collection intégrées à la liste n'a pas atteint un nombre cible. 2. Procédé selon la revendication 1, dans lequel l'étape d'interrogation de l'index inversé débute par une opération d'intégration à la liste ayant pour première caractéristique la caractéristique de poids le plus élevé (C3) dans le vecteur représentant l'image requête, et se poursuit tant que le nombre d'images intégrées à la liste n'a pas atteint le nombre cible en répétant l'opération d'intégration à la liste avec pour autre caractéristique la caractéristique de poids immédiatement plus faible (C1) dans le vecteur représentant l'image requête. 3. Procédé selon l'une des revendications 1 et 2, dans lequel l'opération d'intégration à la liste est réalisée de manière à intégrer une image de la collection mise en correspondance avec une caractéristique dans l'index inversé uniquement si ladite image n'est pas déjà intégrée à la liste. 3041794 16 4. Procédé selon l'une des revendications 1 à 3, comprenant une étape de détermination, à partir du nombre cible d'images dans la liste, et pour chaque caractéristique, d'un nombre maximal d'images pouvant être intégrées à la liste parmi les images mises en correspondance avec ladite caractéristique dans l'index inversé. 5 5. Procédé selon la revendication 4, dans lequel le nombre maximal d'images pouvant être intégrées à la liste est le même pour chacune des caractéristiques. 6. Procédé selon l'une des revendications 1 à 5, comprenant une étape préalable 10 d'indexation de la collection d'images, comprenant : pour chaque image de la collection, l'extraction de caractéristiques (EX, EX-BN, EX-S) de l'image pour représenter l'image sous la forme d'un vecteur de caractéristiques associant un poids à chacune des caractéristiques ; pour chaque caractéristique, l'ordonnancement des images de la 15 collection en fonction de leur poids associé à la caractéristique pour créer une liste d'images ordonnées par poids décroissant ; la création (CREA-II) de l'index inversé (11) en venant mettre en correspondance chacune des caractéristiques (C1, C2, C3) avec un nombre prédéfini d'images de la collection (11-12, 13-15, 16-18) correspondant aux premières images dans la 20 liste d'images ordonnées associée à la caractéristique. 7. Procédé selon la revendication 6 prise en combinaison avec l'une des revendications 4 et 5, dans lequel, pour chacune des caractéristiques, le nombre prédéfini d'images dans l'index inversé correspond au nombre maximal d'images pouvant être 25 intégrées à la liste. 8. Procédé selon l'une des revendications 1 à 7, dans lequel les caractéristiques sont des caractéristiques relatives à la présence de concepts visuels (EX-S) dans une image, le vecteur représentant une image ayant pour poids associé à chacune des caractéristiques une probabilité d'apparition d'un concept visuel dans l'image. 3041794 17 9. Procédé selon l'une des revendications 1 à 8, comprenant en outre une étape de classement (RANK) des images intégrées à la liste (L), ladite étape de classement comprenant, pour chacune des images intégrées à la liste, une mesure de similarité avec l'image requête. 5 10. Procédé selon la revendication 9, dans lequel la mesure de similarité d'une image intégrée à la liste avec l'image requête comprend une comparaison de caractéristiques bas-niveau extraites de l'image requête et de caractéristiques bas-niveau extraites de l'image intégrée à la liste. 10 11. Procédé selon la revendication 9 prise en combinaison avec la revendication 8, dans lequel la mesure de similarité d'une image intégrée à la liste avec l'image requête comprend une comparaison des caractéristiques relatives à la présence de concepts visuels dans l'image requête et des caractéristiques relatives à la présence de concepts 15 visuels de l'image intégrée à la liste. 12. Procédé selon l'une des revendications 1 à 11, comprenant une étape de reformulation (CONF) du vecteur représentant l'image requête consistant à modifier le poids associé à une ou plusieurs caractéristiques pouvant être confondues avec d'autres 20 caractéristiques. 13. Produit programme d'ordinateur comprenant des instructions de code de programme permettant d'effectuer les étapes du procédé selon l'une quelconque des revendications 1 à 12 lorsque ledit programme est exécuté sur un ordinateur. 25 14. Système de recherche d'images similaires à une image requête dans une collection d'images exploitant une représentation de l'image requête par un vecteur de caractéristiques associant un poids à chacune des caractéristiques, comprenant : une base de données (BdB) dans laquelle sont stockées la collection d'images 30 et un index inversé (II) mettant en correspondance chaque caractéristique d'un ensemble de caractéristiques d'image avec des images de la collection ; 3041794 18 un processeur configuré pour interroger (LTU) l'index inversé afin de créer une liste d'images de la collection similaires à l'image requête en venant réaliser une opération d'intégration à la liste d'une ou plusieurs images de la collection mises en correspondance dans l'index inversé avec une première caractéristique (C3) sélectionnée 5 en fonction du poids qui lui est associé dans le vecteur représentant l'image requête, et en venant répéter l'opération d'intégration à la liste pour une autre caractéristique sélectionnée en fonction du poids qui lui est associé dans le vecteur représentant l'image requête tant que le nombre d'images intégrées à la liste n'a pas atteint un nombre cible. 10