Skip to content
Search

Graph cuts

lastmod 2023-10-12created 2022-07-125 edits

As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems (early vision), 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 (and thus, by the max-flow min-cut theorem, define a minimal cut of the graph). Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the 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.

GrabCut

GrabCut is an image based on segmentation.

Starting with a user-specified bounding box around the object to be segmented, the algorithm estimates the color distribution of the target object and of the background using a Gaussian mixture. model. This is used to construct a Markov random field over the pixel labels, with an energy function that prefers connected regions having the same label, and to run a graph cut based optimization to infer their values. . Since this estimate is likely to be more accurate than the original one taken from the bounding box, this two-step procedure is repeated until convergence. The user can point out misclassified regions and rerun the optimization to further correct the estimate. The method also corrects the results to preserve edges.

See also

Favorite site

author Zer0 sitemap