Active Contours



The goal of this project was to isolate a particular object (or curve) in a given image in a semisupervised way using a simple active contour algorithm. This algorithm is semisupervised in the sense that user input is required to initialize the contour to be in some sense “near” the object of interest. To accomplish our task, we implemented a slightly modified version of the SNAKE algorithm outlined in Trucco and Verri. This report is organized as follows. In section 1 we introduce the problem of isolating an object in a greyscale image and outline the basic ideas behind the SNAKE algorithm. In section 2, we describe in detail our implementation of the algorithm as given in Trucco and Verri. In section 3, we describe a very simple multiresolution extension of this algorithm that results in somewhat improved convergence properties. In section 4 we describe a series of experimental results and discuss the effects of each user-tunable parameter on the performance of the algorithm. In section 5 we conclude our report with a brief discussion of the overall effectiveness of the SNAKE algorithm for object isolation.


  1. Introduction

For the purposes of this project, we will consider only the problem of isolating objects in an image that can be well-represented by a single, closed contour (i.e. a polygon). We also make some assumptions about the objects we will be looking for in the image. First, we assume that they are visually distinct from the background in the sense that there is a large gradient magnitude located at the border between the object and the background. This gradient information will form the images contribution to the SNAKE algorithm. We also assume that the object is to some extent “smooth” and is entirely located in the image (i.e. it does not extend beyond the image borders).

Given this information, it is possible to describe several desirable properties for our final closed contour. First, and perhaps most importantly, the contour should pass through regions of high gradient magnitude (edges). The curve should also be somewhat continuous—it should not include one or more isolated points very far from the rest of the image. Finally, as we are assuming that the objects we search for are somewhat smooth in appearance, it is reasonable to assume that we should desire our final closed contour be smooth in some sense.

From these desirable properties we may devise a very simple cost function for our contour. This development follows exactly that in Truco and Verri. We will represent the points on our closed contour by p1, p2, … , pN. As the contour is closed, we will follow Matlab’s convention and assume p1 = pN. We therefore have N-1 unique points in our curve and N-1 line segments connecting these curves. For the first condition above, which depends upon the gradient magnitude, we would like a term which decreases monotonically as the gradient magnitude increases. The simplest such functional form gives us one term for our cost function:

, (1)

where I represents the input image. As usual, it is not advisable to calculate gradients directly on the input image but rather on some smoothed version of the input image. The degree of image smoothing is an algorithm parameter and is discussed in greater detail in section 4.

For the second term of our cost function, we would like some measure of the “continuity” of the contour. Trucco and Verri suggest a simple term calculated using the following expression:

(2)

where is the average distance between points on the contour and is calculated via:

. (3)

This is effectively the variance of the distances between points on the contour.

Finally, Trucco and Verri suggest that the “smoothness” of the contour should be measured using a discrete approximation to the second derivative of the contour via:

. (4)

This term favors points aligned equidistantly in a straight line across the image. Unfortunately, it is also minimized whenever we have pi-1 = pi = pi+1. This effect is discussed in more detail in section 4. One can therefore naively define a total energy functional using a weighted linear combination of the terms in equations (1), (2), and (4). In the following section, however, we will see that it will be necessary to perform some sort of normalization to ensure that none of these three terms numerically dominates the others.


2. The basic SNAKE algorithm

Trucco and Verri suggest a simple greedy algorithm for minimizing a representative cost function. First, the constants α, β, and γ are selected by the user to weight the continuity, curvature, and image gradient terms respectively in the final cost function. For a single point in the contour (pi), it is possible to perform the following steps. First, for every point in a 7 x 7 neighborhood1, compute the following functional:

. (5)

Here, it is important to normalize each of the terms in this functional to the range [0,1]. Note that only a few of the terms in (5) are affected by the location of pi in its neighborhood. Specifically, pi only affects one Eimage term, two Econt terms, and three Ecurv terms. Once the normalized version of (5) is computed for every point in the neighborhood, it is possible to update pi, moving it to the location of the locally minimizing point.

The overall idea of the SNAKE algorithm as presented in Trucco and Verri’s text is to iterate the above procedure. Specifically, they suggest cycling through the N-1 points on the contour and choosing (in a purely greedy fashion) the “best” location for each of the points. Proceeding in this manner, it is easy to see that one will eventually arrive at a local minimum of the cost surface (although this argument is somewhat complicated by the normalization process which uses a different normalization constant for each point on the contour) but certainly is not guaranteed to reach the global minimum.

4. Our implementation of the SNAKE algorithm

In our implementation, we made a few departures from Trucco and Verri’s description of the SNAKE algorithm. First, as suggested by Professor Collins, we ignored the corner elimination step from their algorithm. More substantially, Trucco and Verri suggest calculating only once per iteration (N-1 points) of the algorithm. While this is computationally efficient, it fails somewhat in capturing the fundamental essence of the continuity term to the energy function—i.e. by not taking into account the effect of moving each point on the contour on the mean distance between points we cannot be sure we are accurately minimizing the variance of distances in the contour. This problem is especially visible when considering only the continuity term, in which case the variance of the inter-point distances along the contour should be decreased after each iteration and eventually forced to a very small value. By exactly tracking the effect of each change on the overall mean and variance of the inter-point distances, this does indeed happen.

