Résumé
Nous présentons une méthode de recherche automatique d’images prenant en compte la distribution spatiale des couleurs, et l’appliquons à une base de données d’enluminures de l’Institut de Recherche et d’Histoire des Textes. Cette méthode permet d’apprécier la composition des formes colorées des enluminures. Les requêtes effectuées sont faites par l’exemple, c’est-à-dire qu’une image est soumise à la base, puis les images les plus proches selon des critères de placement des couleurs sont ensuite retournées à l’utilisateur. Les images sont représentées par des versions à basse résolution dans un espace psychométrique et la distance dite « du cantonnier » est utilisée pour évaluer leur similitude. Nous développons enfin un critère statistique permettant de décider quelles images doivent être retenues lors de la requête.
Abstract
We introduce a color image retrieval method which includes spatial color organization. Tests have been performed on the illuminated manuscript database provided by the Institut de Recherche et d’Histoire des Textes. Starting from a query image, we display images that have a similar overall spatial organization of colors. The method relies on small image thumbnails and the Earth Mover’s Distance (EMD). We also introduce a statistical framework that enables us to derive an unsupervised matching criterion.
Sommaire
Introduction
Cet article présente une méthode de recherche automatique dans une base de données d’images selon un critère de composition spatiale des couleurs. Nous présentons une méthode de recherche par l’exemple, c’est à dire permettant de trouver dans une base de données toutes les images dont la répartition spatiale des formes colorées est proche d’un exemple soumis par l’utilisateur. Cette méthode analyse directement le contenu de l’image sans avoir besoin de s’appuyer sur des métadonnées. Il est possible de privilégier soit la position soit la teinte des couleurs en ajustant un paramètre de pondération. Après un rapide état de l’art du domaine de la recherche automatique d’images selon des critères de couleur à la section 2, nous présentons notre méthode à la section 3, puis des résultats sur une base d’enluminures de l’Institut de Recherche et d’Histoire des Textes (IRHT)1 à la section 4.
État de l’art
L’indexation automatique d’images par le contenu est un domaine de recherche très actif. La couleur est un critère essentiel pour ce type de recherche [1]. Les méthodes les plus simples et les plus classiques reposent sur le contenu global de couleurs des images, le plus souvent par l’intermédiaire d’histogrammes, voir par exemple [2]. Ces méthodes ignorent néanmoins des informations importantes pour la perception visuelle, en particulier l’organisation spatiale des couleurs dans l’image. Différentes approches ont été proposées pour prendre en compte cette organisation. Un premier groupe de méthodes intègre aux histogrammes de couleurs la localisation de chaque pixel de l’image [3,4,5,6]. Ces méthodes sont malheureusement sensibles aux variations d’intensité. Un second groupe repose sur des points d’intérêts de l’image [7,8]. Ces points ou zones d’intérêts correspondent aux régions où le contraste est très élevé et reflètent la présence de structures particulières, telles des coins. Ces méthodes sont bien adaptées à la recherche d’objets particuliers dans les images, mais ne permettent généralement pas la représentation de l’organisation macroscopique des couleurs. Pour l’étude de la composition, les méthodes les plus adaptées et prometteuses sont celles fondées sur une segmentation préliminaire de l’image en régions perceptuellement homogènes [9,10,11,12,13]. Cette segmentation automatique de l’image est un problème difficile et non résolu bien qu’étudié dans le domaine de l’analyse automatique des images depuis ses débuts dans les années 1970. Les erreurs inévitables de segmentation produites par ces méthodes et le nombre de paramètres qu’elles nécessitent rendent l’indexation peu robuste et influencent beaucoup les résultats des requêtes. La méthodologie que nous proposons dans la section suivante vise à éviter cette étape de segmentation de l’image en régions, ce qui est rendu possible par l’utilisation d’une distance adéquate entre images.
Méthode proposée
La méthode que nous présentons repose sur l’utilisation de représentations sous-échantillonnées, possédant peu de pixels, des images numériques. Nous appellerons ces représentations imagettes dans ce qui suit. Lorsqu’une requête est soumise par l’utilisateur, les distances entre l’imagette requête et les imagettes de la base sont tout d’abord calculées, puis les images les plus proches de la requête sont retournées à l’utilisateur. Nous détaillons plus loin la distance retenue. Nous définissons ensuite un critère de décision non supervisé ajustant le nombre N d’images pertinentes à renvoyer à l’utilisateur. Les N premières images les plus proches de la requête sont retournées, N variant automatiquement en fonction de la requête et du contenu de la base.
Espace de couleur
Dans une image en noir et blanc, le niveau de gris de chaque pixel est représenté par un nombre compris entre 0 (noir) et 255 (blanc), codé sur un octet. Les images couleurs nécessitent trois nombres en chaque pixel pour décrire l’information couleur. Cela est dû à la trivariance visuelle mise en évidence par les expériences de psychovision et à la présence dans la rétine de trois types distincts de cônes. Une couleur s’exprime donc dans un espace à 3 dimensions. Il existe de nombreux espaces différents pour représenter les images, le plus connu étant l’espace RVB (rouge, vert, bleu), utilisé pour reproduire les images sur les écrans. Celui que nous utilisons est l’espace CIE-Lab, dans lequel chaque couleur est représentée par les coordonnées L, a et b. L exprime la luminosité d’une couleur, a et b permettent de caractériser sa teinte et sa saturation. Le canal a représente l’antagonisme rouge-vert et le canal b l’antagonisme bleu-jaune. Ces antagonismes connus aussi des artistes ont leur origine dans le système visuel humain. Une représentation de cet espace à trois dimensions sous la forme d’une sphère est donnée sur la figure 1. L’espace CIE-Lab a été choisi car il est adapté aux calculs de distances perceptuelles que nous faisons par la suite. Il a en effet été construit de manière à ce que la distance euclidienne entre deux points de couleurs proches corresponde à la différence de perception que nous avons de ces couleurs. Cet espace est dit psychométrique.
L’axe vertical L représente la luminosité (du clair au sombre).
Les axes a et b permettent de caractériser la teinte et la saturation,
a représentant l’antagonisme rouge-vert et b l’antagonisme bleu-jaune.
Calculs des imagettes
Les images d’enluminures dont nous disposons sont de résolution élevée (plusieurs millions de pixels) et contiennent des détails très fins, plus petits que le millimètre. Un tel niveau de détail est indispensable à la préservation du patrimoine, à la consultation des enluminures, ainsi qu’à une analyse colorimétrique fine, mais il n’est pas nécessaire pour étudier la composition globale des formes colorées. Nous avons donc travaillé sur des imagettes, images fortement sous-échantillonnées ne comportant que quelques centaines ou quelques milliers de pixels. À cette échelle, seules les plus grandes structures sont visibles. Cette étape correspond en quelque sorte à un partitionnement simpliste de l’image en zones colorées. Chaque pixel de l’imagette est obtenu par moyennage des couleurs de la région couverte dans l’image originale exprimée dans l’espace CIE-Lab. Un exemple de calcul d’imagette est présenté sur la figure 2.
À gauche l’image originale (3200*2200 pixels), à droite l’imagette (10*15 pixels).
Distance entre imagettes
Pour quantifier la ressemblance entre imagettes, nous avons choisi la distance dite du cantonnier, appelée Earth Movers’s Distance en anglais, [14]. Cette distance s’inspire de problèmes de transport, initialement étudiés par le mathématicien G. Monge à la fin du dix-huitième siècle. À chaque pixel d’une imagette correspond un point dans un espace à 5 dimensions (trois dimensions pour la couleur Lab, et deux pour la position x et y dans l’image). Une imagette est donc représentée par un ensemble de points dans cet espace à 5 dimensions. Intuitivement la distance du cantonnier représente chacun de ces points comme un tas de terre d’un certain volume pour l’imagette requête, et comme des trous de même volume pour les autres imagettes de la base de données. La distance entre la requête et une image de la base est le travail minimum à fournir pour déplacer les tas de terre et remplir les trous. La figure 3 illustre cette vision intuitive de la distance du cantonnier. Dans le contexte de la représentation des images par des nuages de points dans un espace à 5 dimensions, la distance d’une enluminure à une autre est le travail minimal pour transformer l’imagette de la première enluminure en celle de la deuxième. Le travail est défini comme la distance totale parcourue pour envoyer les points les uns sur les autres dans l’espace à 5 dimensions. Si deux enluminures ont une composition similaire, le travail pour aller de l’une à l’autre sera faible. Si elles sont très différentes, il sera au contraire très élevé. Dans le cadre de ce calcul, nous pouvons favoriser l’aspect colorimétrique (Lab) ou spatial (x,y) par l’intermédiaire d’un paramètre de pondération dont le choix peut être laissé à l’utilisateur en fonction de ce qu’il souhaite privilégier dans sa recherche.
Le travail est défini comme le poids de la terre transportée multiplié par la distance parcourue
Requête adaptative
Après avoir calculé les distances précédentes, la base au complet peut être classée en fonction de la requête, de l’image la plus proche à la plus éloignée. Il faut ensuite décider du nombre d’images de la base devant être retournées à l’utilisateur. La majorité des outils de recherche automatique renvoient un nombre arbitrairement fixé d’images (N=20 par exemple). Une méthode alternative consiste à retourner les images dont la distance à l’image requête est inférieure à un certain seuil, généralement fixé empiriquement. Notre méthode propose que ce nombre s’adapte de manière non supervisée (c’est-à-dire sans intervention de l’utilisateur) au contenu de la base et à la requête, et elle repose sur une méthode proche de celle présentée dans [15,16].
Le principe utilisé, appelé principe de Helmholtz ([17]), est le suivant : un événement est perceptuellement significatif si sa chance d’apparaître dans un contexte aléatoire (souvent appelé « bruit ») est faible. Pour appliquer ce principe à la recherche automatique, nous commençons par simuler une base d’imagettes aléatoires dont le contenu global de couleurs est le même que celui de la base sur laquelle la recherche est effectuée. Plus précisément, ces images aléatoires sont obtenues par agencement de disques dont les couleurs sont apprises sur la base d’enluminures. La description complète du modèle aléatoire utilisé pour générer ces images sort du cadre de cet article, et nous renvoyons le lecteur intéressé à [18]. Le seuil de mise en correspondance des images est ensuite calculé de sorte qu’aucune des images aléatoires ne soit associée à la requête, ce qui revient à retenir la distance minimale dm entre les images aléatoires et la requête. Les images retournées à l’utilisateur sont alors toutes celles qui sont à une distance de la requête inférieure à dm. L’interprétation intuitive de cette méthode est que, lorsque nous effectuons une recherche dans la base à partir d’une image requête, nous décidons de présenter à l’utilisateur toutes les images de la base dont la proximité à cette image requête n’est pas le fruit du hasard. Une illustration de l’approche proposée est présentée sur les figures 4 et 5 .
Résultats
Les résultats sont présentés sous forme de planches d’enluminures. L’image en haut à gauche de chaque planche est l’image requête soumise à la base. Les images résultats sont placées de gauche à droite et de haut en bas à partir de cette image, de la plus proche à la plus éloignée. Sur les figures 6 et 7, nous illustrons l’adaptativité des requêtes. Sur la planche 6a sont présentés uniquement les 10 premiers résultats. Sur la planche 6b), les N premiers résultats significatifs (ici N=16) tel qu’expliqué au paragraphe précédent. Nous voyons qu’en s’arrêtant arbitrairement aux 10 premiers résultats, des images intéressantes et proches de la requête sont perdues. Inversement sur les planches 7a et 7b, la base contient peu d’images ayant la même composition que la requête, et il est inutile de retourner plus de N=5 résultats. Comme nous le voyons dans l’ensemble des résultats suivants, cette méthode adaptative n’est pas parfaite. Il arrive assez souvent que quelques images non pertinentes soient retournées en fin de planche (figures 10 et 18 par exemple). En revanche, nous avons pu observer que les résultats pertinents sont rarement manqués.
Sur la figure 8a, la couleur et l’organisation spatiale sont prises en compte. Sur la figure 8b, seul l’histogramme des couleurs est pris en compte (c’est à dire le contenu global de couleurs). L’avant-dernier résultat présente effectivement un histogramme des couleurs identique aux autres, mais l’organisation spatiale de ces couleurs est différente. Les régions ocres correspondant aux vêtements des personnages sur les trois premiers résultats sont en bordure gauche et basse du quatrième résultat. De même, la région verte en bas à droite sur les trois premiers résultats est en arrière-plan de l’ange sur le quatrième résultat. Le cinquième résultat (serpent), bien que sémantiquement différent des trois premiers, est semblable au niveau de son organisation spatiale des couleurs.
Sur la figure 9 est présentée une illustration de l’influence de la pondération choisie par l’utilisateur entre ces deux aspects. Sur cette figure nous nous limitons aux N=10 premiers résultats, pour une meilleure visualisation. Sur la première planche, l’importance est portée à 99% sur la composition spatiale. On voit sur cet exemple que la composition spatiale est en effet bien respectée. Les enluminures se situent aux mêmes endroits par rapport au texte que sur la requête, mais peuvent être rouges ou bleues. Plus on accorde de l’importance à la couleur, plus le positionnement et la taille de l’enluminure peuvent varier, mais plus sa couleur sera fidèle à la requête. Lorsque la pondération est portée à 100% vers la couleur, la méthode est équivalente à une recherche par comparaison des histogrammes de couleurs utilisant la distance du cantonnier [14].
Sur les figures 10 à 20, la même importance est accordée à la couleur et à la répartition spatiale des formes.
En haut, les 10 premiers résultats. En bas, le seuil adaptatif est calculé pour la requête (N=5 résultats).
La pondération entre composition spatiale et respect des couleurs est de 50%
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
La pondération entre composition spatiale et respect des couleurs est de 50%.
Conclusion
Nous avons présenté dans cet article une méthode de recherche automatique d’images par le contenu qui tient compte de la composition spatiale des couleurs. Cette méthode est appliquée à une base d’enluminures de l’IRHT. Elle est robuste car fondée sur une méthode de partitionnement simple qui ne nécessite pas de segmentation des images en régions. L’utilisateur peut varier l’importance qu’il accorde à la fidélité aux couleurs ou à la répartition purement spatiale des formes. La méthodologie proposée intègre aussi un critère de décision non supervisé qui adapte le nombre de résultats au contenu de la base et à chaque requête. Les résutats sur la base d’enluminures de l’IRHT montrent que la composition spatiale des couleurs est effectivement bien respectée.
Remerciements
Nous remercions Gilles Kagan, de l’IRHT, pour nous avoir fourni la base d’images utilisée dans ce travail ainsi que pour ses remarques et suggestions. Le travail présenté a été partiellement effectué dans le cadre d’une ACI multidisciplinaire du CNRS pilotée par Anne-Marie Eddé et Dominique Poirel de l’IRHT.
Bibliographie
1 Del Bimbo A., Visual Information Retrieval, San Francisco, Morgan Kufman Publishers, 1999.
2 Swain M. J. et Ballard D. H., « Color Indexing », International Journal of Computer Vision, 7/1, 1991, p. 11-32.
3 Lambert P., Hervey N. et Grecu H., « Image retrieval using spatial chromatic histograms », dans Conference on Colour in Graphics, Imaging, and Vision (CGIV), 2004, p. 343-347.
4 Giocca G., Schettini R. et Cinque L., « Image indexing and retrieval using spatial chromatic histograms and signatures », dans Conference on Colour in Graphics, Imaging, and Vision (CGIV), 2002, p. 255-258.
5 Huang J., Kumar S. R., Mitra M., Zhu W. J. et Zabih R., « Image indexing using color correlograms », dans Computer Vision and Pattern Recognition (CVPR), 1997, p. 762.
6 Pass Greg, Zabih Ramin et Miller Justin., « Comparing images using color coherence vectors », dans Association for Computing Machinery (ACM) Multimedia, 1996, p. 65-73.
7 Grauman K. et Darrell T., « Efficient image matching with distributions of local invariant features », Proc. Computer Vision and Pattern Recognition (CVPR), 2005, p. 627-634.
8 Heidemann G., « Combining spatial and colour information for content based image retrieval », dans Computer Vision and Image Understanding, 94, 2004, p. 234-270.
9 Carson C., Belongie S., Greenspan H. et Malik J., « Blobworld : image segmentation using EM and its application to image querying », dans Pattern Analysis and Machine Intelligence (PAMI), 24/8, 2002, p. 1026-1038.
10 Liu Y., Zhang D., Lu G. et Ma W. Y., « Region-based image retrieval with high-level semantic color names », dans Institute of Electrical and Electronics Engineers (IEEE) International Multimedia Modelling Conference, 2005, p. 180-187.
11 Rugna J. D. et Konik H., « Color coarse segmentation and regions selection for similar images retrieval », dans Conference on Colour in Graphics, Imaging, and Vision (CGIV), 2002, p. 241-244.
12 Prasad B. G., Biswas K. K et Gupta S. K., «Region-based image retrieval using integrated color, shape, and location index », Computer Vision and Image Understanding, 94, 2004, p. 193-233.
13 Dvir G., Greenspan H. et Rubner Y., « Context-based image modelling »,dans International Conference on Pattern Recognition (ICPR), 2002, p. 162-165.
14 Rubner Y., Tomasi C. et Guibas L. J., « The earth mover's distance as a metric for image retrieval », International Journal of Computer Vision, 40/2, 2000, p. 99-121.
15 Gousseau Y., « Comparaison de la composition de deux images », dans GRETSI (Groupe d'Etudes du Traitement du Signal et des Images) 03, Paris, 2003, 371 p.
16 Musé P., Sur F., Cao F., Gousseau Y. et Morel J.-M., « An a contraario decision method for shape element recognition », dans International Journal of Computer Vision, 2006, à paraître.
17 Desolneux A., Evénements significatifs et application à l'analyse d'images, PhD Thesis, ENS Cachan, 2000.
18 Hurtut T., Dalazoana H., Gousseau Y. et Schmitt F., « Spatial color image retrieval without segmentation using thumbnails and the Earth Mover's Distance », à paraître dans Proceedings of the Conference on Colour in Graphics, Imaging, and Vision, Leeds, England, june 2006.
retour haut de page