Brevet FR2857130A1 — publié le 20050107

L'invention concerne un dispositif et une méthode de mesure de similarité visuelle. Le contexte de l'invention est l'indexation des images par le contenu et la recherche par similarité visuelle dans les bases de données d'images fixes. Traditionnellement, ces bases de données étaient indexées manuellement par mot-clés. L'accumulation d'immenses quantités de données numériques, suite à la croissance accélérée des débits de communication et de la capacité des dispositifs de stockage, a rendu nécessaire le développement d'outils robustes d'annotation automatique des images par leur contenu. Dans une application typique de recherche par similarité, l'utilisateur formule sa requête à l'aide d'une image exemple et le système lui retôurne une liste d'images supposées proches visuellement, classées par distances croissantes. La distance utilisée est une distance entre attributs automatiquement extraits des images (c'est pourquoi on parle d'indexation des images par leur contenu). Les attributs utilisés sont de "bas niveau", proches du signal image (couleurs, textures, transformée en ondelettes...) par opposition à une interprétation "sémantique" de la scène en terme d'objets et d'évènements. La similarité visuelle calculée par la machine peut parfois ne pas coïncider avec la similarité sémantique attendue par l'utilisateur, ce qui constitue la limitation principale de ces systèmes d'indexation et de recherche par le contenu. La première génération de systèmes de recherche par le contenu utilise des attributs "globaux", c'est-à-dire calculés sur l'image entière. L'histogramme des couleurs présentes dans l'image en est l'exemple type. Pour prendre en compte la notion de localisation spatiale des objets dans l'image, la génération suivante découpe l'image en régions et attache des descripteurs "locaux" à chaque région Un partitionnement arbitraire de l'image, tel qu'un quadrillage par exemple, ne coïncide bien évidemment pas avec les frontières des différents objets qui composent l'image. Une description plus précise consiste alors à attacher les descripteurs locaux à des régions de forme quelconque, qui correspondent aux objets ou à leurs sous-parties, obtenues par un algorithme de segmentation. On espère ainsi aboutir à un calcul automatique de similarité visuelle qui soit plus proche de la similarité intuitive perçue par un observateur humain, et qui permettent de reconnaître que deux images sont semblables même si les objets similaires ne sont pas à la même échelle, pas à la même position et ne composent qu'une partie de la scène. Autant le calcul d'une distance entre deux images décrites par descripteurs locaux associés à un quadrillage est quasi-immédiat, la distance globale étant la moyenne des distances entre attributs locaux associés à des blocs de mêmes coordonnées spatiales, autant la solution est loin d'être intuitive quand les deux images sont segmentées en régions de formes quelconques. Le document de A Natsev, R Rasogi et K Shim Walrus: A similarity retrieval algorithm for image databases publié lors de la conférence internationale ACM SIGMOD internationale conference on management of data de Philadelphie en Juin 99, propose une mesure de similarité visuelle entre deux images segmentées en régions de formes quelconques, la distance élémentaire entre deux attributs locaux étant supposée connue. Dans cette méthode, deux régions (Q;, Ti) appartenant respectivement à deux images (Q, T) différentes sont similaires si la distance entre deux de leurs attributs (FI, F2) est inférieure à un seuil e. Une région de l'image Q étant mise en correspondance avec au plus une région de T et réciproquement. Parmi toutes les paires de régions similaires possibles, celle choisie étant celle qui maximise un critère de similarité selon la formule suivante: / P ( ÜT1 air e U Q, + aire aire (Q)+aire (T) E(Q,T)= p étant le nombre de régions similaires entre les images Q et T. Cette méthode permet donc de mesurer la similarité visuelle par la fraction de la surface des deux images constituées par des régions mises en 5 correspondance. La méthode proposée dans cet art antérieur propose une résolution sousoptimale dans laquelle les paires de régions candidates d'aire maximale sont itérativement mises en correspondance. Cependant, cette méthode est très dépendante de la valeur de seuil c. Une fois que deux régions sont déclarées visuellement similaires car la distance entre leurs attributs est inférieure à c, ce choix binaire n'est plus remis en cause dans le reste du calcul. Un seuil trop bas conduira à une sous estimation de la similarité globale entre les images, fixé trop haut il conduira à traiter sur le même plan des paires de régions très semblables ou au contraire faiblement semblables. De plus, lors de la mise en oeuvre de la métrique, les tailles (aires) respectives des régions mises en correspondance dans les deux images ne sont pas prises en compte. Ceci permet d'être robuste aux changements d'échelles (c'est-à-dire de facteur de zoom) mais conduit à des situations peu souhaitables où une très petite région est mise en correspondance avec une image entière, sur la seule base de leur similarité en terme d'attributs. En outre de telles configurations sont favorisées par le critère global de maximisation des surfaces mises en correspondance. La présente invention propose un procédé de mesure de similarité visuelle prenant en compte la distance entre attributs dans le critère global de maximisation de la similarité pour la détermination de la liste des paires de régions mises en correspondance. De cette manière, la présente invention rend possible une meilleure mesure de similarité entre images et est utilisable dans des applications de recherche d'images par mesure de similarité visuelle. A cet effet, la présente invention propose un procédé de mesure de similarité visuelle entre deux images, une image étant dite image modèle et une image étant dite cible, comportant une étape préalable de segmentation des images en régions, à chaque région étant associé au moins un attribut représentatif d'au moins une caractéristique de la région, comportant les étapes de - calcul de la similarité visuelle entre les paires de régions possibles des deux images, - sélection d'un certain nombre de paires de régions dont la 10 similarité est supérieure à un premier seuil fixé, - calcul de la similarité globale entre les deux images basée sur les paires de régions sélectionnées, Selon l'invention, l'étape de calcul de la similarité visuelle entre les paires de régions possibles des deux images prend en compte la distance entre lesdits attributs des régions mises en correspondance et les aires des régions mises en correspondance. Selon un mode préféré de réalisation, le procédé comporte en outre après I 'étape de sélection et avant l'étape de calcul de la similarité globale, une étape d'exclusion à partir de la liste des paires de régions sélectionnées, des paires de régions pour lesquelles le rapport entre leurs aires est supérieur à un second seuil ou inférieur à l'inverse dudit second seuil. De cette manière, il peut être possible de ne pas prendre en compte les paires de régions préalablement sélectionnées dont les surfaces sont trop 25 différentes en terme de taille. Selon un mode préféré de réalisation, l'étape de calcul de la similarité visuelle entre toutes les paires de régions possibles des deux images pondère la distance entre lesdits attributs des régions mises en correspondance et la 30 fraction entre la surface des régions mises en correspondance sur la surface des deux images. Selon un mode préféré de réalisation, l'étape de calcul de la similarité visuelle entre les paires de régions possibles des deux images et l'étape de sélection d'un certain nombre de paires de régions dont la similarité est supérieure à un premier seuil fixé comportent pour toutes les régions de l'image modèle, les sous-étapes de - sélection d'une région de l'image modèle, - mesure de la similarité visuelle entre la région parcourue et les régions de l'image cible, - sélection de la région présentant la plus forte similarité visuelle avec l'image parcourue. Ceci correspond à une solution sous-optimale qui rend possible une diminution de la complexité des calculs de similarité entre toutes les régions possibles. Effectivement, une mise en correspondance de toutes les régions possibles de l'image modèle avec toutes les régions possibles de l'image cible et une décision à postériori des paires de régions est très coûteuse en temps de calcul. Le mode préféré de réalisation proposé permet de minimiser les calculs en prenant une région de l'image modèle, en mesurant la similarité visuelle entre cette région et toutes les régions de l'image cible et en choisissant la région de l'image cible présentant la plus forte similarité avec la région de l'image modèle. La paire de régions ainsi formée n'est ensuite plus remise en cause et l'on passe à une autre région de l'image modèle tant qu'il reste des régions. Selon un mode préféré de réalisation, la sous-étape de sélection d'une région de l'image modèle, sélectionne les régions de l'image modèle selon 25 leur ordre croissant de surface. De cette manière, les régions ayant une surface importante sont prioritaires dans la recherche des régions présentant une similarité visuelle. La présente invention propose également un dispositif de similarité visuelle ayant les avantages précités. La présente invention propose également un produit programme d'ordinateur comprenant des instructions de code de programme aptes à mettre en oeuvre le procédé selon l'invention lorsque le programme est exécuté sur un ordinateur. L'invention sera mieux comprise et illustrée au moyen d'exemples de 5 modes de réalisation et de mise en oeuvre avantageux, nullement limitatifs, en référence aux figures annexées sur lesquelles: - la figure 1 représente une décomposition d'une image en régions de forme quelconque, - la figure 2 représente un mode de réalisation d'un organigramme de fonctionnement d'un dispositif selon l'invention. La figure 1 représente un exemple de décomposition d'une image Q appelée image modèle décomposée en Q régions Qi. L'image Q représente l'image exemple soumise au dispositif selon l'invention et pour laquelle le dispositif doit retourner des images similaires. L'image Q est une image découpée en régions de forme quelconque par opposition à une découpe en quadrillage. La découpe en régions Qi correspond à une découpe suivant les objets, ou selon des sous-parties de ces objets, représentés sur l'image. Ces sous-parties sont obtenues par un algorithme de segmentation couramment employé par l'homme du métier. L'image T, appelée image cible, représente une image d'une base de données comportant des images dont on recherche la similarité visuelle avec l'image sélectionnée Q. Les images de la base de données telle T, sont également décomposées en régions en utilisant la même méthode de segmentation que l'image Q. L'image Q peut être une image proposée par l'utilisateur ou une image elle-même issue de la base de donnée et sélectionnée par l'utilisateur. A cet effet, l'image Q est décomposée en régions Qi lorsqu'elle est soumise au dispositif selon l'invention ou alors elle est préalablement décomposée en régions et stockée dans la base de données et son découpage en régions lui est associé. A chaque région est associée au moins un attribut F. F est représentatif d'une caractéristique de l'image choisie, à titre illustratif et non limitatif, parmi la texture, la couleur. A titre d'alternative, les coefficients dominants de la transformée en ondelettes peuvent également être pris en tant qu'attribut. Les attributs F associés à chaque région de l'image sont calculés et stockés dans la base de données avec chaque image. ils peuvent également être calculés au fur et à mesure lorsqu'une image est utilisée par le dispositif mais ceci peut ralentir considérablement le procédé de mesure. Différentes méthodes de calcul des attributs existent et sont bien connues de l'homme du métier. La méthode proposée calcule la distance entre les attributs F des régions Qi de l'image Q et Ti de l'image T. La distance D calculée peut être une distance de type euclidienne à titre illustratif. Dans les équations suivantes, il est supposé que la distance D renvoie des valeurs normalisées comprises entre 0 et 1. La figure 2 illustre une méthode de calcul de la similarité entre une 20 image Q et des images T cibles selon un mode de réalisation préféré de l'invention. A l'étape El, l'utilisateur sélectionne une image Q pour laquelle il souhaite trouver des images présentant une similarité visuelle avec elle. Ensuite, lors de l'étape E2, on segmente l'image Q en régions Qi. Le nombre de régions Qi est dépendant du contenu de l'image, les régions pouvant correspondre à des objets présents dans l'image ou à des sousparties de ces objets. On calcule également, pour chaque région de l'image Qi, des attributs représentatifs du contenu visuel de cette image. Ces attributs pouvant être représentatifs de la couleur, de la texture ou également correspondre aux coefficients d'une décomposition en cosinus discrète ou d'une transformation en ondelettes. Lorsque l'image Q est une image de la base de données dans laquelle on va recherche les images similaires, l'image Q est déjà segmentée et les attributs associés aux régions sont déjà calculés et stockés également dans la base de données. Dans ce cas, l'étape E2 est facultative et l'on passe directement de l'étape El à l'étape E3. A l'étape E3, on calcule la similarité E possible entre toutes les régions de l'image Q et toutes les régions des images T candidates en utilisant la 5 formule suivante à titre illustratif. aire(g) + aire(T) dans laquelle: w est un facteur de pondération, - D(Qi, Ti) représente la distance entre les attributs F des régions Qi et Ti, Aire (Qi) et aire(Ti) représentent les aires respectives des régions Qi et Ti, exprimées en pixels, Aire(Q) et aire(T) représentent les aires respectives des 15 images Q et T exprimées en pixels. Dans un mode de réalisation préféré, le facteur de pondération w est fixé à la valeur 1/3. La similarité calculée prend en compte la distance D entre les attributs F des régions de l'image T et les régions de l'image Q en mettant en correspondance toutes les régions Q; de l'image Q et toutes les régions Ti des images T et le rapport de l'aire recouverte par les régions sur l'aire totale des images. Le facteur de pondération w permet de donner plus d'importance à l'aire des régions mises en correspondance tout en prenant en compte la distance entre leurs attributs. Ceci par opposition à la méthode de Natsev précédemment décrite qui elle prend en compte l'aire mais sur des régions déjà sélectionnées au préalable. Ensuite, lors de l'étape E4, une sélection des paires (Q;, Ti) de régions les plus similaires est effectuée. Seules sont sélectionnées les paires de régions dont la similarité est supérieure à un seuil prédéterminé. E(Q,,Ti)=w*(1-D(Q;,T,))+(1 V w) aire (Q)+ aire (T) a E(Q,,T,) >_ s Dans un mode préféré de réalisation, le seuils est fixé à la valeur 0,7. Lorsque ces paires ne sont pas sélectionnées, on passe alors à l'étape E6 dans lesquelles ces paires sont référencées comme non sélectionnées et pourront donc être mises en correspondance avec d'autres régions puis à l'étape E3. Puis, parmi les paires de régions sélectionnées, on exclue certaines paires dont le facteur d'agrandissement/réduction est trop grand. Le facteur d'agrandissement/réduction est représenté par le rapport des surfaces des deux régions. Par exemple, soient deux régions Qi et Ti, alors le facteur d'agrandissement/réduction R peut être représenté par: R _ aire(Q, ) aire(T, ) Lorsque ce rapport R est supérieur à une valeur a ou inférieur à une valeur lia, la paire de régions (Q;, Ti) est exclue (étape E6). Dans un mode préféré de réalisation, la valeur a est fixée à 4. Dans ce mode de réalisation, les régions Q sont sélectionnées l'une après l'autre et on passe d'une région à l'autre après avoir trouvé une région correspondante Ti présentant la similarité maximale avec la région Q; . Dans un autre mode de réalisation, il pourrait être envisagé de calculer toutes les similarités possibles entre toutes les régions et de sélectionner ensuite les paires optimisant la similarité totale de l'image. Dans un autre mode de réalisation, il pourrait être envisagé de parcourir les régions Q; par ordre de taille croissante de façon à trouver préférentiellement une région présentant une similarité optimale pour les régions les plus grandes. Lors de l'étape E7, les paires (Q;, Ti) sont sélectionnées et mises de côté, dans un moyen de stockage par exemple, et ne pourront plus être 30 sélectionnées par la suite. Si toutes les paires (Q;, Ti) ont été mises en correspondance (étape E8), alors on repasse à l'étape E3, sinon, on passe à l'étape E9. Lors de cette étape, afin de calculer la similarité globale entre l'image Q et une image T candidate, la similarité globale entre les images Q et T est 5 calculée selon la formule suivante: Sini (Q, T D(Q T, )) aire p UQ +aire UT, aire (Q)+ aire (T) dans laquelle: p représente le nombre de régions dont la similarité est supérieure au seuils et qui n'ont pas été exclues lors de l'étape d'exclusion précédente. Cette formule est donnée à titre d'exemple mais ii serait égaiement possible de calculer la similarité en se basant sur tout autre formule qui prendrait en compte la distance entre attributs ainsi que les aires des régions mises en correspondance en les pondérant. Revendications 1. Procédé de mesure de similarité visuelle entre deux images (Q, T), une image (Q) étant dite modèle et une image (T) étant dite cible, comportant une étape (E2) préalable de segmentation des images en régions (Q;, Ti), à chaque région étant associé au moins un attribut (F) représentatif d'au moins une caractéristique de la région, comportant les étapes de - calcul (E3) de la similarité visuelle entre les paires (Q;, Ti) de régions possibles des deux images (Q, T), - sélection (E4) d'un certain nombre de paires (Q;, Ti) de régions dont la similarité est supérieure à un premier seuil (0 fixé, - calcul (E9) de la similarité globale entre les deux images basée sur les paires (Q;, Ti) de régions sélectionnées, caractérisé en ce que l'étape (E3) de calcul de la similarité visuelle entre les paires (Q;, Ti) de régions possibles des deux images (Q, T) prend en compte la distance (D((Q;, T;)) entre lesdits attributs (F) des régions (Cl, Ti) mises en correspondance et les aires des régions (Q;, Ti) mises en correspondance. 2. Procédé selon la revendication 1 caractérisé en ce qu'il comporte en outre après I étape (E4) de sélection et avant l'étape (E9) de calcul de la similarité globale, une étape d'exclusion (E5) à partir de la liste des paires (Q;, Ti) de régions sélectionnées, des paires de régions (Q;, Ti) pour lesquelles le rapport entre leurs aires est supérieur à un second seuil (a) ou inférieur à l'inverse (1/a) dudit second seuil. 3. Procédé selon l'une des revendications précédentes caractérisé en ce que l'étape (E3) de calcul de la similarité visuelle entre les paires de régions possibles des deux images pondère (w) la distance (D) entre lesdits attributs (F) des régions (Q;, Ti) mises en correspondance et la fraction entre la surface des régions mises en correspondance sur la surface des deux images. 4. Procédé selon l'une des revendications précédentes caractérisé en ce que l'étape (E3) de calcul de la similarité visuelle entre les paires (Q;, Ti) de régions possibles des deux images (Q, T) et l'étape (E4) de sélection d'un certain nombre de paires de régions (Q;, Ti) dont la similarité est supérieure à un premier seuil (s) fixé comportent pour toutes les régions de l'image (Q) modèle, les sous-étapes de - sélection d'une région de l'image modèle, - mesure de la similarité visuelle entre la région parcourue et les régions de l'image cible, - sélection de la région présentant la plus forte similarité visuelle avec l'image parcourue. 5. Procédé selon la revendication précédente caractérisé en ce que la sous-étape de sélection d'une région de l'image modèle, sélectionne les régions de l'image modèle selon leur ordre croissant de surface. 6. Dispositif de mesure de similarité visuelle entre deux images caractérisé en ce qu'il comprend des moyens de segmenter des images en régions, à chaque région étant associé au moins un attribut représentatif d'au moins une caractéristique de la région, comprenant: - des moyens de calculer la similarité visuelle entre les paires de régions (Q;, Ti) possibles des deux images (Q, T), - des moyens de sélectionner un certain nombre de paires (Q;, T) de régions dont la similarité est supérieure à un premier seuil (E) fixé, des moyens de calcul de la similarité globale entre!es deux 30 images (Q, T) basée sur les paires de régions (Q;, Ti) sélectionnées, caractérisé en ce que les moyens de calcul de la similarité visuelle entre les paires de régions (Q;, Ti) possibles des deux images (Q, T) sont aptes à prendre en compte la distance (D) entre lesdits attributs (F) des régions (Q;, Ti) mises en correspondance et les aires des régions (QT.) mises en correspondance, ledit dispositif étant de préférence adapté à mettre en oeuvre le procédé 5 selon l'une des revendications 1 à 5. 7. Produit programme d'ordinateur caractérisé en ce qu'il comprend des instructions de code de programme aptes à mettre en oeuvre le procédé selon l'une des revendications 1 à 3 lorsque le programme est exécuté sur un ordinateur.