Department of Statistics, UCLA

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.