Graph cuts in computer vision

As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems ("early vision"), such as image smoothing, the stereo correspondence problem, image segmentation, object co-segmentation, and many other computer vision problems that can be formulated in terms of energy minimization. Many of these energy minimization problems can be approximated by solving a maximum flow problem in a graph (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution. Although many computer vision algorithms involve cutting a graph (e.g., normalized cuts), the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization (other graph cutting algorithms may be considered as graph partitioning algorithms).
"Binary" problems (such as denoising a binary image) can be solved exactly using this approach; problems where pixels can be labeled with more than two different labels (such as stereo correspondence, or denoising of a grayscale image) cannot be solved exactly, but solutions produced are usually near the global optimum.
History.
The theory of graph cuts used as an optimization method was first applied in computer vision in the seminal paper by Greig, Porteous and Seheult of Durham University. Allan Seheult and Bruce Porteous were members of Durham's lauded statistics group of the time, lead by Julian Besag and Peter Green (statistician), with the optimisation expert Margaret Greig notable as the first ever female member of staff of the Durham Mathematical Sciences Department. 
In the Bayesian statistical context of smoothing noisy (or corrupted) images, they showed how the maximum a posteriori estimate of a binary image can be obtained "exactly" by maximizing the flow through an associated image network, involving the introduction of a "source" and "sink". The problem was therefore shown to be efficiently solvable. Prior to this result, "approximate" techniques such as simulated annealing (as proposed by the Geman brothers), or iterated conditional modes (a type of greedy algorithm as suggested by Julian Besag) were used to solve such image smoothing problems.
Although the general formula_1-colour problem remains unsolved for formula_2 the approach of Greig, Porteous and Seheult has turned out to have wide applicability in general computer vision problems. Greig, Porteous and Seheult approaches are often applied iteratively to a sequence of binary problems, usually yielding near optimal solutions.
In 2011, C. Couprie et al. proposed a general image segmentation framework, called the "Power Watershed", that minimized a real-valued indicator function from [0,1] over a graph, constrained by user seeds (or unary terms) set to 0 or 1, in which the minimization of the indicator function over the graph is optimized with respect to an exponent formula_3. When formula_4, the Power Watershed is optimized by graph cuts, when formula_5 the Power Watershed is optimized by shortest paths, formula_6 is optimized by the Random walker algorithm and formula_7 is optimized by the Watershed (image processing) algorithm. In this way, the Power Watershed may be viewed as a generalization of graph cuts that provides a straightforward connection with other energy optimization segmentation/clustering algorithms.
Binary segmentation of images.
Energy function.
where the energy formula_15 is composed of two different models (formula_16 and formula_17):
Likelihood / Color model / Regional term.
formula_16 — unary term describing the likelihood of each color.
Prior / Coherence model / Boundary term.
formula_17 — binary term describing the coherence between neighborhood pixels.
Criticism.
Graph cuts methods have become popular alternatives to the level set-based approaches for optimizing the location of a contour (see for an extensive comparison). However, graph cut approaches have been criticized in the literature for several issues:
Algorithm.
Implementation (exact).
The Boykov-Kolmogorov algorithm is an efficient way to compute the max-flow for computer vision related graph.
Implementation (approximation).
The Sim Cut algorithm approximates the graph cut. The algorithm implements a solution by simulation of an electrical network. This is the approach suggested by Cederbaum's maximum flow theorem. Acceleration of the algorithm is possible through parallel computing.