Swendsen-Wang Cuts

Adrian Barbu

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.Cheetah
The algorithm was applied to many computer vision problems:

  1. Image Segmentation. A. Barbu, S.C. Zhu

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)

  1. Curve Grouping. A. Barbu, S.C. Zhu

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)

 

  1. Image-Motion Segmentation. A. Barbu, S.C. Zhu

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)

 

  1.   Performance comparison of Swendsen-Wang Cuts with Graph Cuts and Belief Propagation on stereo. A. Barbu, S.C. Zhu

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)

 

  1. Stereo Matching using generative linear models and Swendsen-Wang Cuts . A. Barbu, S.C. Zhu

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)

 
 

 home    research