Graph cuts in computer vision: Difference between revisions

Revision as of 10:39, 19 August 2025

Latest revision as of 08:06, 20 August 2025

Line 12:

The foundational theory of [[Cut (graph theory)|graph cuts]] was first applied in [[computer vision]] in the seminal paper by Greig, Porteous and Seheult<ref name="D.M. Greig, B.T 1989">D.M. Greig, B.T. Porteous and A.H. Seheult (1989), ''[https://classes.cs.uchicago.edu/archive/2006/fall/35040-1/gps.pdf Exact maximum a posteriori estimation for binary images]'', Journal of the Royal Statistical Society, Series B, '''51''', 271–279.</ref> 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 (statistician)|Peter Green]], with the optimisation expert [[Margaret Greig]] notable as the first ever female member of staff of the Durham Mathematical Sciences Department.

In the [[Bayesian statistics|Bayesian]] statistical context of smoothing noisy (or corrupted) images, they showed how the [[MAP estimate|maximum a posteriori estimate]] of a [[binary image]] can be obtained ''exactly'' by maximizing the [[Flow network|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 [[Donald Geman|Geman brothers]]),<ref>D. Geman and S. Geman (1984), ''[httphttps://www.dam.brown.edu/people/documents/stochasticrelaxation.pdf Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images]'', IEEE Trans. Pattern Anal. Mach. Intell., '''6''', 721–741.</ref> or [[iterated conditional modes]] (a type of [[greedy algorithm]] suggested by [[Julian Besag]])<ref>J.E. Besag (1986), ''On the statistical analysis of dirty pictures (with discussion)'', [[Journal of the Royal Statistical Society]] Series B, '''48''', 259–302</ref> were used to solve such image smoothing problems.

Although the general [[Graph coloring|<math>k</math>-colour problem]] is NP hard for <math>k > 2,</math> the approach of Greig, Porteous and Seheult<ref name="D.M. Greig, B.T 1989" /> has turned out<ref>Y. Boykov, O. Veksler and R. Zabih (1998), "[https://www.cs.cornell.edu/~rdz/Papers/BVZ-cvpr98.pdf Markov Random Fields with Efficient Approximations]", ''International Conference on Computer Vision and Pattern Recognition (CVPR)''.</ref><ref name="boykov2001fast">Y. Boykov, O. Veksler and R. Zabih (2001), "[https://www.cs.cornell.edu/~rdz/Papers/BVZ-pami01-final.pdf Fast approximate energy minimisation via graph cuts]", ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', '''29''', 1222–1239.</ref> 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.