10.

6 Region Segmentation Using Graph Cuts 777

in Eq. (10-91), where the l’s are intensity levels of the points for which the distance
is being computed.
In 3-D, superpixels become supervoxels, which are handled by defining

12
ds = ⎡⎣( x j − xi )2 + ( y j − yi )2 + (zj − zi )2 ⎤⎦ (10-93)

where the z’s are the coordinates of the third spatial dimension. We must also add
the third spatial variable, z, to the vector in Eq. (10-86).
Because no provision is made in the algorithm to enforce connectivity, it is pos-
sible for isolated pixels to remain after convergence. These are assigned the label
of the nearest cluster using a connected components algorithm (see Section 9.6).
Although we explained the algorithm in the context of RGB color components, the
method is equally applicable to other colors systems. In fact, other components of
vector z in Eq. (10-86) (with the exception of the spatial variables) could be other
real-valued feature values, provided that a meaningful distance measure can be
defined for them.

EXAMPLE 10.23 : Using superpixels for image segmentation.

Figure 10.52(a) shows an image of an iceberg, and Fig. 10.52(b) shows the result of segmenting this
image using the k-means algorithm developed in the last section, with k = 3. Although the main regions
of the image were segmented, there are numerous segmentation errors in both regions of the iceberg,
and also on the boundary separating it from the background. Errors are visible as isolated pixels (and
also as small groups of pixels) with the wrong shade (e.g., black pixels within a white region). Figure
10.52(c) shows a 100-superpixel representation of the image with the superpixel boundaries superim-
posed for reference, and Fig. 10.52(d) shows the same image without the boundaries. Figure 10.52(e) is
the segmentation of (d) using the k-means algorithm with k = 3 as before. Note the significant improve-
ment over the result in (b), indicating that the original image has considerably more (irrelevant) detail
than is needed for a proper segmentation. In terms of computational advantage, consider that generat-
ing Fig. 10.52(b) required individual processing of over 300K pixels, while (e) required processing of 100
pixels with considerably fewer shades of gray.

10.6 REGION SEGMENTATION USING GRAPH CUTS

10.6

In this section, we discuss an approach for partitioning an image into regions by

expressing the pixels of the image as nodes of a graph, and then finding an optimum
partition (cut) of the graph into groups of nodes. Optimality is based on criteria whose
values are high for members within a group (i.e., a region) and low across members of
different groups. As you will see later in this section, graph-cut segmentation is capa-
ble in some cases of results that can be superior to the results achievable by any of the
segmentation methods studied thus far. The price of this potential benefit is added
complexity in implementation, which generally translates into slower execution.

[Link]

DIP4E_GLOBAL_Print_Ready.indb 777 6/16/2017 2:14:01 PM

 778 Chapter 10 Image Segmentation

a b
c d e
FIGURE 10.52 (a) Image of size 533 × 566 (301,678) pixels. (b) Image segmented using the k-means algorithm.
(c) 100-element superpixel image showing boundaries for reference. (d) Same image without boundaries. (e) Super-
pixel image (d) segmented using the k-means algorithm. (Original image courtesy of NOAA.)

IMAGES AS GRAPHS

Nodes and edges are also

A graph, G, is a mathematical structure consisting of a set V of nodes and a set E of
referred to as vertices edges connecting those vertices:
and links, respectively.
G = (V, E ) (10-94)
where V is a set and

See Section 2.5 for an

E 8 V×V (10-95)
explanation of the
Cartesian product V × V
and for a review of the is a set of ordered pairs of elements from V. If (u, v) ∈ E implies that (v, u) ∈ E, and
set symbols used in this vice versa, the graph is said to be undirected; otherwise the graph is directed. For
section.
example, we may consider a street map as a graph in which the nodes are street
intersections, and the edges are the streets connecting those intersections. If all
streets are bidirectional, the graph is undirected (meaning that we can travel both
ways from any two intersections). Otherwise, if at least one street is a one-way street,
the graph is directed.

