Parameter Estimation in Hidden Markov Chains and Segmentation of Images. Estimation des Paramètres dans les Chaînes de Markov Cachées et Segmentation D'Images

Parameter Estimation in Hidden Markov Chains and Segmentation of Images

Estimation des Paramètres dans les Chaînes de Markov Cachées et Segmentation D'Images

Btissam Benmiloud Wojciech Pieczynski 

Département Signal et Image Institut National des Télécommunications 9, rue Charles Fourier 91011 Évry cedex

Page: 
433-454
|
Received: 
30 May 1994
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

Our study deals with the parameter estimation problem of Hidden Marko v Chain models and with unsupervised Bayesian image segmentation . We propose two new estimation algorithms obtained from Iterative Conditional Estimation (ICE) and Stochastic Estimation Maximisation (SEM), denoted by MICE and MSEM respectively, and show their competitiveness with respect to the Estimation Maximisation (EM) algorithm in different situations of chain homogeneity an d noise. We then study three unsupervised chain restauration algorithms, obtained by adding EM, MICE and MSEM respectively to the Maximum Posterior Mod e (MPM) restauration method. The transformation of bi-dimentional process to mono-dimentional ones using Peano curves makes possible the application of these three methods to the problem of unsupervised statistical image segmentation . Doing so, we obtain faster methods than those obtained by models using hidden Markov random fields and we show that the loss of effectiveness, due to the poore r adequacy of the model, is acceptable in general. On the other hand, the flexibility of our modeling allows the conception of numerous unsupervised spatio-tempora l segmentation methods. We propose three of them and present results showing thei r application to the segmentation of a sequence of real images.

Résumé

Notre étude traite de l'estimation des paramètres dans les chaînes de Marko v cachées et de la segmentation statistique non supervisée d'images . Nous proposons deux algorithmes originaux d'estimation obtenus à partir des méthode s Iterative Conditional Estimation (ICE) et Stochastic Expectation Maximisation (SEM), notés MICE et MSEM respectivement, et montrons leur compétitivité vis-à-vis de l'algorithme Expectation Maximisation (EM) dans différents cas d'homogénéité et de bruitage des chaînes . L'étude du comportement des trois algorithmes de restauration non supervisée des chaînes obtenus par l'adjonction à la méthode Mode de la Marginale a Posteriori (MPM) des algorithmes EM, MICE, MSEM respectivement est ensuite proposée . La transformation des processus bidimentionnels en processus mono-dimentionnels par le parcours de Peano rend possible l'application de ces algorithmes au problème de la segmentation statistique non supervisée d'images . On obtient ainsi des méthodes plus rapides que celles utilisant des modélisations par champs de Markov cachés et nous montron s que la perte de l'efficacité est, en général, acceptable. La souplesse de notre modélisation permet par ailleurs la conception de nombreux algorithmes de segmentatio n statistique non supervisée spatio-temporelle d'images. Nous en proposons trois et présentons les résultats de leur application à la segmentation d'une séquence d'images réelles.

Keywords: 

Hidden Markov chains, parameter estimation, unsupervised segmentation, spatio-temporal segmentation, expectation-maximisation, iterative conditional estimation, stochastic expectation-maximisation, backward-forward algorithm.

Mots clés

Chaînes de Markov cachées, estimation des paramètres, segmentation non supervisée, segmentation spatio-temporelle, expectation-maximisation, iterative conditional estimation, stochastic expectation-maximisation, backwardforward algorithm.

1. Introduction
2. Les Chaînes de Markov Cachées
3. Algorithmes de Reconnaissances
4. Algorithmes d'Estimation des Paramètres du Modèle
5. Étude de l'Efficacité des Algorithmes EM, MICE, MSEM
6. Restauration Non Supervisée dans le Cas des Chaînes Simulées
7. Segmentation Non Supervisée d'Images
8. Segmentation Non Supervisée Spatio Temporelle d'Images
9. Conclusion
  References

[1] K. Abend, T.J. Harley, L.N. Kanal, «Classification of binary random patterns », IEEE Transactions on Information Theory, Vol. IT-11, N°4,1965. 

[2] M. Avila, C. Olivier, T. Paquet, Y. Lecoutier, « Procédure de reconnaissance de l'écriture manuscrite, basée sur deschaînes de Markov cachées, etappliquéeà un vocabulaire limité », Actes de Quatorzième Colloque GRETSI 93, Juansles–Pins, France, 1993, pp. 803-806.

