Comme nous l'avons vu dans l'introduction, les systèmes classiques de recherches d'images peuvent être classés en deux catégories :
Dans ce chapitre, nous détaillons comment les informations textuelles, puis visuelles, sont extraites des documents, et comment ces systèmes les utilisent pour rechercher l'information. Nous cherchons surtout à mettre en évidence les difficultés rencontrées pour construire de tel système. Puis nous décrivons quelques systèmes de recherche d'images par le contenu de l'état de l'art, et pour chaque système nous regardons s'il utilise et si oui de quelle manière l'information textuelle.
Cependant, les iconographes comme les utilisateurs rencontrent différents problèmes d'indexation manuelle des images [Vézina, 1998]. Le principal problème est le choix des termes. En effet, la personne qui indexe l'image et la personne qui recherche une image ne choisiront pas forcément le même terme pour décrire le même concept. En effet, la probabilité pour que le même terme soit choisi par deux individus différents pour décrire une entité quelconque est inférieur à 20% [Furnas et al., 1987,Ventresque, 2006]. Une même image peut avoir plusieurs sens, contenir plusieurs thèmes (polysémie de l'image). D'ailleurs, Sara Shatford Layne [Shatford Layne, 1994], spécialiste de l'indexation manuelle d'images, a dit en 1986 : «the delight and frustation of pictorial ressources is that a picture can mean different things to different people». L'indexation d'une image est donc subjective, plusieurs indexations sont donc possibles.
D'après [Krauze, 1988], il existe deux types d'indexation d'images. La première, le hard indexing (appelé aussi ofness) correspond à ce que l'indexeur voit dans l'image : le portrait d'une femme au sourire énigmatique. La seconde, le soft indexing (appelé aussi aboutness) qui porte sur la signification de l'image : la femme est «La Joconde» de Léonard de Vinci.
Malgré sa subjectivité, l'indexation manuelle reste une méthode efficace pour associer un sens à des images. Cependant, lorsque l'on a un grand volume d'images à indexer, ce travail devient vite fastidieux, voire impossible, ce qui n'est pas le cas pour l'indexation automatique. De plus, en ce qui concerne les photographies personnelles, une étude [Rodden & Wood, 2003] sur la façon dont les utilisateurs gèrent leurs photographies conclue que ceux-ci ne sont pas intéressés par annoter leurs photographies du fait des efforts nécessaires, et du fait qu'ils les connaissent. Une manière originale et plus évidente pour les utilisateurs d'indexer textuellement des images est d'enregistrer un message audio qui décrive leur contenu. Il ne reste plus alors au système qu'à transcrire ce message en texte pour obtenir une indexation automatique.
L'indexation textuelle automatique d'images consiste à associer des mots à une image au moyen d'un système informatique sans aucune intervention humaine. Il existe deux approches : l'indexation textuelle automatique à partir du texte associé à l'image, et l'indexation textuelle automatique à partir du contenu visuel de l'image.
La première approche n'est possible que lorsque les images sont associées à du texte. C'est le cas des images des encyclopédies, des catalogues de vente, des manuels techniques... et aussi du web. L'indexation textuelle des images sur le web peut s'effectuer à partir des mots présents dans le titre de la page ou des mots les plus fréquents ou pertinents de cette page. Cependant, toutes les images présentes sur une même page web ne devraient pas être indexées avec les mêmes mots. Beaucoup de moteurs de recherche utilisent aussi l'URL et le nom de l'image, mais la plupart des images ne sont pas nommées de façon pertinente, mais bien souvent par des noms génériques comme img001.jpg qui ne portent pas de sens. D'autres techniques considèrent les mots associés à l'attribut ALT de la balise IMG d'une image ou bien le texte proche de l'image, ou bien une fusion de toutes ces informations [Coelho et al., 2004,Jayaratne et al., 2003,Srihari & Burhans, 1994]. Mais, dans la pratique, peu d'images sur le web sont indexées de cette façon, car cela nécessite une indexation manuelle que l'on sait être très coûteuse en temps. De plus, le texte proche de l'image n'est pas forcément celui que l'on associerait à l'image.
La deuxième approche est souvent appelée auto-annotation par le contenu. Annoter une image avec des mots seulement à partir du contenu visuel est impossible. C'est pourquoi la plupart du temps les méthodes d'auto-annotation sont en fait des méthodes de classification supervisée multi-classes (une classe par mot). Elles utilisent un ensemble d'apprentissage où les images sont associées aux classes de mots pour apprendre à prédire des mots sur de nouvelles images. Nous présentons dans la partie 4 de cette thèse une description de quelques unes de ces méthodes. Cependant, comme nous le verrons, l'auto-annotation d'images est un problème toujours ouvert, même les meilleurs systèmes ne sont pas capables d'apporter un gain de plus de 40% sur le modèle empirique basé sur la distribution a priori qui a lui-même un score de classification très faible.
L'indexation textuelle automatique d'images, qu'elle s'effectue à partir du texte associé à l'image ou du contenu de l'image, commet donc beaucoup d'erreurs. Les images sont mal annotées.
Une fois indexées textuellement, les images peuvent être recherchées avec les modèles classiques de recherche dans les documents textuels (modèle booléen [Cooper, 1970], modèle vectoriel [Salton, 1971], modèle probabiliste [Robertson & Jones, 1976] et modèle logique).
Pour une présentation plus détaillée à ces modèles le lecteur peut se reporter à [Baeza-Yates & Ribeiro-Neto, 1999,Savoy, 2003].
Tous ces modèles utilisent des représentations de type «sac de mots» (bag-of-words). Il existe d'autres modèles, moins classiques, utilisant cette approche que nous décrirons dans la partie 4.2.1 page . Des techniques statistiques du traitement de la langue naturelle permettent des analyses et des représentations plus poussées, mais en contre partie perdent en simplicité et en rapidité. Nous renvoyons le lecteur intéressé à [Manning & Schütze, 1999,Gaussier et al., 2003,Besançon et al., 2003].
L'annotation textuelle d'images peut être effectuée manuellement, mais cela est très coûteux et subjectif. Elle peut également être effectuée automatiquement à partir du texte associé à l'image ou du contenu visuel, mais ces types de systèmes sont peu performants et les images sont finalement mal annotées. Cependant, l'avantage des systèmes textuels est qu'ils donnent la possibilité à l'utilisateur de poser des requêtes dans un langage de haut niveau lui permettant ainsi d'exprimer son besoin d'information facilement [Rodden & Wood, 2003,Mulhem et al., 2003]. De plus, les modèles, tels que le modèle vectoriel, permettent de retrouver rapidement et efficacement les documents répondant à une requête.
En ce qui concerne le problème de la subjectivité des termes, un thésaurus donnant les liens de synonymie et de hiérarchie entre les termes, tels que WordNet [Fellbaum, 1998], permet de réduire dans une certaine mesure les distances entre deux termes voisins [Tollari, 2003,Tollari et al., 2005,Benitez & Chang, 2002,Ferecatu et al., 2005,Srihari & Burhans, 1994]. Cependant, il n'existe pas à notre connaissance de thésaurus hiérarchique conséquent spécialement adapté pour décrire les images.
Les modèles «sac de mots» ont l'avantage d'être très rapides, mais ils ne permettent pas de poser des requêtes plus complexes. Par exemple, rechercher des images avec une voiture rouge près d'une personne sur un fond un vert. L'approche conceptuelle permet de faire ce type de requête. Elle nécessite que les images soient décrites par des graphes représentant les relations entre les objets dans les images. [Martinet, 2004] propose d'étendre le modèle vectoriel pour représenter les graphes conceptuels dans le cas de bases d'images.
Un cas particulier de systèmes généralistes sont les bases de photographies personnelles. Ces systèmes sont généralistes dans le sens où ils doivent être capable de traiter tous types d'images, mais ce type de systèmes doit être simple et fournir des informations sur les images, comme la date de prise de vue, qui soit adaptées à l'utilisateur.
D'après [Cox et al., 2000], un utilisateur peut avoir différents objectifs lorsqu'il effectue une recherche d'images. Il peut rechercher :
Pour trouver l'information qu'il recherche, l'utilisateur dispose d'au moins trois types de moyens (1) (les numéros entre parenthèses se rapportent au schéma de la figure 2.1) :
Des études [McDonald et al., 2001,McDonald & Tait, 2003] qui comparent trois outils (navigation dans une classification hiérarchique d'image, requête par croquis-exemple ou requête par image-exemple) montrent que les utilisateurs utilisent les trois outils pour effectuer leur requête, et que lorsque l'utilisateur n'a pas un objectif précis en tête, il utilise plutôt la navigation dans la classification hiérarchique. De plus, ces études montrent que le choix par l'utilisateur de l'outil de recherche dépend aussi de la facilité à formuler la requête.
Une représentation pratique est l'histogramme. Cet outil est plutôt insensible aux changements d'orientation, de taille et de position des régions, mais il ne capture pas les relations spatiales entre les régions, et par conséquent a un pouvoir discriminant limité. Un histogramme peut être vu comme le nombre d'apparitions d'un élément dans un ensemble. Ainsi pour construire un histogramme de descripteurs de couleurs, on utilise généralement deux phases : d'abord, les couleurs sont quantifiées, puis les couleurs quantifiées sont dénombrées. Chaque composante du vecteur (appelée en anglais bin) donne la quantité d'une couleur présente dans l'image. Afin de rendre les histogrammes invariants à la taille de l'image ou des régions, on peut normaliser l'histogramme par le nombre de pixels. Pour prendre en compte l'information spatiale dans l'histogramme, on peut ajouter la position des régions [Stricker & Dimai, 1996].
La quantification a pour objectif d'obtenir une représentation compacte du contenu visuel sans pour autant réduire son efficacité. Elle est effectuée généralement en deux étapes : d'abord, les histogrammes sont extraits des régions des images d'apprentissage, puis les vecteurs sont regroupés par classification non-supervisée, afin d'obtenir des clusters visuels, parfois appelés visual terms, qui résument l'information. Dans [Souvannavong et al., 2005], une étude comparant les résultats de classification en fonction du nombre de clusters choisi pour la quantification montre qu'à partir d'un nombre suffisant de visual terms (1000 dans leur cas), les performances ne sont plus diminuées par la quantification.
Puisque l'on souhaite construire des systèmes de recherche d'images qui soient utilisables par l'être humain, et que c'est l'être humain qui donne un sens à ce qu'il voit, il peut être intéressant de s'inspirer du système de perception humain pour choisir les espaces visuels afin de s'approcher le plus possible de la compréhension qu'à l'être humain de l'image, et ainsi réduire le fossé sémantique.
L'espace RVB est très simple à utiliser, car c'est celui employé par de nombreux appareils de capture d'images qui effectuent leurs échanges d'informations uniquement en utilisant les triplets (R,V,B). On parle d'espace colorimétrique orienté matériel. Cependant, ces trois composantes sont fortement corrélées (par exemple, si l'on diminue la composante verte, la teinte parait plus rouge), l'espace RVB est sensible aux changements d'illumination, et ne correspond pas au processus de perception humaine.
L'espace HSV (Hue-Saturation-Value) (aussi connu sous le nom de système de cône hexagonal) sépare les informations relatives à la teinte (Hue), la saturation (Saturation) et l'intensité (Value).Cet espace est plus intuitif à utiliser car il correspond à la façon dont nous percevons les couleurs. La teinte décrit la couleur (rouge, vert...), la saturation décrit l'intensité de la couleur, et la valeur décrit la luminosité de la couleur. La composante H de l'espace HSV offre une certaine invariance. Une étude récente [Lim & Lu, 2003] compare six espaces colorimétriques et montre que l'espace HSV est le plus efficace pour la recherche d'images par le contenu, cependant cet espace n'est pas perceptuellement uniforme.
Les espaces Lab, Luv et de Munsell modifié sont eux perceptuellement uniformes. Dans l'espace Lab chaque couleur est définie par 3 paramètres qui sont proches de nos concepts visuels : la clarté «L» (indice de luminosité relatif), et la chromaticité représentée par le couple (a,b). L'axe «a» correspond au couple antagoniste vert-rouge, et l'axe «b» au couple antagoniste bleu-jaune. La chromaticité peut également être représentée par deux paramètres : l'angle de teinte et le chroma appelé de préférence niveau de coloration. En supposant une proportionnalité entre les teintes et les angles de teinte, les teintes sont réparties sur un cercle situé dans un plan perpendiculaire à l'axe achromatique. Le cercle des couleurs part du rouge passe par le jaune, le vert, le bleu, et se referme par les pourpres. L'espace colorimétrique Lab est non-linéaire, mais il est considéré comme approximativement uniforme. Dans cet espace la distance euclidienne entre deux couleurs voisines correspond à leur différence perceptuelle.
Pour analyser et reconnaître une texture, on peut appliquer le schéma suivant (d'après [Bloch et al., 2004] page 52).
Les outils classiques des statistiques (moyenne, variance, moment, énergie, entropie...) peuvent être utilisée pour analyser les textures. Par exemple, le moment d'ordre 3 (skewness) donne une indication sur la symétrie ; le moment d'ordre 4 (kurtosis) donne une indication sur l'aplatissement. Les matrices de cooccurrences sont également des outils adaptés pour l'analyse de texture.
Au niveau sémantique, les textures peuvent apporter une information précieuse. En effet, elles permettent de différencier des parties d'images dont les descripteurs de couleurs sont identiques. Par exemple, le ciel (texture unie ou nuageuse) et la mer (texture des vagues).
L'utilisation de descripteurs de forme (shape) n'a de sens que sur une image segmentée. Pour extraire les descripteurs d'une forme, la première chose à faire est de définir sa fonction caractéristique. En général, elle est représentée sous la forme d'un masque dans lequel chaque pixel est représenté par le numéro de la région à laquelle il appartient. C'est à partir de cette fonction, que sont calculés la plupart des descripteurs de formes, soit à partir de la région entière, soit à partir des contours seulement.
Les descripteurs proposés sont souvent spécifiques à une forme particulière. Par exemple, le rapport iso-périmétrique, qui est un descripteur proportionnel au rapport du carré du périmètre de l'objet à sa surface est maximum, dans des images continues, pour le cercle.
On peut citer quelques descripteurs classiques :
La forme est intéressante pour retrouver certains concepts qui ne peuvent l'être autrement. Prenons le mot ballon, par exemple. Il n'y a pas de couleurs qui puissent caractériser un ballon puisque cet objet peut être de toutes les couleurs, par contre, il a une forme très caractéristique. La forme peut avoir certains avantages également sur la texture. Par exemple, une panthère peut avoir un pelage tacheté ou bien uni. La texture extraite de deux images représentant une panthère pourra donc être très différente, par contre, la forme reste identique. La forme est donc une information discriminante qui peut être utile pour réduire le fossé sémantique. D'ailleurs, dans [Schomaker et al., 1999], les auteurs disent que les utilisateurs de CBIR sont plus intéressés par rechercher en utilisant la forme (requête par croquis) plutôt que par la couleur ou la texture.
Nous avons vu qu'un des inconvénients des histogrammes est qu'il ne capture pas les relations spatiales entre les régions. C'est pourquoi [Hsu et al., 1995,Stricker & Dimai, 1996,Gudivada & Raghavan, 1995,Ma & Manjunath, 1999] proposent d'intégrer les informations spatiales soit directement dans l'histogramme, soit après une phase d'extraction des couleurs afin d'améliorer les résultats de recherche d'images en ajoutant une information discriminante. Par exemple, la plupart des images réelles étant orientées verticalement, la position en ordonnée des régions d'images indique si une région bleu de l'image correspond plutôt à une zone du ciel ou bien à la mer.
Dans [Lee et al., 2006,Lee & Hwang, 2003], les relations spatiales entre les objets d'une image sont intégrés dans le système à l'aide d'un codage symbolique des relations. Plus le nombre d'objets est grand dans l'image, plus le nombre de relations va être important. C'est pourquoi ils proposent de réduire les relations redondantes qui peuvent être déduites des autres relations.
Les relations spatiales entre les objets sont souvent représentées sous forme de graphes de voisinage. La recherche d'images revient alors à rechercher les graphes isomorphes, ce que l'on sait être un problème difficile [Hopcroft & Tarjan, 1974,Prié et al., 2000].
La mesure proposée dans [Martinet et al., 2005] n'est pas une mesure des relations spatiales entre les régions dans le sens qu'elle ne permet pas de mesurer si une région est située à coté de telle autre région, ou bien si une région est située en haut ou en bas de l'image, mais elle permet de mesurer le «désordre» entre les objets dans l'image au moyen d'une entropie, appelée entropie spatiale, calculée à partir des aires des objets dans l'image. Son objectif est de caractériser un type d'images en fonction d'une part du nombre d'objets dans l'image et d'autre part de l'aire des objets présents dans l'image. [Yanai & Barnard, 2005] propose également d'utiliser l'entropie des régions pour caractériser un concept donné, mais sur différents descripteurs visuels.
L'extraction de descripteurs visuels sur l'image entière (descripteurs globaux) permet de réduire le nombre de calculs nécessaires, la taille de la base de données ainsi que le coût des recherches des images les plus similaires. Cependant, l'approche globale ne permet pas une recherche efficace d'objets (au sens large) dans l'image. A l'inverse, les descripteurs extraits d'une partie de l'image (descripteurs locaux) sont efficaces, mais coûteux. Les descripteurs locaux peuvent être :
La segmentation d'image ((6) et (10) du schéma page ) consiste à séparer en régions homogènes les divers composants visibles dans une image. L'humain sait naturellement séparer des objets dans une image. Pour cela, il se base notamment sur des connaissances de haut niveau qui lui permettent de détecter ce qui l'intéresse dans l'image. En traitement du signal, on caractérise une région comme étant un ensemble de points (pixels) ayant des propriétés communes d'intensité, de texture, de couleur..., qui la différencient des régions voisines. Il y a de nombreuses méthodes de segmentation, on distingue cependant deux grandes familles d'algorithmes :
Une des difficultés de la segmentation est de savoir en combien de régions doit être découpée une image, car certaines images peuvent être segmentée en peu de régions (par exemple, un portrait sur fond uniforme), alors que d'autres nécessitent plus de régions. A quel niveau une segmentation doit-elle s'arrêter ?
[Da Rugna & Konik, 2004] compare des méthodes classiques de segmentation pour l'indexation d'images (clustering, mean shift, approche morphologique ou multirésolution). Leurs résultats montrent qu'il n'existe pas de segmentation générique ou meilleure que les autres, mais que en fonction de la tâche à accomplir certaines méthodes sont plus efficaces que d'autres.
[Barnard et al., 2003a] propose une étude comparative des techniques de segmentation pour la reconnaissance d'objets dans les images. Pour cette tâche, il est nécessaire d'obtenir des segmentations qui ne découpent pas un objet en plusieurs régions. Par exemple, dans la figure 2.2, il n'est pas possible de mélanger les parties blanches et noires du pingouin pour obtenir un objet pingouin. Une partie du ciel ou d'un champ peut être séparée en plusieurs régions. Cependant, les régions obtenues à partir de segmentation sur des images décrites par des traits visuels de bas niveaux ne correspondent pas souvent à des objets sémantiques. Les quatre algorithmes de segmentation comparés dans [Barnard et al., 2003a] sont le segmenteur par Expectation-Maximization (EM) de BLOBWORLD [Carson et al., 2002], l'algorithme normalized cuts [Shi & Malik, 2000], et l'algorithme mean shift proposé dans [Comaniciu & Meer, 2002]. Les résultats d'auto-annotation (utilisant un modèle générique similaire à ceux décrit dans la partie 4.3 page de cette thèse) montrent que l'algorithme normalized cuts donne de meilleurs résultats que mean shift et que le segmenteur de BLOBWORLD. C'est aussi la conclusion donnée dans [Datta et al., 2005]. C'est pourquoi [Barnard et al., 2003a] propose d'associer les régions obtenues par segmentation bas niveau avec les mots prédits afin de faire une segmentation prenant en compte des traits bas niveaux et de haut niveaux. Pour cela, il regarde les probabilités a posteriori des mots dans les régions adjacentes : plus la valeur du produit scalaire des deux probabilités de régions adjacentes est grande plus il y a de chance de fusion des deux régions. La comparaison des fusions avec celles réalisées par des êtres humains montrent que cette fusion permet dans une certaine mesure de créer des segmentations plus pertinentes.
Il existe également des approches par segmentation où les régions d'images sont déterminées a priori. Elles supposent par exemple que l'objet intéressant est présent au centre de l'image ou au contraire impose une grille où toutes les régions de l'image ont la même aire. Pour une recherche sémantique d'images, ce type de grille ne nous parait pas être intéressante, car plusieurs objets peuvent se retrouver dans la même région. De plus, les descripteurs de formes et de textures ne peuvent pas être utilisés.
Trois types d'approche pour l'extraction de points d'intérêt :
Pour rechercher les images les plus similaires à une image-exemple ou pour les regrouper (étapes (13) et (14) du schéma page ), il faut pouvoir mesurer la similarité (ou la dissimilarité) des images. Idéalement, les mesures doivent être capable de mesurer la similarité sémantique de deux images, dans la pratique elles ne sont capables que de mesurer la similarité visuelle. Cependant, beaucoup de travaux essayent de s'inspirer du système visuel humain pour proposer des mesures plus efficaces.
Nous allons décrire maintenant des mesures de similarité dans le cadre de la recherche d'images similaires. Ces mesures sont également utilisables pour la recherche de régions similaires, mais aussi dans le cas de la classification supervisée ou non-supervisée d'images (ou de données au sens général). D'ailleurs, d'après [Bisson, 2000], «tout système ayant pour but d'analyser ou d'organiser automatiquement un ensemble de données ou de connaissances doit utiliser, sous une forme ou une autre, un opérateur de similarité dont le but est d'établir les ressemblances ou les relations qui existent entre les informations manipulées».
Il existe un grand nombre de mesures de similarité. Certaines sont des distances, c'est-à-dire des mesures qui ont les propriétés de non-négativité, réflexivité, symétrie et qui respectent l'inégalité triangulaire. Certaines mesures sont spécifiques aux histogrammes ou aux distributions. Dans [Puzicha et al., 1999], une étude comparative de 9 mesures est proposée. Nous donnons ci-après quelques unes des mesures classiques.
(2) |
L'intersection d'histogrammes [Swain & Ballard, 1991] est définie ainsi :
(3) |
La distance entre histogrammes cumulés [Stricker & Orengo, 1995] consiste à calculer la distance entre les histogrammes cumulés dont les composantes sont définies par et . Cette approche est plus robuste que la distance sur les histogrammes classiques [Swain & Ballard, 1991], car elle est moins sensible aux changements (par exemple, aux changements de couleurs), mais elle suppose un ordre sur les composantes des histogrammes, ce qui n'est pas le cas des histogrammes de couleurs.
(4) |
Le test statistique du (chi-square) permet de décider si deux vecteurs et sont engendrés par la même distribution. La version symétrique du test est :
(5) |
La divergence de Kullback-Leibler (noté ) exprime l'entropie relative de la distribution par rapport à la distribution :
(6) |
(7) |
Nous donnons sa définition dans le cas où l'on souhaite calculer la distance entre deux ensembles de distributions. Soit et deux ensembles de distributions où chaque ième distributions est associé à un poids , alors la distance EMD est définie par :
(8) |
EMD peut travailler sur des histogrammes et n'a donc pas besoin qu'une quantification des vecteurs soit effectuée. Cette mesure est intéressante pour calculer la distance entre deux images segmentées où chaque blob serait représenté par une distribution visuelle. Cependant, EMD est très coûteuse au niveau du temps de calcul. Une démonstration théorique de la raison pour laquelle EMD donne de meilleurs résultats que la distance quadratique est proposée dans [Yamane, 2004].
Nous avons présenté les mesures de similarité les plus courantes. Cependant, lorsque l'on travaille sur des espaces de couleurs, certaines de ces mesures rencontrent certaines difficultés. L'inconvénient de la distance euclidienne est que certains points qui sont visuellement proches peuvent être aussi distants que des points visuellement éloignés. L'inconvénient de la distance quadratique est que des vecteurs visuellement différents peuvent être similaires.
La plupart de ces mesures sont coûteuses en temps de calcul et sont de plus sensibles à la malédiction de la dimension. Pour remédier au premier problème, des techniques issues des bases de données ont été proposées, nous verrons quelques unes de ces techniques dans la partie suivante. En ce qui concerne le problème de la malédiction de la dimension, il existe des techniques de réductions de dimensions qui permettent d'appréhender cette difficulté. Nous en décrirons quelques unes dans la partie 3.2 page .
Nous venons de décrire qu'il existe des mesures pour calculer la similarité entre les descripteurs visuels de deux images. Cependant, comment déterminer quelles sont les images les plus similaires à l'image requête ? Pour cela, les systèmes de recherche d'images utilisent généralement un algorithme de recherche des plus proches voisins. La recherche du plus proche voisin (nearest neighbor) est définie ainsi dans [Beyer et al., 1999] : «Given a collection of data points and a query point in an m-dimensional metric space, find the data point that is closest to the query point». Lorsque la base d'images est très grande, cette recherche peut être très coûteuse, car elle nécessite de calculer la similarité entre la requête et tous les vecteurs de la bases. C'est pourquoi afin d'accélérer la recherche des plus proches voisins, on utilise des index multidimensionnels (étape (13) sur le schéma page ) qui permettent un accès plus rapide à certaines données [Berrani et al., 2002]. Le principe est de structurer les données similaires pour accélérer les recherches [Böhm et al., 2001]. Les données aux caractéristiques similaires sont regroupées dans des clusters que nous appellerons cellules. La recherche des plus proches voisins s'effectue en deux étapes :
La technique des PYRAMID-TREES [Berchtold et al.,
1998] permet
de partitionner l'espace en cellules dont le nombre croit de manière linéaire
(et non pas exponentiel) avec le nombre de dimensions.
Si l'on suppose que les données sont contenues dans un hyperrectangle,
le principe des PYRAMID-TREES est
de partitionner l'espace en
pyramides où chacun des sommets des pyramides
est le même point central de l'hyperrectangle (ou bien le centre de gravité des données),
et chacune des bases de la pyramide
est un des cotés de l'hyperrectangle.
Puis chaque pyramide est découpé en tranches parallèles à la base.
Un point de l'espace est codé par le numéro de la pyramide et la distance à son sommet,
ces deux nombres sont ensuite codés par un seul nombre réel.
Ce partitionnement permet d'obtenir une correspondance entre un espace
-dimensionnel
et un espace à une seule dimension !
Enfin, les valeurs sont gérées par un
Une autre technique intéressante est le VA-FILE(Vector Approximation File) [Weber et al., 1998].
Le VA-FILE propose de partitionner l'espace en
hyperrectangles (cellules).
Pour cela, chaque dimension
est séparée en
segments où
est le nombre de bits nécessaires pour coder le nombre de segments de la dimension
.
Chaque vecteur est alors codé (on dit aussi approximé ou compressé) par une séquence de bits de longueur
(
(voir figures 2.3(a) et 2.3(b)).
Pour stocker les données deux fichiers sont utilisés : l'un stocke les vecteurs, l'autre
les vecteurs approximés (d'où le nom de VA-FILE).
Pour rechercher les vecteurs les plus proches, il suffit de déterminer
les cellules les plus proches (phase de filtrage), puis de les parcourir de manière séquentielle
afin de trouver les vecteurs pertinents.
Le bouclage de pertinence (relevance feedback) a d'abord été utilisé sur les documents
textuels [Salton, 1968]. Il est actuellement très utilisé dans le domaine de la recherche
d'images par le contenu, car il permet à l'utilisateur de raffiner sa requête en fournissant au système
plusieurs exemples et contre-exemples de ce qu'il souhaite obtenir.
Le bouclage de pertinence suppose que le jugement de
l'utilisateur est plus pertinent que le jugement du système.
Cette technique est donc un moyen d'apporter de la sémantique à la recherche d'images.
Cependant, elle n'est pas automatique, et nécessite que l'utilisateur indique au système quelles images l'intéressent.
Un bon système de bouclage de pertinence est donc un système qui propose à l'utilisateur
les images qu'il recherche en peu de phases de bouclage.
Un système classique de bouclage de pertinence comporte deux composants : un système de sélection et un système d'apprentissage.
Pour rechercher les images, un utilisateur réalise d'abord une première requête.
Le système lui renvoie des premiers résultats.
Puis parmi les résultats retournés, l'utilisateur sélectionne certains exemples comme exemples pertinents et d'autres
comme non pertinents. Le système prend alors en compte la sélection de l'utilisateur pour réaliser
un apprentissage dit «actif» (active learning) et retourner des résultats plus
pertinents. L'utilisateur peut alors sélectionner d'autres exemples et réitérer le processus
jusqu'à ce qu'il obtienne des résultats satisfaisants ou bien jusqu'à ce que les résultats fournis se stabilisent.
Un état de l'art des techniques de bouclage de pertinence pour la recherche d'images
peut être trouvé dans [Zhou & Huang, 2003,Crucianu et al., 2004].
Dans [Zhang et al., 2005], le bouclage de pertinence est utilisé dans
un système de recherche d'images basé sur le texte. Les résultats montrent que,
contrairement à ce que l'on aurait pu penser, utiliser le bouclage de pertinence dans ce cas précis
ne permet pas d'améliorer les résultats, car les
mots choisis par l'utilisateur sont de moins en moins pertinents.
Dans [Ferecatu et al., 2005,Ferecatu, 2005], le bouclage de pertinence est utilisé sur des descripteurs visuels
et textuels. Pour remédier au problème du choix des mots, l'information hiérarchique
de WordNet [Fellbaum, 1998] est utilisée.
Dans [Debanne & Mulhem, 2004], le bouclage de pertinence est utilisé sur une représentation symbolique des images.
D'autres exemples intéressants d'apprentissage actif peuvent être trouvés dans [Gosselin & Cord, 2004,Jin et al., 2004,Ferecatu et al., 2005]. Nous verrons dans la partie 2.3 quelques systèmes de recherche d'images qui utilisent le bouclage de pertinence (BP).
Nous venons de décrire les principales caractéristiques des systèmes de recherche d'images.
Nous allons maintenant décrire quelques systèmes de recherche d'images
(voir tableau 2.1). Nous avons choisi ces systèmes d'abord en fonction de leur popularité, puis en fonction
de leur capacité à combiner texte et images. Bien entendu il existe de très nombreux autres systèmes,
mais nous ne pouvons pas tous les citer.
Les systèmes sont ordonnés en fonction
de la date du premier article conséquent parlant de ce système. Cette date ne traduit
pas l'année du début du projet (en général, elle se situe deux ou trois années avant),
mais elle donne une idée de l'ordre dans lequel les systèmes ont été développés.
Cet ordre est important, car les anciens systèmes informatiques n'ont pas les mêmes capacités
en calcul et en mémoire que les systèmes actuels.
Avant de rentrer dans le détail de quelques uns de ces systèmes,
notons que certains sont des systèmes dit «académiques»,
que d'autres sont ou sont devenus des systèmes commerciaux (QBIC, IMAGESEEKER,
VIRAGE [Bach et al., 1996]...), que d'autres encore peuvent être vus comme des systèmes proposant
des outils d'extraction et de manipulation d'informations visuelles (GIFT, PICSOM, PHOTOBOOK...).
Notons aussi que nous nous intéresserons surtout à savoir s'ils utilisent
des informations textuelles, et si oui, comment ils les utilisent.
De plus, nous indiquons dans le tableau 2.1 si le système propose une recherche et une indexation textuelle
(colonne W), si le système combine les informations textuelles et visuelles (colonne &),
et s'il utilise le bouclage de pertinence (colonne BP).
Pour remplir les colonnes, nous avons utilisé les informations dans les articles cités en référence,
il se peut que dans des travaux ultérieurs certaines fonctions aient été ajoutées.
Le système CHABOT [Ogle & Stonebraker, 1995] propose de stocker les histogrammes de couleur et le texte associé
dans une base de données relationnelle. Il permet de réaliser des recherches telles que : «rechercher
des images un peu rouges réalisées au bord du lac Tahoe». Ces recherches sont exprimées sous la forme de requêtes dans
la base relationnelle. Il ne fusionne donc pas réellement les informations textuelles et visuelles.
Le système PICTION [Srihari, 1995,Srihari & Burhans, 1994] semble être le premier système
à vraiment proposer de combiner texte et information visuelle. Le texte est extrait de la légende associée
aux images d'articles de presse.
Une hiérarchie visuelle combinant à la fois des informations de structures
textuelles extraites de WordNet [Fellbaum, 1998] et à la fois des informations de couleur, de texture et de forme
est également proposée.
Le système WEBSEER [Frankel et al., 1996] est un système construit pour rechercher des images sur le web.
Les images sont classées en deux classes «photographies» et «dessins»
à l'aide d'arbres de décision
sur les descripteurs de couleur.
Le système utilise le texte des pages web afin d'annoter automatiquement les images.
Des méta-données contenues dans l'en-tête des images telles que le type de fichier, la date, la taille de l'image...
sont également prises en compte.
Ce système permet d'effectuer des recherches du type : «rechercher des photographies de portrait de Rebecca De Mornay
ayant telles caractéristiques de couleur». Les informations visuelles et les informations textuelles
ne sont donc pas vraiment combinées.
Le système VISUALSEEK [Smith & Chang, 1996] a la particularité de rechercher des régions d'intérêt,
et de prendre en compte leurs positions ainsi que leur taille lors des requêtes.
Il n'utilise pas d'information textuelle.
PHOTOBOOK [Pentland et al., 1996] recherche les images en comparant leur descripteurs spécialement
projetés dans un espace adapté au type de recherche (reconnaissance de visages, de formes, de textures...) effectuée.
Il permet de faire des recherches du type : «montre moi des images qui ont la même apparence que cette image».
Dans la version de l'article [Pentland et al., 1996], le système PHOTOBOOK propose d'utiliser le texte associé
aux images pour permettre des requêtes du type : «montre moi des images qui sont annotées de façons similaires à cette image,
mais prise à Boston». Les informations visuelles et les informations textuelles
ne sont donc pas vraiment combinées.
Cependant, PHOTOBOOK propose un module appelée FOUREYES [Minka & Picard, 1996]
qui est capable d'apprendre des concepts au fur et à mesure de l'interaction avec l'utilisateur.
Les images sont segmentées en
blocs.
Avant l'intervention de l'utilisateur, le système précalcule des similarités entre blocs d'images et les regroupe.
Puis l'utilisateur annote certains des blocs avec des mots tels que building.
Cette technique est très coûteuse car elle nécessite l'annotation manuelle de
régions d'images.
Le système MARS (Multimedia Analysis and Retrieval System) [Rui, 1997]
est un des premiers systèmes de recherche d'images par le contenu à utiliser le bouclage de pertinence.
Les images sont segmentées en blocs par une grille
de
. De chaque bloc, sont ensuite extraits des descripteurs de couleur et de texture (ondelettes).
Le système propose de retrouver et d'ordonner les résultats à l'aide d'un modèle booléen.
Il n'utilise pas d'information textuelle.
Le système IMAGEROVER [Sclaroff et al., 1997,La Cascia et al., 1998] a pour objectif de
combiner les informations textuelles d'une page web avec le contenu visuel des images.
Dans ce système, chaque image est indexée par un vecteur global
concaténant les vecteurs visuels (réduits par ACP) et textuels (réduits dans l'espace latent).
Ce système sera décrit plus en détail dans la partie 4.2.3 page .
Le système NETRA [Ma & Manjunath, 1999] utilise des descripteurs de couleur, de texture,
de forme, une segmentation en régions et les relations spatiales entre ces régions.
La localisation spatiale d'une région est mesurée par deux rectangles (intérieur et
extérieur). Il n'utilise pas d'information textuelle.
Le système BLOBWORLD [Carson et al., 1999] propose de segmenter les images
en regroupant les pixels qui ont des couleurs et des textures similaires à l'aide d'un algorithme de clustering
basé sur l'estimation de distributions gaussiennes par EM (voir annexe B.2.4 page ).
Ce type de segmentation doit permettre de retrouver plus efficacement les objets dans les images.
Des expériences sont réalisées sur le corpus Corel et montrent que retrouver
par blobs similaires est plus efficace que retrouver
les images ayant des histogrammes de couleurs et de textures similaires.
Au niveau de l'interface, BLOBWORLD permet à l'utilisateur de sélectionner
la région qui l'intéresse, et de retrouver les images qui possèdent des blobs similaires.
L'information textuelle ajoutée aux images de Corel est utilisée pour vérifier les
catégories sémantiques lors des tests et non pas pour améliorer l'efficacité du système.
Le système PICHUNTER [Cox et al., 2000] est un système
qui utilise les probabilités bayésiennes pour prédire quel est l'objectif des utilisateurs
en fonction de leurs actions. Pour la phase de bouclage de pertinence,
l'algorithme essaye de maximiser l'information (au sens de l'entropie) obtenu par l'utilisateur
à chaque itération. Les résultats obtenus sont comparés à ceux obtenus par des expériences
de psychovision. Le système utilise des annotations «cachées» pour améliorer les résultats.
Le principe est que le texte associé aux images est utilisé pour améliorer les résultats renvoyés,
mais il n'est pas proposé à l'utilisateur de faire des recherches textuelles.
Dans SIMPLICITY (Semantics-sensitive Integrated Matching for Picture LIbraries) [Wang et al., 2001], la requête est un ensemble de régions
et la distance entre deux ensembles est la somme des
distances entre les régions appariées, pondérées par un
score de satisfaction attribué à l'appariement. La distance
ne tient pas compte de l'information spatiale, mais la
méthode permet la mise en correspondance d'une région
d'une image à plusieurs régions de l'autre image.
Ce système n'utilise pas d'information textuelle.
Par contre, il possède un module appelé A-LIP (voir ci-après) qui
permet de faire de l'auto-annotation d'images.
Le système IKONA [Boujemaa et al., 2001] fait suite au système SURFIMAGE [Nastar et al., 1998]
du groupe IMEDIA d'unité INRIA-Rocquencourt. Ce système propose de rechercher des images
par similarité visuelle (couleur, texture, forme). Il propose également des recherches par sélection de régions,
et d'utiliser le bouclage de pertinence.
Dans [Boujemaa et al., 2001], la combinaison avec le texte est mis dans les perspectives d'évolution du système.
Cela a notamment été le cas dans la thèse de Marin Ferecatu [Ferecatu, 2005].
Il part du principe que si une image a été annotée par des mots-clés, le système
peut utiliser ces mots-clés pour une recherche plus rapide.
Cependant, comme les mots-clés peuvent être ambigus, ils proposent de propager les mots-clés
à l'aide d'informations entre les termes extraites de WordNet [Fellbaum, 1998].
Plusieurs combinaisons des informations textuelles et visuelles sont comparées
en association à des phases de bouclages de pertinence.
Le système PICSOM [Laaksonen et al., 2002] utilise des cartes auto-organisatrices
(Self-Organising Map) [Kohonen et al., 2000] pour classer les images. Il fournit
en plus un grand nombre d'outils pour la classification et la recherche d'images par le contenu.
Ce système n'a donc pas pour vocation de combiner information textuelle et visuelle.
Notons cependant que dans [Viitaniemi & Laaksonen, 2005], ce système est utilisé pour l'auto-annotation
d'images. Pour cela, pour chaque mot, le système construit deux ensembles d'images, les images annotées
par ce mot et les autres, et les utilisent pour apprendre un classifieur. Les images de test sont ensuite annotées
en fonction de leur classement dans la classe pertinent ou non pertinent pour un mot donné.
Le système A-LIP (Automatic Linguistic Indexing of Pictures) [Li & Wang, 2003]
est un module du système SIMPLICITY.
Il propose d'annoter les images à l'aide de modèles de Markov cachés.
A partir des descripteurs des images d'apprentissage correspondant à un certain concept, le système construit
des modèles des images sur plusieurs niveaux de résolution. Les modèles ainsi construits pour chaque concept
forment un dictionnaire de concepts. Lorsqu'une nouvelle image doit être annotée, la vraisemblance
entre les descripteurs (multirésolution) de l'image et le modèle est calculée.
Les mots associés aux concepts les plus significatifs sont associés à l'image pour permettre
une recherche textuelle ultérieure.
Le système GIFT (GNU Image-Finding Tool)anciennement appelé VIPER est un système
de recherche d'images par le contenu libre. Il propose un ensemble d'outils
d'extraction de descripteurs visuels des images. Il n'a pas été conçu pour utiliser l'information textuelle.
Cependant, comme ce système est un système où chacun peut proposer des contributions, il n'est pas
exclu de rajouter des capacités de gestion des informations textuelles.
Le système IMAGESEEKER est un système commercial qui
permet de faire des recherches textuelles et visuelles. Cependant, il semble que les informations
textuelles et visuelles ne soient pas vraiment combinées pour améliorer la pertinence des indexations.
Il y a finalement peu de systèmes qui combinent vraiment les informations
textuelles et visuelles (PICTION, FOUREYES, IMAGEROVER, PICHUNTER, A-LIP).
De plus, la plupart sont des modèles d'auto-annotation d'images, et non pas des systèmes de recherche d'images complets.
Nous parlerons de l'auto-annotation dans le chapitre 4.
Le système PICHUNTER propose une combinaison originale des informations textuelles
et visuelles, car il utilise le texte associé aux images pour améliorer les similarités
entre les images, mais l'utilisateur ne peut pas effectuer de recherche textuelle et ne sait pas
que le système utilise ce type d'information.
Il y a que peu de systèmes complets qui combinent vraiment les informations
textuelles et visuelles, mais il existe cependant quelques travaux prometteurs parmi
lesquels [La Cascia et al., 1998,Haddad & Mulhem, 2001,Zhao & Grosky, 2002,Adams et al., 2003,Omhover & Detyniecki, 2004,Belkhatir et al., 2005].
Nous en verrons d'autres dans le chapitre 4.
Un état de l'art des techniques de recherche d'images par le contenu peut être trouvé dans [Datta et al., 2005,Smeulders et al., 2000,Goodrum, 2000,Eakins, 2002].
Les systèmes textuels de recherche d'images ne sont pas efficaces, car ils effectuent
leur recherche sur le texte associé aux images, qui n'a souvent que peu de rapport avec
le contenu visuel de l'image.
D'un autre coté, les systèmes de recherche d'images par le contenu doivent résoudre de nombreuses difficultés
afin d'être efficaces :
Une question intéressante est de savoir comment l'être humain est capable de discerner un objet dans
une image. Quelles sont les caractéristiques qui lui permettent de discerner que deux images visuellement très différentes
concernent le même concept, et cela simplement en regardant l'image ?
Pour répondre à ce genre de questions, on utilise des méthodes inspirées par l'être humain,
comme les techniques d'apprentissage.
Nous décrirons dans le chapitre 3 quelques techniques d'apprentissage.
5 Bouclage de pertinence
3 Systèmes de recherche d'images combinant texte et images
Systèmes
V
W
&
BP
Principales particularités
QBIC
O
O
requête par image-exemple/par croquis/directe
[Niblack et al., 1993]
CHABOT
O
O
SGBD relationnel
[Ogle & Stonebraker, 1995]
PICTION
O
O
O
hiérarchie visuelle utilisant Wordnet
[Srihari, 1995]
WEBSEER
O
O
web, texte et méta données, détection de faces
[Frankel et al., 1996]
VISUALSEEK
O
régions d'intérêt, relation spatiale
[Smith & Chang, 1996]
PHOTOBOOK
O
O
descripteurs pré-calculés, navigation
[Pentland et al., 1996]
FOUREYES
O
O
O
O
annotation d'images manuelle, combinaison de modèles
[Minka & Picard, 1996]
MARS
O
O
modèle booléen
[Rui, 1997]
IMAGEROVER
O
O
O
O
web, ACP, LSA
[Sclaroff et al., 1997]
NETRA
O
information spatiale
[Ma & Manjunath, 1999]
BLOBWORLD
O
segmentation en régions homogènes couleur/texture par EM
[Carson et al., 1999]
PICHUNTER
O
O
O
système bayésien
[Cox et al., 2000]
SIMPLICITY
O
segmentation
[Wang et al., 2001]
IKONA
O
O
segmentation
[Boujemaa et al., 2001]
PICSOM
O
O
cartes auto-organisatrices
[Laaksonen et al., 2002]
A-LIP
O
O
O
auto-annotation par modèle de Markov caché (2D-MHMM)
[Li & Wang, 2003]
GIFT
O
O
système libre proposant des outils de gestion du contenu
gnu.org/software/gift
IMAGESEEKER
O
O
système commercial
ltutech.com
1 Quelques systèmes de recherche d'images
L'un des premiers systèmes de recherche d'image par le contenu visuel est le système
QBIC (Query By Image Content) [Niblack et al., 1993,Flickner et al., 1995]. QBIC utilise des traits de couleur, de texture et de forme.
Il permet des requêtes par image-exemple, directes ou par croquis. Il permet également de faire de la navigation
avec bouclage de pertinence (BP).
Le texte associé aux images, comme le nom de l'auteur ou du média, est seulement utilisé pour faire
un filtrage des résultats (par exemple, seules les images associées à tel auteur sont affichées),
et non pas pour améliorer sémantiquement les résultats.
2 Remarques
Si nous observons l'évolution des systèmes de recherche d'images par le contenu, nous remarquons
que ces systèmes sont de plus en plus complexes.
Les premiers systèmes proposaient de rechercher des images visuellement similaires
en réalisant une mesure entre les histogrammes de couleurs des images entières, puis des régions d'images.
Maintenant, les améliorations sont obtenues en utilisant des systèmes d'apprentissage de plus en plus complexes
(systèmes bayésiens, cartes auto-organisatrices, modèles de Markov cachés...) qui sont nécessaires pour fusionner
les différentes informations visuelles et/ou textuelles.
Il est assez surprenant de constater que depuis 2003, il n'y a que peu de nouveaux systèmes complets de recherche d'images
par le contenu. La plupart des travaux proposent d'améliorer une partie d'un système,
mais pas un nouveau type de système.
4 Discussion
Les systèmes par le contenu visuel sont de plus en plus performants
pour résoudre chacune de ces difficultés, et donc de plus en plus performants pour
retrouver les images les plus similaires visuellement. De plus, le bouclage
de pertinence permet de rajouter dans une certaine mesure de la sémantique au recherche d'images par le contenu visuel.
Cependant, ils ne sont pas beaucoup plus efficaces en ce qui concerne la recherche
automatique d'images sémantiquement similaires. La raison en est que deux images sémantiquement
similaires ne sont pas forcément visuellement similaires
(voir par exemple, les images (b) et (c) de la figure 1.1 page ).
En effet, en fonction du concept recherché, il existe des descripteurs visuels informatifs
et d'autres qui n'apportent aucune information, voir même du bruit.
Par exemple, pour le concept maison, la couleur n'est pas discriminante
car les maisons peuvent être de différentes couleurs. Elle peut même apporter du bruit, car d'après
les descripteurs de couleurs l'image du tigre (a) et de l'une des maisons (b) sont similaires.
Il est donc préférable d'utiliser pour rechercher une maison un autre descripteur visuel que la couleur.
Par contre, la couleur peut être discriminante pour le concept de coucher de soleil,
car les couchers de soleil sont souvent rouge-orangé, et rarement d'une autre couleur.
Si l'on recherche des images de couchers de soleil, il est préférable de prendre en compte
les descripteurs de couleurs.
Nous voyons apparaître une question importante : quels sont les descripteurs
visuels qui permettent de mieux discriminer un certain concept ?
Les systèmes qui travaillent sur des bases d'images généralistes uniquement à partir
du contenu visuel ne peuvent y répondre, car ils ne connaissent pas le concept que l'utilisateur recherche.
Par contre, lorsqu'il travaille avec des systèmes combinant textes et images,
l'utilisateur peut rentrer le mot-clé correspondant à ce qu'il recherche
en plus d'une image requête. Dans le chapitre 7, nous proposons
pour surmonter cette difficulté d'utiliser deux techniques classiques : l'analyse linéaire discriminante (LDA) et
la diversité marginale maximale (MMD) pour rechercher automatiquement quels
descripteurs visuels sont vraiment pertinents pour un concept donné.
Next: 3 Apprentissage automatique et
Up: 1 État de l'art
Previous: 1 État de l'art
Contents
Index
Tollari Sabrina
2008-01-08