[Link]

DIP4E_GLOBAL_Print_Ready.indb 778 6/16/2017 2:14:02 PM

 10.6 Region Segmentation Using Graph Cuts 779

The types of graphs in which we are interested are undirected graphs whose
edges are further characterized by a matrix, W, whose element w(i, j ) is a weight
associated with the edge that connects nodes i and j. Because the graph is undirected,
w(i, j ) = w( j, i), which means that W is a symmetric matrix. The weights are selected
to be proportional to one or more similarity measures between all pairs of nodes. A
graph whose edges are associated with weights is called a weighted graph.
The essence of the material in this section is to represent an image to be seg-
Superpixels are also well
mented as a weighted, undirected graph, where the nodes of the graph are the pixels
suited for use as graph in the image, and an edge is formed between every pair of nodes. The weight, w(i, j ),
nodes. Thus, when we of each edge is a function of the similarity between nodes i and j. We then seek to
refer in this section to
“pixels” in an image, we partition the nodes of the graph into disjoint subsets V1 , V2 ,…, VK where, by some
are, by implication, measure, the similarity among the nodes within a subset is high, and the similarity
also referring to super-
pixels. across the nodes of different subsets is low. The nodes of the partitioned subsets
correspond to the regions in the segmented image.
Set V is partitioned into subsets by cutting the graph. A cut of a graph is a parti-
tion of V into two subsets A and B such that

A ´ B = V and A ¨ B = ∅ (10-96)

where the cut is implemented by removing the edges connecting subgraphs A and B.
There are two key aspects of using graph cuts for image segmentation: (1) how to
associate a graph with an image; and (2) how to cut the graph in a way that makes
sense in terms of partitioning the image into background and foreground (object)
pixels. We address these two questions next.
Figure 10.53 shows a simplified approach for generating a graph from an image.
The nodes of the graph correspond to the pixels in the image and, to keep the expla-
nation simple, we allow edges only between adjacent pixels using 4-connectivity,
which means that there are no diagonal edges linking the pixels. But, keep in mind
that, in general, edges are specified between every pair of pixels. The weights for the
edges typically are formed from spatial relationships (for example, distance from the
vertex pixel) and intensity measures (for example, texture and color), consistent with
exhibiting similarity between pixels. In this simple example, we define the degree
of similarity between two pixels as the inverse of the difference in their intensities.
That is, for two nodes (pixels) ni and n j , the weight of the edge between them is
w(i, j ) = 1冫A 冷 I (ni ) − I (n j ) 冷 + cB, where I (ni ) and I (n j ), are the intensities of the two
nodes (pixels) and c is a constant included to prevent division by 0. Thus, the closer
the values of intensity between adjacent pixels is, the larger the value of w will be.
For illustrative purposes, the thickness of each edge in Fig. 10.53 is shown propor-
tional to the degree of similarity between the pixels that it connects (see Problem
10.44). As you can see in the figure, the edges between the dark pixels are stronger
than the edges between dark and light pixels, and vice versa. Conceptually, segmen-
tation is achieved by cutting the graph along its weak edges, as illustrated by the
dashed line in Fig. 10.53(d). Figure 10.53(c) shows the segmented image.
Although the basic structure in Fig. 10.53 is the focus of the discussion in this
section, we mention for completeness another common approach for constructing

[Link]

DIP4E_GLOBAL_Print_Ready.indb 779 6/16/2017 2:14:03 PM

 780 Chapter 10 Image Segmentation

a b
c d
FIGURE 10.53
(a) A 3 × 3 image.
(c) A corresponding
graph.
(d) Graph cut.
(c) Segmented
image.

Image Segmentation
⇓
⇓ Node
Edge

⇓
Graph Cut

