next up previous contents index
Next: 3 Apprentissage automatique et Up: 1 État de l'art Previous: 1 État de l'art   Contents   Index

Subsections


2 Indexation et recherche d'images

Comme nous l'avons vu dans l'introduction, les systèmes classiques de recherches d'images peuvent être classés en deux catégories :

Ils possèdent tous les deux une phase d'indexation et une phase de recherche. Le terme «indexation» est parfois ambigu, car il est utilisé pour deux problèmes distincts : L'indexation a donc pour but d'extraire et de représenter le sens d'un document de manière à ce qu'il puisse être retrouvé par l'utilisateur. Nous utiliserons indifféremment les deux emplois de ce terme.

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.

1 Indexation et recherche textuelle d'images


1 Indexation textuelle manuelle

L'indexation textuelle manuelle d'images est le plus souvent réalisée par un documentaliste appelé iconographe. Son rôle est de classer et d'indexer les images en les associant à des catégories et à des groupes de mots, souvent extraits d'un thésaurus, permettant de retrouver facilement les images. Son travail est très utile pour les agences de presse, les centres de documentation, les musées... Du fait de l'accroissement du nombre de photographies personnelles, ce travail est aussi souvent réalisé par les utilisateurs qui souhaitent décrire leurs images personnelles.

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.


2 Indexation textuelle 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.

3 Modèles classiques de recherche textuelle

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).


1 Modèle booléen

Dans le modèle booléen, un document $ d_{i}$ est représenté par une conjonction de termes indépendants que l'on représente sous la forme d'un ensemble : $ d_{i}=\{w_1,w_2,\cdots,w_{n_{\mathcal{W}^{d}}}\}$ sans pondération. La requête $ q$ est une expression logique composée de termes connectés par les opérateurs logiques ET, OU et NON. Un document sera jugé pertinent par le système si l'expression logique de la requête est satisfaite par ce document. Ce modèle ne permet pas de retrouver des documents qui ne correspondent que partiellement à la requête.


2 Modèle vectoriel

Dans le modèle vectoriel, un document est représenté sous la forme d'un vecteur à $ n_{\mathcal{W}}$ dimensions : $ d_{i}=
(w_{i,1},w_{i,2},\cdots,w_{i,n_{\mathcal{W}}})$ où chaque $ w_{i,j}$ est la pondération associée au terme $ w_{j}$ dans le document $ d_{i}$ . Ce modèle suppose que les vecteurs sont des points dans un espace où les termes forment une base orthogonale. Les termes sont supposés indépendants. La requête est exprimée selon le même formalisme : $ q=
(w_{q,1},w_{q,2},\cdots,w_{q,j})$ . Pour évaluer la pertinence d'un document par rapport à une requête, le système calcule une valeur de similarité entre les deux vecteurs $ d_{i}$ et $ q$ . Les mesures de similarité classiques sont le cosinus, la formule de Dice et la formule de Jaccard. Les pondérations $ w_{i,j}$ tiennent compte de la fréquence du terme dans le document (term frequency, tf), du nombre de documents dans lesquels apparaît le terme (document frequency, df), de la longueur du document, et de l'apparition des termes d'indexation dans les parties logiques du document, comme le titre, le résumé...


3 Modèle probabiliste

Le modèle probabiliste [Robertson & Jones, 1976] essaye d'estimer la probabilité qu'un utilisateur a de trouver un document $ d$ pertinent. Ce modèle suppose qu'il y a un sous-ensemble  $ \mathcal{R}$ de documents que l'utilisateur veut retrouver parmi ceux disponibles, les autres documents $ \overline{\mathcal{R}}$ étant considérés non pertinents. Un document $ d$ et une requête $ q$ sont représentés par un vecteur comme dans le modèle vectoriel, mais les poids sont binaires (le mot apparaît ou non dans le document). Si $ P(\mathcal{R}\vert d)$ est la probabilité que le document $ d$ soit pertinent pour la requête $ q$ et si $ P(\overline{\mathcal{R}}\vert d)$ est la probabilité que le document $ d$ ne soit pas pertinent pour la requête $ q$ , alors la similarité entre le document $ d$ et la requête $ q$ est :

$\displaystyle sim(d,q)=\frac{P(\mathcal{R}\vert d)}{P(\overline{\mathcal{R}}\vert d)}.$ (1)

Ce modèle est difficile à mettre en oeuvre en raison du calcul de probabilité initiale.

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].

4 Avantages et limites

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.

2 Indexation et recherche d'images par le contenu visuel

1 Les types de systèmes

