Graphics Reference
In-Depth Information
Li et al. [
280
] proposed an algorithm called
lazy snapping
that speeds up the
graph-cut segmentation algorithm by operating on
superpixels
instead of pixels.
That is, the image pixels are clustered into small, roughly constant color regions
using the watershed algorithm [
514
]. These regions then become the nodes of the
graph-cut problem, since it's assumed that all pixels within a superpixel have the
same label. Since there are typically about ten to twenty times fewer nodes and edges
in the superpixel problem, the cut can be computed at interactive rates. Liu et al. [
296
]
proposed an interactive algorithm called
paint selection
that uses an efficient multi-
core graph cut algorithm to progressively hard segment an image as the user drags
the mouse around an object boundary.
2.8.2
GrabCut
Rother et al. [
405
] were the first to extend graph-cut segmentation to the matting
problem. The basic idea of their
GrabCut
algorithm is to first compute a hard seg-
mentation using graph cuts (Figure
2.21
a), and then to dilate the border around the
hard edge to effectively create a trimap (Figure
2.21
b). Inside the unknown region of
the trimap, an
profile that transitions smoothly from 0 to 1 is fit (Figure
2.21
c).
The process begins with user input in the form of a simple bounding box around
the foreground (i.e., a garbage matte). Everything outside the box is assumed to be
backgroundwith
α
α
=
0, and everything inside the box is assumed to be unknown, with
an initial estimate of
1. As in Bayesian matting, initial Gaussian mixture models
are fit to the foreground and background intensities inside and outside the box. The
GrabCut algorithm iterates three steps until the binary
α
=
α
labels have converged:
1. Each pixel is assigned to one of the foreground (if
α
=
1) or background (if
i
0) Gaussian mixture components.
2. The parameters of each Gaussian mixture component are re-estimated based
on pixel memberships. This results in updated terms like Equation (
2.84
) for
the pixel-to-terminal weights.
3. The graph cut algorithm is used to update the hard segmentation.
α
=
i
F
F
1
U
B
B
0
profile width
(a)
(b)
(c)
Figure 2.21.
(a) A hard segmentation. (b) A trimap is created by dilating the foreground-
background boundary. (c) Parameters of a smooth transition of
α
between 0 and 1 are fit inside
profiles of the unknown region (dotted lines).
