A reversible Marov chain Monte Carlo
algorithm for graph partition and labeling, that changes the label of
many nodes in one step. The algorithm is applicable to arbitrary
posterior probabilities and uses data driven information encoded in the
graph edges to propose meaningful clusters for label switching.
The algorithm was applied to many computer vision problems:
The Swendsen-Wang Cuts algorithm is used to label atomic regions (superpixels) based on their intensity patterns using generative models in a Bayesian framework. The prior is based on areas of connected components, which provides a clean segmentation result. A performance comparison of the Swendsen-Wang Cuts algorithm with the Gibbs sampler shows that our algorithm is 400 times faster.
A.
Barbu, S.C. Zhu. Generalizing Swendsen-Wang for Image
Analysis. J. Comp. Graph. Stat. 16, No 4, 2007 (pdf)
A. Barbu, S.C. Zhu. Generalizing Swendsen-Wang to sampling arbitrary
posterior probabilities, PAMI, 27, August
2005 (pdf)
A. Barbu, S.C. Zhu. Graph Partition By Swendsen-Wang Cuts, ICCV 2003
(pdf)
The
Swendsen-Wang Cuts algorithm is used
to group small edge segments obtained from edge detection into long and
smooth curves. The continuity prior is learned from manual
segmentations.
A. Barbu, S.C. Zhu. Graph Partition By Swendsen-Wang Cuts, ICCV 2003
(pdf)
The Swendsen-Wang Cuts algorithm is used to simultaneously obtain an image segmentation and a motion segmentation from two frames.
A.
Barbu, S.C. Zhu. Generalizing
Swendsen-Wang for Image Analysis. J. Comp. Graph. Stat. 16, No 4, 2007 (pdf)
A. Barbu, S.C. Zhu. Generalizing Swendsen-Wang to sampling arbitrary
posterior probabilities, PAMI, 27, August
2005 (pdf)
A. Barbu, S.C. Zhu. Multigrid and Multi-level Swendsen-Wang Cuts for
Hierarchic Graph Partition, CVPR 2004 (pdf)
The performance of the Swendsen-Wang Cuts algorithm is compared to Graph Cuts and Belief Propagation using a simple Potts model for dense stereo matching.
A.
Barbu, S.C. Zhu. Generalizing
Swendsen-Wang to sampling arbitrary posterior
probabilities, PAMI, 27, August 2005 (pdf)
The
Swendsen-Wang Cuts algorithm is used
for stereo matching, using generative linear models for each label. The
linear models can properly model planes that are not fronto-parallel.
A.
Barbu, S.C. Zhu. Generalizing
Swendsen-Wang to sampling arbitrary posterior
probabilities, PAMI, 27, August 2005 (pdf)