Graph cuts in computer vision: Difference between revisions

Revision as of 10:38, 1 January 2021

Revision as of 16:02, 3 May 2021

Line 1:

As applied in the field of [[computer vision]], '''[[graph cut optimization]]''' 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]], [[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 (discrete mathematics)|graph]]<ref>Boykov, Y., Veksler, O., and Zabih, R. (2001), "[http://www.cs.cornell.edu/rdz/Papers/BVZ-pami01-final.pdfFast approximate energy minimization via graph cuts]," ''IEEE Transactions on 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 [[MAPBayesian estimateestimation of templates in computational anatomy|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 partition|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 ==