La gestion des bases de données images nécessite des systèmes spécifiques, les premiers systèmes étaient basés sur la recherche par mot-clés, ces systèmes ont montré quelques limites à cause de la subjectivité des mots-clés attribués. Ces limites ont conduit à la naissance des systèmes d'indexation et de recherche d'images par le contenu physique de l'image (CBIR, en anglais Content-Based Image Retrieval).
Le contenu d'une image possède des caractéristiques permettant de la résumer par des métriques mathématiques appelés descripteurs, ces descripteurs sont fondés sur des caractéristiques visuelles comme la couleur [6] [10], la texture [4] [8] et la forme [12].
Ces caractéristiques, dites de bas niveau, peuvent être calculées globalement sur l'image (descripteur global), comme ils peuvent être calculés au niveau local. Dans plusieurs travaux [1] [5] [6], l'arbre quaternaire a été employé pour le calcul des descripteurs local d'une image, il permet de décrire l'image à plusieurs niveaux, en la décomposant récursivement en quatre quadrants, plus l'arbre est profond plus la description est locale. La mesure de similarité entre deux images correspond à la distance entre leurs arbres quaternaires, on distingue trois distances principales T, Q, V [9].
Bien que cette technique de recherche (CBIR), soit puissante, elle aussi souffre d'un certain nombre de limites comme le fossé sémantique et le temps requis pour la recherche. La première limite est dû au fait que la recherche vise les images similaires à une image donnée [11], alors que le deuxième problème est la conséquence du volume élevé des données à explorer pour trouver des résultats.
Dans ce travail, nous proposons une architecture d'une base d'image en clusters, qui va permettre de réduire le volume des données à explorer en n'effectuant la recherche que dans le cluster jugé pertinent, les images du même cluster doivent être le plus similaires possible pour assurer la qualité des résultats. La conception de notre système assure les fonctionnalités requises pour ces deux étapes à l'aide de quatre modules : module de représentation des images, module de classification, le module de stockage et le module de recherche.
Architecture en module du CBIR.
Ce module est chargé de représenter les images dans un format unique et approprié, il permet aussi certaines opérations de base. Notre système exploite des descripteurs locaux, d'où la nécessité d'une représentation en arbre quaternaire. Cette représentation rend le système indépendant du type (matriciel ou vectoriel) et du format d'image (BMP ou JPEG... etc.), de plus, cela permet la compression d'une image représentant une zone homogène par noeud du quadtree au lieu d'un grand nombre de pixels. L'avantage de cette technique est qu'elle est indépendante de la méthode de regroupement et de la distance choisie. Le choix des valeurs trop éloignées permet de maximiser l'inertie inter classe, la minimisation de l'inertie intra classe est assurée par l'algorithme de regroupement.
Le choix du nombre de groupes est un facteur important qui influence sur les résultats en classification automatique, pour un nombre de groupes élevés1 cela conduit à une partition non signifiante en divisant des groupes homogènes en plusieurs, au contraire un nombre plus faible conduit à une partition de groupe non homogène, ceci est dû au principe de création d'une partition, un élément doit appartenir à un seul et unique groupe, même si tous les groupes lui sont différents, il doit appartenir à l'un d'entre eux.
Rappelons que notre objectif vise à regrouper les images similaires dans un même cluster pour réduire l'espace de recherche et assurer une bonne qualité des résultats d'une recherche dans un cluster. Nous proposons de fixer une distance maximale entre une image et le représentant de son groupe, une image n'est affectée à un groupe que si la distance qui les sépare est inférieur à ce seuil, parmi les images non classées, nous choisissons celle qui possède la distance la plus élevée vers un groupe, cette image sera la représentante du groupe construit.
Remarquons que ce principe va augmenter le nombre de classes à chaque fois que cela sera nécessaire, en plus il peut être appliqué après l'organisation de la base d'images lors d'une mise à jour, si une image n'appartient à aucun des groupes existants, un nouveau groupe est créé. Enfin, il est recommandé d'amorcer le classifieur avec un nombre de groupes minimal.
Le k-means [2] exploite la représentation de classe en centroïde (moyenne des descripteurs de l'ensemble), l'application de cet algorithme au partitionnement d'un ensemble d'images représentées par des arbres quaternaires nécessite la définition du vecteur de descripteur et le représentant de classe.
Le vecteur de descripteur est construit à partir des arbres quaternaires, c'est un vecteur où chaque élément contient les descripteurs d'une feuille de sorte à avoir dans la même position dans le vecteur les feuilles homologue (du même identifiant). La • En complétant à la structure maximale (le plus grand arbre représentant une image de la base), ce qui va produire des vecteurs de descripteur de très grande taille. • En fixant une profondeur maximale, les arbres n'ayant pas atteint cette profondeur seront complétés, ceux qui ont dépassé seront réduits, par conséquent, la taille de descripteur sera raisonnable avec une perte d'information.
D'après la nature de représentation des images (arbre quaternaire), la distance visuelle (V) est la mieux adaptée à ce type de situation, de plus, cette structure ne pose pas de problèmes lors du calcul de la distance v, puisque la structure est connue (arbre et descripteur), et donc les pondérations de chaque niveau sont connu.
Le représentant de classe est un vecteur de descripteur d'une image virtuelle, il sert à regrouper les images les plus similaires dans le même cluster, sa valeur est la moyenne des descripteurs appartenant au groupe lui-même.
Ce module utilise les deux modules décrit précédemment, pour accomplir sa tache, il est capable de gérer une base d'images organisée en plusieurs clusters en utilisant des méta-informations de l'ensemble de données.
Les méta-informations contiennent deux types d'informations, le premier concerne l'organisation de la base, il donne des informations sur le nombre des clusters utilisés et l'emplacement de chaque cluster, le deuxième type décrit les groupes, il diffère selon le type de la méthode de clustering utilisée.
Dans le cas du k-means nous avons besoin de connaître les représentants des clusters, ils sont stockés sous forme d'arbre quaternaire afin de pouvoir calculer la distance visuelle entre l'image2 à classer et les différents représentants des groupes.
Le cas d'une méthode indépendante du type et de la structure de données tel que le PAM, les informations sont relativement plus simples, pour déterminer le groupe d'appartenance d'une image, il suffit de connaître l'identifiant de l'image medoïde de chaque groupe, et le type de distance utilisé pour le regroupement de la base (distance V, Q ou autre).
Le module de recherche fournit une interface qui permet aux utilisateurs de spécifier leurs requêtes, et restitue les résultats correspondants aux critères de la requête (images similaires). Dans notre prototype, on a opté pour les requêtes par l'exemple [7], nous proposant deux types de recherches, la première baptisée « N plus proches images » dont le résultat est un ensemble de N images similaires à la requête, le deuxième permet de restituer les images qui sont dissimilaire à x % de l'image requête. L'exécution d'une requête suit le processus suivant : Tout d'abord le module de présentation transforme l'image en arbre quaternaire il la transmet ensuite au module de classification pour la classer et déterminer le meilleur groupe qui fournit un bon résultat, enfin le module de recherche procède à un balayage de l'ensemble des descripteurs des images du cluster ciblé.
Notre expérimentation porte sur trois points principaux, évaluation de la structure de données utilisées par le module de classification où nous effectuons une comparaison entre l'usage d'un ensemble de vecteurs de descripteur et une ensemble de distances entre les objets à classer. Le deuxième point, évalue la qualité de la classification pour les deux algorithmes et l'apport de notre stratégie d'initialisation proposée. Enfin, le dernier point abordera le temps de réponse du système dans le cas d'une BDI organisée en mono ou multi clusters.
Les images représenté par les arbres quaternaire peuvent se présenté a un classifieur sous deux formes : ensemble de vecteurs de descripteur, ceci nécessite que les arbres quaternaires de l'ensemble aient la même structure pour qu'on puisse les transformer en vecteurs de même dimension, ou un ensemble de distance, dans ce cas, on à besoin de calculer toutes les distances entre chaque pair d'image. Cette partie discute l'utilisation des deux modes (centroide pour représentation en vecteur ou medoide pour l'ensemble des distances). Ce qui fait la différence entre les deux modes de représentation est la structure requise pour effectuer cette opération. Lorsqu'on travaille avec des centres, on est obligé de transformer l'arbre quaternaire en vecteur de même dimension que celui qui représente les centres des groupes, ce qui nécessite de garder la structure de l'arbre obtenu dans la phase hors ligne. Par contre l'utilisation des medoïdes, seul l'identifient de l'image medoïde (représentant du groupe) est requis.
La structure de données légères et la flexibilité de classer une nouvelle image sont deux arguments qui nous motivent et qui nous boutent à utiliser des algorithmes basés sur les mesures de similarité pour ce type données (image représentée en arbre quaternaire).
Dans cette partie, nous validons l'apport de notre stratégie d'initialisation par l'application du k-means et PAM sur l'ensemble d'images. Rappelons qu'on ne peut utiliser que la distance visuelle V dans le cas des centres nous avons choisi appliqué le PAM en utilisant la distance visuelle afin de tester les deux algorithmes dans le même contexte. Bien que les deux algorithmes ont procédé à l'optimisation de la même partition leurs résultats sont différents, cette différence est expliquée par le fait que la nature des deux algorithmes tel que le PAM qui regroupe au sein du mêmes ensembles les images dont la distance entre eux est minimale, alors que le k-means utilise des centres, qui représentent la moyenne de chaque groupe, ces centres changent de position (valeur) au cours de la classification et de fausse moyenne conduit à de faux résultats. Le temps de recherche sur la même base d'images organisé en mono cluster est :
• Requête 1 : 57650,85 ms.
• Requête 2 : 51002.24 ms.
• Requête 3 : 49215,29 ms.
Dans un cluster le temps de recherche diminue lorsque le nombre de ces derniers augmente. Il est évident que lorsque le nombre de clusters augmente leurs cardinalités réduit, en conséquence l'espace de recherche est limité sur un sous ensemble ce qui explique la réduction du temps de recherche. Au contraire, lorsque le nombre de clusters augmente, l'image requête est comparée avec un nombre plus élevé de représentants des clusters est provoquera donc l'augmentation du temps requis pour l'affectation d'une image.
On augmentant le nombre de clusters, le temps de classification augmente et celui de la recherche diminue et influence le temps global de recherche, on observe sur le graphe de la Figure 12 que le temps global de recherche est décroissant sur la première partie du graphe et croissant dans la deuxième partie, ainsi que le taux de décroissance est supérieur à celui de croissance à cause des fortes changement des nombres d'images des clusters pour un nombre faible de clusters. Du point de vu temps de recherche, le nombre de clusters optimale est celui qui réduit au minimum le temps de recherche, malheureusement, il ne l'est pas forcément pour la classification de l'ensemble de la base d'image et peut produire une mauvaise classification entraînant une pauvre pertinence des résultats lors de la recherche.
Le temps global de recherche est moins prioritaire que la qualité des résultats pour cette raison notre solution au problème du nombre de classes a été : de fixer une dissimilarité maximale intra groupe, tel que tout groupe ayant un élément qui dépasse cette valeur doit construire son propre groupe, cette astuce permettra non seulement de préserver la qualité des résultats mais aussi d'équilibrer les clusters.
Nous avons présenté dans ce document une architecture d'un système d'indexation et de recherche d'images par le contenu basé sur une indexation en clusters, nous avons abordé certains problèmes et difficultés rencontrés lors de la mise en oeuvre de cette architecture qui sont relié au module de classification (le coeur du système).
Notre système utilise des descripteurs locale basée sur les arbres quaternaires, pour la classification de cette structure de données, nous avons divisé les algorithmes de clustering en deux types : Méthodes basées sur représentation en centre et méthodes basées sur les distances entre les objets à classer, à des fins d'optimisation, l'utilisation des algorithmes basés sur les distances entre les objets est recommandé.
Le module de classification utilise deux mécanismes d'optimisation, le premier permet de déterminer le nombre optimal de clusters dans la phase indexation, et de contrôler les résultats d'une recherche dans la phase online, ceci en fixant la dissimilarité maximal entre une image est le représentant de son cluster. Le deuxième mécanisme est un algorithme d'initialisation qui permet d'améliorer les résultats du clustering, il est applicable avec tout algorithme de clustering nécessitant une initialisation (EM, PAM, …).