Markov chain Monte Carlo (MCMC) methods have been used in many fields (physics, chemistry, biology, and computer science) for simulation, inference, and optimization. The essence of these methods is to simulate a Markov chain whose state X follows a target probability X ∼ π(X). In many applications, π(X) is defined on a graph G whose vertices represent elements in the system and whose edges represent the connectivity of the elements. X is a vector of variables on the vertices which often take discrete values called labels or colors. Designing rapid mixing Markov chain is a challenging task when the variables in the graph are strongly coupled. Methods, like the single-site Gibbs sampler, often experience long waiting time. A well-celebrated algorithm for sampling on graphs is the Swendsen-Wang (1987) (SW) method. The SWmethod finds a cluster of vertices as a connected component after turning off some edges probabilistically, and flips the color of the cluster as a whole. It is shown to mix rapidly under certain conditions. Unfortunately, the SW method is only applicable to the Ising/Potts models and slow down critically in the presence of "external fields" i.e. likelihood in Bayesian inference.

In this paper, we present a general cluster sampling method which achieves the following objectives. Firstly, it extends the SW algorithm to general Bayesian inference on graphs. Especially we focus a number of image analysis problems where the graph sizes are in the order of O(103) — O(106) with O(1) connectivity. Secondly, the edge probability for clustering the vertices are discriminative probabilities computed from data. Empirically such data driven clustering leads to much improved efficiency. Thirdly, we present a generalized Gibbs sampler which samples the color of a cluster according to a conditional probability (like the Gibbs sampler) weighted by a product of edge probabilities. Fourthly, we design the algorithm to work on multi-grid and multi-level graphs. The algorithm is tested on typical problems in image analysis, such as image segmentation and motion analysis, In our experiments, the algorithm is O(102) orders faster than the single-site Gibbs sampler. In the literature, there are several ways for interpreting the SW-method which leads to various analyses or generalizations, including random cluster model (RCM), data augmentation, slice sampling, and partial decoupling. We take a different route by interpreting SW as a Metropolis-Hastings step with auxiliary variables for proposing the moves or we can view it as a generalized hit-and-run method.

Our paper has two main contributions. Firstly, it presents a model for image sequences motivated by an im- age encoding perspective. It models accreted regions, where objects appear, as well as motion and motion boundaries. We formulate the problem as probabilistic inference using prior models of images and the motion field. Secondly, it introduces a new algorithm for motion estimation based on Swendsen-Wang Cuts, which performs inference on the image sequence model using bottom-up proposals to guide the search. The algorithm proceeds by first estimating the motion without the boundaries, and then by clustering in the velocity space to obtain initial estimates of the motion boundaries. The algorithm performs MAP estimation by evolving the motion boundaries by a stochastic boundary diffusion algorithm, while improving the motion estimates. Our approach is illustrated on real images of city scenes and on simulated data and can deal with large motions (even 10 pixels or more per frame). We show a brief com- parison of Swendsen-Wang Cuts with Graph Cuts and Belief Propagation on the related stereo matching problem.

Vision tasks, such as segmentation, grouping, recognition, and learning, have a "what-goes-with-what" component. It can be formulated as partitioning an adjacent graph into a number of subgraphs, each being a "coherent" visual pattern in the sense of optimizing a Bayesian posterior probability or minimizing an energy functional. In this paper, we generalize Swendsen-Wang (1987)- a well celebrated algorithm in statistical mechanics-for general graph partition. Our objective is to design reversible Markov chain moves in the space of all possible partitions to search for global optimum in the Bayesian framework. We start with an adjacency graph whose vertices are image elements, such as pixels, edgels, small regions, or image bases. For each edge in the graph, we compute a local discriminative probability or probability ratio for how likely the two vertices belong to an underlying visual pattern. These edge probabilities are computed in a bottom-up fasion through previous supervised learning techniques. By turning on/off the edges independently according to these edge probabilities, we obtain a partition of the graph into a number of connected subgraphs. This procedure is in fact a sample from the space of graph partitions. We use it as a proposal (hypothesis) in a probabilistic manner. Thus the algorithm picks up a connected subgraph and flips the label of all its vertices in a single reversible Markov chain jump. In comparison to the classic Gibbs sampler which flips a single vertex at a time, the proposed method achieves: 1) Fast mixing rate it can flip a large subgraph at a time and the acceptance probability can be made to be one. 2) Short burn-in period - it can walk at low temperature and does not need a long sumulated annealing procedure. Thus it is shown to be nearly 100 times faster than the Gibbs sampler and thus produce results in about 1 minute on a PC for image segmentation and curve grouping experiments. The algorithm is tested in image segmentation and curve grouping task, and it is general for many problems in vision and beyond.