image graphs. Figure 10.54 shows the same graph as the one we just discussed, but
here you see two additional nodes called the source and sink terminal nodes, respec-
tively, each connected to all nodes in the graph via unidirectional links called t-links.
The terminal nodes are not part of the image; their role, for example, is to associate
with each pixel a probability that it is a background or foreground (object) pixel.
The probabilities are the weights of the t-links. In Figs. 10.54(c) and (d), the thickness
of each t-link is proportional to the value of the probability that the graph node to
which it is connected is a foreground or background pixel (the thicknesses shown
are so that the segmentation result would be the same as in Fig. 10.53). Which of the
two nodes we call background or foreground is arbitrary.

MINIMUM GRAPH CUTS

Once an image has been expressed as a graph, the next step is to cut the graph into
two or more subgraphs. The nodes (pixels) in each resulting subgraph correspond
to a region in the segmented image. Approaches based on Fig. 10.54 rely on inter-
preting the graph as a flow network (of pipes, for example) and obtaining what is
commonly referred to as a minimum graph cut. This formulation is based on the
so-called Max-Flow, Min-Cut Theorem. This theorem states that, in a flow network,
the maximum amount of flow passing from the source to the sink is equal to the
minimum cut. This minimum cut is defined as the smallest total weight of the edges
that, if removed, would disconnect the sink from the source:

cut( A, B) = ∑
u ∈A,v∈B
w(u, v) (10-97)

[Link]

DIP4E_GLOBAL_Print_Ready.indb 780 6/16/2017 2:14:03 PM

 10.6 Region Segmentation Using Graph Cuts 781

a b
c d
FIGURE 10.54
(a) Same image
as in Fig. 10.53(a).
(c) Corresponding
graph and terminal
nodes. (d) Graph
cut. (b) Segmented
image.
Image ⇓ Segmentation

⇓
Source Terminal Source Terminal
(Background) (Background)

Graph

⇓ Cut

Sink Terminal Sink Terminal

(Foreground) (Foreground)

where A and B satisfy Eq. (10-96). The optimum partition of a graph is the one that
minimizes this cut value. There is an exponential number of such partitions, which
would present us with an intractable computational problem. However, efficient
algorithms that run in polynomial time have been developed for solving max-flow
problems. Therefore, based on the Max-Flow, Min-Cut Theorem, we can apply these
algorithms to image segmentation, provided that we cast segmentation as a flow
problem and select the weights for the edges and t-links such that minimum graph
cuts will result in meaningful segmentations.
Although the min-cut approach offers an elegant solution, it can result in group-
ings that favor cutting small sets of isolated nodes in a graph, leading to improper
segmentations. Figure 10.55 shows an example, in which the two regions of interest
are characterized by the tightness of the pixel groupings. Meaningful edge weights
that reflect this property would be inversely proportional to the distance between
pairs of points. But this would lead to weights that would be smaller for isolated
points, resulting in min cuts such as the example in Fig. 10.55. In fact, any cut that
partitions out individual points on the left of the figure will have a smaller cut value
in Eq. (10-4) than a cut that properly partitions the points into two groups based on

[Link]

DIP4E_GLOBAL_Print_Ready.indb 781 6/16/2017 2:14:03 PM

 782 Chapter 10 Image Segmentation

FIGURE 10.55 A min cut A more meaningful cut

An example
showing how a
min cut can lead
to a meaningless
segmentation. In
this example, the
similarity between
pixels is defined
as their spatial
proximity, which
results in two
distinct regions.

their proximity, such as the partition shown in Fig. 10.55. The approach presented in
this section, proposed by Shi and Malik [2000] (see also Hochbaum [2010]), is aimed
at avoiding this type of behavior by redefining the concept of a cut.
Instead of looking at the total weight value of the edges that connect two parti-
tions, the idea is to work with a measure of “disassociation” that computes the cost
as a fraction of the total edge connections to all nodes in the graph. This measure,
called the normalized cut (Ncut), is defined as

cut( A, B) cut( A, B)
Ncut ( A, B) = + (10-98)
assoc( A, V ) assoc(B, V )
where cut( A, B) is given by Eq. (10-97) and

