Tags

Type your tag names separated by a space and hit enter

Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities.
IEEE Trans Pattern Anal Mach Intell. 2005 Aug; 27(8):1239-53.IT

Abstract

Many vision tasks can be formulated as graph partition problems that minimize energy functions. For such problems, the Gibbs sampler provides a general solution but is very slow, while other methods, such as Ncut and graph cuts are computationally effective but only work for specific energy forms and are not generally applicable. In this paper, we present a new inference algorithm that generalizes the Swendsen-Wang method to arbitrary probabilities defined on graph partitions. We begin by computing graph edge weights, based on local image features. Then, the algorithm iterates two steps. 1) Graph clustering: It forms connected components by cutting the edges probabilistically based on their weights. 2) Graph relabeling: It selects one connected component and flips probabilistically, the coloring of all vertices in the component simultaneously. Thus, it realizes the split, merge, and regrouping of a "chunk" of the graph, in contrast to Gibbs sampler that flips a single vertex. We prove that this algorithm simulates ergodic and reversible Markov chain jumps in the space of graph partitions and is applicable to arbitrary posterior probabilities or energy functions defined on graphs. We demonstrate the algorithm on two typical problems in computer vision--image segmentation and stereo vision. Experimentally, we show that it is 100-400 times faster in CPU time than the classical Gibbs sampler and 20-40 times faster then the DDMCMC segmentation algorithm. For stereo, we compare performance with graph cuts and belief propagation. We also show that our algorithm can automatically infer generative models and obtain satisfactory results (better than the graphic cuts or belief propagation) in the same amount of time.

Authors+Show Affiliations

Barbu A
Department of Computer Science, University of California, Los Angeles, 8125 Math Science Bldg., Los Angeles, CA 90095, USA. abarbu@ucla.edu
Zhu SC
No affiliation info available

MeSH

AlgorithmsArtificial IntelligenceCluster AnalysisComputer GraphicsComputer SimulationImage EnhancementImage Interpretation, Computer-AssistedImaging, Three-DimensionalInformation Storage and RetrievalModels, StatisticalNumerical Analysis, Computer-AssistedPattern Recognition, AutomatedPhotogrammetrySignal Processing, Computer-AssistedSubtraction Technique

Pub Type(s)

Comparative Study
Evaluation Study
Journal Article
Research Support, U.S. Gov't, Non-P.H.S.

Language

eng

PubMed ID

16119263

Citation

Barbu, Adrian, and Song-Chun Zhu. "Generalizing Swendsen-Wang to Sampling Arbitrary Posterior Probabilities." IEEE Transactions On Pattern Analysis and Machine Intelligence, vol. 27, no. 8, 2005, pp. 1239-53.
Barbu A, Zhu SC. Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. IEEE Trans Pattern Anal Mach Intell. 2005;27(8):1239-53.
Barbu, A., & Zhu, S. C. (2005). Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. IEEE Transactions On Pattern Analysis and Machine Intelligence, 27(8), 1239-53.
Barbu A, Zhu SC. Generalizing Swendsen-Wang to Sampling Arbitrary Posterior Probabilities. IEEE Trans Pattern Anal Mach Intell. 2005;27(8):1239-53. PubMed PMID: 16119263.
* Article titles in AMA citation format should be in sentence-case
TY - JOUR T1 - Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities. AU - Barbu,Adrian, AU - Zhu,Song-Chun, PY - 2005/8/27/pubmed PY - 2005/9/17/medline PY - 2005/8/27/entrez SP - 1239 EP - 53 JF - IEEE transactions on pattern analysis and machine intelligence JO - IEEE Trans Pattern Anal Mach Intell VL - 27 IS - 8 N2 - Many vision tasks can be formulated as graph partition problems that minimize energy functions. For such problems, the Gibbs sampler provides a general solution but is very slow, while other methods, such as Ncut and graph cuts are computationally effective but only work for specific energy forms and are not generally applicable. In this paper, we present a new inference algorithm that generalizes the Swendsen-Wang method to arbitrary probabilities defined on graph partitions. We begin by computing graph edge weights, based on local image features. Then, the algorithm iterates two steps. 1) Graph clustering: It forms connected components by cutting the edges probabilistically based on their weights. 2) Graph relabeling: It selects one connected component and flips probabilistically, the coloring of all vertices in the component simultaneously. Thus, it realizes the split, merge, and regrouping of a "chunk" of the graph, in contrast to Gibbs sampler that flips a single vertex. We prove that this algorithm simulates ergodic and reversible Markov chain jumps in the space of graph partitions and is applicable to arbitrary posterior probabilities or energy functions defined on graphs. We demonstrate the algorithm on two typical problems in computer vision--image segmentation and stereo vision. Experimentally, we show that it is 100-400 times faster in CPU time than the classical Gibbs sampler and 20-40 times faster then the DDMCMC segmentation algorithm. For stereo, we compare performance with graph cuts and belief propagation. We also show that our algorithm can automatically infer generative models and obtain satisfactory results (better than the graphic cuts or belief propagation) in the same amount of time. SN - 0162-8828 UR - https://www.unboundmedicine.com/medline/citation/16119263/Generalizing_Swendsen_Wang_to_sampling_arbitrary_posterior_probabilities_ DB - PRIME DP - Unbound Medicine ER -