This section introduces three extensions to the basic snake approach to facilitate the extraction of features.
The first extension affects the direction the snake moves when hill climbing the gradient. In normal hill climbing, each step is taken in the direction of steepest ascent, the step size being determined by the size of the differential. Roughly, this translates into forces at points along the body of the snake. Each force points in the direction of steepest ascent locally, but interacts with other forces through the various shape constraints. Looking at the gradient function and contour lines of Figure 14, there is a steep slope leading to the top of each ridge. But there is also a significant slope along each ridge away from the doorway towards the boundary of the state space. Thus the force on a single point on the body of the snake is not directly towards the top of the ridge but turned towards its apex, as indicated by the bold black arrow on the left hand side of Figure 15.
This force can be broken into two components with respect to the snake, a normal and a tangential force. The latter force acts along the body of the snake. Once the shape is constrained to be a quadrilateral, this will cause the relevant side to shrink. This effect will be partially counteracted by the force towards the top of the ridge on the adjacent side of the quadrilateral. But the net result will be a shrinking of the two sides associated with the ridges inwards until the forces are balanced. This will push the corner of the quadrilateral near the doorway inwards, as indicated by the thin black arrow in Figure 15. In an extreme case, this might cause the snake to collapse into something close to a triangle. But the more likely outcome will just be a degradation of the accuracy of registration of the ridges.
Drummond (1998) prevented this degradation of the accuracy by restricting the snakes to rectangular shapes. But with the weakening of this constraint to more general polygons, this effect again becomes a problem. This problem is addressed by removing the component of the force tangential to the snake. Then hill climbing is always in the direction of the normal. This does not significantly restrict the motion of the snake: all that is being removed is the component along the body of the snake. Thus it mainly prevents the stretching and shrinking of the snake due to the gradient.
The second extension controls the way the snake is expanded to reach the base of the hills. Drummond (1998) used a ballooning force, as introduced by Cohen and Cohen (1993). But problems arose when extending the system to deal with more general shapes than rectangles, such as the outer L-shaped room in Figure 6. The ballooning force expands the snake in directions normal to its body. One deleterious effect of this is if the snake contacts a sharp external corner, such as that of the inner room, the force tends to push the snake through the corner. This can be seen in Figure 16; the bold continuous lines are the snake; the bold dashed lines are the ridges. If we imagine starting off with a circular snake in the middle of the L-shaped outer room, by the time it reaches the walls of the inner room the sides of the snake are roughly perpendicular to the ridges. Thus there is little to restrain the expansion of the snake and it passes completely through the walls of the inner room.
The approach adopted here is analogous to the flow of mercury. If we imagine starting somewhere in the middle of the L-shaped room and progressively adding mercury, it would tend to fill up the lower regions of the valley first and reach the bases of the hills roughly at the same time. The analogy of mercury is used as it has a high surface tension preventing it from flowing through small gaps in the edges associated with doorways. To increase the effectiveness of this idea, the absolute value of the differential of the gradient is thresholded, values above the threshold being set to one those below to zero. It is then smoothed with a truncated Gaussian, as shown in Figure 17. Smoothing and thresholding are commonly used techniques in machine vision (Tanimoto 1990). They are typically used to remove noise, but here the aim is to strongly blur the thresholded image. This produces bowls associated with each room. In this example, the smoothing has almost completely obscured the presence of the doorway, although this is generally not the case.
The snake is initialized as a small circle at the minimum of one of these bowls. This is shown as the circle in the middle of Figure 18, where the dashed lines are the contour lines of this function. It then flows outwards, so as to follow the contour lines of the bowl; the largest component of the flow being in the direction of the arrows in Figure 18. This is achieved by varying the force normal to the body of the snake according to the height difference with the average height of the snake. Thus points along the snake which are higher than average tend to get pushed inwards, those lower pushed outwards. The surface tension of the mercury is produced by various smoothing constraints on the first and second differentials of the snake (see Appendix A).
The third extension limits changes in the shape of the snake as it expands from its initial position to reach the base of the hills. The smoothness constraints on the snake, that give the mercury-like properties, prevent the snake flowing through the gaps associated with the doorways. But even this proved insufficient if the width of the rooms and the width of doorways were of similar sizes. In Figure 12, looking at the ``room'' on the left hand side of the configuration space of the robot arm, the ``doorway'' and the ``room'' at the top are of similar width. Increasing the surface tension of the mercury sufficiently to prevent flow through the doorways also prevents the flow to the top of the room.
The solution is to limit the amount the snake can change its shape as it grows. This is achieved by constraining how much the second differential of the snake can change from step to step. In Figure 18, it is apparent that the snake takes up a good approximation to the shape of the room some time before it reaches the ridges. If the shape can be locked-in before reaching the ridges, the problem just described can be avoided. When the snake is initialized, the only constraint is smoothness. As the snake is expanded, this smoothness constraint is progressively weakened and the curvature constraint progressively strengthened. This progressively locks in the shape while still allowing the snake to make small local adjustments to better fit the features.
The extensions, discussed in this section, either modify the
traditional forces that act on the snake or add new ones. There are
also forces associated with knot spacing and drag. How the snake
moves, with each iteration, depends on the vector addition of these
forces. The sum acts to accelerate the body of the snake which has
both mass and velocity, and therefore momentum. A schematic
representation of these forces is shown in Figure 19; a
more detailed mathematical description is given in Appendix A. The
dashed line represents the body of the snake; the arrows are the
forces applied to one point on the body. The snake is a parameterized
function, given by 
where x(s) and y(s)
are individual cubic b-splines giving the x and y coordinates
associated with a variable s along the body of the snake. The
circles represent points equi-distant in s but not necessarily in
x and y. These points are kept roughly the same Euclidean distance
apart in x and y due to the knot spacing force. The momentum,
although not strictly a force, encourages the point to move in
constant direction; the drag opposes any motion. The stiffness
encourages the snake to maintain a smooth shape. The overall stiffness
is reduced as the snake grows, to keep its flexibility per unit length
roughly constant, and is also controlled locally to maintain its
shape.
The following is an algorithmic summary of the processing of the snake: