Page 285 -

264 5 Segmentation

Figure 5.22 Comparative segmentation results (Alpert, Galun, Basri et al. 2007) c 2007 IEEE. “Our method”
refers to the probabilistic bottom-up merging algorithm developed by Alpert et al.

5.5 Graph cuts and energy-based methods

A common theme in image segmentation algorithms is the desire to group pixels that have
similar appearance (statistics) and to have the boundaries between pixels in different regions
be of short length and across visible discontinuities. If we restrict the boundary measurements
to be between immediate neighbors and compute region membership statistics by summing
over pixels, we can formulate this as a classic pixel-based energy function using either a
variational formulation (regularization, see Section 3.7.1) or as a binary Markov random
field (Section 3.7.2).
Examples of the continuous approach include (Mumford and Shah 1989; Chan and Vese
1992; Zhu and Yuille 1996; Tabb and Ahuja 1997) along with the level set approaches dis-
cussed in Section 5.1.4. An early example of a discrete labeling problem that combines
both region-based and boundary-based energy terms is the work of Leclerc (1989), who used
minimum description length (MDL) coding to derive the energy function being minimized.
Boykov and Funka-Lea (2006) present a wonderful survey of various energy-based tech-
niques for binary object segmentation, some of which we discuss below.
As we saw in Section 3.7.2, the energy corresponding to a segmentation problem can be
written (c.f. Equations (3.100) and (3.108–3.113)) as

E(f)= E r (i, j)+ E b (i, j), (5.50)
i,j
where the region term
E r (i, j)= E S (I(i, j); R(f(i, j))) (5.51)

is the negative log likelihood that pixel intensity (or color) I(i, j) is consistent with the statis-