GrabCut is an image
segmentation method based on
graph cuts.
Starting with a user-specified
bounding box
In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...
around the object to be segmented, the algorithm estimates the color distribution of the target object and that of the background using a
Gaussian mixture model. This is used to construct a
Markov random field
In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to b ...
over the pixel labels, with an
energy function that prefers connected regions having the same label, and running a graph cut based optimization to infer their values. As this estimate is likely to be more accurate than the original, taken from the bounding box, this two-step procedure is repeated until convergence.
Estimates can be further corrected by the user by pointing out misclassified regions and rerunning the optimization. The method also corrects the results to preserve edges.
There are several
open source implementations available including
OpenCV
OpenCV (''Open Source Computer Vision Library'') is a library of programming functions mainly aimed at real-time computer vision. Originally developed by Intel, it was later supported by Willow Garage then Itseez (which was later acquired by In ...
(as of version 2.1).{{citation needed, date=March 2021
See also
*
Connectivity (graph theory)
*
Prim's algorithm
In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every v ...
*
Edmonds–Karp algorithm
In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(, V, , E, ^2) time. The algorithm was first published by Yefim Dinitz (whose name is also ...
*
Graph cuts in computer vision 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 seg ...
References
*C. Rother, V. Kolmogorov, and A. Blake
Interactive foreground extraction using iterated graph cuts'' ACM Trans. Graph., vol. 23, pp. 309–314, 2004.
Image segmentation