Dans cet article, nous présentons un système d'indexation et de recherche d'images par le contenu Requit. Chaque image est représentée par un arbre quaternaire et notre base d'images est stockée en une structure de données appelée arbre quaternaire générique. Ce dernier permet de minimiser l'espace de stockage par partage d'informations entre les images et facilite les opérations entre elle.
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.
Deux approches de recherches sont envisagées:
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. 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.
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" [
Deux aspects indissociables coexistent dans les systèmes de recherche d’images par le contenu, l’indexation et la recherche.
La phase d’indexation (hors-Ligne) : Dans cette phase, des caractéristiques sont automatiquement extraites à partir de l’image et stockées dans un vecteur numérique appelé descripteur visuel. Grâce aux techniques de la base de données, on peut stocker ces caractéristiques et les récupérer rapidement et efficacement. La phase recherche (On-line) : Dans cette étape, le système analyse une ou plusieurs requêtes émises par l’utilisateur et lui donne le résultat correspond en une liste d’images ordonnées, en fonction de la similarité entre leur descripteur visuel et celui de l’image requête en utilisant une mesure de distance.
La figure2 schématise le d’indexationd’images.
fonctionnant d’un système de recherche et
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.
Un système d’indexation comprend généralement deux phases de traitement :
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.
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.
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 [
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.
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.…...
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.
Exemple1. La figure 4 présente un Arbre d’Image organisant les images, u, v,w et y. On suppose que l’image u est une image originale sur laquelle ont été appliqués des traitements dont les images v et w ont résultées. L’image y correspond au résultat de l’image w après traitement. 6.1.4.
La représentation et le stockage d’un ensemble d’images similaires sont effectués
dans un arbre quaternaire générique, dont les noeuds sont appelés noeuds génériques.
Chaque noeud générique n représente tous les noeuds n des arbres quaternaires des
images de la base, et contient toute l’information pour recomposer la valeur du noeud
de même identification dans chaque arbre quaternaire
Exemple2. La figure5 représente l’Arbre Quaternaire Générique des images de la
figure4 le noeud générique 0 contient une seule ligne de valeur Int : elle signifie que
les noeuds 0 sont internes dans les arbres quaternaires de toutes les images de
l’ensemble
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) [
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.
La distance est une distance entre images représentée par des arbres quaternaires. La distance entre deux images i et j est définie par une somme de distance k (i, j) entre les noeuds des arbres quaternaires représentant les images i et j, pondérées par des coefficients Ck tel que
Ck > 0 : ( i , j ) c K K ( i , j ) / c K Δk (i,j) est une distance normalisée entre les noeuds homologues k des arbres quaternaire i et j. k est l’identificateur d’un noeud pris parmi l’union des identificateurs de noeuds apparaissant dans les arbres quaternaires des images i et j.
Ck est un coefficient positif représentant le poids du noeud k dans le calcul de la distance Chaque poids Ck est choisit selon l’importance qu'on souhaite donner à certains quadrants d’image par rapport à d’autres dans le calcul de la distance .
En fonction des différents poids Ck associés aux noeuds et de la distance choisie entre les noeuds, plusieurs types de distances peuvent être définies à partir de la distance :
La distance T (T pour Tree) : Cette distance permet la comparaison de la structure de deux arbres quaternaires représentant des images, sans tenir compte de la valeur des noeuds feuilles la distance k (i, j) entre les noeuds d’arbre quaternaire ne prend que 2 valeurs : 0 lorsque les deux noeud sont tous les deux internes ou tous les deux feuilles et 1 lorsque le noeud est feuille dans un arbre quaternaire et interne dans l’autre ou lorsque le noeud k existe seulement dans un arbre.
La distance Q (Q pour quadrant) : Cette distance compare deux arbres quaternaires non seulement du point de vue de leur structure, mais également du point de vue des valeurs de leurs noeuds. La distance k (i, j) entre les noeuds d’arbres quaternaires prend la valeur 0 lorsque tous les noeuds homologues sont tous les deux internes ou tous les deux feuilles avec la même valeur ; la valeur 1 lorsque le noeud est feuille dans un arbre quaternaire et interne dans l’autre ou lorsque le noeud k existe seulement dans un arbre et une valeur comprise entre ]0,1[ lorsque les deux noeuds sont à la même position mais leurs valeurs sont différentes Cette distance Q est utilisée dans notre prototype d’indexation des images de la base.
La distance V (V pour visuel): Lors du calcul de la distance entre deux images i et j, les arbres quaternaires de ces images sont complétés pour avoir la même structure. On ne tient compte alors que des valeurs des noeuds ( k (i, j) = 0 pour tous les noeuds internes ).
Le système d’indexation et de recherche d’images (REQUIT) que nous avons développé en C++, permet de représenter des images Noir et Blanc, niveau de gris ou couleur, par des quadtree dont le critère de découpage est l’homogénéité de la couleur. La base d’images obtenue est stockée sous forme d’un arbre quaternaire générique sans partage implicite (ARGSPI).Ce prototype permet à l’utilisateur de choisir les opérations qu’il désire effectuer sur la base d’images telles que :
Afficher une image, la stocker sous forme d’arbre quaternaire, l’insérer ou la supprimer de la base Rechercher des images similaires à une image requête suivant différents critères (utilisation des distances T, Q, V) ou rechercher des images ayant des régions similaires. Réaliser des opérations sur les images telles que l’Union, l’intersection, ect…..
La figure suivante schématise l’architecture générale de REQUIT
Les images peuvent être stockées sous le format QT (en quadtree). Le prototype permet la lecture des images en format QT et leur conversion en bmp. Nous donnons un exemple d’images stockées en QT et leurs tailles correspondantes :
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. 92.1 Recherche de similarité globale 822 1318 1646 1726 1891 2056 2385
Taille Initiale Image Tollari
2.
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).
Le gain de stockage augmente en fonction de la taille de la base. La figure 7 montre la variation du gain du taux de stockage en fonction de la taille des bases d’images an i g60,00% 40,00% 20,00% 0,00% -20,00% -40,00% -60,00% -80,00% 390 650 975 1300
1690
images satellitaire niveau de gris
taille initiale
Les systèmes de recherche d’images par le contenu (Content-Based Image Retrieval
systems) permettent de rechercher les images d’une base de données en fonction de
leurs caractéristiques visuelles. Dans ces systèmes, la requête est une image et le
résultat de la requête correspand à une liste d’images ordonnées en fonction de la
similarité. Dans plusieurs domaines d’application, l’utilisation de descripteurs
résumant l’information globale des images, tels que les histogrammes de couleurs des
images entières, n’offre pas toujours des résultats satisfaisants car cette description ne
tient pas compte de la localisation des pixels et des régions d’intérêt. Pour remédier à
cette limite et tenir compte de la localisation des caractéristiques visuelles dans le
calcul de la similarité des images, plusieurs approches ([
L’utilisation de la distance entre images organisées en arbre quaternaires et stockées en arbre quaternaire générique, nous a permis d’obtenir des résultats très satisfaisants.
Comme perspectives nous tentons d’extraire d’autres caractéristiques de l’image comme la texture, de les combiner afin d’obtenir une meilleure description de l’image améliorant ainsi la qualité de recherche future.