[3]Azencott R. Ed., « Simulated annealing : Parallelization techniques », Wiley, 1992. 

[4] L.E. Baum, T. Petrie, G. Soules, N. Weiss, «A maximization technique occuring in the statstical analysis of probabilistic functions of Markov chains », Ann, Math. Statistic., 41, 1970, pp. 164-171. 

[5] B. Benmiloud, A. Peng, W. Pieczynskì, « Estimation conditionnelle itérative dans les chaînes de Markovcachéeset segmentation statistiquenonsupervisée d'images », Actes de Quatorzième Colloque GRETSI 93, Juans–les–Pins, France, 1993, pp. 105-108. 

[6] B. Benmiloud, « Chaînes de Markov cachées et segmentation statistique non supervisée de séquence d'images », Thèse, Université Paris VII, 1994. 

[7] A. Benveniste, M. Métivier, B. Priouret, « Algorithmes adaptatifs et approximations stochastiques », Techniques stochastiques, Masson, Paris, 1987. 

[8] J. Besag, « On the statistical analysis of dirty pictures », Journal of the Royal Statistical Society, Series B, 48, 1986, pp. 259-302. 

[9] R. Boite, M. Kunt, « Traitement de la parole », Presses Polytechniques Romandes, 1987.

[10] P. Bouthemy, « Modèles et méthodes pourl'analyse du mouvement dans une séquence d'images », Technique et Science Informatique, Vol. 7, N°6, 1988, pp. 527-543.

[11] P. Bouthemy, P. Lalande, « Motion detection in an image sequence using Gibbs distribution », Actes d'ICASSP'89, Glasgow, 1989, pp. 1651-1654. 

[12] B. Braathen, W. Pieczynski, P. Masson, « Global and local methods of unsupervised Bayesian segmentation of images », Machine Graphics and Vision, Vol. 2, N°1, 1993, pp. 39-52. 

[13] H. Caillol, A. Hillon, W. Pieczynski, « Fuzzy random fields and unsupervised image segmentation », IEEE Transactions on GRS, Vol. 31, N°4, 1993, pp. 801-810. 

[14] G. Celeux, J. Diebolt, « L'algorithme SEM : un algorithme d'apprentissage probabiliste pour la reconnaissance de mélanges de densités », Revue de Statistique Appliquée, Vol. 34, N°2, 1986. 

[15] B . Chalmond, « An iterative Gibbsian technique for reconstruction of m—ary images », Pattern Recognition, Vol. 22, N°6, 1989, pp . 747-761. 

[16] M.M. Dempster, N.M. Laird, D.B. Rubin, «Maximum likelihood from incomplete data via the EM algorithm », Journal of the Royal Statistical Society, Series B, 39, 1977, pp. 1-38. 

[17] P.A. Devijver, « Baum's forward—backward algorithm revisited », Pattern Recognition Letters, 3, 1985, pp. 369-373.

[18] P.A. Devijver, M. Dekesel, «Champs aléatoires de Pickard et modélisation d'images digitales », Traitementdu Signal, Vol. 5, N°5, 1988, pp. 131-150. 

[19] M. Emsalem, H. Caillol, P. Obvié, G. Carnat, W. Pieczynski, « Fast unsupervised statistical image segmentation », IEEE International Geoscience and Remote Sensing Symposium (IGARSS 92), Houston, Texas, 1992. 

[20] G.D. Fornay, « The Viterbi algorithm », Proceedings of the IEEE, Vol. 61, N°3, 1973, pp. 268-277. 

[21] S. Geman and D. Geman, « Stochastic relaxation, Gibbs distributions and the Bayesian restoration ofimages »,IEEE Transactions on PAMI, Vol.PAMI—6, N°6, 1984, pp. 721-741 . 

[22] X. Guyon, «Champs aléatoires sur un réseau », Collection Techniques Stochastiques, Masson, Paris, 1993. 

[23] F. Heitz, P. Bouthemy, « Motion estimation and segmentation using a globa l bayesian approach », IEEE Actes de ASSP'90, Albuquerque, 1990. 

[24] F. Heitz, P. Bouthemy, «Estimation et segmentation du mouvement : approche Bayésienne et modélisation Markovienne des occlusions », Actes de la 7ème Conf . AFCET/RFIA, Paris, 1989, pp. 1359-1368. 

