Image Segmentation by Data Driven Markov Chain Monte Carlo

Z. Tu and S. C. Zhu, "Image Segmentation by Data-Driven Markov Chain Monte Carlo",  
 PAMI, vol.24, no.5, pp. 657-673, May, 2002. A short version appeared in ICCV 2001. (co-authored with H. Shum)

DMCMC is a follow-up work of region competition [Zhu and Yuille, 1996]. DDMCMC contributes in the following aspects:

1. It makes the split-merge process reversible, thus the algorithm form ergodic Markov chain searching in the heterogeneously structured solution space, and it achieves global optimization independent of initial segmentation conditions.

2. We regard image segmentation as a computing process Not a vision task. Thus the algorithm should run endlessly and output many distinct solutions, i.e. the more it looks, the more it sees. This is consistent with human attention at a single image. We studied a k-adventurers algorithm which prune trivial solutions and preserve K-most important and distinct segmentations. This generalizes the conventional maximum a posteriori (MAP) estimation.

3. The DDMCMC framework engages various image models: multinomial, texture, color, global spline et al. These are generative models, and are compatible with each other. We are in a process to integrating other image models.

4. The DDMCMC framework provides a unified view for the role of conventional algorithms, region growing, SNAKE/Balloon, split-merge, model switching and adaptation, PDEs and diffusions, region competition and subsume these algorithms. It provides a compatible platform to embed perceptual organization and object recognition. A DDMCMC method has been applied to object recognition and face detection in other papers.

The anatomy of solution space reveals a hierarchic and heterogeneous structures which contains subspaces of varying dimensions. The Bayesian posterior is distributed in such a space. The design of MCMC consists of reversible jump and diffusion dynamics. The efficiency is measured by the 2nd largest eigen-value of the Markov kernel, which is bounded by the conductance of the transition map.

Some typical examples:

input segmentation synthesis

 

We present some results of image segmentation below in a few categories, more are coming ....

1. [An Example]
Grey level images
1. [People]
2. [Animals]
3. [Outdoor scenes]
4. [Indoor scenes]
 
Color images
1. [People]
2. [Animals]
3. [Outdoor and indoor scenes]

Images for Berkeley Image Segmentation Benchmark

1. [Color]
2. [Grey level]

Parsing images into region and curve processes