A Metropolis Sampler for Polygonal Image Reconstruction

Peter Clifford and Geoff Nicholls

Department of Statistics
Oxford University
Oxford OX1 3TG, UK

We show how a stochastic model of polygonal objects can provide a Bayesian framework for the interpretation of colouring data in the plane. We describe a particular model and give a Markov Chain Monte Carlo (MCMC) algorithm for simulating the posterior distribution of the polygonal pattern.

Two important observations arise from our implementation of the algorithm. First, it is computationally feasible to use MCMC to simulate the posterior distribution of a polygonal process for moderately large problems ({\it{ie}}, 10000 data points, w ith polygonal patterns involving around 120 edges). Our implementation, which we would describe as careful, but unsophisticated, produces satisfactory approximations to the mode of the posterior in about 5 minutes on a SUN Sparc 2. Independent samples from the posterior take a few seconds to generate.

The second observation is that the Arak process, a particular type of polygonal process, makes a wonderful debugging tool for testing shape simulation software. This is no mundane observation. Given the usually very complicated nature of such software it is essential to demonstrate that samples genuinely do come from whichever shape distribution is proposed. The Arak process has the advantage that many of its properties can be expressed in precise analytic terms. Computer programmes designed to sample mosaics formed from polygonal shapes can thereby be tested on this process by comparing computer output with exact theoretical expectations.

The paper is available here.