Page 272 -

5.2 Split and merge 251

then allowing both merging and splitting operations (Horowitz and Pavlidis 1976; Pavlidis
and Liow 1990).

5.2.1 Watershed

A technique related to thresholding, since it operates on a grayscale image, is watershed com-
putation (Vincent and Soille 1991). This technique segments an image into several catchment
basins, which are the regions of an image (interpreted as a height field or landscape) where
rain would flow into the same lake. An efficient way to compute such regions is to start flood-
ing the landscape at all of the local minima and to label ridges wherever differently evolving
components meet. The whole algorithm can be implemented using a priority queue of pixels
and breadth-first search (Vincent and Soille 1991). 8
Since images rarely have dark regions separated by lighter ridges, watershed segmen-
tation is usually applied to a smoothed version of the gradient magnitude image, which also
makes it usable with color images. As an alternative, the maximum oriented energy in a steer-
able filter (3.28–3.29)(Freeman and Adelson 1991) can be used as the basis of the oriented
watershed transform developed by Arbel´ aez, Maire, Fowlkes et al. (2010). Such techniques
end up finding smooth regions separated by visible (higher gradient) boundaries. Since such
boundaries are what active contours usually follow, active contour algorithms (Mortensen and
Barrett 1999; Li, Sun, Tang et al. 2004) often precompute such a segmentation using either
the watershed or the related tobogganing technique (Section 5.1.3).
Unfortunately, watershed segmentation associates a unique region with each local mini-
mum, which can lead to over-segmentation. Watershed segmentation is therefore often used
as part of an interactive system, where the user first marks seed locations (with a click or
a short stroke) that correspond to the centers of different desired components. Figure 5.13
shows the results of running the watershed algorithm with some manually placed markers on
a confocal microscopy image. It also shows the result for an improved version of watershed
that uses local morphology to smooth out and optimize the boundaries separating the regions
(Beare 2006).

5.2.2 Region splitting (divisive clustering)

Splitting the image into successively finer regions is one of the oldest techniques in computer
vision. Ohlander, Price, and Reddy (1978) present such a technique, which first computes a
histogram for the whole image and then finds a threshold that best separates the large peaks
in the histogram. This process is repeated until regions are either fairly uniform or below a
certain size.
More recent splitting algorithms often optimize some metric of intra-region similarity and
inter-region dissimilarity. These are covered in Sections 5.4 and 5.5.

5.2.3 Region merging (agglomerative clustering)

Region merging techniques also date back to the beginnings of computer vision. Brice and
Fennema (1970) use a dual grid for representing boundaries between pixels and merge re-

8 A related algorithm can be used to compute maximally stable extremal regions (MSERs) efficiently (Sec-
tion 4.1.1)(Nist´ er and Stew´ enius 2008).