Active Contours

Psychologists of vision have delighted in various demonstrations in which prior knowledge helps with interpreting an image. Sometimes the effects are dramatic, to the point that the viewer can make no sense of the image at all until, when cued with a single word, the object pops out of the image. This idea of “priming” with prior knowledge is illustrated (light-heartedly) in figure 1.1.

Active shape models encompass a variety of forms, principally snakes, deformable templates and dynamic contours. Snakes are a mechanism for bringing a certain degree of prior knowledge to bear on low-level image interpretation. Rather than expecting desirable properties such as continuity and smoothness to emerge from image data, those properties are imposed from the start. Specifically, an elastic model of a continuous, flexible curve is imposed upon and matched to an image. By varying elastic parameters, the strength of prior assumptions can be controlled. Prior modelling can be made more specific by constructing assemblies of flexible curves in which a set of parameters controls kinematic variables, for instance the sizes of various subparts and the angles of hinges which join them. Such a model is known as a deformable template, and is a powerful mechanism for locating structures in an image.

Throughout this book, visual curves are represented in terms of parametric spline curves, as is common in computer graphics. These are curves (x(s),y(s)) in which s is a parameter that increases as the curve is traversed, and x and y are particular functions of s, known as splines. A spline of order d is a piecewise polynomial function, consisting of concatenated polynomial segments or spans, each of some polynomial order d, joined together at breakpoints. Parametric spline curves are attractive because they are capable of representing efficiently sets of boundary curves in an image (figure 3.1). Simple shapes can be represented by a curve with just a few spans. More complex shapes could be accommodated by raising the polynomial order d but it is preferable to increase the number of spans used. Usually the polynomial order is fixed at quadratic (d = 3) or cubic (d = 4)¹. Maintaining a fixed, low polynomial degree, even in the face of geometric complexity, makes for computational stability and simplicity.

In practice, it is very desirable to distinguish between the spline-vector Q ∈ SQ that describes the basic shape of an object and the shape-vector which we denote X ∈ S, where S is a shape-space. Whereas SQ is a vector space of B-splines and has dimension NQ = 2N _B , the shape-space S _X is constructed from an underlying vector space of dimension N _X which is typically considerably smaller than NQ. The shape-space is a linear parameterisation of the set of allowed deformations of a base curve. The necessity for the distinction is made clear in figure 4.1. To obtain a spline that does justice to the geometric complexity of the face shape, thirteen control points have been used. However, if all of the resulting 26 degrees of freedom of the spline-vector Q are manipulated arbitrarily, many uninteresting shapes are generated that are not at all reminiscent of faces. Restricting the displacements of control points to a lower- dimensional shape-space is more meaningful if it preserves the face-like quality of the shape. Conversely, using the unconstrained control-vector Q leads to unstable active contours and this was illustrated in figure 2.4 on page 31.

The use of image-filtering operations to highlight image features was illustrated in chapter 2. Figure 2.1 on page 27 illustrated operators for emphasising edges, valleys and ridges, and it was shown how the emphasised image could be used as a landscape for a snake. However, for efficiency, the deformable templates described in the next two chapters are driven towards a distinguished feature curve rf(s) rather than over the entire image landscape F that is used in the snake model. This is rather like making a quadratic approximation to the external snake energy: where rf(s) lies along a ridge of the feature-map function F. The increase in efficiency comes from being able to move directly to the curve rf, rather than having to iterate towards it as in the original snake algorithm described in section 2.1.

Chapters 3 and 4 dealt with the geometry and representation of curves and classes of curves — the shape-spaces. Now it is time to look at some image data to see how shapes can be approximated by members of those classes. The norm and inner product machinery developed earlier proves useful together with the image-processing techniques of chapter 5. Curve approximation techniques are built up step by step in this chapter until the necessary tools are assembled for basic B-spline snakes and deformable templates.

In certain three-dimensional applications (chapter 1), such as the 3D mouse in figure 1.16 on page 20, a shape-vector X is used to compute pose, in that case the position and attitude of the hand. Similarly, in facial animation, it is desirable to compute the attitude of the head, independently of expression if possible. The problem is to convert a shape-vector X, from a planar or three-dimensional shape-space respectively, into three-dimensional translation R _c and rotation R.

The remainder of the book aims to establish effective procedures for tracking curves in sequences of images. As with single images, the importance of powerful prior models of shape holds good, but now prior models can be extended to capitalise on the coherence of typical motions through a sequence. Crudely this could mean a repeated application of the regularised curve-fitting of chapter 6, in which the fitted curve in the k — 1th frame of a sequence is used as an initial estimate of curve position and shape for the kth frame. In the probabilistic context of chapter 8 this would involve applying, to each frame, a Gaussian prior distribution with fixed covariance but whose mean was simply the estimated shape from the previous frame. This immediately suggests a more subtle approach. Rather than fixing the form of the prior via one constant covariance for all frames, it seems more natural to take the posterior from frame k — 1 as the prior for frame k. In that way, it would not be merely an estimated shape that would pass from time-step to time-step but an entire probability distribution.

In the previous chapter, dynamical models were characterised by a second-order state density p(X(t)), evolving temporally, and representing the prior distribution for the state X at each time t. In this chapter, both the prior dynamical model and visual measurements are to be taken into account. The result is a fusion of information, both prior and observational, as was set out in chapter 8 for single images, but done now for image sequences, to track motion.

In the previous chapter, dynamic contour tracking was based on prediction using dynamical models of the kind set out in chapter 9. The parameters of the models were fixed by hand to represent plausible motions such as constant velocity or critically damped oscillation. Experimentation allows these parameters to be refined by hand for improved tracking but this is a difficult and unsystematic business, especially in high-dimensional shape-spaces which may have complex couplings between the dimensions. What is far more attractive is to learn dynamical models on the basis of training sets. Initially, a hand-built model is used in a tracker to follow a training sequence which must be not too hard to track. This can be achieved by allowing only motions which are not too fast, and limiting background clutter or eliminating it using background subtraction (chapter 5). Once a new dynamical model has been learned, it can be used to build a more competent tracker, one that is specifically tuned to the sort of motions it is expected to encounter. That can be used either to track the original training sequence more accurately, or to track a new and more demanding training sequence, involving greater agility of motion. The cycle of learning and tracking is described in figure 11.1. Typically two or three cycles suffice to learn an effective dynamical model.

This chapter describes in detail a powerful algorithm for contour tracking that uses random sampling — the Condensation algorithm. It applies to cases where there is substantial clutter in the background. Clutter presents a particular challenge because elements in the background may mimic parts of foreground features. In the most severe case of camouflage, the background may consist of objects similar to the foreground object, for instance when a person is moving past a crowd. The probability density for X at time t _k is multi-modal and therefore not even approximately Gaussian. The Kaiman filter is not suited to this task, being based on pure Gaussian distributions.