Les systèmes de recherche d'images par le contenu visuel peuvent être construits avec différents objectifs en vue. Certains systèmes cherchent à reconnaître un objet en particulier (un visage, un type d'objet...). On parle alors de reconnaissances de formes (pattern matching) ou d'objets (object recognition). Parmi ceux-ci, certains systèmes sont spécialisés pour travailler sur des images médicales ou des photos satellites. D'autres cherchent à classer les images en fonction du type de scènes qu'elles représentent (naturel/artificiel, intérieur/extérieur...). On parle alors de reconnaissance de scènes ou de classification de scènes. Une troisième catégorie de systèmes cherche à reconnaître les images similaires à une image requête. Les deux premiers types de systèmes nécessitent l'emploi de techniques et de descripteurs spécifiques à l'objet ou à la scène recherché. Par contre, la troisième catégorie de systèmes traite des images généralistes et cherche à obtenir de bonnes performances en moyenne sur toutes les images. Dans le cadre de cette thèse, nous nous intéressons surtout au troisième type de systèmes.

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.

2 Les bases d'images

On peut distinguer deux catégories de bases d'images : Les stratégies de recherche d'images pour ces deux catégories de base sont très différentes. Pour la première, on connaît a priori le type d'images que l'on peut y rencontrer, ainsi que le type de recherche que l'on va y mener. Par exemple, rechercher une personne parmi d'autres même si elle porte des lunettes, un chapeau ou non. Cette connaissance a priori permet de développer des techniques d'indexation et de recherche très efficaces. Pour la seconde catégorie, par contre, on ne sait pas ce que contiennent les images, et du fait du fossé sémantique, on ne sait pas sémantiquement ce que recherche l'utilisateur. Dans cette thèse, nous nous intéressons uniquement aux bases d'images généralistes.

3 Types de requêtes visuelles

D'après [Cox et al., 2000], un utilisateur peut avoir différents objectifs lorsqu'il effectue une recherche d'images. Il peut rechercher :