assoc( A, V ) = ∑
u ∈A, z ∈V
w(u, z) (10-99)

is the sum of the weights of all the edges from the nodes of subgraph A to the nodes
of the entire graph. Similarly,

assoc(B, V ) = ∑
v ∈B, z ∈V
w(v, z) (10-100)

is the sum of the weights of the edges from all the edges in B to the entire graph. As
you can see, assoc( A, V ) is simply the cut of A from the rest of the graph, and simi-
larly for assoc(B, V ).
By using Ncut ( A, B) instead of cut( A, B), the cut that partitions isolated points
will no longer have small values. You can see this, for example, by noting in Fig. 10.55
that if A is the single node shown, cut( A, B) and assoc( A, V ) will have the same val-
ue. Thus, independently of how small cut( A, B) is, Ncut ( A, B) will always be greater
than or equal to 1, thus providing normalization for “pathological” cases such as this.
Based on similar concepts, we can define a measure for total normalized associa-
tion within graph partitions as

[Link]

DIP4E_GLOBAL_Print_Ready.indb 782 6/16/2017 2:14:05 PM

 10.6 Region Segmentation Using Graph Cuts 783

assoc( A, A) assoc(B, B)
Nassoc( A, B) = + (10-101)
assoc( A, V ) assoc(B, V )
where assoc( A, A) and assoc(B, B) are the total weights connecting the nodes within
A and within B, respectively. It is not difficult to show (see Problem 10.46) that

Ncut ( A, B) = 2 − Nassoc( A, B) (10-102)

which implies that minimizing Ncut ( A, B) simultaneously maximizes Nassoc( A, B).

Based on the preceding discussion, image segmentation using graph cuts is now
based on finding a partition that minimizes Ncut ( A, B). Unfortunately, minimizing
this quantity exactly is an NP-complete computational task, and we can no longer
rely on the solutions available for max flow because the approach being followed
now is based on the concepts explained in connection with Fig. 10.53. However, Shi
and Malik [2000] (see also Hochbaum [2010]) were able to find an approximate dis-
crete solution to minimizing Ncut ( A, B) by formulating minimization as a general-
ized eigenvalue problem, for which numerous implementations exist.

COMPUTING MINIMAL GRAPH CUTS

As above, let V denote the nodes of a graph G, and let A and B be two subsets
If the nodes of graph of V satisfying Eq. (10-96). Let K denote the number of nodes in V and define a
G are the pixels in an K-dimensional indicator vector, x, whose element xi has the property xi = 1 if node
image, then K = M × N,
where M and N are the ni of V is in A and xi = −1 if it is in B. Let
number of rows and

di = ∑ w(i, j )
columns in the image.
(10-103)
j

be the sum of the weights from node ni to all other nodes in V. Using these defini-
tions, we can write Eq. (10-98) as

cut( A, B) cut( A, B)
Ncut ( A, B) = +
cut( A, V ) cut(B, V )
∑
xi > 0, x j < 0
− w(i, j )xi x j ∑
xi < 0 , x j > 0
−w(i, j )xi x j (10-104)
= +
∑ di
x >0
∑ di
xi < 0
i

The objective is to find a vector, x, that minimizes Ncut ( A, B). A closed-form solu-
tion that minimizes Eq. (10-104) can be found, but only if the elements of x are
allowed to be real, continuous numbers instead of being constrained to be ±1. The
solution derived by Shi and Malik [2000] is given by solving the generalized eigen-
system expression
(D − W)y = lDy (10-105)

where D is a K × K diagonal matrix with main-diagonal elements di , i = 1, 2, … , K ,

and W is a K × K weight matrix with elements w(i, j ), as defined earlier. Solving

[Link]

DIP4E_GLOBAL_Print_Ready.indb 783 6/16/2017 2:14:07 PM

 784 Chapter 10 Image Segmentation

Eq. (10-105) gives K eigenvalues and K eigenvectors, each corresponding to one

