What Energy Functions can be Minimized via Graph Cuts?

Many problems in computer vision can be naturally phrased in terms of energy minimization. In the last few years researchers have developed a powerful class of energy minimization methods based on graph cuts. These techniques construct a specialized graph, such that the minimum cut on the graph also minimizes the energy. The minimum cut in turn is efficiently computed by max flow algorithms. Such methods have been successfully applied to a number of important vision problems, including image restoration, motion, stereo, voxel occupancy and medical imaging. However, each graph construction to date has been highly specific for a particular energy function. In this paper we address a much broader problem, by characterizing the class of energy functions that can be minimized by graph cuts, and by giving a general-purpose construction that minimizes any energy function in this class. Our results generalize several previous vision algorithms based on graph cuts, and also show how to minimize an interesting new class of energy functions