Etude comparative des stratégies de segmentation non supervisée en régions par champs de Markov
A Comparative Study of Unsupervised Regions Segmentation Strategies by Markov Random Fields
OPEN ACCESS
This article deals with the important problem of unsupervised segmentation of luminance images based on a markovian relaxation. As these relaxations need important computation times, we have developed a new approach which considerably decreases these times, without modify quality of segmentation results. This approach is based on a split and merge technique. The splitting step allows to decrease, in a important way, the number of entities present in the merging step and, thereafter, computation times.
The method introduced for the splitting step is original; it is based on extraction of second order statistics from cooccurrence matrices. The study shows advantages of these statistics, and compares them to those of one order extracted from grey levels histograms.
The second point developed in this report concerns the merging step . It is accomplished by a markovian relaxation achieved on irregular adjacency graph of regions coming from the splitting step. Many original contributions are presented to estimate the hyper – parameters of the system.
At this level, several results of segmentation on different real images types are presented in order to validate the method. A comparative study on the different strategies of use of markovian relaxation is then led, in a rigorous manner, on synthesis images. It takes into account quality of results as well as computation times. Interesting results of comparison are presented.
Résumé
Cet article aborde le problème de la segmentation non supervisée par champs de Markov d'images de luminance . L'approche développée est de type division-fusion. L'étape de division, qui est une sursegmentation rapide, permet de diminuer de manière importante le nombre de données présentes dans le processus de fusion et, par la suite, les temps de calcul.
La méthode introduite pour la division est basée sur l'extraction de statistiques d'ordre deux à partir des matrices de cooccurrence. L'étude menée montre l'avantage de ces statistiques par rapport à celles, d'ordre un, extraites des histogrammes de niveaux de gris.
Le second point abordé dans cet article concerne la fusion . Elle est réalisée grâce à une modélisation par champs de Markov, à partir du graphe d'adjacence irrégulier de régions issues de la division. Des contributions sont amenées afin d'estimer les hyper-paramètres du système et le nombre d'étiquettes. Plusieurs résultats de segmentation sur différents types d'images réelles sont présentés afin de valider la méthode.
Une étude comparative sur les différentes stratégies d'utilisation de relaxation par champs de Markov est alors menée, de manière rigoureuse, sur des images de synthèse. Cette comparaison est effectuée aussi bien du point de vue qualité des résultats que du point de vue coût algorithmique. Elle permet de montrer les avantages de la méthode proposée: diminuer considérablement les temps de calcul mis pour obtenir les segmentations, tout en n'altérant pas la qualité des résultats de celles-ci.
Segmentation, relaxation, Markov random fields
Mots clés
Segmentation, relaxation, champs de Markov
[1] R . Azencott, C . Graffigne . Non supervised segmentation using multi-leve l markov random fields, In Proc. International Joint Conf on Pattern Recognition, vol . 3, p. 201-205, The Hague, the Netherlands, septembre 1992.
[2] A . Ackah-Miezan, A . Gagalowicz . Discrete models for energy minimizing segmentation, ln International Conference on computer vision, p . 200-207, Berlin, mai 1993.
[31 R . Azencott. Champs markoviens et imagerie, Congrès AFCET. Reconnaissance des formes et intelligence artificielle, p . 1183-1191, 1987.
[4] J . Besag. On the statistical analysis of dirty pictures, vol . 48 of B . J. Royal Stat . Soc., 1986.
[5] C. Bouman, M . Shapiro . A multiscale random field model for bayesian image segmentation, IEEE Trans. Image Processing, 3(2) :162-177, mars 1994.
[6] G . Celeux, J . Diebolt. The SEM algorithm : à probabilistic teacher algorithm derived from the EM algorithm for the Mixture Problem, Computation statistics quaterly, 2 :73-82, 1985 .
[7] J .P. Cocquerez, S . Philipp . Analyse d'images : filtrage et segmentation, collection Enseignement de la physique, Masson, Paris, 1995.
[8] M . Derras, C . Debain, M. Berducat, P. Bonton, J. Gallice. Unsupervised regions segmentation : real time control of an upkeep machine of natural spaces, Ineuropean conference on computer vision, vol . B, p. 207-212, Stockholm, Sweden, mai 1994, vol . B.
[9] H. Derin, H. Elliot. Modeling and segmentation of noisy and texture d'images using gibbs random fields, IEEE trans. pattern analysis and machine intelligence, 9(1) : 39-55, janvier 1987.
[10] A.P. Dempster, N .M. Laird, D .B . Rubin . Maximum likelihood from incomplete Data via the EM Algorithm, J. Roy. Statist. Soc., 39(1) : 1-38, 1977, série B . methodological.
[11] S. Geman, D . Geman . Stochastic relaxation, gibbs distribution, and the Bayesian restoration of images, IEEE trans . pattern analysis and machine intelligence, PAMI 6(6) : 721-741, novembre 1984.
[12] D. Geman, S . Geman, C. Graffigne, P. Dong . Boundary detection by constrained optimization, IEEE trans. pattern analysis and machine intelligence, 12(7) : 609-628, juillet 1990.
[13] R.C. Gonzalez, P. Wintz . Digital image processing, Addison-Wesley publishing comagny, 1987, second edition.
[14] I .L. Herlin, D . Bereziat, G . Giraudon, C. Nguyen, C. Graffigne . Segmentation of Echocardiographic images with Markov random fields, technical report 2424, INRIA, décembre 1994.
[15] S. Houzelle, G . Giraudon . Segmentation en régions par modélisation de matrices de cooccurrence . In AFCET, 8eme congrès de reconnaissance des formes et intelligence artificielle, vol . 3, p . 1177-1183, Lyon Villeurbanne, novembre 1991, tome 3.
[16] F. Heitz, P. Perez, P. Bouthemy. Multiscale minimization of global energy functions in some visual recovery problems; computer vision, graphics and image processing, 59(1) : 125-134, janvier 1994, image understanding.
[17] R. Kara-Falah, P. Bolon . Mesure de dissimilarité entre deux segmentations. In Quatorzième colloque GRETSI, p . 763-766, Juan les Pins, septembre 1993.
[18] C . Kervrann, F. Heitz. A markov random field model based approach to unsupervised texture segmentation using local and global spatial statistics, IEEE trans . image processing, 4(6) : 856-862, 1995.
[19] H .Y. Kim, H.S . Yang . A systematic way for region-based image segmentation based on Markov random fields model, Pattern recognition letters, 15 :969-976, 1994.
[20] S. Lakshmanan, H. Derin . Simultaneous parameter estimation and segmentation of gibbs random fields using simulated annealing, IEEE trans. pattern analysis and machine intelligence, 11(8) : 799-813, août 1989.
[21] B .S. Manjunath, R. Chellappa . Unsupervised texture segmentation using Markov random field models, IEEE trans . pattern analysis and machine intelligence, 13(5) : 478-482, mai 1991.
[22] J.W. Modestino, J . Zhang . A Markov random field model-based approach to image interpretation, IEEE trans . pattern analysis and machine intelligence, 14(6) : 606-615, juin 1992.
[23) P. Perez, F. Heitz . Une approche multi-échelle â l'analyse d'images par champs markoviens, Traitement du Signal, 9(6) : 459-472, 1992.
[24] W. Pieczynski. Champs de Markov cachés et estimation conditionnelle itérative, Traitement du Signal, 11(2) : 141-153, 1994.
[25] N .R . Pal, S .K . Pal . A review of image segmentation technique, pattern recognition 26(9) : 1277-1294, 1993.
[26] C . Rouquet, F. Chausse, R. Chapuis, P. Bonton . Segmentation non-supervisée d'images de scènes routières, une approche multi-critères, Traitement du Signal, 13(3) : 195-208.
[27] L . Vinet, Segmentation et mise en correspondance de régions de paires d'images stéréoscopiques, PhD thesis, Université de Dauphine, Paris IX , juillet 1991.
[28] Y.J . Zhang, J.J . Gerbrands. Segmentation evaluation using ultimate measurement accuracy, image processing algorithms and techniques III, SPIE 1657 : 449-460, 1992.