Skip to main content

Quad-Trees, Multiresolution image analysis, and boundaries

At MSc level / first year of PhD, it is proposed that the student assimilate basic material concerning CFTP and also the quad-tree analysis of Kendall and Wilson (2003), and then construct and implement a CFTP algorithm to segment ("remove noise from") a typical quad-tree-like image. The work programme would be:

  1. Read up CFTP from Kendall (2015) also referring to Kendall (2005) and Huber (2015).
  2. Use the template provided by Kendall (2015) to construct one's own implement of CFTP for segmentation of an image using Ising model. Kendall (2015) uses R: the implementation should use a language such as Python, for which it is relatively easy to obtain speed-ups using (for example) numerical packages.
  3. Read up quad-trees from Kendall and Wilson (2003), and amend the CFTP-Ising construction to segment using the Ising quad-tree model.
  4. Investigate optimal settings of parameters, behaviour at object boundaries. Compare reconstruction speeds for original and quad-tree Ising models. Consider effect of conditioning at all levels using quad-tree decimation of original image.

This could lead on to a PhD in many possible different ways, depending on the inclinations and strengths of the student:

[Theory] Adapt Finch (2010) work to establish weak limit for small lambda of Ising quad-tree conditioned on having an interface.
[Theory] Develop Finch (2010) work to understand interfaces, using estimates analogous to those of Gielis and Grimmett (2002).
[Implementation] Study "adaptive-resolution CFTP", in which one does just enough work to capture reconstruction at desired level of detail (which might even depend on image itself!). This is a new idea, based on work by Ambler and Silverman (2010).
[Theory] Study applicability of ideas to generalize the so-called "mass transport" principle to the quad-tree case.
[Implementation] Consider evidence for "cut-off" for Ising quad-tree, based on the theoretical work of Lubetzky and Sly (2014).


1. Ambler, G. K., & Silverman, B. W. (2010). Perfect simulation using dominated coupling from the past with application to area-interaction point processes and wavelet thresholding. In N. H. Bingham & C. M. Goldie (Eds.), Probability and Mathematical Genetics: Papers in Honour of Sir John Kingman (pp. 64–90). Cambridge: Cambridge University Press.
2. Finch, S. (2010). The Random Cluster Model on the Tree. PhD Thesis, Warwick.
3. Gielis, G., & Grimmett, G. R. (2002). Rigidity of the interface in percolation and random-cluster models. Journal of Statistical Physics, 109(1-2), 1–37.
4. Huber, M. (2015). Perfect Simulation. Boca Raton: Chapman and Hall/CRC.
5. Kendall, W. S. (2005). Notes on Perfect Simulation. In Wilfrid S Kendall and F. Liang and J.-S. Wang (Ed.), Markov chain Monte Carlo: Innovations and Applications (pp. 93–146). Singapore: World Scientific.
6. Kendall, W. S. (2015). Introduction to CFTP using R. In V. Schmidt (Ed.), Stochastic Geometry, Spatial Statistics and Random Fields (pp. 405–439). Springer.
7. Kendall, W. S., & Wilson, R. G. (2003). Ising models and multiresolution quad-trees. Advances in Applied Probability, 35(1), 96–122.
8. Lubetzky, E., & Sly, A. (2014). Universality of cutoff for the Ising model. arXiv, 1407.1761, 24–27.