Page 313 -

Section 9.4 Segmentation, Clustering, and Graphs 281

FIGURE 9.22: Images segmented using Algorithm 9.8, shown next to segments. Figures
obtained from http://people.cs.uchicago.edu/ ~ pff/segment/, by kind permission of
Pedro Felzenszwalb.

Comparing the edge weight to the internal difference of the clusters requires
some care, because in small clusters the internal distance might be zero (if there
is only one vertex), or implausibly small. To deal with this, Felzenszwalb and
Huttenlocher (2004) define a function of two clusters, MInt, as
MInt(C 1 , C 2 ) = min(int(C 1 )+ τ(C 1 ), int(C 2 )+ τ(C 2 ))

where τ(C) is a term that biases the internal difference upward for small clusters;
Felzenszwalb and Huttenlocher (2004) use τ(C)= k/ |C |,for k some constant
parameter. This algorithm is notably fast and relatively accurate (Figure 9.22).

9.4.3 Divisive Clustering with a Graph
As we have seen (Section 9.2.3), it is extremely useful to separate an image into
a foreground and background based on examples. Assume we have a map of pix-
els, one per image pixel, where each pixel in the map carries one of three labels:
foreground, background or unknown (these maps are sometimes known as trimaps)
depending on whether the corresponding image is in the foreground, background
or is unknown. We should like to take the foreground and background pixels, build
models from these, then label the unknown pixels with these models. There are two
important constraints on the labels. First, a pixel that looks like the foreground
examples should get a foreground label (similarly for background). Second, pixels
should tend to have labels that are the same as their neighbors’.
Boykov and Jolly (2001) phrase this problem as energy minimization. Write F
for the set of pixels with foreground labels, B for the set with background labels, and
U for the unknown pixels. We associate a binary variable δ i with the ith unknown