Page 315 -

Section 9.4 Segmentation, Clustering, and Graphs 283

B B
S S

D D
d d
edge weight case
(i, j) B(p , p ) i, j,neighbors
i j
K p ∈F
(S → i) 0 p ∈B
d f (i) otherwise
K p ∈B
(i → D) 0 p ∈F
d b (i) otherwise

FIGURE 9.23: On the left, a graph derived from an image to set up foreground/background
segmentation as a graph cut problem. We interpret pixels linked to the source (S) as
foreground pixels, and pixels linked to the drain (D) as background pixels. Some pixels—
whose labels are known—are linked to only one of the two, and to their neighbors. Link
weights are given in the table. The links between neighbors have the same capacity in each
direction, which is why they are drawn without a direction. On the right,a cut ofthat
graph (edges that have been cut are grayed out). Notice that each pixel is linked to either
the foreground or to the background, but not to both (because otherwise we would not
have disconnected S and D) or to neither (because we could restore one of the two edges
and get a cut with a better value). Furthermore, the sum of weights of cut edges is equal
to the energy cost function. As a result, we can segment the image into foreground and
background by solving for the minimum cost cut. With the weights shown in the table, the
value of a cut on the graph is the same as the value of the energy function, as long as the

cut does not cut both (S → i)and (i → D), and K =1 + maxp∈I B(p, q).
q:{p,q}∈N
A minimum cut will not cut both, because a better cut will cut only one; this means that
the energy function in the text can be minimized by cutting the graph.

specialized algorithms are now very fast at cutting graphs from images.
This procedure gives us one way to deal with the problem of Section 6.3.2.
Here we had a hole in an image and a patch that matched the hole; but the patch
typically is square, and the hole typically is not. Place the patch over the hole. For
some pixels we know only one value (those inside the hole, and those outside the
patch), but for others we know two values. For these, we would like to choose which
pixel appears in the final image. Again, we have a combinatorial problem. Write δ i
for a variable that takes the value −1ifthe ith pixel in the final image should come
from the patch, and 1 otherwise. Write U for the pixels that could take either label,
P for the pixels that can take values only from the patch, and I for the pixels that
can take values only from the image. We do not have a foreground or background
model. Generally, we would like pixels to have a δ that agrees with their neighbors.
When two neighboring pixels have different δ values (i.e., at a point where we cut