[25] A. Hillion, « Les approches statistiques pour la reconnaissance des images de télédétection », Atti della XXXVI Riunione Scientifica, SIS, Vol. 1, 1992, pp. 287-297.

[26] S. Lakshmanan, H. Derin, « Simultaneous parameter estimation and segmentation ofGibbs random fields using simulated annealing », IEEE Transactions on PAMI, Vol. 11, N°8, 1989, pp. 799-813. 

[27] P . Lalande, «Détection du mouvement dans une séquence d'images selo n une approche markovienne ; Application à la robotiquesous—marine », Thèse, Université de Rennes I, 1990. 

[28] N. Marhic, P. Masson, W. Pieczynski, «Mélange de lois et segmentation non supervisée des données SPOT », Statistique et Analyse des Données, Vol. 16, No2, 1991, pp. 59-79.

[29] J.L. Marroquin, S. Mittle, T. Poggio, «Probabilistic solution of ill-pose d problems in computational vision », Journal of the American Statistical Association, Vol. 82, 1987, pp. 76-89. 

[30] P. Masson, W. Pieczynski, « SEM algorithm and unsupervised statistical segmentation ofsatellite images »,IEEE Transactions on GRS, Vol. 34, N°3, 1993, pp. 618-633. 

[31] A. Peng, W. Pieczynski, « Adaptative mixture estimation and unsupervised contextual Bayesian image segmentation », Graphical Models and Image Processing, Vol. 57, N°5, 1995, pp. 389-399. 

[32] W. Pieczynski, « Estimation of context in random fields », Journal ofApplied Statistics, Vol. 16, N°2, 1989, pp. 283-290. 

[33] W. Pieczynski, « Statistical image segmentation », Machine Graphies and Vision, Vol. 1, N°1/2, 1992, pp. 261-268. 

[34] W. Pieczynski, « Champs de Markov cachés et estimation conditionnelle itérative », Traitement du Signal, Vol. 11, N°2, 1994, pp. 141-153. 

[35] W. Pieczynski, J.-M. Cahen, « Champs de Markov flous cachés et segmentation d'images », Revue de Statistique Appliquée, Vol. 42, N°3, 1994, pp. 1331 . 

[36] H.C. Quelle,J.-M.Boucher, W. Pieczynski, « Local parameter estimation and unsupervised segmentation of SARimages », Actes de IGARSS '92, Houston, Texas, 1992.

[37] W. Qian,D.M.Titterington, « On the use of Gibbs Markov chain models in the analysis of images based on second—order pairwise interactive distributions » , Journal of Applied Statistics, Vol. 16, N°2, 1989, pp. 267-282.

[38] J. Quinqueton, « Le concept de dimension intrinsèque en reconnaissance des formes », Thèse, Université Paris VI, 1981.

[39] L.R. Rabiner, S.E. Levinson, M.M. Sondhi, « On the use of hidden Markov model for speaker—Independent recognition of isolated words from o f medium—size vocabulary »,AT&T Bell Laboratory Technical Journal, 1984, pp. 627-642. 

[40] L.R. Rabiner, « A tutorial on hidden Markov models and selected applications in speech recognition », Proceedings of IEEE, Vol. 77, No2, 1989, pp. 257286. 

[41] W. Skarbek, «Generalized Hilbert scan in image printing », Theoretical Foundations of Computer Vision, R. Klette et W. G. Kropetsh Ed., Akademik Verlag, 1992, pp. 45-57. 

[42] J. Tilton, S. Vardeman, P. Swain, « Estimation of context for statistical classification of multispectral image data », IEEE Transactions on GRS, GE— 20, 1982, pp. 445-452. 

[43] Y. He, A. Kundu, « 2—D Shape Classification Using Hidden Markov Model » , IEEE Transactions on PAMI, Vol. 13, N°11, 1991, pp. 1172-1184. 

[44] J.F. Yao, « Segmentation bayésienne d'images : comparaisons de méthodes contextuelles et globales », Cahier du Centre d'Études et de Recherches, Op.30 (4), 1989, pp. 269-290. 

[45] L. Younes, « Parametric inference for imperfectly observed Gibbsian fields » , Probability Theory and Related Fields, 82, 1989, pp. 625-645.