Page 317 -

Section 9.5 Image Segmentation in Practice 285

(where cut(A, B) is the sum of weights of all edges in V that have one end in A and
the other in B,and assoc(A, V ) is the sum of weights of all edges that have one end
in A). This score is small if the cut separates two components that have few edges
of low weight between them and many internal edges of high weight. We would like
to find the cut with the minimum value of this criterion, called a normalized cut.
The criterion is successful in practice (Figure 9.24).
This problem is too difficult to solve in this form, because we would need to
look at every graph cut. It is a combinatorial optimization problem, so we can’t
use continuity arguments to reason about how good a neighboring cut is given the
value of a particular cut. Worse, it’s an NP-complete problem, even for grid graphs.
However, Shi and Malik (2000) give an approximation algorithm that generates a
good cut.

FIGURE 9.24: The images on top are segmented using the normalized cuts framework,
described in the text, into the components shown. The affinity measures used involved
intensity and texture, as in Table 9.1. The image of the swimming tiger yields one seg-
ment that is essentially tiger, one that is grass, and four components corresponding to the
lake. Similarly, the railing shows as three reasonably coherent segments. Note the im-
provement over k-means segmentation obtained by having a texture measure. This figure
was originally published as Figure 2 of “Image and video segmentation: the normalized
cut framework,” by J. Shi, S. Belongie, T. Leung, and J. Malik, Proc. IEEE Int. Conf.
Image Processing, 1998 c IEEE, 1998.

9.5 IMAGE SEGMENTATION IN PRACTICE
Code is now available for many important image segmenters. The EDISON codes
(from Rutgers’ computer vision group, available at http://coewww.rutgers.edu/