Modèles markoviens d'images et algorithmes d'estimation non linéaire sur le quadarbre

Modèles markoviens d'images et algorithmes d'estimation non linéaire sur le quadarbre

Markov Image Models and Non-Linear Estimation Algorithms on the Quad-Tree

Jean-Marc Laferté Fabrice Heitz  Patrick Pérez 

IRISA/INRA Campus de Beaulieu, 35042 Rennes Cedex

SAT - UPRES-A CNRS 7005 / Université Strasbourg I, ENSPS, Bd Sébastien Brant, 67400 Illkirc h

Corresponding Author Email: 
perez@irisa .fr
Page: 
213-230
|
Received: 
22 July 1997
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

Non-causal Markov Random Field (MRF) models are now widely used for representing images, but are known to yield iterative, often computational intensive, estimation algorithms . In this paper we consider a special class of Markov models which allow to circumvent the latter drawback : MRF attached to the nodes of a quad-tree . The specific structure of these models results in an appealing causality property through scale, which allows the design of exact, non-iterative inference algorithms which are similar to those used in the context of Markov chain models. We first introduce an original extension of the Viterbi algorithm for the exact computation of Maximum A Posteriori (MAP) estimates, along with two other algorithms respectively related to a modified MAP estimator, and to the Marginal Posterior Mode (MPM) estimator. The estimation of the parameters of the model is then addressed with two original Expectation-Maximization (EM)-type algorithms, allowing an unsupervised use of these models. The practical relevance of the different algorithms is investigated in the context of a standard image classification problem, both on synthetic and natural images.

Résumé

Les modèles markoviens spatiaux non causaux utilisés dans le domaine de l'analyse d'images conduisent à des algorithmes d'estimation itératifs, réputés pour leur complexité calculatoire. Dans cet article, nous considérons une classe de processus markoviens hiérarchiques et non linéaires, définis sur le quadarbre . Ces modèles markoviens présentent des propriétés de causalité en échelle qui permettent de construire des algorithmes non itératifs exacts, similaires à ceux existant pour les chaînes de Markov, dans le cas des signaux mono-dimensionnels. Nous présentons ainsi une version originale de l'algorithme de Viterbi sur le quadarbre, associé à une estimation exacte au sens du Maximum A Posteriori (MAP), ainsi que deux autres algorithmes d'estimation, respectivement associés à un critère du MAP modifié et au critère du MPM (mode de la marginale a posteriori) . Deux nouveaux algorithmes EM, permettant une estimation non supervisée sur le quadarbre, sont également introduits pour cette classe de représentations. Les propriétés de ces modèles et algorithmes sont illustrées et comparées, pour un problème simple de classification d'images, sur des images synthétiques et réelles.

Keywords: 

Hierarchical image modeling, causal Markov models, quad-trees, non iterative inference, supervised and unsupervised image classification

Mots clés

Modèles hiérarchiques d'images, modèles markovien causaux, quadarbre, algorithmes non itératifs, classification supervisée et non supervisée

1. Introduction
2. Modèles Markoviens Sur Des Graphes Hiérarchiques
3. Modèle Markovien Sur Le Quadarbre
4. Algorithmes D'estimation Sur Le Quadarbre
5. Algorithmes: EM D"estimation Des Paramètres Du Modèle Sur Le Quadarbre
6. Conclusion
  References

[1] R . Azencott and C . Graffigne, "Non supervised segmentation using multi-level Markov Random Fields," In Int. Conf. Pattern Rec., pp. 111.201–I11.204, The Hague, The Netherlands, Sept . 1992.

[2] M. Basseville, A. Benveniste, K .C. Chou, S .A. Golden, R. Nikoukhah, and A .S . WILLSKY, "Modeling and estimation of multiresolution stochastic processes," IEEE Trans . Information Theory, Vol . 38, No . 2, pp . 766–784, 1992 .

[3] M. Basseville, A . Benveniste, and A .S . Willsky, "Multiscale autoregressive processes - Part I : Schur-Levinson parametrizations," IEEE Trans . Signal Processing, Vol . 40, No . 8, pp . 1915–1934, 1992.

[4] L.E. Baum, T. Petrie, G . Soules and N . Weiss, "A Maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains," IEEEAnn. Math. Stat., Vol . 41, pp. 164–171, 1970.

[5]L.E . Baum, "An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes," Inequalities, Vol . 3, pp . 1–8, 1972.

[6] B . Benmiloud et W. Pieczynski, "Estimation des paramètres dans les chaînes de Markov cachées et segmentation d'images," Traitement du Signal, Vol. 12, No 5 : pages 433–454, 1995 .

[7]J. Besag, "On the statistical analysis of dirty pictures," J. Royal Statist. Soc. , Vol. 48, Serie B, No. 3, pp. 259–302, 1986 .

[8]C. Bouman and M . Shapiro, "A multiscale random field model for Bayesian image segmentation," IEEE Trans. Image Processing, Vol . 3, No. 2, pp . 162–177, 1994 .

[9] G. Celeux , D. Chauveau an d J. Diebolt , "On stochastic versions of the EM algorithm" Technical Report INRIA, No 2514, 1995 .

[10] B . Chalmond, "An iterative Gibbsian technique for reconstruction of m-ary images," Pattern Recognition, Vol . 22, No. 6, pp.747—761, 1989 .

[11] P. Charbonnier, L . Blanc-Féraud, and M . Barlaud, "Noisy image restoration using multiresolution Markov random fields," J. of Visual Corn. and Image Representation, Vol . 3, No . 4, pp . 338—346, 1992.

[12] K .C. Chou, S .A. Golden, and A.S. Willsky, "Multiresolution stochastic models, data fusion and wavelet transforms," Signal Processing, Vol . 34, No. 3, pp . 257—282, 1993 .

[13] H . Derin and P. Kelly, "Discrete-Index Markov-Type Random Processes, " Proc. IEEE, Vol . 77, No 10 : pages 1485—1510, 1989 .

[14] X. Descombes, M . Sigelle, and F. Prêteux, "Estimating Gaussian Markov random field parameters in a non-stationnary framework : application to remote sensing imaging," Submitted to IEEE Trans. Image Proc., 1994.

[15] P.A. Devijver et M . Dekesel, "Champs aléatoires de Pickard et modélisation d'images," Traitement du Signal, Vol . 5, No . 5, pp . 131—150, 1988.

[16] E . Fabre, Traitement du signal multirésolution : conception de lisseurs rapides pour une famille de modèles, Thèse de Doctorat, Université de Rennes 1, France, Dec . 1994.

[17] P.W. Fieguth, W.C. Karl, A .S . Willsky and C . Wunsch, "Multiresolution optimal interpolation and statistical analysis of Topex/Poseidon Satellite Altimetry," IEEE Trans. Geoscience Remote Sensing, Vol. 33, No 2, pages 280—292, March 1995 .

[18] P.W. Fieguth, Application of Multiscale Estimation to Large Multidimensional Imaging and Remote Sensing Problems, PhD thesis, No LIDS-TH-2302, MIT Laboratory of Information and Decision Systems, May 1995 .

[19] G .D . Forney, "The Viterbi Algorithm," Proc. IEEE, Vol. 61, No . 3, pp. 268—278, 1973 .

[20] S . Geman and D . Geman, "Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images," IEEE Trans . Pattern Anal. Machine Intell. , Vol . 6, No . 6, pp. 721—741, 1984 .

[21] B . Gidas, "A renormalization group approach to image processing problems, " IEEE Trans . Pattern Anal. Machine Intell., Vol . 11, No . 2, pp . 164-180, Feb, 1989 .

[22] C . Graffigne, F. Heitz, F. Prêteux, M . Sigelle, and J . Zerubia, "Modèles markoviens hiérarchiques pour l'analyse d'images", Ed. CNRS-GdR TdSI, Novembre 1994 .

[23] C . Graffigne, F. Heitz, P. Pérez, F. Prêteux, M . Sigelle, J . Zerubia, "Hierarchical Markov random field models applied to image analysis : a review," soumis à IEEE Trans. Information Theory, Mars 1997, également : In SPIE Conference on Neural, Morphological and Stochastic Methods in Image and Signal Processing, San Diego, USA, July 1995 .

[24] F. Heitz and P. Bouthemy, "Multimodal estimation of discontinuous optical flow using Markov Random Fields," IEEE Trans. Pattern Anal . Machine Intell., Vol . 15, No . 12, pp . 1217—1232, 1993 .

[25] F. Heitz, P. Pérez, and P. Bouthemy, "Multiscale minimization of global energy functions in some visual recovery problems," CVGIP : Image Under standing, Vol . 59, No. 1, pp . 125—134, 1994 .

[26] Z. Kato, M . Berthod, and J . Zerubia, "A hierarchical Markov random field model and multitemperature annealing for parallel image classification, " Graph. Model and Image Proc., Vol . 58, No . 1, pp . 18—37, 1996.

[27] S. Krishnamachari and R. Chellappa, "Multiresolution Gauss-Markov Random Field Models for Texture Segmentation," IEEE Trans. Image Proc . , Vol . 6, No. 2, pp. 251—267, Feb . 1997.

[28] J .-M. Laferté P. Pérez, and F. Heitz, "Global non-linear multigrid optimization for image analysis tasks," In Proc. Int. Conf. Acoust, Speech, Signa l Processing, pp . 533—536, Adelaide, Australia, April 1994 .

[29] J .-M . Laferté, F. Heitz, P. Pérez, and E . Fabre, "Hierarchical Statistical Models for the Fusion of Multiresolution Image Data," In Proc. Int. Conf. Computer Vision, pp . 908—913, Cambridge, USA, June 1995 .

[30] J .-M. Laferté, F. Heitz and P. Pérez, "A multiresolution EM algorithm for unsupervised image classification," In Proc. Int. Conf. Pattern Recognition ICPR 96, Vienna, Austria, Aug . 1996 .

[31] J .-M . Laferté, Contribution à l'analyse d'images par modèles markoviens sur des graphes hiérarchiques . Application à la fusion de données multirésolutions, Thèse de doctorat, Université de Rennes I, Octobre 1996 .

[32] M .R . Luettgen, W. Karl, and AS . Willsky, "Efficient multiscale regularization with applications to the computation of optical flow," IEEE Trans. Imag e Processing, Vol . 3, No. 1, pp. 41—64, 1992.

[33] M . Luettgen, W. Karl, A . Willsky, and R. Tenney, "Multiscale representations of Markov random fields," IEEE Trans . Signal Processing, Vol . 41, No . 12 , pp . 3377—3395, 1993.

[34] M .R . Luettgen and AS . Willsky, "Likelihood calculation for a class of multiscale stochastic models with application to texture discrimination," IEEE Trans . Image Processing, Vol. 4, No 2 : pages 194—207, 1995 .

[35] J. Marroquin, S . Mitter and T. Poggio, "Probabilistic solution of ill-posed problems in computational vision," J. American Statistical Association, Vol . 82, No 397 : pages 76—89, 1987 .

[36] P. Pérez et F. Heitz "Une approche multiéchelle à l'analyse d'images par champs markoviens," Traitement du Signal, Vol . 9, No . 6, pp . 459—466, 1992 .

[37]P. Pérez and F. Heitz, "Restriction of a Markov Random Field on a Graph and Multiresolution Statistical Image Modeling," IEEE Trans. Information Theory, Vol . 42, No 1 : pages 180—190, 1996.

[38] F. Prêteux and X . Descombes, "Synthèse et analyse de textures par coopération de processus multi-échelles", In Proc. Sème congrès AFCET/INRIA Reconnaisance des Formes et Intelligence Artificielle, pp . 1015—1022, Lyon , France, 1991 .

[39] R .A. Redner and H .F. Walker, "Mixture densities, maximum likelihood and the EM algorithm," SIAM Review, Vol. 26, No. 2, pp . 195—239, April 1984.

[40] C .S . Regazzoni, F. Arduini, and G . Vernazza, "A multilevel GMRF-based approach to image segmentation and restoration," Signal Processing, Vol. 34, No . 1, pp . 43—67, 1993 .

[41] D . Terzopoulos, "Image analysis using multigrid relaxation methods," IEEE Trans. Pattern Anal. Machine Intell ., Vol . 8, No . 2, pp . 129—139, 1986.

[42] G .C . Wei and M .A . Tanner, "A Monte-Carlo implementation of the EM algorithm and the poor man's data augmentation algorithms," J. American Stat. Assoc., Vol. 85, pp . 699-704, 1990 .

[43] J . Whittaker . Graphical Models in Applied Multivariate Statistics . Wiley, 1990 .

[44] J. Zhang, J .W. Modestino and D .A . Langan, "Maximum-Likelihood parameter estimation for unsupervised stochastic model-based image segmentation, " IEEE Trans . Image Proc ., Vol . 3, No 4, pp. 404—420, July 1994.