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[1]), 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[2] (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph).
"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.
The foundational theory of graph cuts was first applied in computer vision in the seminal paper by Greig, Porteous and Seheult[3] of Durham University.
Allan Seheult and Bruce Porteous were members of Durham's lauded statistics group of the time, led by Julian Besag and Peter Green, with the optimisation expert Margaret Greig notable as the first ever female member of staff of the Durham Mathematical Sciences Department.
Prior to this result, approximate techniques such as simulated annealing (as proposed by the Geman brothers),[4] or iterated conditional modes (a type of greedy algorithm suggested by Julian Besag)[5] were used to solve such image smoothing problems.
the approach of Greig, Porteous and Seheult[3] has turned out[6][7] to have wide applicability in general computer vision problems.
For general problems, Greig, Porteous and Seheult's approach is often applied iteratively to sequences of related binary problems, usually yielding near optimal solutions.
In 2011, C. Couprie et al.[8] 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
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.
Graph cuts methods have become popular alternatives to the level set-based approaches for optimizing the location of a contour (see[9] for an extensive comparison).