Figure 2.1: Schéma d'un système classique de recherche d'images par le contenu visuel
\begin{figure}
\begin{center}
\centerline{\psfig{figure=partieA/imagesRI//schema_RI5.eps,width=11cm}} \end{center}
\end{figure}

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.

4 Extraction des informations visuelles

Les valeurs des pixels d'une image ou d'une région d'images ne peuvent pas être exploitées directement. C'est pourquoi on extrait à l'aide d'algorithmes plus ou moins complexes des descripteurs visuels afin d'obtenir une représentation plus facile à utiliser, et qui correspondent si possible au contenu sémantique. L'extraction des informations visuelles des images doit être effectuée aussi bien pour les images de la base que pour la requête. Elle est généralement constituée de trois étapes (voir schéma de la figure 2.1 page [*]) :

5 Histogrammes et quantification

Pour pouvoir comparer des descripteurs visuels, il faut prendre en compte le fait que les régions visuelles considérées n'ont pas forcément la même taille. Il faut donc que la représentation des descripteurs visuels obtenue soit :

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.


1 Descripteurs visuels

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.


1 Couleurs

La couleur est le descripteur visuel le plus employé, certainement car c'est le plus perceptuel. Les grands problèmes soulevés par le choix de bons descripteurs de couleurs sont l'identification de l'espace de couleur le plus discriminant, la prise en compte des problèmes d'invariance aux conditions d'illumination et de prise de vue, la combinaison avec des descripteurs complémentaires (textures, formes...). Il existe plusieurs espaces colorimétriques qui ont chacun certaines caractéristiques intéressantes.

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.


\begin{definition}[Espace perceptuellement uniforme]
Un espace colorimétrique es...
...ignée de la couleur $c_i$ que la couleur $c_2$.
\end{itemize}
\end{definition}

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.


2 Textures

Il n'existe pas de définition pertinente de la texture. Cependant, une définition de sens commun est la suivante : la texture est la répétition d'éléments de base construits à partir de pixels qui respectent un certain ordre. Le sable, l'eau, l'herbe, la peau sont autant d'exemples de textures. L'aléatoire joue un rôle particulier dans les textures. On peut distinguer deux types extrêmes de textures, entre lesquels se positionnent toutes les textures :

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).

3 Formes

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 :

Pour plus de détails concernant les descripteurs de formes, le lecteur peut se reporter à [Veltkamp & Hagedoorn, 2001,Bloch et al., 2004].

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.


4 Positions et relations spatiales

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.


2 Segmentation et points d'intérêt

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 :

1 Segmentation

Dans [Smeulders et al., 2000], il est affirmé que : «The theoretically best approach to a semantic interpretation of an image remains the use of a strong segmentation of the scene. Automatic strong segmentation is, however, hard to achieve[*]».

Figure 2.2: Exemple de segmentation par approche région. L'objet pingouin ne peut être représenté par une seule région d'images, car les parties blanches et noires ne peuvent être regroupées par un algorithme de segmentation.
\begin{figure}\centering
\psfig{figure=partieA/imagesRI//pinguin2.eps,width=3cm}\end{figure}

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.

2 Points d'intérêt

Les points d'intérêt d'une image sont les points qui seront trouvés similaires dans les images similaires. Une manière de les déterminer est de prendre en compte les zones où le signal change. Par exemple, les points d'intérêt peuvent être les coins, les jonctions en T ou les points de fortes variations de texture.

Trois types d'approche pour l'extraction de points d'intérêt :

Les approches intensité sont les plus utilisées, car elles sont indépendantes des contours et du type de points d'intérêt. On peut citer au moins deux avantages des points d'intérêt par rapport aux régions : ils ne nécessitent pas de chaînages pour détecter les contours des régions, et on peut les extraire efficacement de la plupart des images.


3 Mesures de similarité

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.

1 Distance euclidienne

Une distance classique est la $ L_{p}-norme$ (ou distance de Minkowski) :

$\displaystyle L_{p}-norme(\vec{x},\vec{y})=\big(\sum_{i=1}^{n}\vert x_{i}-y_{i}\vert^{p}\big)^{\frac{1}{p}}$ (2)

$ p$ est le paramètre de la norme. La $ L_{1}-norme$ est appelée distance de Manhattan ou distance City-Block. La $ L_{2}-norme$ est la distance euclidienne.


2 Distances entre histogrammes

Les techniques géométriques, telles que la distance euclidienne, peuvent être appliquées sur des histogrammes. Il existe cependant des mesures spécifiques aux histogrammes.

L'intersection d'histogrammes [Swain & Ballard, 1991] est définie ainsi :

$\displaystyle \delta_{Intersec}(\vec{h}_{x},\vec{h}_{y})=\frac{\sum_{i=1}^{n}\min(h_{x,i},h_{y,i})} {\sum_{i=1}^{n}h_{y,i}}$ (3)

Dans le cas où les histogrammes sont normalisés, cette mesure est équivalente à la $ L_{1}-norme$ . Ce n'est pas une distance, car elle ne respecte pas l'axiome de symétrie.

La distance entre histogrammes cumulés [Stricker & Orengo, 1995] consiste à calculer la distance $ L_{1}-norme$ entre les histogrammes cumulés dont les composantes sont définies par $ h'_{x,i}=\sum_{j=1}^{i}h_{x,j}$ et $ h'_{y,i}=\sum_{j=1}^{i}h_{y,j}$ . 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.

3 Distances quadratiques

L'inconvénient des mesures telles que la distance euclidienne ou l'intersection d'histogrammes est qu'elles comparent les composantes des vecteurs une par une, sans prendre en compte les autres composantes. Pour remédier à ce problème, on peut utiliser la distance quadratique [Hafner et al., 1995]. Elle est définie ainsi :

$\displaystyle \delta _{Q}(\vec{x},\vec{y})=\sqrt{(\vec{x}-\vec{y})A^{T}(\vec{x}-\vec{y})}.$ (4)

La matrice $ A$ permet de pondérer le poids des composantes voisines en fonction de leur distance à la composante considérée. Cependant, cette mesure a une complexité quadratique. Un cas particulier de distances quadratiques est la distance de Mahalanobis$ A$ correspond à la matrice de covariance des données d'apprentissage. Cette distance nécessite donc la connaissance d'un ensemble de données d'apprentissage. Lorsque $ A$ est la matrice identitaire alors $ \delta _{Q}$ est équivalente à la distance euclidienne.

4 Distances entre distributions

La similarité entre distributions consiste à déterminer si deux distributions peuvent être issues de la même distribution de probabilités.

Le test statistique du $ \chi ^{2}$ (chi-square) permet de décider si deux vecteurs $ \vec{x}$ et $ \vec{y}$ sont engendrés par la même distribution. La version symétrique du test est :

$\displaystyle \chi^{2}(\vec{x},\vec{y})=\sum_{i=1}^{n}\frac{(x_{i}-y_{i})^{2}}{x_{i}+y_{i}}$ (5)

C'est une des mesures de similarité parmi les plus rapides, elle donne de bons résultats sur les grands ensemble de données [Puzicha et al., 1999].

La divergence de Kullback-Leibler (noté  $ \mathrm{divKL}$ ) exprime l'entropie relative de la distribution $ \vec{x}$ par rapport à la distribution $ \vec{y}$  :

$\displaystyle \mathrm{divKL}(\vec{x},\vec{y})=\sum_{i=1}^{n}x_{i}\log_2\frac{x_{i}}{y_{i}}$ (6)

Cette mesure n'est pas une distance, car elle n'est pas symétrique $ \mathrm{divKL}(\vec{x},\vec{y})\not=\mathrm{divKL}(\vec{y},\vec{x})$ . Si l'on souhaite une distance, on peut utiliser la distance de Kullback-Leibler (notée  $ \mathrm{dKL}$ ) [Kullback & Leibler, 1951] définie par :

$\displaystyle \mathrm{dKL}(\vec{x},\vec{y})=\mathrm{divKL}(\vec{x},\vec{y})+\mathrm{divKL}(\vec{y},\vec{x}).$ (7)

En statistique bayésienne, la divergence de Kullback-Leibler peut être utilisée pour mesurer la «distance» entre la distribution a priori, et la distribution a posteriori.

5 Earth Mover's Distance (EMD)

La mesure Earth Mover's Distance (EMD) [Rubner et al., 1998] est basée sur la minimisation du coût nécessaire pour transformer une distribution en une autre distribution. Elle peut être appliquée pour calculer la similarité entre deux distributions ou entre deux ensembles de distributions. Elle porte ce nom car pour la comprendre on peut voir l'une des distributions comme une collection de planètes associées à leur masse et l'autre comme une collection de trous dans le même espace. C'est l'une des seules distances qui permet de travailler sur des histogrammes qui n'ont pas forcément le même nombre de bins.

Nous donnons sa définition dans le cas où l'on souhaite calculer la distance entre deux ensembles de distributions. Soit $ \mathcal{X}=\{(\vec{x}_{1},\omega_{x,1}),(\vec{x}_{2},\omega_{x,2}),\cdots,(\vec{x}_{n},\omega_{x,n})\}$ et $ \mathcal{Y}=\{(\vec{y}_{1},\omega_{y,1}),(\vec{y}_{2},\omega_{y,2}),\cdots,(\vec{y}_{m},\omega_{y,m})\}$ deux ensembles de distributions où chaque $ k$ ième distributions $ \vec{z}_{k}$ est associé à un poids $ \omega_{z,k}$ , alors la distance EMD est définie par :

$\displaystyle EMD(\mathcal{X},\mathcal{Y})= \frac{\sum_{i=1}^{n}\sum_{j=1}^{m}\delta (\vec{x}_{i},\vec{y}_{j})W_{i,j}} {\sum_{i=1}^{n}\sum_{j=1}^{m}W_{i,j}}$ (8)

$ \delta (\vec{x}_{i},\vec{y}_{j})$ est la distance (par exemple euclidienne) entre les distributions $ \vec{x}_{i}$ et $ \vec{y}_{j}$ , et $ W_{i,j}$ est le coût (appelé «flux») nécessaire pour se déplacer de la composante $ \vec{x}_{i}$ à la composante $ \vec{y}_{j}$ . La matrice $ W$ est le résultat de la minimisation de la fonction de coût $ C(\mathcal{X},\mathcal{Y},W)=\sum_{i=1}^{n}\sum_{j=1}^{m}\delta (\vec{x}_{i},\vec{y}_{j})W_{i,j}$ avec les contraintes suivantes $ \forall(i,j) W_{i,j}\geq 0$ , $ \forall i \sum_{i=1}^{n}W_{i,j}\leq\omega_{x,i}$ , $ \forall j \sum_{j=1}^{n}W_{i,j}\leq\omega_{y,j}$ et $ \sum_{i=1}^{n}\sum_{j=1}^{m}W_{i,j}
=\min\big(\sum_{i=1}^{n}W_{i,j},\sum_{j=1}^{m}W_{i,j}\big)$ .

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].

6 Discussion

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 [*].


4 Techniques d'indexation multidimensionnelle

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 :

Cette façon de procéder permet de réduire le nombre d'entrées-sorties et le nombre de calcul de distances à effectuer. Pour créer ces cellules, il existe deux types de stratégies : Les principes de création des cellules sont très proches des algorithmes de classification non-supervisée. Ainsi dans [Keim & Hinneburg, 1999], les auteurs considèrent les techniques d'index multidimensionnels comme des méthodes de classification non-supervisée.

1 Techniques basées sur le partitionnement des données

Ces techniques, souvent dérivées du R-TREE [Guttman, 1984], proposent de regrouper les vecteurs selon leur similarité dans l'espace. Chaque groupe de vecteurs est englobé dans une forme géométrique (hyperrectangle, hypersphère...) et regroupé dans un arbre dont les feuilles contiennent les données et les noeuds contiennent les formes englobantes. Pour la famille des R-TREES, les noeuds sont des hyperrectangles, appelés rectangles englobants minimaux (REM), qui correspondent aux plus petits hyperrectangles pouvant englober les données de niveau inférieur. Cependant, un des problèmes du stockage des données dans un hyperrectangle est que deux vecteurs appartenant à un même hyperrectangle peuvent avoir des caractéristiques très peu semblables. Pour rendre efficace les R-Trees, leurs dérivés ( MATHEND000#-TREE, MATHEND000#-TREE...) proposent différentes méthodes pour minimiser le volume de l'espace couvert par le REM, et le taux de chevauchement entre les entrées d'un même noeud. Il existe de nombreuses autres techniques basées sur le partitionnement des données (X-/SS-/SR-/TV-/M-TREE...) qui permettent d'accélérer la recherche des plus proches voisins, mais la plupart sont sensibles à la malédiction de la dimension.


2 Techniques basées sur le partitionnement de l'espace

Les techniques basées sur le partitionnement de l'espace sont plus simples à gérer que celles basées sur le partitionnement des données, et de plus aucun chevauchement n'existent entre les cellules. Le principe est de partitionner l'espace sans prendre en compte les données. Les cellules peuvent être gérées de deux manières différentes : Pour ces techniques, l'absence de chevauchement accroît les performances des algorithmes de recherche, mais si un vecteur requête est suffisamment proche de la frontière d'une région alors il est nécessaire de visiter les régions voisines. Or quand le nombre de dimensions est grand et selon la technique utilisée, le nombre de régions voisines peut être exponentiel. De plus, ces techniques indexent des espaces vides en données. La plupart des techniques de partitionnement de l'espace sont donc elles aussi sensibles à la malédiction de la dimension, mais de nouvelles techniques proposent des méthodes originales qui permettent de réduire les problèmes rencontres sur les espaces de grandes dimensions.

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 $ 2\times m$ 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 $ m$ -dimensionnel et un espace à une seule dimension ! Enfin, les valeurs sont gérées par un MATHEND000#-TREE. Cependant, cette technique ne permet pas de faire des recherches de plus proches voisins, mais elle permet de répondre à des requêtes par intervalle, car plusieurs vecteurs peuvent être codés par le même nombre réel. De plus, le risque que seules les tranches les plus basses des pyramides soient utilisées est fort, car, comme nous allons le voir dans la partie 3.2.1, en grande dimension, la probabilité qu'un vecteur se trouve près de la bordure d'un hypercube est très grande.

Figure 2.3: Exemple de codage par la technique VA-FILE
\begin{figure}\center
\subfigure[Vecteurs]{
\begin{tabular}{\vert c\vert c\vert}...
...icolumn{1}{c\vert}{}\\
\cline{2-5}
&00&01&10&11\\
\end{tabular}}\end{figure}

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 $ 2^\rho$ hyperrectangles (cellules). Pour cela, chaque dimension $ u$ est séparée en $ 2^{\rho_u}$ segments où $ \rho_u$ est le nombre de bits nécessaires pour coder le nombre de segments de la dimension $ u$ . Chaque vecteur est alors codé (on dit aussi approximé ou compressé) par une séquence de bits de longueur $ \rho$ ( $ \rho=\sum_{u=1}^{m}\rho_{u})$ (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.


5 Bouclage de pertinence

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).


3 Systèmes de recherche d'images combinant texte et images


Table 2.1: Résumé de quelques systèmes de recherche d'images par le contenu. Un «O» dans la colonne V signifie que le système utilise des descripteurs visuels pour la recherche et l'indexation. Un «O» dans la colonne W signifie que le système utilise des descripteurs textuels pour la recherche et l'indexation. Un «O» dans la colonne & indique que le système combine les deux informations. BP indique que le système permet d'utiliser le bouclage de pertinence.
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


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.

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.

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 $ 16\times16$ 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 $ 5\times5$ . 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.

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.

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].

4 Discussion

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 :

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é.

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.


next up previous contents index
Next: 3 Apprentissage automatique et Up: 1 État de l'art Previous: 1 État de l'art   Contents   Index
Tollari Sabrina 2008-01-08