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

Fig. 9.14. A closed snake search space converted to a trellis.
once. So with a value of, say, m = 30, the optimal closed snake evolution
would run 30 times slower than the open snake evolution.
As this would be unacceptably slow, Geiger et al. suggest a heuristic speed-
up that requires only two passes of the algorithm. The Viterbi algorithm is
run once using an arbitrary start point—in practice, it is best to choose the
candidate point with highest image gradient that is likely to be on the optimal
contour. Then for the second run the contour is reordered so as to start and
terminate from the second point of the trellis. The argument for this procedure
would be that the second point is more likely to be on the optimal contour
that the arbitrary first point since the snake energy minimization process will
have “pulled” it toward the optimal contour. Now assuming our trellis has N
control points, if the second point is more likely to be on the optimal contour
than the first, why not unwrap the trellis at the N/ 2 th point on the other side
of the circular search space?
This idea leads us to the mid-point heuristic. The mid-point heuristic can
be stated as, the optimal positions of the mid-points of a snake are generally
independent of the positions of the end-points . This led Gunn and Nixon [71] to
propose a similar two-pass technique to use dynamic programming to solve the
closed snake problem using two open snakes. The closed snake is converted
to an open snake problem by unwrapping about an arbitrary cut point as
before. First an open snake minimization is performed using no smoothness
or continuity constraints on the endpoints. The two points at the mid-point
of this contour are then taken as the start and end points for the closed
contour. The Viterbi algorithm is run again with the start and end points
fixed. Thus we only require two runs of the Viterbi algorithm instead of the
m runs required for the optimal method.
Although these heuristics work well in practice, there is a theoretical pos-
sibility that they may fail to find the true optimal contour. We address this
issue in Section 10.2 and describe a fast and optimal minimization method
using branch and bound techniques.