Gaudron, Isabelle Rate of convergence of the Swendsen-Wang dynamics in image segmentation problems: A theoretical and experimental study. (English) Zbl 0931.60095 ESAIM, Probab. Stat. 1, 259-284 (1997). Summary: We study the convergence rate of the Swendsen-Wang dynamics towards its equilibrium law, when the energy belongs to a large family of energies used in image segmentation problems. We compute the exponential equivalents of the transitions which control the process at low temperature, as well as the critical constant which gives its convergence rate. We give some theoretical tools to compare this dynamics with Metropolis, and develop an experimental study in order to calibrate both dynamics performances in image segmentation problems. Cited in 1 Document MSC: 60K99 Special processes 60J27 Continuous-time Markov processes on discrete state spaces Keywords:Metropolis relaxation; Swendsen-Wang dynamics; image segmentation problems PDFBibTeX XMLCite \textit{I. Gaudron}, ESAIM, Probab. Stat. 1, 259--284 (1997; Zbl 0931.60095) Full Text: DOI EuDML References: [1] BESAG, J. and Green, P. J. ( 1993). Spatial statistics and bayesian computation. J. R. Statis. Soc. B 55 25-37. Zbl0800.62572 MR1210422 · Zbl 0800.62572 [2] BESAG, J., GREEN, P. J., HIGDON, D. and MENGERSEN, K. ( 1995). Bayesian computation and stochastic systems. Statistical Science 10 3-66. Zbl0955.62552 MR1349818 · Zbl 0955.62552 [3] DEUSCHEL, J.-D. and MAZZA, C. ( 1994). L2 convergence of time nonhomogeneous Markov processes: I. Spectral estimates. Ann. Appl. Prob. 4 1012-1056. Zbl0819.60063 MR1304771 · Zbl 0819.60063 [4] DIACONIS, P. and STROOCK, D. ( 1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1 36-61. Zbl0731.60061 MR1097463 · Zbl 0731.60061 [5] FREIDLIN, M. I. and WENTZELL, A. D. ( 1984). Random perturbations of dynamical systems, 260, Springer-Verlag. Zbl0522.60055 MR722136 · Zbl 0522.60055 [6] GAUDRON, I. and TROUVÉ, A. ( 1996). Fluctuations of empirical means at low temperature for finite Markov chains with rare transitions in the general case. Preprint CMLA, Cachan, France. MR1633578 · Zbl 0907.60029 [7] GEMAN, D. ( 1990). Ch. Random fields and inverse problems in imaging. Lectures on Probability Theory and Statistics. XVIIIème École d’Eté de Probabilités de Saint-Flour, Lecture Notes in Mathematics, Springer-Verlag. Zbl0718.60119 MR1100283 · Zbl 0718.60119 [8] GEMAN, D., GEMAN, S., and GRAFFIGNE, C. ( 1986). Locating texture and object boundaries, in Pattern Recognition Theory and Applications, Devijver ed., NATO ASI, Springer-Verlag, Heidelberg. · Zbl 0665.68067 [9] GRAFFIGNE, C. ( 1987). Experiments in texture analysis and segmentation. PhD thesis, Brown University. [10] GRAY, A. ( 1994). Simulating posterior Gibbs distributions: A comparison of the Swendsen-Wang and Gibbs sampler methods. Statistics and Computing A 189-201. [11] HERLIN, I., NGUYEN, C., and GRAFFIGNE, C. ( 1992). Stochastic Segmentation of ultrasound images, in 11th IAPR International Conference on Pattern Recognition, IEEE Computer Society Press, 1 289-292. [12] HURN, M. ( 1995). On the use of auxiliary variables in Markov chain Monte-Carlo methods, Tech. Rep. #95-07, Statistics Group at the University of Bath, School of Mathematical Sciences, University of Bath, Bath, BA2 7AY. [13] HURN, M. and JENNISON, C. ( 1993). Multiple-site updates in maximum a posteriori and marginal posterior modes image estimation, in Advances in Applied Statistics: Statistics and Images, Mardia and Kanji eds., Oxford - Carfax, 155-186. [14] MARTINELLI, F. ( 1992). Dynamical analysis of low-temperature Monte-Carlo cluster algorithms. J. Stat. Physics 66 1245-1276. Zbl0925.82181 MR1156404 · Zbl 0925.82181 [15] MARTINELLI, F., OLIVIERI, E., and SCOPPOLA, E. ( 1991). On the Swendsen-Wang dynamics. I. Exponential convergence to equilibrium. J. Stat. Physics 62 117-133. Zbl0739.60097 MR1105259 · Zbl 0739.60097 [16] MARTINELLI, F., OLIVIERI, E., and SCOPPOLA, E. ( 1991). On the Swendsen-Wang dynamics. II. Critical droplets and homogeneous nucleation at low temperature for the two-dimensional Ising models. J. Stat. Physics 62 117-133. Zbl0739.60097 MR1105259 · Zbl 0739.60097 [17] SOKAL, A. D.( 1989). Monte-Carlo methods in statistical mechanics: Foundations and new algorithms. Cours de troisième cycle de la physique en Suisse Romande, Lausanne. · Zbl 0890.65006 [18] SWENDSEN, R. H. and WANG, J. S. ( 1987). Nonuniversal critical dynamics in Monte-Carlo simulation. Physical Review Letters 58 86-88. [19] WANG, J. ( 1994). Multiscale Markov fields: applications to the segmentation of textured images and film fusion, PhD thesis, Orsay University. [20] WANG, J. ( 1997). Stochastic relaxation on partitions with connected components and its application to image segmentation. Preprint CMLA, Cachan, France. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.