eigenvalue. The solution to our problem is the eigenvector corresponding the second
smallest eigenvalue.
We can convert the preceding generalized eigenvalue formulation into a standard
eigenvalue problem by writing Eq. (10-105) as (see Problem 10.45):

Az = l z (10-106)

where
−1 − 12
A = D 2 (D − W)D (10-107)

and
1
z = D2 y (10-108)

from which it follows that

−1
y = D 2z (10-109)

Thus, we can find the (continuous-valued) eigenvector corresponding to the second

smallest eigenvalue using either a generalized or a standard eigenvalue solver. The
desired (discrete) vector x can be generated from the resulting, continuous valued
solution vector by finding a splitting point that divides the values of the continuous
eigenvector elements into two parts. We do this by finding the splitting point that
yields the smallest value of Ncut ( A, B), since this is the quantity we are trying to
minimize. To simplify the search, we divide the range of values in the continuous
vector into Q evenly spaced values, evaluate Eq. (10-104) for each value, and choose
the splitting point that yields the smallest value of Ncut ( A, B). Then, all values of the
eigenvector with values above the split point are assigned the value 1; all others are
assigned the value −1. The result is the desired vector x. Then, partition A is the set
nodes in V corresponding to 1’s in x; the remaining nodes correspond to partition B.
This partitioning is carried out only if the stability criterion discussed in the follow-
ing paragraph is met.
Searching for a splitting point implies computing a total of Q values of Ncut ( A, B)
and selecting the smallest one. A region that is not clearly segmentable into two
subregions using the specified weights will usually result in many splitting points
with similar values of Ncut ( A, B). Trying to segment such a region is likely to result
in a meaningless partition. To avoid this behavior, a region (i.e., subgraph) is split
only if it satisfies a stability criterion, obtained by first computing the histogram of
the eigenvector values, then forming the ratio of the minimum to the maximum bin
counts. In an “uncertain” eigenvector, the values in the histogram will stay relatively
the same, and the ratio will be relatively high. Shi and Malik [2000] found experi-
mentally that thresholding the ratio at 0.06 was a effective criterion for not splitting
the region in question.

[Link]

DIP4E_GLOBAL_Print_Ready.indb 784 6/16/2017 2:14:07 PM

 10.6 Region Segmentation Using Graph Cuts 785

GRAPH CUT SEGMENTATION ALGORITHM

In the preceding discussion, we illustrated two ways in which edge weights can be
generated from an image. In Figs. 10.53 and 10.54, we looked at weights generated
using image intensity values, and in Fig. 10.55 we considered weights based on the
distance between pixels. But these are just two examples of the many ways that
we can generate a graph and corresponding weights from an image. For example,
we could use color, texture, statistical moments about a region, and other types of
features to be discussed in Chapter 11. In general, then, graphs can be constructed
from image features, of which pixel intensities are a special case. With this concept
as background, we can summarize the discussion thus far in this section as the fol-
lowing algorithm:

1. Given a set of features, specify a weighted graph, G = (V , E ) in which V contains

the points in the feature space, and E contains the edges of the graph. Compute
the edge weights and use them to construct matrices W and D. Let K denote the
desired number of partitions of the graph.
2. Solve the eigenvalue system (D − W)y = lDy to find the eigenvector with the
second smallest eigenvalue.
3. Use the eigenvector from Step 2 to bipartition the graph by finding the splitting
point such that Ncut ( A, B) is minimized.
4. If the number of cuts has not reached K, decide if the current partition should
be subdivided by checking the stability of the cut.
5. Recursively repartition the segmented parts if necessary.

Note that the algorithm works by recursively generating two-way cuts. The number of
groups (e.g., regions) in the segmented image is controlled by K. Other criteria, such
as the maximum size allowed for each cut, can further refine the final segmentation.
For example, when using pixels and their intensities as the basis for constructing the
graph, we can specify the maximum and/or minimum size allowed for each region.

