Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graph cuts in computer vision
open-in-new
<p>As applied in the field of <a href="/facts/Computer_vision/Tl2Yyk66">computer vision</a>, <a href="/facts/Graph_cut_optimization/BHn61p1N">graph cut optimization</a> can be employed to <a href="/facts/Polynomial_time/77T62gmf">efficiently</a> solve a wide variety of low-level computer vision problems (<i>early vision</i>), such as <a href="/facts/Image_smoothing/l5LvzVBa">image smoothing</a>, the stereo <a href="/facts/Correspondence_problem/YBe0HbVX">correspondence problem</a>, <a href="/facts/Image_segmentation/jofAhbxa">image segmentation</a>, <a href="/facts/Object_co-segmentation/m8Wueo7A">object co-segmentation</a>, and many other computer vision problems that can be formulated in terms of <a href="/facts/Energy_minimization/NYjCryaS">energy minimization</a>. </p><p>Many of these energy minimization problems can be approximated by solving a <a href="/facts/Maximum_flow_problem/aSal0FGF">maximum flow problem</a> in a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> (and thus, by the <a href="/facts/Max-flow_min-cut_theorem/qrXp2ut7">max-flow min-cut theorem</a>, define a minimal <a href="/facts/Cut_(graph_theory)/1lKf2IIW">cut</a> of the graph). </p><p>Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the <a href="/facts/Maximum_a_posteriori_estimation/Y5zHyqfX">maximum a posteriori estimate</a> of a solution. </p><p>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 <a href="/facts/Graph_partition/MSQF0WyD">graph partitioning</a> algorithms). </p><p>"Binary" problems (such as <a href="/facts/Denoising/9jrDQnAN">denoising</a> a <a href="/facts/Binary_image/qaKaPntY">binary image</a>) 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 <a href="/facts/Grayscale/Tjb9kR8v">grayscale</a> image) cannot be solved exactly, but solutions produced are usually near the global optimum. </p>