Abstract: Many computer vision problems can be formulated as graph partition problems that minimize energy functions. Generally applicable algorithms like the Gibbs sampler can perform the minimization task, but they are very slow to converge, especially since the graphs in vision tasks are large (105–10 6 nodes). On the other hand, computationally effective algorithms like Graph Cuts and Belief Propagation are specialized to particular forms of energy functions, and they cannot be applied for complex statistical models using generative models and high-order priors. In this thesis, a new stochastic algorithm capable of sampling arbitrary energy functions defined on graph partitions is presented. To increase efficiency, the algorithm uses the image information to make informed jumps in the search space. The image information is given in the form of edge weights and represents an empirical probability that the nodes connected by the edge belong to the same object. At each step, the algorithm creates clusters of nodes by turning on/off the edges randomly according to their weights, and changes the label of all nodes in one cluster (connected component) in a single move. Each move is accepted or rejected according to an acceptance probability given by a simple and explicit equation. The algorithm is applied to 4 important problems in computer vision: image segmentation, perceptual organization, stereo matching and motion segmentation. To address different computational or representational issues, multi-grid, multi-level and multi-cue variants of the algorithm are presented. In image segmentation, the algorithm's performance is compared to the Gibbs sampler, while in stereo matching, it is compared to Graph Cuts and Belief Propagation.