Graphics Reference
In-Depth Information
2.8.1
Graph Cut Segmentation
Many of the leading hard segmentation algorithms are based on Boykov and Jolly's
pioneering work on
graph cuts
[
59
]. The setup is similar to the graphs from belief-
propagation and random-walk methods, but the graph problem solved is quite
different. We create a set of nodes
that contains all the pixels of the image, as well
as two special
terminal nodes
that we call
V
F
and
B
for foreground and background.
We also create a set of edges
between nodes, typically based on 4-adjacency in the
image. Each node is also connected to both
E
F
B
by an edge. An example graph
is shown in Figure
2.19
a. Finally, we put a nonnegative weight
w
ij
on each edge
e
ij
so that
w
ij
is large if the nodes are similar (i.e., we have evidence that they should be
assigned to the same region) and small otherwise.
A
cut
is a subset of edges
and
C
such that if we remove these edges from
E
, there is
no path from
in the resulting subgraph; that is, the terminals are separated
(Figure
2.19
b). A cut induces a segmentation in the sense that all the nodes con-
nected to
F
to
B
constitute the
background. Our goal is to find the
minimum cut
, that is, the one that minimizes the
cost:
F
constitute the foreground and all the nodes connected to
B
|
C
|=
w
ij
(2.83)
(
i
,
j
)
∈
C
Boykov and colleagues showed that the globally optimal minimum cut could
quickly be computed in low-order polynomial time [
60
], leading to an explosion
of interest in graph-cut methods in the computer vision community. Appendix
A.3
gives more details on the basic algorithm. GPU-based [
515
] and multi-core [
296
]
algorithms have been proposed to further accelerate finding the minimum cut.
As with scribble-based matting, the user designates certain pixels to belong to the
foreground
F
and others to the background
B
. For a labeled foreground pixel
i
, the
weight on edge
is set to infinity (or a very
large number) to force the minimum cut to assign
i
to the foreground. The reverse
is true for labeled background pixels. The scribbles also serve to generate weights
for connecting the rest of the nodes to the terminals. Boykov and Jolly originally
(
i
,
B
)
is set to 0 and the weight on edge
(
i
,
F
)
F
F
B
B
(a)
(b)
Figure 2.19.
(a) The configuration of nodes and edges for graph-cut-based segmentation. Each
pixel is connected to its neighbors aswell as to two special foreground and background terminals.
(b) A cut (dotted line) removes edges so that there is no path from the foreground terminal to
the background terminal.
