Page 303 -

Section 9.3 Image Segmentation by Clustering Pixels 271

FIGURE 9.16: Segmentation results from the watershed algorithm, applied to an image
by Martin Brigdale. Center: watershed applied to the image intensity; notice some long
superpixels. Right: watershed applied to image gradient magnitude; this tends to produce
rounder superpixels. Martin Brigdale c Dorling Kindersley, used with permission.

It is straightforward to modify both divisive and agglomerative clusterers to
ensure that regions are connected. Agglomerative clusterers need to merge only
clusters with shared boundaries. It is more difficult to modify divisive clusterers,
which need to ensure that the children of any split are connected. One way to do
this is to split along spatial boundaries in the segment being split. It is usually
impractical to look for the best split of a cluster (for a divisive method) or the
best merge (for an agglomerative method). Divisive methods are usually modified
by using some form of summary of a cluster to suggest a good split (for example,
a histogram of pixel colors). Agglomerative methods also need to be modified,
because the number of pixels means that one needs to be careful about the inter-
cluster distance (the distance between cluster centers of gravity is often used).
Finally, it can be useful to merge regions simply by scanning the image and merging
all pairs whose distance falls below a threshold, rather than searching for the closest
pair.
9.3.2 The Watershed Algorithm

An early segmentation algorithm that is still widely used is the watershed algorithm.
Assume we wish to segment image I. In this algorithm, we compute a map of the
image gradient magnitude, ||∇I ||. Zeros of this map are locally extreme intensity
values; we take each as a seed for a segment, and give each seed a unique label.
Now we assign pixels to seeds by a procedure that is, rather roughly, analogous to
filling a height map with water (hence the name). Imagine starting at pixel (i, j);
if we travel backward down the gradient of ||∇I ||, we will hit a unique seed. Each
pixel gets the label of the seed that is hit by this procedure.
You should recognize this description as a form of shortest path algorithm;
it can also be seen as a form of agglomerative clusterer. We start with seed clus-
ters, then agglomerate pixels to clusters when the path to the cluster is “downhill”