The theory of graph cuts, Cut (graph theory), was first applied in Computer vision in the now "classic" 1989 paper by Greig, Porteous and Seheult of Durham University, UK, as referenced below.
In the Bayesian statistical context of smoothing noisy, or corrupted, images, Greig, Porteous and Seheult showed how the maximum a posteriori estimate of a binary image can be obtained exactly by maximising the flow through an associated image network. The problem was therefore converted into a NP hard problem which could be solved using known efficient algorithms.
Prior to this result approximate, although more general techniques such as simulated annealing, as proposed by the Geman brothers, or iterated conditional modes, as suggested by Julian Besag, were used to solve these types of problems. See the references below.
Although the general k-colour problem remains unsolved for k > 2, the approach of Greig, Porteous and Seheult is now very commonly used in computer vision problems, often by applying their approach iteratively to a sequence of binary images to yield near optimal solutions.
References
- J.E. Besag (1986), On the statistical analysis of dirty pictures (with discussion), Journal of the Royal Statistical Society Series B, 48, 259 - 302.
- Geman. D and Geman. S (1984), Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, IEEE Trans. Pattn Anal. Mach. Intell., 6, 721 - 741.
- D.M. Greig, B.T. Porteous and A.H. Seheult (1989), Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society Series B, 51, 271 - 279.