Graph cuts in computer vision: Difference between revisions

Revision as of 22:52, 28 October 2018

Revision as of 17:48, 14 January 2019

Line 1:

As applied in the field of [[computer vision]], '''[[Cut (graph theory)|graphcut cutsoptimization]]''' can be employed to [[Polynomial time|efficiently]] solve a wide variety of low-level computer vision problems (''early vision''<ref>Adelson, Edward H., and James R. Bergen (1991), "[http://persci.mit.edu/pub_pdfs/elements91.pdf The plenoptic function and the elements of early vision]", Computational models of visual processing 1.2 (1991).</ref>), such as image [[smoothing]], the stereo [[correspondence problem]], [[image 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 (discrete mathematics)|graph]]<ref>Boykov, Y., Veksler, O., and Zabih, R. (2001), "Fast approximate energy minimization via graph cuts," ''IEEE Trans. Pattern Analysis and Machine Intelligence,'' 23(11): 1222-1239.</ref> (and thus, by the [[max-flow min-cut theorem]], define a minimal [[cut (graph theory)|cut]] of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the [[MAP estimate|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 [[Cut (graph theory)|graph cuts]] used as [[graph cut optimization|an optimization method]] 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), ''Exact maximum a posteriori estimation for binary images'', Journal of the Royal Statistical Society, Series B, '''51''', 271–279.</ref> of [[Durham University]]. 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), ''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]] as 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 <math>k</math>[[Graph coloring|-colour problem]] remains unsolved 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), "[http://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), "[http://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. Greig, Porteous and Seheult approaches are often applied iteratively to a sequence of binary problems, usually yielding near optimal solutions.