EXAMPLE 10.24 : Specifying weights for graph cut segmentation.

In Fig. 10.53, we illustrated how to generate graph weights using intensity values, and in Fig. 10.55 we
discussed briefly how to generate weights based on the distance between pixels. In this example, we give
a more practical approach for generating weights that include both intensity and distance from a pixel,
thus introducing the concept of a neighborhood in graph segmentation.
Let ni and n j denote two nodes (image pixels). As mentioned earlier in this section, weights are sup-
posed to reflect the similarity between nodes in a graph. When considering segmentation, one of the
principal ways to establish how likely two pixels in an image are to be a part of the same region or object
is to determine the difference in their intensity values, and how close the pixels are to each other. The
weight value of the edge between two pixels should be large when the pixels are very close in intensity
and proximity (i.e., when the pixels are “similar), and should decrease as their intensity difference and
distance from each other increases. That is, the weight value should be a function of how similar the
pixels are in intensity and distance. These two concepts can be embedded into a single weight function
using the following expression:

[Link]

DIP4E_GLOBAL_Print_Ready.indb 785 6/16/2017 2:14:08 PM

 786 Chapter 10 Image Segmentation

⎧ − [ I ( ni )− I ( nj )]2 − dist ( ni , nj )
⎪ s I2 sd2
if dist(ni , n j ) < r
w(i, j ) = ⎨ e e
⎪0 otherwise
⎩

where I (ni ) is the intensity of node ni , s I2 and sd2 are constants determining the spread of the two
Gaussian-like functions, dist(ni , n j ) is the distance (e.g., the Euclidean distance) between the two nodes,
and r is a radial constant that establishes how far away we are willing to consider similarity. The expo-
nential terms decrease as a function of dissimilarity in intensity and as function of distance between the
nodes, as required of our measure of similarity in this case.

EXAMPLE 10.25 : Segmentation using graph cuts.

Graph cuts are ideally suited for obtaining a rough segmentation of the principal regions in an image.
Figure 10.56 shows a typical result. Figure 10.56(a) is the familiar building image. Consistent with the
idea of extracting the principal regions of an image, Fig. 10.56(b) shows the image smoothed with a
simple 25 × 25 box kernel. Observe how the fine detail is smoothed out, leaving only major regional
features such as the facade and sky. Figure 10.56(c) is the result of segmentation using the graph cut
algorithm just developed, with weights of the form discussed in the previous example, and allowing only
two partitions. Note how well the region corresponding to the building was extracted, with none of the
details characteristic of the methods discussed earlier in this chapter. In fact, it would have been nearly
impossible to obtain comparable results using any of the methods we have discussed thus far without
significant additional processing. This type of result is ideal for tasks such as providing broad cues for
autonomous navigation, for searching image databases, and for low-level image analysis.

10.7 SEGMENTATION USING MORPHOLOGICAL WATERSHEDS

10.7

Thus far, we have discussed segmentation based on three principal concepts: edge
detection, thresholding, and region extraction. Each of these approaches was found
to have advantages (for example, speed in the case of global thresholding) and dis-
advantages (for example, the need for post-processing, such as edge linking, in edge-
based segmentation). In this section, we discuss an approach based on the concept of
so-called morphological watersheds. Segmentation by watersheds embodies many of
the concepts of the other three approaches and, as such, often produces more stable
segmentation results, including connected segmentation boundaries. This approach
also provides a simple framework for incorporating knowledge-based constraints
(see Fig. 1.23) in the segmentation process, as we discuss at the end of this section.

BACKGROUND
The concept of a watershed is based on visualizing an image in three dimensions,
two spatial coordinates versus intensity, as in Fig. 2.18(a). In such a “topographic”
interpretation, we consider three types of points: (1) points belonging to a regional
minimum; (2) points at which a drop of water, if placed at the location of any of those

[Link]

DIP4E_GLOBAL_Print_Ready.indb 786 6/16/2017 2:14:09 PM