The Library

Ising models and multiresolution quad-trees

Tools

Kendall, Wilfrid S. and Wilson, Roland. (2003) Ising models and multiresolution quad-trees. Advances in Applied Probability, Vol.35 (No.1). pp. 96-122. ISSN 0001-8678

Preview

PDF
WRAP_kendall_KendallWilson-2003.pdf - Accepted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (558Kb)

Official URL: http://dx.doi.org/10.1239/aap/1046366101

Abstract

We study percolation and Ising models defined on generalizations of quad-trees used in multiresolution image analysis. These can be viewed as trees for which each mother vertex has 2(d) daughter vertices, and for which daughter vertices are linked together in d-dimensional Euclidean configurations. Retention probabilities and interaction strengths differ according to whether the relevant bond is between mother and daughter or between neighbours. Bounds are established which locate phase transitions and show the existence of a coexistence phase for the percolation model. Results are extended to the corresponding Ising model using the Fortuin-Kasteleyn random-cluster representation.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Percolation (Statistical physics), Ising model, Image analysis
Journal or Publication Title:	Advances in Applied Probability
Publisher:	Applied Probability Trust
ISSN:	0001-8678
Date:	March 2003
Volume:	Vol.35
Number:	No.1
Number of Pages:	27
Page Range:	pp. 96-122
Identification Number:	10.1239/aap/1046366101
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	GR/M75785 (EPSRC)
References:	[1] I. Benjamini and O. Schramm. Percolation beyond Zd, many questions and a few answers. Electronic Communications in Probability, 1:no. 8, 71–82 (electronic), 1996. [2] C. A. Bouman and M. Shapiro. A Multiscale Random Field Model for Bayesian Image Segmentation. IEEE Transactions on Image Processing, 3:162–176, 1994. [3] R. Dobrushin. Coexistence of phase. Theory of Probability and Applications, 17:582–600, 1972. [4] C.M. Fortuin. On the random-cluster model. II. The percolation model. Physica, 58:393–418, 1972. [5] C.M. Fortuin. On the random-cluster model. III. The simple random-cluster model. Physica, 59:545–570, 1972. [6] C.M. Fortuin and P.W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models. Physica, 57:536–564, 1972. [7] D. Geman, S. Geman, C. Graffigne, and P. Dong. Boundary Detection by Constrained Optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12:609–628, 1990. [8] S. Geman and D. Geman. Stochastic relaxation, Gibbs distribution, and Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721–741, 1984. [9] H. Georgii, O. H¨aggstr¨om, and C. Maes. The random geometry of equilibrium phases. In C. Domb and J.L. Lebowitz, editors, Phase Transitions and Critical Phenomena, pages 1–142, London, 2001. Academic Press. [10] G. Gielis and G.R. Grimmett. Rigidity of the interface for percolation and random-cluster models. Journal of Statistical Physics, 109:1–37, 2002. See also arXiv:math.PR/0109103. [11] R.C. Gonzalez and R.E. Woods. Digital Image Processing. Prentice Hall, 2nd edition, 2002. [12] G. Grimmett. Percolation. Springer-Verlag, Berlin, second edition, 1999. [13] G. Grimmett and C. Newman. Percolation in1+1 dimensions. In Disorder in physical systems, pages 167–190. The Clarendon Press Oxford University Press, New York, 1990. [14] O. H¨aggstr¨om, Y. Peres, and R.H. Schonmann. Percolation on transitive graphs as a coalescent process: relentless merging followed by simultaneous uniqueness. In Perplexing problems in probability, pages 69–90. Birkh¨auser Boston, Boston, MA, 1999. [15] Z. Kato, M. Berthod, and J. Zerubia. A Hierarchical Markov Random Field Model and Multi-Temperature Annealing for Parallel Image Classification. Technical Report Tech. Rept. 1938, INRIA, 1993. [16] J-M. Laferte, P. Perez, and F Heitz. Discrete Markov Image Modeling and Inference on the Quadtree. IEEE Transactions on Image Processing, 9:390–404, 2000. [17] S. M. Lavalle and S. A. Hutchinson. A Bayesian Segmentation Methodology For Parametric Image Models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:211–217, 1995. [18] J. Li, R.M. Gray, and R.A. Olshen. Multiresolution Image Classification by Hierarchical Modeling with Two-Dimensional Hidden Markov Models. IEEE Transactions on Information Theory, 46:1826–1840, 2000. [19] S.G. Mallat. Multifrequency Channel Decompositions of Images and Wavelet Models. IEEE Transactions on Acoustics, Speech, Signal Processing, 37(12), December 1989. [20] B. S. Manjunath and R. Chellappa. Unsupervised Texture Segmentation Using Markov Random Field Models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:478–482, 1991. [21] M. Mignotte, C. Collet, P. Perez, and P. Bouthemy. Sonar Image Segmentation Using an Unsupervised Hierarchical MRF Model. IEEE Transactions on Image Processing, 9:1216–1231, 2000. [22] C. Newman and C. Wu. Markov fields on branching planes. Probability Theory and Related Fields, 85(4):539–552, 1990. [23] D. K. Panjwani and G. Healey. Markov Random Field Models For Unsupervised Segmentation Of Textured color Images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:939–954, 1995. [24] C.J. Preston. Spatial birth-and-death processes. Bull. Inst. Internat. Statist., 46:371–391, 1977. [25] J.G. Propp and D.B. Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms, 9:223–252, 1996. [26] R.H. Schonmann. Multiplicity of phase transitions and mean-field criticality on highly non-amenable graphs. Comm. Math. Phys., 219(2):271–322, 2001. [27] C. Series and Y. Sina˘ı. Ising models on the Lobachevsky plane. Comm. Math. Phys., 128(1):63–76, 1990. [28] F. Spitzer. Markov random fields on an infinite tree. The Annals of Probability, 3(3):387–398, 1975. [29] R. Szeliski. Bayesian Modelling of Uncertainty in Low-level Vision. Kluwer Academic Publishers, 1989. [30] R. Wilson and M. Spann. Image Segmentation and Uncertainty. Research Studies Press, 1988. [31] R.G. Wilson and C.T. Li. A class of discrete multiresolution random fields and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(11):Accepted for publication, 2002. [32] C. Wu. Ising models on hyperbolic graphs. J. Statist. Phys., 85(1-2):251– 259, 1996. [33] C. Wu. Ising models on hyperbolic graphs. II. J. Statist. Phys., 100(5- 6):893–904, 2000.
URI:	http://wrap.warwick.ac.uk/id/eprint/9912