Page 258 -

5.1 Active contours 237

Image segmentation is the task of finding groups of pixels that “go together”. In statistics, this
problem is known as cluster analysis and is a widely studied area with hundreds of different
algorithms (Jain and Dubes 1988; Kaufman and Rousseeuw 1990; Jain, Duin, and Mao 2000;
Jain, Topchy, Law et al. 2004).
In computer vision, image segmentation is one of the oldest and most widely studied prob-
lems (Brice and Fennema 1970; Pavlidis 1977; Riseman and Arbib 1977; Ohlander, Price,
and Reddy 1978; Rosenfeld and Davis 1979; Haralick and Shapiro 1985). Early techniques
tend to use region splitting or merging (Brice and Fennema 1970; Horowitz and Pavlidis 1976;
Ohlander, Price, and Reddy 1978; Pavlidis and Liow 1990), which correspond to divisive and
agglomerative algorithms in the clustering literature (Jain, Topchy, Law et al. 2004). More
recent algorithms often optimize some global criterion, such as intra-region consistency and
inter-region boundary lengths or dissimilarity (Leclerc 1989; Mumford and Shah 1989; Shi
and Malik 2000; Comaniciu and Meer 2002; Felzenszwalb and Huttenlocher 2004b; Cremers,
Rousson, and Deriche 2007).
We have already seen examples of image segmentation in Sections 3.3.2 and 3.7.2.In
this chapter, we review some additional techniques that have been developed for image seg-
mentation. These include algorithms based on active contours (Section 5.1) and level sets
(Section 5.1.4), region splitting and merging (Section 5.2), mean shift (mode finding) (Sec-
tion 5.3), normalized cuts (splitting based on pixel similarity metrics) (Section 5.4), and bi-
nary Markov random fields solved using graph cuts (Section 5.5). Figure 5.1 shows some
examples of these techniques applied to different images.
Since the literature on image segmentation is so vast, a good way to get a handle on some
of the better performing algorithms is to look at experimental comparisons on human-labeled
databases (Arbel´ aez, Maire, Fowlkes et al. 2010). The best known of these is the Berkeley
1
Segmentation Dataset and Benchmark (Martin, Fowlkes, Tal et al. 2001), which consists
of 1000 images from a Corel image dataset that were hand-labeled by 30 human subjects.
Many of the more recent image segmentation algorithms report comparative results on this
database. For example, Unnikrishnan, Pantofaru, and Hebert (2007) propose new metrics
for comparing such algorithms. Estrada and Jepson (2009) compare four well-known seg-
mentation algorithms on the Berkeley data set and conclude that while their own SE-MinCut
algorithm (Estrada, Jepson, and Chennubhotla 2004) algorithm outperforms the others by a
small margin, there still exists a wide gap between automated and human segmentation per-
2
formance. A new database of foreground and background segmentations, used by Alpert,
Galun, Basri et al. (2007), is also available. 3

5.1 Active contours

While lines, vanishing points, and rectangles are commonplace in the man-made world,
curves corresponding to object boundaries are even more common, especially in the natural
environment. In this section, we describe three related approaches to locating such boundary
curves in images.

1 http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/
2 An interesting observation about their ROC plots is that automated techniques cluster tightly along similar
curves, but human performance is all over the map.
3 http://www.wisdom.weizmann.ac.il/ ∼ vision/Seg Evaluation DB/index.html