Segmentation and motion analysis using polygonal Markov fields

This proposal concerns many-colour polygonal Markov fields. Realisations of such fields, introduced by Arak and Surgailis (1989), partition the plane in polygonal cells such that no two adjacent cells share the same colour. The boundaries of the cells form a planar graph. The appeal of this class of models lies in its special properties: (i) an explicit formula for the partition function, (ii) consistency, (iii) a spatial Markov property, (iv) Poisson sections, and (v) a dynamic representation as the coloured trajectory of a one-dimensional particle system. However, despite their elegance, polygonal Markov fields have not been studied much and applied even less. Recently, the sub-class of bi-colour fields with V-shaped vertices only has received some attention, both from a theoretical point of view (Van Lieshout and Schreiber, 2007; Nicholls, 2001; Schreiber, 2005, 2006)and in the context of foreground-background segmentation in image analysis (Kluszczynski et al., 2005, 2007; Schreiber and Van Lieshout, 2007). The time is ripe to turn to many-colour polygonal Markov fields with vertices of degrees two and higher. Our objectives are three-fold. Firstly, we will focus on the design of efficient simulation algorithms for Gibbsian modifications of general polygonal Markov fields. Next, two important image interpretation problems will be tackled: classification/segmentation of still images, and depth map calculation from video frames by tracking T-junctions between a variable number of moving regions. Ideas and tools from stochastic geometry and hierarchical Bayesian modelling will play an important role.