Active contours or `Snakes' were first introduced by Kass et al. [1] in 1987 as a method for extracting contours from images, or tracking contours through an image sequence. The snake algorithm is essentially just the minimization of an energy function which depends on the snakes position and attributes of the image (typically the position of edges - as determined by the magnitude of the image gradient).  The sequence of images below show how the position of a typical snake changes as the minimization progresses:
 
 

Initial Frame	8 Iterations	15 Iterations
25 Iterations	30 Iterations	43 Iterations

Snakes can also be used to track a contour moving through an image sequence by using the position of the contour in the last frame as the starting point for the relaxation in the current frame. When the snake is relaxed it should find the new position of the contour. This type of technique has been used succesfully to track the movement of lips in a computerised lip-reading application, and for tracking the movements of objects in medical images.

Snakes have been succesfully used in a number of real applications, particularly in the field of medical imaging, however they are a number of issues which must be addressed before snakes can be used to track general objects. One of the most trouble some situations occurs when the object the snake is tracking becomes occluded, the snakes usually become attached to the leading edge of the occluding object. They also have a tendency to slide off edges or jump onto nearby images without warning. These problems are demonstrated in the sequence below:
 
 

Frame 1	Frame 10
Frame 30	Frame 50

The snakes on the green volkswagon in the background are completely stripped off as the volkswagon is occluded by the box. A snake at the top of the blue truck also becomes attached to the box as the truck goes past.

We have used two techniques to prevent this type of behaviour: texture correlation, and a multiple-hypothesis based technique which we've called `Virtual Snakes'. Texture correlation has been applied to snakes before, however previous techniques would not function well in this particular application since many of the snakes aresituated on occlusion boundaries where, on average, half of the texture doesn't belong to the object that the snake is trying to track. We have dealt with this problem by calculating a texture correlation score for each side of the snake and weighting each score by our estimate of how reliable the texture on that side of the snake is. This approach significantly reduces the probability of a snake sliding, or jumping onto another edge.

Virtual snakes allow the system to cope with strong object occlusion. Essentially the approach is to generate multiple hypotheses whenever an object collision is detected - one hypothses corresponds to the situation where the object is occluded, and one for the situation where the object is occluding. The virtual snakes which correspond to these unresolved hypotheses can also intersect with other objects generating a tree of virtual snakes. At some time after the collision, the hypothsis which appears to be tracking correctly is found and the hypothesis tree (and its associated virtual snakes) is collapsed, and tracking resumes as normal.  The sequence below demonstrates how this system performs on the sequence used above. The colored boxes indicate the objects in the scene. The system is completely automomous - the initial snake positions, the objects, and the detection of the which object is occluded is all automatic.
 
 

Frame 1	Frame 10
Frame 30	Frame 50

The system performs much better than the standard technique, tracking the snakes on the green volkswagon even when it is almost completely occluded.  For more details, you can download our paper.

The sequence showed on this page is available as a zipfile and as a gtarred file. These files contain each frame of the occlusion sequence as a ppm image file.
 

References

[1]   M. Kass, A. Witkin, and D. Terzopoulos, "Snakes: Active contour models." International Journal of Computer Vision. v. 1, n. 4, pp. 321-331, 1987