Introduction

Un des problèmes rencontrés lors de la manipulation de grandes quantités d'images est la structuration, le stockage et la recherche d'informations. De ce fait en résulte un fort dynamisme de recherche dans le domaine de l'indexation multimédia durant cette dernière décennie, donnant naissance à de nombreuses méthodes d'indexation par le contenu, de recherche interactive et de navigation dans des bases d'images ; dans le but de pouvoir les interroger d'une manière ergonomique et intuitive pour l'utilisateur.

Comment retrouver une image parmi un corpus d'images ?

Deux approches de recherches sont envisagées:

Recherche d'images par mot clés

Une des attentes des utilisateurs dans le domaine de recherche d'images se situe au niveau de sa sémantique c'est pour cela que la plupart des systèmes de recherche d'images développés utilisent des mots clés ou des descripteurs textuelles pour caractériser chaque image de la base (ex : recherche d'images sur Internet).

Ce type de caractérisation comporte un certain nombre d'inconvénients, en effet : La description textuelle est une opération longue, coûteuse et difficile à élaborée car l'information externe est manuellement attachée par l'utilisateur ce qui conditionne la qualité de recherche future, et puis elle ne décrit pas fidèlement le contenu de l'image car elle se fait de manière automatique à partir du nom, de la légende ou du texte qui l'entoure. La figure1 illustre bien donne les inconvenients de ce type de requête. En effet l'utilisateur veut trouver des images qui contiennent une ou (des) voiture(s) avec le ciel cependant les premières images ne sont pas pertinenenes.

Fig. 1. Un exemple de recherche d'images dans Google

Pour palier aux inconvénients de la recherche par mots clés, une deuxième approche a été proposée : la recherche par le contenu.

Recherche d'images par le contenu

Comme son nom l'indique, le principe de cette méthode est d'identifier des images à partir de leur contenu (c'est à dire à partir des données de l'image elles même et non à partir du texte associé aux images).

L'indexation des images, qui se fait automatiquement, nécessite l'extraction des paramètres de celles ci au préalable. Ces paramètres "quantifient" la couleur, la texture, l'intensité ou bien encore les formes contenues dans l'image et fournissent une "signature" [6] de l'image.

L'indexation

L'indexation a pour but de substituer à une image un représentant (ou descripteur) moins encombrant qui la caractérise le mieux possible et de ne travailler que sur ce modèle lors de la recherche. Cela permettra une meilleure organisation des données, de limiter la quantité de données examinées durant une recherche, d'y accéder rapidement et de confiner la recherche au maximum.

Les phases d'indexation

Un système d'indexation comprend généralement deux phases de traitement :

Indexation logique

L'indexation logique consiste à extraire et à modéliser les caractéristiques de l'image qui sont principalement la forme, la couleur et la texture. Chacune de ces caractéristiques pouvant être considérée pour une image entière ou pour une région de l'image.

Indexation physique

L'indexation physique consiste à déterminer une structure efficace d'accès aux données pour trouver rapidement une information. De nombreuses techniques basées sur des arbres (arbre-B, arbre-R, arbre quaternaire,…) ont été proposées.

Pour qu'un système de recherche d'images soit performant, il faut que l'indexation logique soit pertinente et que l'indexation physique permette un accès rapide aux documents recherchés.

Structures d'index arborescentes non équilibrées: Les Arbres Quaternaires

L'arbre quaternaire est une structure de données qui permet de représenter les images à deux dimensions. Elle est basée sur la décomposition récursive [8] de l'image en quadrants réguliers selon un critère particulier (ex : homogénéité de la couleur des pixels ou homogénéité de la texture…).

Cette méthode offre des avantages en terme de modification d'image, en plus, on peut réduire dans certains cas la taille de l'arbre si on révise le critère d'uniformité d'un quadrant. Par exemple on dira qu'un quadrant est homogène si le pourcentage d'une des couleurs est supérieur à un seuil de qualité, ce seuil de qualité évolue entre 51% (ce qui n'est pas très significatif) et 100% (si on arrête la division uniquement quand la zone est totalement homogène, ce qui est le traitement par défaut). L'Arbre Quaternaire Générique [4] est une structure permettant de représenter et de gérer des images similaires dans une base de données d'images organisées en arbres quaternaires. Cette structure minimise l'espace de stockage d'un ensemble d'images tout en accélérant certaines opérations comme la comparaison ou la mise à jour de plusieurs images simultanément. Via cette structure un utilisateur peut facilement faire différentes opérations (modifier une image existante dans la base, insérer ou supprimer des images, extraire des images pour construire des séquences etc.…).

Principe

Partage entre images

Le partage entre arbres quaternaires d'images consiste à partager les régions similaires des images. Si un quadrant a la même valeur v dans un ensemble d'images E' qui est inclut dans l'ensemble de toutes les images de la base E, alors cette valeur v sera stockée qu'une seule fois dans la base.

On a deux types de partages :

 Partage explicite : Dans ce cas l'identificateur de chaque image partageant cette valeur apparaît explicitement dans la liste des images associées à cette valeur dans la base.  Partage implicite : Dans le partage implicite chaque image i partage implicitement la valeur associée à son image mère, excepté lorsque l'identificateur de l'image i est associé explicitement avec une autre valeur.

Similarité entre images

Les images sont regroupées, dans la base de données, en fonction d'une distance de similarité entre les arbres quaternaires qui les représentent. Cette distance est basée sur plusieurs critères tels que : la structure de l'arbre, la valeurs des noeuds etc.…...

Arbre d'images

Les images représentées par un arbre quaternaire générique sont organisées à l'aide d'une structure particulière, l'Arbre d'image. A chaque fois qu'une nouvelle image est insérée dans l'arbre d'image, elle est insérée comme fille de l'image dont elle est la plus similaire, c'est à dire dont la distance entres l'arbre quaternaire associé et celui de l'image à insérer est la plus petite.

La recherche d'images

Dans le domaine de l'imagerie, il existe plusieurs façons de mesurer la ressemblance entre images dans une base d'images, à une image requête. La définition de la similarité dépend beaucoup de la manière avec laquelle l'image est recherchée.

La définition générale de la distance entre des images représentées en arbres quaternaires. Cette distance, notée  (i,j) [5], permet de mesurer la similarité entre les images i et j.

Distances de similarité basées sur les arbres quaternaires

La recherche d'image par le contenu est basée sur la similarité des caractéristiques visuelles des images. La fonction de distance utilisée pour évaluer la similarité entre images dépend des critères de la recherche mais également de la représentation des caractéristiques de l'image.

L'idée principale est généralement d'associer à chaque image un arbre quaternaire représentant les caractéristiques de l'image, et de mesurer la similarité des images en utilisant une fonction de distance entre ces arbres.

Définition de la distance entre images

Recherche d'images

Différents types de recherches ont été implantés dans ce logiciel : -la recherche globale -la recherche par région -la recherche par niveaux. La similarité entre images est calculée en fonction des trois distances définies dans la section 8.

Recherche de similarité globale 10 Résultats et discussions

Le prototype a été testé sur plusieurs types de bases d'images couleurs et niveau de gris. L'interprétation des résultats obtenus est donnée à travers les remarques suivantes :

1. Le taux de gain de stockage varie en fonction des tailles des bases. Le prototype est plus performant lorsque les tailles des bases sont importantes (voir figure 6). 2. Le gain de stockage augmente en fonction de la taille de la base. La figure 7