Evidential Markov Chains and Trees with Applications to Non Stationary Processes Segmentation
Chaînes et Arbres de Markov Évidentiels avec Applications À la Segmentation des Processus Non Stationnaires
OPEN ACCESS
The triplet Markov chains (TMC) generalize the pairwise Markov chains (PMC), and the latter generalize the hidden Markov chains (HMC).Otherwise,in an HMC the posterior distribution of the hidden process can be viewed as a particular case of the so called "Dempster's combination rule" of its prior Markov distribution p with a probability q defined from the observations.When we place ourselves in the theory of evidence context by replacing p by a mass function m,the result of the Dempster's combination of m with q generalizes the conventional posterior distribution of the hidden process.Although this result is not necessarily a Markov distribution,it has been recently shown that it is a TMC, which renders traditional restoration methods applicable.Further,these results remain valid when replacing the Markov chains with Markov trees.We propose to extend these results to Pairwise Markov trees. Further,we show the practical interest of such combination in the unsupervised segmentation of non stationary hidden Markov chains,with application to unsupervised image segmentation.
Résumé
Les chaînes de Markov Triplet (CMT) généralisent les chaînes de Markov Couple (CMCouple),ces dernières généralisant les chaînes de Markov cachées (CMC). Par ailleurs,dans une CMC la loi a posteriori du processus caché,qui est de Markov,peut être vue comme une combinaison de Dempster de sa loi a priori p avec une probabilité q définie à partir des observations. Lorsque l'on se place dans le contexte de la théorie de l'évidence en remplaçant p par une fonction de masse m,sa combinaison de Dempster avec q généralise ainsi la probabilité a posteriori. Bien que le résultat de cette fusion ne soit pas nécessairement une chaîne de Markov,il a été récemment établi qu'il est une CMT,ce qui autorise les divers traitements d'intérêt. De plus, les résultats analogues restent valables lorsque l'on généralise les différentes chaînes de Markov aux arbres de Markov. Nous proposons d'étendre ces résultats aux arbres de Markov Couple,dans lesquels la loi du processus caché n'est pas nécessairement de Markov. Nous montrons également l'intérêt pratique de ce type de fusion dans la segmentation non supervisée des chaînes de Markov non stationnaires,avec application à la segmentation d'images.
Evidential Markov chains, evidential Markov trees, Bayesian image segmentation, Expectation-Maximization, Dempster's combination rule, theory of evidence, pairwise Markov chains, triplet Markov chains, non stationary hidden Markov processes.
Mots clés
Chaînes de Markov évidentielles,arbres de Markov évidentiels,segmentation bayésienne d'images,EspéranceMaximisation,règle de combinaison de Dempster,théorie de l'évidence,chaînes de Markov couple,chaînes de Markov triplet,processus de Markov cachés non stationnaires.
[1] A. APPRIOU, Probabilités et incertitude en fusion de données multisenseurs, Revue Scientifique et Technique de la Défense, (11):27-40, 1991.
[2] A. BENDJEBBOUR, Y. DELIGNON, L. FOUQUE, V. SAMSON, and W. PIECZYNSKI, Multisensor images segmentation using Dempster-Shafer fusion in Markov fields context, IEEE Trans. on Geoscience and Remote Sensing, 39(8):1789-1798, 2001.
[3] B. BENMILOUD and W. PIECZYNSKI, Estimation des paramètres dans les chaînes de Markov cachées et segmentation d'images, Traitement du Signal, 12(5):433-454, 1995.
[4] N. BRUNEL and W. PIECZYNSKI, Unsupervised signal restoration using copulas and pairwise Markov chains, In IEEE Workshop on Statistical Signal Processing (SSP 2003), Saint Louis, Missouri, September 28-October 1 2003.
[5] C. CARINCOTTE, S. DERRODE, G. SICOT, and J.-M. BOUCHER, Unsupervised image segmentation based on a new fuzzy HMC model, In ICASSP'04, Montreal, Canada, May 17-21 2004.
[6] B. R. COBB and P. P. SHENOY, A Comparison of Methods for Transforming Belief Function Models to Probability Models, volume 2711, Symbolic and Quantitative Approaches to rensoning with uncertainty – Lecture Notes in Artificial Intelligence, SpringerVerlag, 2003.
[7] C. COLLET, J.-N. PROVOST, P. ROSTAING, P. PÉREZ, and P. BOUTHEMY, Segmentation bathymétrique d'images multispectrales SPOT, Traitement du Signal, 18(1):1-16, 2001.
[8] M. DANG and G. GOVAERT, Spatial fuzzy clustering using EM and Markov random fields, InternationalJournal of System Research and Information Science, 8(4):183-202, 1998.
[9] T. DENOEUX,Analysis of evidence-theoristic decision rules for pattern classification, Pattern Recognition, 30(7), 1997.
[10] S. DERRODE and W. PIECZYNSKI, Signal and image segmentation using pairwise Markov chains, IEEE Trans. on Signal Processing, 52(9):2477-2489, 2004.
[11] F. DESBOUVRIES and W. PIECZYNSKI, Modèles de Markov triplet et filtrage de Kalman, CRAS, 336(8):667-670, 2003, Serie I.
[12] F. DESBOUVRIES and W. PIECZYNSKI, Particle filtering with pairwise Markov processes, In ICASSP'03, Hong-Kong, 2003.
[13] S. FOUCHER, M. GERMAIN, J.-M. BOUCHER, and G. B. BENIÉ, Multisource classification using ICM and Dempster-Shafer theory. IEEE Trans. on IM, 51(2):277-281, 2002.
[14] L. FOUQUE, A. APPRIOU, and W. PIECZYNSKI, An evidential markovian model for data fusion and unsupervised image classification, Proceedings of 3rd International conference on Information Fusion, FUSION 2000 volume 1, pages TuB4-25 - TuB4-31, Paris, France, July 10th-13th 2000.
[15] N. GIORDANA and W. PIECZYNSKI, Estimation of generalized multisensor hidden Markov chains and unsupervised image segmentation, IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(5):465-475, 1997.
[16] S. L. HÉGARAT-MASCLE, I. BLOCH, and D. VIDAL-MADJAR, Introduction of neighborhood information on evidence theory and application to data fusion of radar and optical images with partial cloud cover, Pattern Recognition, 31(11):1811-1823, 1998.
[17] F. JANEZ and A. APPRIOU. Theory of evidence and non-exhaustive frames of discernment : plausibilities correction methods, International Journal of Approximate Reasoning, (18):1-19, 1998.
[18] F. V. JENSEN, An Introduction to Bayesian Networks, UCL Press, 2000.
[19] J.-M. LAFERTÉ, P. PÉREZ, and F. HEITZ, Discrete Markov image modeling and inference on the quadtree, IEEE Trans. on Image Processing, 9(3):390- 404, 2000.
[20] P. LANCHANTIN and W. PIECZYNSKI,Arbres de Markov triplet et théorie de l'évidence, In Actes du colloque GRETSI'03, Paris, France, 8-11 Septembre 2003.
[21] P. LANCHANTIN and W. PIECZYNSKI, Unsupervised non stationary image segmentation using triplet Markov chain, In Advanced Concepts for Intelligent Vision Systems (ACIVS 2004), Brussels, Belgium,August 31-September 3 2004.
[22] P. LANCHANTIN and W. PIECZYNSKI, Unsupervised restoration of non stationary Markov chain using evidential priors, IEEE Trans. on Signal Processing, September 2004, accepted.
[23] E. MONFRINI, J. LECOMTE, F. DESBOUVRIES, and W. PIECZYNSKI, Image and signal restoration using pairwise Markov trees, In IEEE Workshop on Statistical Signal Processing (SSP 2003), Saint Louis, Missouri, September 28-October 1 2003.
[24] P. PÉREZ, Markov random fields and images, CWI Quarterly, 11(4):413-437, 1998.
[25] P. PÉREZ, Modèles et algorithmes pour l'analyse probabiliste des images, Habilitation à diriger des recherches de l'Université de Rennes 1,D écembre 2003.
[26] P. PÉREZ, A. CHARDIN, and J.-M. LAFERTÉ, Noniterative manipulation of discrete energy-based models for image analysis, Pattern Recognition, 33(4):573-586, 2000.
[27] W. PIECZYNSKI, Triplet Markov chains and theory of evidence,submitted.
[28] W. PIECZYNSKI, Arbres de Markov couple, CRAS, 335:79-82, 2002.
[29] W. PIECZYNSKI, Chaînes de Markov triplet, CRAS, 335(I):275-278, 2002.
[30] W. PIECZYNSKI, Arbres de Markov triplet et fusion de DempsterShafer, CRAS, 336:869-872, 2003, Serie I, ISSUE 10.
[31] W. PIECZYNSKI, Modèles de Markov en traitement d'images, Traitement du Signal, 20(3):255-278, 2003.
[32] W. PIECZYNSKI, Pairwise Markov chains, IEEE Trans. on Pattern Analysis and Machine Intelligence, 25(5):634-639, 2003.
[33] W. PIECZYNSKI, D. BENBOUDJEMA, and P. LANCHANTIN, Statistical image segmentation using triplet Markov fields, In SPIE's International Symposium on Remote Sensing, pages 92-101, Crete, Greece, September 22-27 2002.
[34] W. PIECZYNSKI and A.-N. TEBBACHE, Pairwise Markov random fields and segmentation of textured images, Machine Graphics and Vision, 9(3):705-718, 2000.
[35] J.-N. PROVOST, C. COLLET, P. ROSTAING, P. PÉREZ, and P. BOUTHEMY, Hierarchical Markovian segmentation of multispectral images for reconstruction of water depth maps, Computer Vision and Image Understanding, 93(2):155-174, 2004.
[36] S. RUAN, B. MORETTI, J. FADILI, and D. BLOYET, Fuzzy Markovian segmentation in application of magnetic resonance images, Computer Vision and Image Understanding, 85(1):54-69, 2002.
[37] F. SALZENSTEIN and W. PIECZYNSKI, Parameter estimation in hidden fuzzy Markov random fields and image segmentation, Graphical Models and Image Processing, 59(4):205-220, 1997.
[38] F. SALZENSTEIN and W. PIECZYNSKI, Sur le choix de méthode de segmentation statistique d'images, Traitement du Signal, 15(2):119-128, 1998.
[39] G. SHAFER, A mathematical theory of evidence, Princeton University Press, Princeton, 1976.
[40] P. SMETS, Belief functions: the disjunctive rule of combination and the generalized bayesian theorem, International Journal of Approximate Reasoning, 9:1-35, 1993.
[41] J. J. SUDANO, Equivalence between belief theories and naïve Bayesian fusion for systems with independent evidential data, In Proceeding of The Sixth International Conference on Information Fusion, 2003.
[42] J. WHITTAKER, Graphical models in applied multivariate statistics, Wiley, 1990.
[43] A. S. WILLSKY, Multiresolution Markov models for signal and image processing, Proceedings of IEEE, 90(8):1396-1458, 2002.
[44] G. WINKLER, Image analysis, random fields and Markov Chain Monte Carlo Methods: a mathematical introduction, Springer, 2003.
[45] R. R. YAGER, J. KACPRZYK, and M. FEDRIZZI, Advances in the Dempster-Shafer theory of evidence, Wiley, 1994.