Page 260 -

5.1 Active contours 239

(a) (b)
Figure 5.2 Snakes (Kass, Witkin, and Terzopoulos 1988) c 1988 Springer: (a) the “snake pit” for interactively
controlling shape; (b) lip tracking.

In interactive applications, a variety of user-placed constraints can also be added, e.g.,
attractive (spring) forces towards anchor points d(i),

2
E spring = k i f(i) − d(i) , (5.6)
as well as repulsive 1/r (“volcano”) forces (Figure 5.2a). As the snakes evolve by minimiz-
ing their energy, they often “wiggle” and “slither”, which accounts for their popular name.
Figure 5.2b shows snakes being used to track a person’s lips.
Because regular snakes have a tendency to shrink (Exercise 5.1), it is usually better to
initialize them by drawing the snake outside the object of interest to be tracked. Alterna-
tively, an expansion ballooning force can be added to the dynamics (Cohen and Cohen 1993),
essentially moving each point outwards along its normal.
To efficiently solve the sparse linear system arising from snake energy minimization, a
sparse direct solver (Appendix A.4) can be used, since the linear system is essentially penta-
4
diagonal. Snake evolution is usually implemented as an alternation between this linear sys-
tem solution and the linearization of non-linear constraints such as edge energy. A more direct
way to find a global energy minimum is to use dynamic programming (Amini, Weymouth,
and Jain 1990; Williams and Shah 1992), but this is not often used in practice, since it has
been superseded by even more efficient or interactive algorithms such as intelligent scissors
(Section 5.1.3) and GrabCut (Section 5.5).

Elastic nets and slippery springs
An interesting variant on snakes, first proposed by Durbin and Willshaw (1987) and later
re-formulated in an energy-minimizing framework by Durbin, Szeliski, and Yuille (1989), is
the elastic net formulation of the Traveling Salesman Problem (TSP). Recall that in a TSP,
the salesman must visit each city once while minimizing the total distance traversed. A snake
that is constrained to pass through each city could solve this problem (without any optimality
guarantees) but it is impossible to tell ahead of time which snake control point should be
associated with each city.

4 A closed snake has a Toeplitz matrix form, which can still be factored and solved in O(N) time.