In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 26(2):147-159, February 2004. Earlier version appeared in European Conference on Computer Vision (ECCV), May 2002 (best paper award).

Abstract

In the last few years, several new algorithms based on graph cuts have been
developed to solve energy minimization problems in computer vision. Each of
these techniques constructs a graph such that the minimum cut on the graph
also minimizes the energy. Yet because these graph constructions are complex
and highly specific to a particular energy function, graph cuts have seen
limited application to date. In this paper we give a characterization of the
energy functions that can be minimized by graph cuts. Our results are
restricted to functions of binary variables. However, our work generalizes
many previous constructions, and is easily applicable to vision problems that
involve large numbers of labels, such as stereo, motion, image restoration and
scene reconstruction. We give a precise characterization of what energy
functions can be minimized using graph cuts, among the energy functions that
can be written as a sum of terms containing three or fewer binary variables.
We also provide a general-purpose construction to minimize such an energy
function. Finally, we give a necessary condition for any energy function of
binary variables to be minimized by graph cuts. Researchers who are
considering the use of graph cuts to optimize a particular energy function can
use our results to determine if this is possible, and then follow our
construction to create the appropriate graph.

Note: After the paper has been published, I found out that most
of its results appeared a long time ago. The fact that submodular functions can be
minimized via graph cuts (min-cut/max-flow algorithm) is well-known in the optimization
literature, see e.g.

P.L. Hammer. "Some network flow problems solved with pseudo-Boolean programming." Operations Research 13:388-399, 1965.

Graph construction for submodular functions with triple cliques was given in

A. Billionnet and M. Minoux. "Maximizing a supermodular pseudo-boolean function:
a polynomial algorithm for supermodular cubic functions." Discrete Appl. Math. 12(1):1-11, 1985

For a review of pseudo-boolean optimization literature, see

E. Boros and P.L. Hammer. "Pseudo-boolean optimization." Discrete Appl. Math. 123:155-225, 2002