Many energy minimization problems involve assigning a label to every node in a graph, where adjacent nodes should have similar labels. These optimization problems arise in fields as diverse as lassifying web documents, biometry and computer vision. Until recently, these problems were thought to be completely intractable, since the energy functions have multiple local minima and the search space typically has thousands of dimensions.

We will present some fast algorithms for solving these energy minimization problems using graph cuts. For a few energy functions, the global minimum can
be rapidly computed using a single graph cut. A much broader class of energy functions is NP-hard to minimize. However, for these functions we can produce
answers with two quality guarantees. First, our answer is within a known factor of the global minimum. Second, we produce a local minimum even when very large moves are allowed.

We have applied these algorithms to several low-level vision problems, including stereo, motion and image restoration. The experimental results, especially for stereo, are quite striking. For example, on a real stereo pair with ground truth, our results contain 4 times fewer errors than appear to be obtainable from conventional stereo algorithms.

This is joint work with Yuri Boykov and Olga Veksler.