Markov random fields with efficient approximations

Markov Random Fields (MRF's) can be used for a wide variety of vision problems, fn this paper we focus on MRF's with two-valued clique potentials, which form a generalized Potts model, We show that the maximum a posteriori estimate of such an MRF can be obtained by solving a multiway minimum cut problem on a graph. We develop efficient algorithms Sar computing good approximations to the minimum multiway cut. The visual correspondence problem can be formulated as an MRF in our framework this yields quite promising results on real data with ground truth. We also apply our techniques to MRF's with linear clique potentials.