Our second major departure from the Trucco and Verri formulation of the algorithm was in the calculation of image gradients. The authors do not explicitly mention the use of Gaussian smoothing in the calculation of the image gradients, but it is certainly necessary to do so. There is, however, the difficulty of choosing a reasonable standard deviation for the smoothing. If not enough smoothing is applied, the contour can be somewhat “myopic” and not see strong image gradients lying outside its neighborhood. On the other hand, if the smoothing is too aggressive, edge localization suffers. An obvious compromise between these two extremes is to use a large standard deviation early in the learning, when the contour may be somewhat far from the object of interest, and a small standard deviation late in the learning, when the contour should already be somewhat near the edges of interest. There are two major drawbacks to this method. The first is computational complexity, as the smoothing and gradient operations must be performed more than once per object. In our experiments, this did not appear to be a problem. The other obvious difficulty lies in choosing an appropriate schedule by which the standard deviation is decreased. Theoretically, it should be possible to adaptively calculate a reasonable standard deviation value based on whether or not the contour points are “near” regions of high edge activity in the image. For the purposes of this project, however, we used a simple, fixed schedule that worked well in our (admittedly limited) experimentation.


4. Experimental results

In order to investigate the contour configurations favored by each of the three cost terms, we first ran the SNAKE algorithm using each of the three cost terms alone. The results of these experiments are summarized in Figure 1. In the first image, we see the results using only the continuity term (i.e. α = 1, β = 0, γ = 0). Here, we see the contour does not move far from its initial location. It does, however, move so that each of the N-1 points are equidistant from their neighbors. In this case, the variance of the distance between each point and its neighbors is very nearly zero (it may not exactly achieve zero as the points must adhere to a discrete lattice). In the second image, we allow the edge term to dominate (i.e. α = 0, β = 0, γ = 1). Here, we see that for the same initialization, the contour prefers a trapezoidal configuration in which several points lie at exactly the same location in the image. The reason for this behavior is that the image is not exactly a circle and hence does not have an exactly circular edge. Because of discrete sampling effects, there are actually points on the circle that have higher gradient responses than their neighbors. These are the points favored by the contour vertices. In the final example, we see a result when the continuity term dominates. Here, we do see two sharp edges, but these are apparently offset by the remaining vertices becoming nearly perfectly aligned.

In figures 2 and 3, we display the final results of Trucco and Verri’s SNAKE algorithm using all three cost function terms and weights (i.e. α = 3, β = 1, γ = 1.2). We see that these results are quite reasonable, although we did need to begin quite close to the swan to achieve a reasonable segmentation. In figure 1, we also more closely investigate the effect of the standard deviation of the smoothing function on algorithm performance. While good results were achieved with a standard deviation of 3, we see that increasing the standard deviation to 10 results in very poor edge localization. This occurs primarily because the edge information is spread out over a very large area in the image and the difference between the final contour location and the “desired” contour location in terms of image gradient is rather small. In this case, the other two terms dominate to some degree. Conversely, we see that if the standard deviation of the smoothing function is too small (in this case 1), some points on the contour never “see” the edges of the object and do not move much from their initial locations.

In figure 4, we presented the algorithm with a more challenging initialization. Here, we see that the method with a single, fixed standard deviation (lower left) gets “stuck” in a local minimum with three points stranded far from the object edge. The proposed method (lower right) which gradually decreases the value of sigma as the number of iterations increases, however, handles this case quite nicely.

Finally, in figure 5, we show the operation of the proposed method on the circle image. Here, we have superimposed the contour over the smoothed gradient image to illustrate how allowing the standard deviation of the smoothing function to change over time affects the convergence properties of the algorithm. The number of iterations required before convergence for this method is somewhat larger, but the final result is good for a rather larger range of initializations.


5. Conclusions

The SNAKE algorithm as described in Trucco and Verri is very simple to implement, converges relatively quickly, and works fairly well under controlled conditions. We note, however, that even for the swan image, which should be a fairly simple segmentation task, it was necessary to initialize the contour close to the object to achieve satisfactory results. We note also that there are a number of free parameters that need to be well-tuned for this algorithm to work. If, for instance, the standard deviation of the smoothing function is too high or too low or if the balance between α, β, and γ is not correct, the algorithm does not perform well at all. Many of these problems can be traced back to the greedy nature of the optimization and the rather heuristic cost function devised for the task. For most practical applications, this algorithm does not appear to be a good choice.


Figures

Figure 1: Results achieved using only one of the three cost terms


1 The size of this neighborhood has been chosen to match that used in Trucco and Verri’s implementation and can be arbitrar.



Silverlight Version Rss
<February 2012>
MoTuWeThFrSaSu
303112345
6789101112
13141516171819
20212223242526
2728291234
567891011