Snakes and Active Contours - Bezier and Splines in Image Processing and Machine Vision - page 197

Dynamic Programming for Open Snakes
Returning now to the calculation of evolving snakes, the usage of the Viterbi
algorithm is quite straightforward. For each control point, we determine a set
of candidate points for the next evolution of the snake spread along a short
distance in a direction perpendicular to the snake as illustrated in Figure 9.13.
Then the problem of minimizing snake energy becomes the problem of finding
the minimum cost path on this (distorted) trellis. We can allow the starting
node to remain fixed, or by using the initialization trick above, we can allow
both ends of the snake to move freely to a new minimal energy configuration.
This algorithm can be applied iteratively to allow the snake to evolve over a
larger area.
A problem that can be encountered is that the control points of the snake
may bunch up and become uneven after several iterations. Thus it becomes
necessary to reinterpolate the control points from time to time. Another prob-
lem common to all snake techniques is the risk of the snake crossing itself or
forming loops that may be undesirable for the purposes of image segmenta-
tion. While many researchers have tackled this problem [82, 128, 123], most
solutions are somewhat inelegant and add significant complexity to the ap-
proach.
Fig. 9.13. An open snake converted to a trellis.
Dynamic Programming for Closed Snakes
Closed snake energy minimization presents a challenge because the ecient
application of dynamic programming is not entirely straightforward. Geiger
et al. [66] address this problem in the context of dynamic programming for
energy minimization. Their approach is to unwrap the circular domain to
form a linear trellis as shown in Figure 9.14. To ensure that the solution is
indeed a closed contour, they examine shortest paths where the start and finish
nodes have the same index and select the global minimum contour. Thus if m
candidate points are to be examined, this method would require the Viterbi
algorithm to be run m times for each possible starting node instead of just