Snakes: Active Contour Models
Michael Kass, Andrew Witkin, and Dimitri Terzopoulos
Jonathan Chappelow
Biocontrols, Modeling and Computation
Spring 2005
Model Overview and Literature Review
This paper describes a system defined by a very specific energy minimization criteria used for reaching local minima corresponding to a model of an edge or subjective contour in an image. While edge and contour detection has an expansive literature base, deterministic modeling of contours and shapes makes up a much more limited area of research. In addition, modeling contours using energy-minimizing splines, as described in this paper, comprises a very unique approach to the modeling problem. Unlike parametric shape models which are defined by explicit equations of shape [10], active contours are geometric models in which their coordinates arethe parameters of the model. This research is unique in that they have developed an entirely new system for modeling image contours, and they provide an efficient and flexible numerical solution for the system. As will be described, active contours have become an invaluable base tool for segmentation and object tracking.
The energy minimization system developed here differs from traditional contour modeling approaches, which typically involved edge detection followed by subjective interpretation and edge connection [1]. The majority of previous edge detection techniques did not employ deterministic system for modeling contours. Simple edge detection merely involves the use of linear operators such as the Laplacian, followed by thresholding or the use of Canny edge selectionor similar algorithms [8]. The Hough transform has also been used for shape detection and general image characterization. Towards the goals of image segmentation and understanding, many techniques have been employed, such as k-means, optical flow, and region growing [6, 7]. These methods, however, are limited in their inability to recognize and incorporate contour continuity, an important factor in the selection of meaningful edges, as well as in their inability to accept interactive guidance [1].
While modern contour modeling methods such as level set and fast marching methods have been developed [5, 12], the system of energy minimization developed in this paper has continued to provide a unique and flexible way of constraining and controlling the process. The traditional techniques described above solely employ image information in their operations. Snakes introduce low-level mechanisms (contour constraints) that provide additional information and alternative organizations from which higher-level image information can build upon [1]. Alsoas described in this research, there has been no shortage of techniques involving optimization and relaxation for line and edge detection [9]. While these techniques begin to incorporate inherent contour characteristics with image information, the active contour system provides the ability to interactively guide the contour detection by placing initial points.
This paper has contributed an insightful and extensively employed energy-based spline system, which has been built upon and expanded in many respects [13, 14, 15]. Improved external forces have recently been formulated [2], providing much improved edge detection at greater distances from image features. Active contours have also been extended to 3D surface modeling and tracking [3, 4], allowing dynamic segmentation and tracking of cardiac motion [11]. As such, this paper has contributed a versatile framework for assisting in the determination of subjective image contours for the purposes of segmentation and object motion tracking.
Model Details and Matlab Implementation
The snake model is desribed as a controlled continuity model under the influence of image forces [1]. Internal forces control the bending characteristics of the line, while image forces, such as the gradient, serve to push the snake toward image features. When the snake coordinate vector is defined parametrically as, the total energy of the snake is defined as
where Eint and Eimage are the internal and image energy terms, respectively.
The spline’s internal bending energy has been defined by this paper as follows
Here is the first spatial derivative and is the second spatial derivative of the snakes parameters (coordinates). Therefore, the first term represents elasticity, or membrane-like behavior, while the second term represents rigidity, or thin-plate behavior [1]. The coefficients, and , can be used to control the continuity characteristics of the snake by changing its elasticity and rigidity.
When is minimized, the snake has reached a local minimum associated with a contour of the image, and the modeling ceases to evolve until the image is changed. Through variational calculus, the minimization of snake energy is determined by the Euler-Lagrange equation
Since is a vector of x and y points, this equation represents two independent equations. This equation is easily solved using discrete formulations of differentials. First, the internal energy is discretized by the following equation
Applying this result and further differentiating, the Euler equations are represented in discrete formulation by
Grouping snake parameter (v) terms, the following equation is obtained
This equation is solved by use of matrix formulation for efficient calculation of each snake point in a single matrix operation. This can be seen by representing the parameter coefficients as in the equation
and then building a pentadiagonal matrix [1] for seven hypothetical x coordinates:
In this formulation, I am assuming the use of a closed contour for the purposes of segmentation. Evaluation of this matrix equation is equivalent to the Euler equations derived for the minimization of snake energy. In general, the following matrix notation is used to represent the system
This matrix formulation is easily extended to any number of snake points (snake parameters).
The solution of the previous independent equations involves setting the right hand side equal to an arbitrary step size,, times the negative derivative of the left hand side. Assuming the external force is constant during a time step, the solution to a single iteration is determined by matrix inversion:
This procedure is applied iteratively for given internal energy parameters and the specified image information. Under the smoothness constraints of the internal energy coefficients, the local minimum system is determined through the application of the image information. Given elasticity and rigidity parameters appropriate for the physiological system being modeled, along with user-placed initial snake parameters and meaningful image information, an image contour can be precisely modeled. An example of the iterative deformation of a snake toward an image contour is shown below in the segmentation of a large cavity in the abdomen.
I began by forming an initial contour by placing a small number of points near the cavity boundary and interpolating points in between to provide a sufficient number of coordinates for deformation by the discrete formulation of the energy minimization solution. Following this reparameterization step, an iterative deformation process was begun, each time recalculating the pentadiagonal contour continuity matrix to accommodate spatial variations of the elasticity and rigidity coefficients, if such variations are desired. In this model, I set alpha and beta to constants, but the recalculation was nevertheless done. Since the initial snake was placed near a distinct boundary, the model was able to converge on a local minimum very well.
It should be noted that reparameterization of the snake at every iteration is necessary to prevent excessively large or small distances between points from appearing. More importantly, this is necessary to provide consistent meaning to the elasticity and rigidity coefficients along the perimeter of the snake.
As previously mentioned, the gradient of the image was used as the external force in order to draw the snake to areas of the image defined by change in intensity, namely boundaries. In order to allow the snake to lock onto the gradient from a distance, I smoothed the image with a 2D Gaussian kernel with sigma 1. This smoothing window was defined with a diameter of 7 pixels, so as to extend the range at which the snake is able to detect the contour. Increasing the smoothing of the image can provide increased range, but decreases the precision of the final snake. This is a serious limitation of the current implementation of snakes that has been remedied by the use of alternative external forces such as gradient vector flow [2]. The final snake is shown below.
The performance of the snake model was further explored by segmenting additional features of the above image. The success and failure of the model to converge for these additional image features is demonstrated and examined in the discussion section.
Discussion
This modeling procedure is basically a minimization procedure used in the determination of snake parameters, which comprise a geometric model of an image contour. While deterministic relationships in the form of partial differential equations are used in the minimization procedure, the discretized numerical solution is not direct and involves taking iterative Euler steps toward a local minimum. In addition, the system is dynamically determined by the image information, and its convergence, or stability, depends on both appropriate placement of the initial contour and a set of continuity coefficients that allow for solutions concordant with the image features. In these respects,I believe the authors were correct in their assertion that their energy minimization system is a novel approach at detecting and modeling edges and subjective image contours, but the model has several drawbacks that detract from its practical value.
The authors repeatedly characterize active contours as a “power assist” in the process of determining image contours, and this is provided at substantial cost. The primary limitation in the use of active contours is the model’s sensitivity to the user specified coefficients for the internal and external forces. Achieving desired results requires a trial and error process of fine tuning these model coefficients. Not only is the model very sensitive to changes in these parameters, a set of universally applicable parameters does not seem to exist. Changing the image, the shape of the contour, or the location of the contour within an image often requires that new optimal parameters be manually determined for successful convergence of the snake to the desired contour.
The model also proved to be very sensitive to the initial snake positioning. If the snake is placed too far from the relevant contour, the boundary may not be captured. In the segmentation steps shown in the first image, it is evident that parts of the snake did not easily reach the boundary. Especially at the bottom portion of the boundary, the snake can be seen curling towards the boundary as closer points pull the rest of the snake into the invisible gradient field of the smoothed image. In the absence of elasticity and rigidity constraints, portions of the snake not initially exposed to the localized gradient field would not have found their way onto the boundary. In addition, had I placed this snake much farther from the boundary, the snake may not have successfully reached the edge.
The sensitivity of the model to initial snake positioning can be seen in the figures shown on the following page. In the first set of images, the left image shows a carelessly placed snake around a fairly rigid image feature, a vertebra. The snake was placed too far from a portion of the vertebra and was unable to capture the desired contour. The image on the right shows a repositioned snake that was able to capture the entire vertebra edge. In the second set of image, the effect of adjacent image features can be seen. In the left image, portions of the active contour are pushed to contours of adjacent image features instead of the boundary of the desired image feature. While this represents a failure of the snake to produce the desired results, the snake was still able to reach a local minimum of the energy function. This demonstrates the importance of careful initialization of the snake in producing the desired results. The image on the right shows a successful deformation.
Failed Segmentation.Successful Segmentation.
Failed Segmentation. Successful Segmentation
I agree with the authors that the inclusion of internal contour forces contributes greatly to edge detection in its ability to guide contour progression and limit the set of solutions that are obtained from merely considering the image information. This is conceptually evident in the application of snakes to noisy images, where countless local minima are present. The scattered nature of image noise precludes it from being detected as an image feature as a result of the rigidity constraints. In essence, the rigidity constraints implicitly define a contour as a smooth feature. In the above segmentations, the active contour can be seen traversing gradients in background image intensity, which can be viewed as noise in this context. This is a result of the internal energies guiding the active contour.
For the purposes of modeling most physiological structures, smoothness is a generally useful constraint and a ubiquitous image feature. Cancerous tumors on the other hand are typically amorphous and are likely to possess acute features that would not be well fit by snakes with continuity constraints. When I attempted to capture the boundaries of image features with jagged edges, the snake would become rounded and fail to capture the feature. Without relaxing the rigidity constraints, the only way to remedy this behavior is by using a high resolution image and using a finely interpolated snake. This shortcoming is especially evident when the image gradients that define such features are weaker. While it is obvious that strong image information is integral to the functioning of active contours, it is worth noting that as contours become more subjective, snakes become less robust in their ability to capture the local minimum associated with the desired contour.
The authors emphasized the “active” nature of snakes in that the contour is continually minimizing its energy functional. As a result, changes in the modeled image feature due to translation or deformation will influence the model through changes in the image forces. While I was unable to evaluate the dynamic nature of active contours due to the absence of an appropriate data set, I will surmise that snakes are capable of accomplishing this goal for sufficiently small deformations of the boundary being tracked. As I have seen in experimenting with static images, misplacing the snake at a distance too far from the image contour often results in failure of the snake to capture the desired contour. Similar failure will undoubtedly result from excessive movements of image features.
In addition to many of the operational difficulties already mentioned, there were a number of challenges in implementing the model. For many images that I used for testing, the image forces were not strong enough to capture the contour. In many cases, simply relaxing the elasticity and rigidity constraints proved sufficient to allow the snake to fit the contour. However, I found it necessary to add an arbitrary image energy weighting constant as an input to the snake energy minimization solution. While this did not add to the complexity of the implementation greatly, the utilization of the model has an additional element of complexity.
The primary challenge in implementing the energy minimization procedure involved working through the formulation of the discrete representation of the Euler equations and organizing the coefficients into the pentadiagonal matrix described in the paper. The paper’s appendix contained an extremely insightful description of the numerical methods used in the model, and I was able to glean enough information to visualize how the matrix was created and how the solution should be implemented. The result of this effort was given in equations and matrix formulations given earlier.
Smoothing the image, coding a selection routine for the initial snake points, and interpolating snake parameters and vector fields proved to be minor implementation challenges. A 2D Gaussian smoothing kernel was generated using the well known Gaussian distribution equation. The kernel was convolved using Fourier space multiplication for efficient smoothing of large test images. Selection of initial snake points was accomplished with Matlab’s ginput routine, followed by the interpolation routine. Precise equal spacing between snake points was achieved by continuously approximating the step size required for an integer number of segments. Using this method, the snake was able to keep very close to a constant step size while avoiding any boundary anomalies where the ends of the snake are joined.
References
[1] M. Kass, A. Witkin, and D. Terzopoulos, ``Snakes – ActiveContour Models.'' International Journal of Computer Vision,1(4): 321-331, 1987.
[2] C. Xu and J. L. Prince, “Snakes, Shapes, and Gradient VectorFlow.” IEEE Transactions on Image Processing, 7(3): 359-369, 1998.
[3]M. Bertalmio, G. Sapiro and G. Randall. “Morphing Active Contours.”IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(7), 2000.
[4] F. Leymarie and M.D. Levine, "Tracking deformable objects in the plane using an active contour model." IEEE Transactions on Pattern Analysis and Machine Intelligence.15(6). 617-634, 1993.
[5] R. Malladi, J. A. Sethian, B. C. Vemuri, "Shape modeling with front propagation: A level set approach." IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(2): 158-175, 995.