Page 291 -

270 5 Segmentation

5.7 Exercises

Ex 5.1: Snake evolution Prove that, in the absence of external forces, a snake will always
shrink to a small circle and eventually a single point, regardless of whether first- or second-
order smoothness (or some combination) is used.
(Hint: If you can show that the evolution of the x(s) and y(s) components are indepen-
dent, you can analyze the 1D case more easily.)
Ex 5.2: Snake tracker Implement a snake-based contour tracker:

1. Decide whether to use a large number of contour points or a smaller number interpo-
lated with a B-spline.
2. Define your internal smoothness energy function and decide what image-based attrac-
tive forces to use.
3. At each iteration, set up the banded linear system of equations (quadratic energy func-
tion) and solve it using banded Cholesky factorization (Appendix A.4).

Ex 5.3: Intelligent scissors Implement the intelligent scissors (live-wire) interactive seg-
mentation algorithm (Mortensen and Barrett 1995) and design a graphical user interface
(GUI) to let you draw such curves over an image and use them for segmentation.
Ex 5.4: Region segmentation Implement one of the region segmentation algorithms de-
scribed in this chapter. Some popular segmentation algorithms include:

• k-means (Section 5.3.1);
• mixtures of Gaussians (Section 5.3.1);

• mean shift (Section 5.3.2) and Exercise 5.5;
• normalized cuts (Section 5.4);

• similarity graph-based segmentation (Section 5.2.4);
• binary Markov random fields solved using graph cuts (Section 5.5).

Apply your region segmentation to a video sequence and use it to track moving regions
from frame to frame.
Alternatively, test out your segmentation algorithm on the Berkeley segmentation database
(Martin, Fowlkes, Tal et al. 2001).

Ex 5.5: Mean shift Develop a mean-shift segmentation algorithm for color images (Co-
maniciu and Meer 2002).

1. Convert your image to L*a*b* space, or keep the original RGB colors, and augment
them with the pixel (x, y) locations.

2. For every pixel (L, a, b, x, y), compute the weighted mean of its neighbors using either
a unit ball (Epanechnikov kernel) or finite-radius Gaussian, or some other kernel of
your choosing. Weight the color and spatial scales differently, e.g., using values of
(h s ,h r ,M) = (16, 19, 40) as shown in Figure 5.18.