Brevet FR2939537A1 — publié le 20100611

SYSTEME DE RECHERCHE D'INFORMATION VISUELLE L'objet de la présente invention concerne un système et un procédé permettant d'effectuer une recherche d'information visuelle d'objets au sein d'une base de données multi-modales de taille importante (images, vidéos, signaux, documents, etc...). L'invention concerne de manière générale la visualisation d'images, de textes lorsque la base est constituée de dépêches AFP par exemple, ou de signaux audio lorsque la base concerne des enregistrements de communications, par exemple, etc. De manière plus générale, le système selon l'invention est utilisé dans le domaine de la recherche d'informations visuelles de données multi-modales, et permet une navigation et une recherche, dans les bases de données, plus rapide, grâce à une meilleure structuration de la base sous forme de classes homogènes d'objets de cette base. Dans la suite de la description, l'invention illustrée, à titre d'exemple sur des données images issues de la base wikipédia. Le terme image est utilisé pour désigner une image dans une base de données, l'image étant décrite par plusieurs descripteurs ou attributs, tels que sa texture, sa couleur, le texte associé à cette image, etc. Une carte SOM est une carte connue de l'Homme du métier correspondant à une Carte auto adaptative ou auto organisatrice qui est une classe de réseau de neurones artificiels fondée sur des méthodes d'apprentissage non supervisée. On la désigne souvent par le terme anglais self organizing map (SOM), on encore carte de Kohonen. La fonction de l'algorithme mis en oeuvre par une carte est notamment de classifier des objets. La masse de données collectées chaque jour devient de plus en plus importante. A l'heure actuelle, des études estiment que la quantité d'informations dans le monde double tous les vingt mois. Le Web et les bibliothèques numériques donnent naissance à de nouveaux enjeux dans les domaines des bases de données (BD) et de la recherche d'informations (RI) au sein de ces bases de données. Dans de nombreuses applications, il devient important, voire nécessaire, de faciliter l'accès aux informations au moyen de système d'aide à la navigation pour le Web, de système d'aide à la formulation de requêtes pour les recherches dans les bases de données, de filtrer, d'adapter et de personnaliser ces informations. L'art antérieur divulgue différents systèmes et des techniques de recherche d'images ou d'informations. Les méthodes classiques de recherche d'images se basent généralement sur des principes liés à des techniques d'indexation linguistique (mots clés) (c'est à dire à une pré-annotation textuelle associée aux images) sans prendre en compte les informations de contenus ou de description structurelle comme la texture, la couleur, la densité, la forme, les contours latents, etc., pour des recherches d'images dans une base de données. La majorité des méthodes n'utilisent que les mots clés associés aux images pour faire de la classification. Elles utilisent, en outre, des techniques de classification telles que les algorithmes de moyennage connus sous l'acronyme anglo-saxon � k-means � où il faut définir arbitrairement le nombre de classes à trouver et les centres (mobiles) de ces classes. De telles techniques impliquent une instabilité des résultats selon les paramétrages d'origine (sensibilité des algorithmes aux points de départ). D'autres méthodes utilisent les autres paramètres tels que la couleur ou la texture séparément sans les combiner et ils ne font pas de retour en arrière pour affiner les résultats obtenus. L'idée de la présente invention consiste notamment à offrir un procédé et un système permettant de répondre aux attentes des utilisateurs et de résoudre notamment les questions telles que : • Comment accéder le plus rapidement possible à une donnée multidimensionnelle ou un ensemble de données, dans une base volumineuse de données multimodales (signaux, parole, image, vidéo, documents, etc.) ? • Comment organiser l'archivage d'une base de données multimodales de taille importante et permettre ainsi un accès rapide lors de la recherche d'un objet dans cette base et offrant plusieurs réponses avec des degrés de pertinence à la requête croissants ? • Comment synthétiser la base de données multimodale sous une forme de cartographie résumant son contenu ? • Comment améliorer le processus et améliorer les réponses aux requêtes en prenant en compte des interactions éventuelles avec un utilisateur. L'invention concerne un système de recherche d'informations au sein d'une base de données de taille importante, comprenant un processeur et des entrées/sorties, ledit système étant caractérisé en ce que ledit processeur comporte au moins les éléments suivants : • Un premier module El adapté à extraire les descripteurs associés à chaque objet de la base de données, et à construire un tableau contenant les objets et la valeur d'un descripteur associé à un objet, ceci pour les descripteurs choisis pour la représentation de l'objet, • Un deuxième module E2 adapté à appliquer plusieurs algorithmes de classification SOMi, pour chacun des tableaux Tu issus du module El, afin d'attribuer pour chaque objet Oi, un numéro de classe xij, pour un algorithme SOMi appliqué, pour chaque catégorie de descripteurs, • Un troisième module E3 adapté à fusionner les résultats issus du module E2 afin de déterminer pour chaque type de descripteur Tk, un numéro de classe associé à un objet Oi, • Un quatrième module E4, adapté à rechercher quelle est la colonne SOMi d'un tableau TS, la plus proche de la colonne obtenue pour lors de la fusion de l'étape E4, et à sélectionner la carte SOMi la plus proche contenue dans le tableau Ti, Sou meilleure carte SOMi, • Un cinquième module E5 adapté à fusionner les � meilleures cartes � sommes SOMi, et appliquer un algorithme de recherche de la meilleure carte à transmettre à un moyen d'affichage. L'algorithme de fusion utilisé est, par exemple, un algorithme d'analyse relationnelle. L'objet est une image et les attributs extraits sont choisis parmi la liste suivante : texture, couleur. Après l'étape de fusion exécutée dans le module E3, le procédé retourne pour chercher la meilleure carte de typé 1, puis la meilleure carte de type N, etc... Selon une autre variante de réalisation, après l'étape de fusion exécutée au sein du module E3, le procédé prend les K résultats issus de la fusion et les fusionne entre eux en utilisant une technique de fusion, afin d'obtenir une seule partition compromis pour aller chercher la meilleure carte pour un type de descripteur. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture d'un exemple non limitatif de réalisation en se référant aux figures qui représentent : • Les figures 1A et 1 B, un exemple de structure de système permettant la mise en oeuvre du procédé selon l'invention, et un synoptique des différentes phases mises en oeuvre par le procédé, • La figure 2, une représentation de l'enchaînement des différentes étapes mises en oeuvre par le procédé selon l'invention, • La figue 3, les étapes de prétraitements et d'extraction de caractéristiques, • La figure 4, les étapes pour la classification (par plusieurs algorithmes) et le recodage des données par catégorie, • La figure 5 la fusion des différents résultats de classification et de recherche de consensus, et • La figure 6 la fusion finale, la recherche du consensus final et la sélection de la meilleure carte permettant la navigation et la recherche d'information dans une base de données de taille volumineuse. De manière à mieux faire comprendre l'objet de la présente invention, l'exemple qui suit va être donné pour un problème de recherche et d'accès rapide à de l'information visuelle dans une base de données d'images décrites par un ensemble de descripteurs numériques (descripteurs couleur, descripteurs texture, etc.) et textuels (plusieurs milliers de mots extraits des pages web). Le terme objet est donc utilisé, dans cet exemple, pour désigner une image dans la base de données. Les termes objets et données sont utilisés indifféremment pour désigner un élément d'une base de données. Ainsi, la figure 1A schématise un exemple de système selon l'invention qui comprend la base de données 1 contenant un nombre important d'images, à partir de laquelle les informations doivent être recherchées. La base de données image 1 est reliée à un processeur 2 qui va comprendre différents modules adaptés à mettre en oeuvre les étapes E,, à E5, dont notamment un module d'analyse relationnelle et un ou plusieurs modules de carte auto organisatrice plus connue sous l'abréviation anglo-saxonne Self Organizing Map ou en abrégé SOM. La base de données 1 et le processeur 2 sont par exemple implémentés dans un système de reconnaissance comprenant des entrées/sorties 3, 4. La sortie 4 peut être en liaison avec une Interface Homme Machine, qui permet par exemple l'affichage des résultats 5 et/ou la possibilité d'entrer différents types de requêtes par un opérateur 6. La figure 1B est un résumé des différentes étapes du procédé, détaillées aux figures suivantes. Le procédé prend en entrée de grandes bases de données 1, images, signaux, documents, ou autres. La première étape E, consiste à extraire des caractéristiques ou descripteurs associés aux objets ou données stockées. La deuxième étape E2 va consister à réduire la dimension de l'espace de description des objets, en recodant chaque donnée, pour chaque type de descripteur k, par autant de numéros que d'algorithmes SOM utilisés pour le recodage. Chaque numéro ni correspondant à la classe d'appartenance de cette donnée par l'algorithme SOMi. On obtient donc un recodage des données dans des espaces des classifications retenues. Lors de la troisième étape E3, le procédé va fusionner les classifications par mise en oeuvre d'un algorithme de recherche de consensus qui peut être réalisé par une analyse relationnelle, méthode connue de l'Homme du métier qui ne sera pas détaillée. Lors d'une quatrième étape E4, le procédé va ensuite recoder les données issues de la première fusion, puis la cinquième étape E5 consiste à sélectionner la meilleure carte auto adaptative ou SOM permettant une visualisation et une navigation simplifiée et rapide au sein de la base de données. La figure 2 représente l'enchaînement des étapes El à E5 exécutés dans les modules E, à E5 qui vont être détaillées aux figures 3 à 6. La figure 3 détaille les étapes exécutées par le processeur 2 pour la première phase. Les données de la base de données volumineuse sont transformées par des prétraitements adaptés afin d'en extraire 20 des caractéristiques ou attributs relatif à chaque descripteur (couleur, texture, etc) pour chaque donnée. Les objets contenus dans la base de données sont référencés Oi. Ces objets Oi sont ainsi décrits par un ensemble de descripteurs, par exemple de K types. A l'issue de cette étape, le processeur possède à sa disposition K tableaux TTK de données ou éléments zij, composés chacun de N lignes qui correspondent au nombre de données Oi contenues dans la base BD, 1, et un nombre variable de colonnes. Le nombre de colonnes varie en fonction du type d'indicateurs. Les attributs permettant de décrire un indicateur (ou descripteur) ne sont pas, forcément, les mêmes. En effet, le nombre d'attributs pour décrire le descripteur couleur n'est pas, forcément le même que celui qui permet de décrire le descripteur texture, par exemple. Un élément zij du tableau correspond à une valeur obtenue par l'étape d'extraction. Par exemple, si l'on considère l'ensemble des couleurs comme type de descripteur, les attributs correspondront chacun à une couleur et l'élément zij sera la valeur associée à une couleur donnée pour la donnée Oi. Les résultats de la première étape E1 se présentent donc sous une forme de K tableaux TTK de données zij qui seront segmentées par la suite en utilisant plusieurs algorithmes de classification automatique non supervisée (figure 4), plus connue sous la dénomination anglo-saxonne SOM. Ces algorithmes peuvent être des variantes de l'algorithme SOM. Chaque tableau TK de données zij issues d'un type de descripteur k sera segmenté par plusieurs algorithmes SOMi. Le nombre d'algorithmes SOMi appliqués sur chaque tableau Tk est choisi par l'utilisateur. Il peut varier pour chaque descripteur. Les algorithmes appliqués à chaque descripteur peuvent varier, ou être les mêmes, d'un descripteur à l'autre. La figure 4 détaille l'application de plusieurs algorithmes SOMi sur les K tableaux Tk de la figure 3. L'application de plusieurs algorithmes SOMi, génèrent des classifications qui permettent une réduction de la dimension de l'espace des données (dimension de l'espace dans lequel la recherche et la navigation vont se faire) et offrent un codage catégoriel de dimensions plus réduites. Ainsi, au départ, il est possible d'avoir des centaines d'attributs (ou colonnes) qui décrivent chacun des K indicateurs (ou descripteurs). Après application des différents algorithmes SOMi, il y aura autant de colonnes (nombre beaucoup plus petit que les attributs de départ, d'où la réduction) que d'algorithmes SOMi appliqués. Les données seront décrites par les numéros de catégories (ou classes) pour chaque algorithme. Les objets Oi d'un tableau seront décrits par les numéros de catégorie pour chaque algorithme. Un élément xij du tableau correspond au numéro de classe à laquelle l'objet Oi appartient après application de l'algorithme j. En effet, Une carte est une vue simplifiée de l'ensemble des images présentes dans la base de données. En effet, si la carte se présente sous la forme d'une vue à deux dimensions (13x13), on aura 169 images représentatives de toute la base d'origine (ce qui représente 169 classes). Mais il faut savoir que chaque image parmi les 169 de la carte cachent (ou représentent) plusieurs autres images de la base. Toutes les images cachées (ou représentées) par l'image numéro n, auront comme numéro (ou appartiendront à la classe) n. Le résultat de l'étape de classification dans le cas de l'application de l'algorithme SOM est une carte topologique à 2 dimensions où chaque objet référent est considéré comme un neurone représenté par un vecteur prototype de la même dimension que les données. En fait chaque algorithme SOMi donne comme résultat une carte topologique Ts, à deux dimensions et chaque neurone (ou élément) de la carte aura un numéro qui identifiera toutes les données xij représentées par ce neurone, où s est un indice pour désigner l'application d'un algorithme SOM et I le nombre d'algorithmes utilisés. Lors de l'étape E2, le procédé va après avoir réduit la dimension de l'espace de description, en utilisant plusieurs algorithmes SOMi, recoder chaque élément des tableaux. Ceci est illustré à la figure 4. L'exemple donné sur cette figure montre l'application de plusieurs algorithmes SOMi, pour chaque donnée Oi, correspondant à des classifications topographiques différentes. Pour chaque élément d'un tableau TS,, et chaque classification de 1 à c, 1 à P, 1 à D, sur la figure, SOM1,...SOMi, avec i= C ou P ou D, le procédé va recoder les éléments xij du tableau, pour chaque type de descripteur de type 1 à K. Ce recodage consiste à représenter chaque donnée Oi par un vecteur ayant autant de composantes que d'algorithmes SOM utilisés. Une composante xij obtenue par recodage correspond au numéro de la classe à laquelle appartient la donnée Oi dans la carte SOMj, elle est aussi égale au numéro du neurone prototype le plus proche de cette donnée dans l'espace de description d'origine. A la fin de ce recodage le processeur dispose, pour chaque type de descripteur k, d'un tableau de données TS, ayant un nombre de lignes (toujours le même égal au nombre N d'objets Oi de la base), un nombre de colonnes correspondant au nombre d'algorithmes SOMi appliqués pour chaque type de descripteur. Sur la figure ceci est illustré par les dimensionnements NxC pour le tableau Tsc, NxD pour le tableau Tsp et NxE pour le tableau TsD, avec C, D et E représentant le nombre d'algorithmes SOM utilisés pour chaque type de descripteur. La figure 5 détaille les étapes mises en oeuvre lors de l'étape correspondant à la 1 ere fusion des classifications SOMi. Cette étape met en oeuvre un algorithme d'analyse relationnelle connu de l'Homme du métier ou de manière plus générale, il peut mettre en oeuvre tout type d'algorithme de fusion présentant des fonctions similaires à celles offertes par l'analyse relationnelle. Pour chaque descripteur k, le tableau des données T'k est soumis à une analyse relationnelle afin de déterminer un consensus entre les différents résultats de classification par les SOMi. II s'agit de la première étape de fusion des objets dans le procédé. Cette étape peut aussi être vue comme une méta-classification dont le résultat final est une classification de compromis. Le principe de l'analyse relationnelle est de trouver un résultat conforme à la majorité des opinions exprimées (en général). Dans le présent exemple, il s'agit de classification, et donc le résultat de l'analyse relationnelle sera de mettre dans la même classe toutes les images ou objets de la base de données qui ont été mis ensembles dans la même classe par la majorité des algorithmes SOMi utilisés. Ainsi sur la figure 5, les données recodées contenues dans le premier tableau T'sc pour chaque SOMi, pour i variant de 1 à c, par exemple, vont être soumises à un algorithme d'analyse relationnelle qui va donner comme résultat la classification la plus proche possible de toutes les classifications obtenues par les algorithmes SOMi i=1, ..., C appliqués à chaque type de descripteur. On obtient ainsi un tableau à deux colonnes, la première colonne désignant les objets Oi et la deuxième colonne le N° de cluster, classe à laquelle appartient l'objet. Les lettres AR correspondent à l'opération d'analyse relationnelle appliquée sur un tableau. A ce stade on se retrouve en présence de deux variantes possibles : 1) la première variante consiste pour chaque descripteur, à retourner vers les SOMi de départ (on mesure les distances entre la partition compromis obtenue par l'AR et chacune des partitions obtenues par les SOM appliquées) en utilisant les résultats du consensus obtenu lors de l'analyse relationnelle. Ceci permettra de sélectionner la meilleure carte SOMi par type de descripteur, et utiliser ces cartes pour la navigation et la recherche d'informations, ceci permettra de répondre aux requêtes des utilisateurs, lorsque ces derniers spécifient le type de descripteur qui les intéresse. 2) la deuxième variante consiste à fusionner les résultats obtenus par l'AR pour tous les descripteurs et retourner chercher les meilleures cartes (comme précédemment). L'avantage de cette approche sera de chercher, pour chaque type de descripteur, la meilleure carte qui prend en compte les autres descripteurs. Rechercher la meilleure carte, revient donc, à trouver la partition la plus proche de la partition � compromis � trouvée par l'analyse relationnelle (ou la plus corrélée avec cette partition). Plusieurs indicateurs mathématiques, connus de l'homme du métier, existent dans la littérature scientifique pour le calcul de cette corrélation. A partir des résultats de la première fusion, un deuxième recodage des données est effectué. La figure 6 est une illustration de l'étape E5. Après avoir trouvé la meilleure carte SOMi de chaque descripteur, on se trouvera en présence de K cartes SOMi (une pour chaque descripteur), considérées comme les K meilleures cartes. Ces K cartes seront soumises à l'analyse relationnelle qui cherchera la partition compromis entre toutes les partitions relatives au K SOM. Après ce deuxième recodage, le processeur dispose d'un tableau de données NxK avec N le nombre d'objets dans la base et K le nombre de descripteurs choisis lors de la première étape El. Les données de ce nouveau tableau TNK se présentent sous une forme semblable à celle des tableaux obtenus à la figure 5. En effet le nombre de colonnes sera égal à K est chaque colonne sera tout simplement l'une des colonnes obtenues à la figure 5 (la meilleure parmi les C SOM pour le descripteur 1, la meilleure parmi les D SOM du descripteur 2, etc...). Les données sont soumises à un algorithme d'analyse relationnelle pour obtenir la fusion des données et la recherche d'un consensus global. Le consensus trouvé par cet algorithme représente une classification finale et permet de sélectionner la meilleure carte SOMi ou carte SOMf qui sera utilisée comme interface avec l'utilisateur final pour la navigation et la recherche d'informations. L'avantage de cette dernière fusion est d'avoir la meilleure classification de la base de données, indépendamment du type de descripteur. A ce stade, un utilisateur pourra avoir une réponse en temps réel à une requête sans devoir spécifier un type de descripteur spécifique. Une autre fonctionnalité que l'on pourra ajouter au système, sera l'interactivité entre le système et l'utilisateur final pour améliorer ou affiner les classes obtenues par le procédé. En effet, quand un utilisateur fait une requête, il aura une ou plusieurs classes qui correspondant à sa demande. Il pourra, éventuellement, enlever une ou plusieurs données (ou images) qu'il juge être mal classées et les proposer au système qui ira chercher la meilleure classe possible pour chaque donnée. L'utilisateur a la possibilité d'indiquer qu'une information est pertinente ou non par rapport à sa requête. Cette interaction avec l'utilisateur se traduit par une mise à jour et un raffinement de la classification. En se basant sur les propriétés topologiques de la carte SOM, le système reclasse les informations en fonction de la réaction de l'utilisateur. Ceci permet une évolution active du système. L'utilisateur en voyant une classe d'images donnée, peut décider qu'une ou plusieurs des images de cette classe ne correspondent pas à la classe observée. Cette (ou ces images) seront alors proposées au système pour qu'il les classe dans la classe la plus pertinente. En résumé, le système selon l'invention permet de pouvoir classifier et visualiser des données à très fortes dimensionnalités multi-modales dans un espace de faibles dimensionnalités, ou espace de partitionnement, sans disposer d'information a priori sur le nombre de groupes. La première contribution consiste à définir le problème de fusion comme un problème de méta-classification dans un espace de variables catégorielles par une technique de classification automatique (l'analyse relationnelle). La deuxième contribution consiste à traiter le problème de fusion d'une manière modulaire, coopérative et évolutive. En effet, ce procédé est évolutif par rapport aux données et par rapport aux utilisateurs ou experts. Un processus de retour en arrière "Backward" et de raffinement des résultats de la classification globale est introduit dans le processus de fusion modulaire. L'utilisation des méthodes connexionnistes non supervisées comme moyen de recodage des données (quantification) et de l'analyse relationnelle comme méthode de fusion permettent une visualisation hiérarchique des résultats de la classification avec plusieurs niveaux de détails. L'efficacité de ce procédé est illustrée sur un problème de recherche et d'accès rapide à l'information visuelle dans une base de données d'images décrites par un ensemble de descripteurs numériques (descripteurs couleur et descripteurs texture) et textuels (plusieurs milliers de mots extraits des pages web).25 REVENDICATIONS1 ù Système de recherche d'informations au sein d'une base de données (1) de taille importante, comprenant un processeur (2) et des entrées/sorties (3, 4), ledit système étant caractérisé en ce que ledit processeur (2) comporte au moins les éléments suivants : • Un premier module E1 adapté à extraire les descripteurs associés à chaque objet de la base de données, et à construire un tableau contenant les objets et la valeur d'un descripteur associé à un objet, ceci pour les descripteurs choisis pour la représentation de l'objet, • Un deuxième module E2 adapté à appliquer plusieurs algorithmes de classification SOMi, pour chacun des tableaux TTk issus du module E1, afin d'attribuer pour chaque objet Oi, un numéro de classe xij, pour un algorithme SOMi appliqué, pour chaque catégorie de descripteurs, • Un troisième module E3 adapté à fusionner les résultats issus du module E2 afin de déterminer pour chaque type de descripteur Tk, un numéro de classe associé à un objet Oi, • Un quatrième module E4, adapté à rechercher quelle est la colonne SOMi d'un tableau Tg, la plus proche de la colonne obtenue lors de la première fusion de l'étape E3, et à sélectionner la carte SOMi la plus proche contenue dans le tableau TS,, ou meilleure carte SOMi, • Un cinquième module E5 adapté à fusionner les � meilleures cartes � sommes SOMi, et appliquer un algorithme de recherche de la meilleure carte SOMf à transmettre à un moyen d'affichage (5). 2 ù Système selon la revendication 1, caractérisé en ce que l'algorithme de fusion est un algorithme d'analyse relationnelle. 3 ù Système selon l'une des revendications 1 à 2, caractérisé en ce que l'objet est une image et en ce que les attributs extraits sont choisis parmi la liste suivante : texture, couleur.4 ù Système selon la revendication 1, caractérisé en ce qu'après l'étape de fusion exécutée dans le module E3, le procédé retourne pour chercher la meilleure carte de type 1, puis la meilleure carte de type N. 5 ù Système selon la revendication 1, caractérisé en ce qu'après l'étape de fusion exécutée au sein du module E3, le procédé prend les K résultats issus de la fusion et les fusionne entre eux en utilisant une technique de fusion, afin d'obtenir une seule partition compromis pour aller chercher la meilleure carte pour un type de descripteur.