Snakes

In order to analyse the frequency components of a curve using Fourier we must first represent it mathematically. As we are working with images, a discrete spatial domain, then we have to deal with discretisation. This is illustrated in Figure 1. 

Figure 1: Two possible boundaries of the edge of an image.

The top diagram is better, as the contour has a constant sampling rate, because each pixel is sampled at its centre. This is suitable for input into Fourier. The bottom diagram does not, as the magnitude of the diagonal vectors are bigger than the others by . Essentially this is all academic, as current techniques for modelling an object’s boundary are far more advanced than iterating around an image analysing a pixel’s neighbourhood for edge points.

Kass et al. [1] proposed a model for representing contours, called active contour models, or snakes. This new technique uses an energy functional to model the contour, the solution is where the snake energy is minimal, and is found using variational calculus. The snake energy is given as

The different terms in the integrand of Eq (1) are different energies which are used to evolve the contour to the desired configuration. Eint is the internal energy of the snake, and it defines the snake’s curvature and elasticity. Eimg is the energy of the image, often called the external energy, and is used to attract the snake to image features of interest. This is usually the image’s edge magnitude. Econ is the constraint energy, and allows for a higher level process to control the snakes evolution; in practice it is normally set to zero.

The internal energy is written as:

although the half multiplication is a matter of debate in the literature, as Williams and Shah [3] use it but Nixon [2] among others, does not. The first order differential is a measure of stretching, the elastic energy, as high values indicate the contour is changing rapidly. The second differential is a measure of the bending, or the curvature energy. α(s) and β(s) are constants, which are usually the same for the entire contour, i.e. all s, and they determine the weighting of the elastic and curvature energies at each point in the contour. More specifically α(s) will help determine the point spacing, high values will mean that the points of the contour will be evenly spaced. Low values of β(s) imply that corners can develop as the curvature is not minimised. The image energy attracts the snake to the details in the image. For this we can use the magnitude of the image’s edges, and define that edges have a low value, so that the snake is attracted to them.

How to catch a snake?

A snake that minimises Esnake must satisfy the Euler equation,

Kass et al. [1] proposed to solve this in one step using variational calculus. Two years after this proposition, in 1990, Williams [3] provided a faster greedy algorithm. This is an algorithm that iterates though the contour. For each contour point, it iterates though the neighbourhood of pixels of the current point, and determines the curvature, contour and image energies for each one. It is then necessary to normalise these energies before multiplying by the coefficients α(s), β(s) and γ(s) (for the image energy) and adding. The minimum of these snake energies is selected as the position for that contour. This processes is repeated until the number of contours points moved is below a threshold.

The derivatives of Eq (2) can be approximated using differencing. Nixon [2] suggests subtracting the Euclidian distance between the current contour point and the following point, from the average Euclidian distance between each contour point and its following one. When the contour is evenly spaced, this energy is zero, as required. The second order differential is approximated as below.

Python code to implement these energies are shown below.

Problems with the Greedy Algorithm

The evolution of the snake depends on the initial contour, and the selection of α(s), β(s) and γ(s), these difficulties are termed initialization and parameterisation respectively. The initial contour must be close to a boundary for the snake to converge on the desired result. In the current algorithm this has been done with a simplistic approach of shrinking a circular contour until it reaches an edge point, and then increasing the radius of the circular contour slightly. In terms of parameterisation, all parameters are set to 1.

There is one other problem associated with active contours; they have difficulties progressing into concave boundaries, and there are no values for α(s) and β(s) that will rectify this. This is illustrated in the movie below of a snake attempting to evolve to the French border.

References