Subscribe Now Subscribe Today
Research Article
 

Review of Deformable Curves-A Retro Analysis



A. Prabhu Britto and G. Ravindran
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study reviews Deformable curves (Active contours). The main strength of Deformable curves stems from their capability to provide to humans or higher processes, several interpretations of image data by supporting interactive mechanisms. Deformable curves offer a unique and powerful approach to segmentation. They are capable of accommodating variability of biological structures. The objective of this study is to study the frameworks of different active contour models, classify the methods according to several properties and compare their properties. This study is expected to yield a very good insight into Deformable curves.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

A. Prabhu Britto and G. Ravindran, 2007. Review of Deformable Curves-A Retro Analysis. Information Technology Journal, 6: 26-36.

DOI: 10.3923/itj.2007.26.36

URL: https://scialert.net/abstract/?doi=itj.2007.26.36

INTRODUCTION

A desirable goal from any image processing task is the ability to provide several interpretations of image data, from which humans or higher processes may be able to choose. In the realm of Medical Imaging, this is almost a necessity, as human life could be at stake sometimes and critical decisions may need to be taken.

One of the fundamental image processing tasks is segmentation. There have been many image processing techniques that have been put forth to achieve segmentation. One of these techniques is the Active contour model first proposed by Kass et al. (1987, 1988). It is capable of providing several interpretations of image data to humans or higher processes and this study is expected to yield a very good insight into the strengths of Active Contour Models.

Active contour models or Deformable Curves are also called as Snake because their convergence to edges resembles a snake slithering across a surface. In an image, a deformable curve can converge to align with the nearest salient feature corresponding to local minima in the energy generated by processing the image. Hence it is a suitable tool to identify appropriate local minima. Snakes always tend to minimize the energy for finding image features. Also, they have the capacity to interact with high level mechanisms to be guided to features of interest.

Snakes do not try to identify salient features of interest in an image but rely on other mechanisms to position them near those features. For instance, standard image processing techniques can be used in automatic initialization procedures and snakes can be used subsequently to refine them. If automatic initialization is not possible, an expert user can initialize the snake near salient features of interest and the energy minimization process can fit the deformable model to the data (Ivins and Porril, 1993.

A type of active contours called gradient vector flow active contours (Xu and Prince, 1997) inspire interest due to their strength in solving problems associated with initialization of the active contour and poor convergence to boundary concavities that are encountered in other types of Active Contours. A series of studies on GVF Active Contours (Prince and Xu, 1996; Xu, 2000; Xu and Prince, 1998, 2000) have helped a good understanding of the strengths of the GVF Active Contours. A study by the authors (Britto and Ravindran, 2005a) has given much needed insight about the GVF Active Contours.

The authors have done significant contributory experimental research in the same area and are now performing a Retro-Analysis in this study. This Retro Analysis study supports and strengthens the previous study (Britto and Ravindran, 2005a) and gives much needed insight about Active Contours to the Researcher and the Layman alike.

IMAGE SEGMENTATION

The most notable theory that explained the fundamental low-level task of Image Segmentation was given by Marr and Hildreth (1980), which led to development of image segmentation algorithms such as the classic edge-detector proposed by Canny (1986) and refined by Deriche (1987). These theorems (and their many relatives) implicitly treat image segmentation as a bottom-up process and consider only local information around each pixel. Although the algorithms often perform very well, they do not produce the semi-global descriptions of image features that are required by high-level processes and human users of interactive systems.

A naïve bottom-up approach to image segmentation propagates mistakes to higher processes without providing opportunities for correction. For many applications, a better strategy is to provide several interpretations of the image data, from which a high-level process or a human user may choose. Deformable models provide one method of generating these alternatives and model based vision is now firmly established as a robust method for automatic segmentation even in noisy and cluttered images or where part of a feature are occluded.

DEFORMABLE MODELS

The mathematical foundations of deformable models represent the confluence of geometry, physics and approximation theory offering a unique and powerful approach to image analysis. Geometry serves to represent object shape; physics imposes constraints on how the shape may vary over space and time and optimal approximation theory provides the formal underpinnings of mechanisms for fitting the models to measured data. They have grown to be effective in segmenting, matching and tracking anatomic structures by exploiting (bottom-up) constraints derived from the image data together with (top-down) a priori knowledge about the location, size and shape of these structures. Deformable models are capable of accommodating the significant variability of biological structures over time and across different individuals. Also, they support highly intuitive interaction mechanisms that (when necessary) allow medical scientists and practitioners to bring their expertise to bear on the model-based image interpretation task (McInerney and Terzopoulos, 1996).

SCIENTIFIC FOUNDATIONS OF DEFORMABLE MODELS

Deformable model geometry usually permits broad shape coverage by employing geometric representations that involve many degrees of freedom (such as splines). The model remains manageable because the degrees of freedom are generally not permitted to evolve independently but are governed by physical principles that bestow intuitively meaningful behavior upon the geometric substrate. The name deformable model stems primarily from the use of elasticity theory at the physical level, generally within a Lagrangian dynamics setting. The physical interpretation views deformable models as elastic bodies which respond naturally to applied forces and constraints. Typically, deformation energy functions defined in terms of the geometric degrees of freedom are associated with the deformable model. The energy grows monotonically as the model deforms away from a specified natural or rest shape and often includes terms that constrain the smoothness or symmetry of the model. Taking a physics-based view of classical optimal approximation, external potential energy functions are defined in terms of the data of interest to which the model is to be fitted. These potential energies give rise to external forces which deform the model such that it fits the data.

Deformable models interact with images in a dynamic manner. The energy functional is defined to give a measure of fit between the model and the image and the model is given some initial parameters which are then updated by an energy minimization algorithm; this process drives the model toward salient image features. Almost all deformable models perform some kind of edge detection.

Deformable models generally make some assumptions about the shape of the features being modeled. The key issue is that a deformable model should be able to accommodate the range of variation found in the objects that it will represent but at the same time it must not be too constrained or too flexible. In medical image segmentation (for instance) the shape of an organ can vary through time and between individuals. Therefore, a highly constrained model is unsuitable.

Deformable models offer a continuum of shape representation from highly constrained rigid and articulated models to freely deformable active contour models. The themes uniting these models are:

That they all attempt to perform image segmentation, usually by searching for some kind of edge and
That they all incorporate some kind of regularizing constraint; in the form of a fixed shape or a probability limit for the shape parameters or a simple constraint that the models should remain smooth and continuous.

Inevitably, each class of models is best suited for representing a particular class of objects.

The widely recognized potency of deformable models stems from their ability to segment, match and track images of anatomic structures by exploiting (bottom-up) constraints derived from image data together with (top-down) a priori knowledge about the location, shape and size of these structures. Deformable models are capable of accommodating the often significant variability of biological structures over time and across different individuals. Deformable models support highly intuitive interaction mechanisms that allow medical scientists and practitioners to bring their expertise to bear on the model-based image interpretation task when necessary.

ACTIVE CONTOUR MODEL REPRESENTATION

The structure of an active contour (Fig. 1) is N control points and the coordinates of each control point. These control points are connected by straight lines to form a contour. The active contour is attracted to the boundary of the object and will converge to the boundary of the object as the connected straight lines and control points shrink like a rubber band.

Active contour models (known colloquially as snakes) are energy minimizing curves that deform to fit image features. Snakes lock on to local minima in the potential energy generated by processing an image. This energy is minimized by iterative gradient descent, moving the model according to equations of motion derived using the calculus of variations. In addition, internal (smoothing) constraints produce tension and stiffness that keep the model smooth and continuous and prevent the formation of sharp corners. External constraints may be specified by a supervising process or a human user.

An active contour is an energy-minimizing spline that detects specified features within an image. It consists of a set of control points connected by straight lines. The active contour is defined by the number of control points and the co-ordinates of each control point.

Active contours, first proposed by Kass et al. (1987) are defined as energy-minimizing contours that apply information about the boundaries as part of an optimization procedure. They are generally initialized around the object of interest by automatic or manual process. The contour then deforms itself from its initial position in conformity with nearest dominant edge feature by minimizing the energy composed of the internal and external forces. Internal forces which enforce smoothness of the curve are computed from within the active contour. External forces derived from the image help to drive the curve toward the desired features of interest during the course of the iterative process. The energy function is minimized, thus making the model active.

The energy minimization process can be viewed as a dynamic problem where the active contour model is governed by the laws of elasticity and lagrangian dynamics (Rueckert, 1997) and the model evolves until equilibrium of all forces is reached, which is equivalent to a minimum of the energy function.

Image for - Review of Deformable Curves-A Retro Analysis
Fig. 1: Structure of an active contour (Guidry, 1997)

Image for - Review of Deformable Curves-A Retro Analysis
Fig. 2: Physical analogy of an active contour (Guidry, 1997)

The physical analogy of an active contour (Fig. 2) is replacing the straight lines (Fig. 1) between control points with springs. At rest, the force and energy of the system is equal to zero. If not at rest, forces pull the contour points toward a position where the force and energy equal zero. The external and internal energy are the energies that form the forces that drive the spring system to the object boundary where the energy is minimum. Using the external and internal energy it is thus possible to detect the image features desired.

Active contour models provide a unified solution to several image processing problems such as the detection of light and dark lines and edges. They are often used to segment spatial and temporal image sequences.

To give a clearer interpretation of active contours, a physical analogy of such a system will be described. The internal forces applied on any physical system are always oriented so as to reduce the energy on that system. For example, it could be imagined that there are springs connecting the control points of the active contour. If the control points are pulled outward, the springs stretch and exert forces on each point trying to bring the spring back to its original position at rest. The active contour is a simulation of this physical description and evolves by minimizing the energy functional. The energy functional is composed of two components, the internal energy component Eint and the external energy component Eext.

Image for - Review of Deformable Curves-A Retro Analysis
Fig. 3: A closed active contour model (Ivins, 1996)

The internal energy deals with intrinsic properties of the contour and is a smoothness constraint which keeps the points contained within the contour. The external energy guides the contour toward image features.

Figure 3 shows a snake with its ends joined so that if forms a closed loop. Over a series of time steps the snake moves into alignment with the nearest local energy minimum-typically an image feature such as an edge. The figure depicts movement of a snake from its current position to the minimum position. The arrows point in the direction of movement of the snake in seeking the minimum position.

Unfortunately, the image minimization process is prone to oscillation unless a very small time step is used with the side-effect that convergence is slow. Other limitations are that:

The models usually incorporate edge information only ignoring other image characteristics such as texture and color and
They must be initialized close to the feature of interest to avoid being distracted by noise and clutter.

An active contour or snake is an elastic curve driven by energy generated from an image. The image is processed to generate a potential field in which the model is constrained to lie. The gradient of this image generates a spatially varying force which makes the model active. Minima in the image energy correspond to features such as lines or terminations, although most active contour models use some measure of edge energy.

From any starting point, subject to certain constraints, an active contour will deform into alignment with the nearest salient feature in an image. Such features correspond to local minima in the energy generated by processing the image. In addition, high-level mechanisms can interact with active contours to guide them towards features of interest. Unlike most other techniques for segmenting images, active contours are always active. Changes in high-level interpretation can therefore affect the energy minimization process and even in the absence of such changes the models will respond to moving image features.

Most active contours do not try to solve the entire problem of finding salient image features. They rely on other mechanisms to place them somewhere near a desired solution. For example, image processing techniques can be used to estimate the locations of interesting features, which are then refined using active contours. However, active contours can still be used for image interpretation in cases where automatic initialization is not possible expert user need only place the active contour near an image feature and the energy minimization process will fit the model to the data. This behavior has been exploited in numerous interactive image processing systems (Porril and Ivins, 1994).

In addition to minimizing the image energy, active contours must also satisfy some internal constraints-typically, they must remain smooth and continuous. Sometimes, the user imposes additional external constraints such as making parts of the image attract or repel the models. The calculus of variations is used to derive the Euler-Lagrange equation which is satisfied at minima in the energy of an active contour model. The nearest of these minima can be found by iterative gradient descent using a simple Euler time-stepping scheme; however the original models proposed by Kass et al. (1987 and 1988) used a more stable semi-implicit scheme based on a fast matrix inversion algorithm.

The original active contour model was represented explicitly in terms of the image co-ordinates of its elements; however, alternate representations exist. For example, B-spline basis functions are used to represent B-snakes and dynamic contours and sines and cosines are used to represent Fourier models. These representations vary in the locality of control that they provide over the models; comparatively local in the case of B-splines and completely global in the case of Fourier series.

There are also alternative methods for numerically simulating active contour models. The original method involved four steps:

Setting up an energy integral on the continuous plane;
Deriving a pair of Euler equations for the x and y co-ordinates of the model;
Approximating these equations using finite differences and
Solving the discrete equations using iterative gradient descent.

One alternative is to use dynamic programming as suggested by Amini et al. (1988 and 1990) and Williams and Shah (1992). The main advantage of this method is that (unlike the original method) it does not require the energy functional to be differentiable and so can be used to impose hard constraints on the model-for example, that it cannot self-instruct.

There are various other methods for representing and simulating (numerically) active contour models-for example, Karaolani et al. (1989, 1990 and 1992) used finite elements. The finite element method uses the energy integral directly, dividing the snake into subsections and minimizing the energy of each subsection individually.

The idea of edge detection by optimizing models of curve contrast and smoothness can be traced back to Montanari (1971) and Martelli (1972). However, a major breakthrough came when active contour models were developed by Kass et al. (1987 and 1988).

Deformable curve, surface and solid models gained popularity after they were proposed for use in computer vision (Terzopoulos et al., 1988) and computer graphics (Terzopoulos and Fleischer, 1988) in the mid 1980’s. Terzopoulos (1986 and 1987) introduced the theory of continuous (multidimensional) deformable models in a Lagrangian dynamics setting, based on deformation energies in the form of (controlled-continuity) generalized splines. Ancestors of deformable models now in common use include Fischler and Elshlager’s spring-loaded templates (Fischler and Elschlager, 1973) and Widrow’s rubber mask technique (Widrow, 1973). The deformable model that has attracted the most attention to date is popularly known as Snakes (Kass et al., 1987, 1988). Snakes or deformable contour models represent a special case of the general multidimensional deformable model theory (Terzopoulos, 1987).

Etoh et al. (1992) describe a contour extraction scheme which refines an estimated initial contour to outline a feature of interest. Mixture density descriptions (parametric descriptions of decomposed regions) were obtained by region clustering and used to evaluate the likelihood that a pixel belonged to the object or the background. Both region- and edge-based estimation schemes were integrated into the energy minimization process using log-likelihood functions based on the mixture density distributions.

Ronfard (1994) proposed a modified variational scheme for segmentation, which (instead of relying on edge-detection) performed local computations around contour neighbourhoods. The paper introduced a region-based energy criterion for deformable models and compared it with the edge-based energy of conventional models. A simplified optimization scheme was also presented that accounted for internal and external energy in separate steps. However, the optimization scheme was mostly heuristic and was presented without a formal derivation.

Snakes also incorporate internal regularizing constraints (Poggio et al., 1985; Terzopoulos, 1986) which ensure that the models remain smooth and continuous and limit the amount that they can bend. However, the models usually incorporate no prior shape knowledge and so are free to take almost any shape.

Although most snakes are essentially semi-global edge detectors, a few attempts have been made to incorporate region information; for example, Leymarie and Levins (1990 and 1992) presented a method for segmenting images at multiple scales using both region and edge features. A two-dimensional grassfire algorithm was used to generate a distance surface on which an active contour model minimized its energy. This distance surface (combined with curvature features extracted from the boundary) led to a Euclidean skeleton representation of shape.

MEDICAL IMAGE ANALYSIS WITH DEFORMABLE MODELS

Although originally developed for application to problems in computer vision and computer graphics, the potential of deformable models for use in medical image analysis has been quickly realized. Two dimensional and three dimensional deformable models have been used to segment, visualize, track and quantify a variety of anatomic structures ranging in scale from the macroscopic to the microscopic. These include the brain, heart, face; cerebral, coronary and retinal arteries, kidneys, lungs, stomach, liver, skull, vertebra, objects such as brain tumors, fetus, etc. Deformable models have been used to track the non-rigid motion of the heart, the growing tip of a neurite and the motion of erythrocytes. They have been used to locate structures in the brain and to register images of the retina, vertebra and neuronal tissue.

IMAGE SEGMENTATION WITH DEFORMABLE CURVES

The segmentation of anatomic structures (the partitioning of the original set of image points into subsets corresponding to the structures) is an essential first stage of most medical image analysis tasks such as registration, labeling and motion tracking. These tasks require anatomic structures in the original image to be reduced to a compact, analytic representation of their shapes. Performing this segmentation manually is extremely labor intensive and time-consuming. A primary example is the segmentation of the heart, especially the Left Ventricle (LV) from cardiac imagery.

Most clinical segmentation is currently performed using manual slice editing. In this scenario, a skilled operator using a computer mouse or trackball manually traces the region of interest on each slice of an image volume. Manual slice editing suffers from several drawbacks. These include the difficulty in achieving reproducible results, operator bias, forcing the operator to view each 2D slice separately to deduce and measure the shape and volume of 3D structures and operator fatigue.

Segmentation using traditional low-level image processing techniques, such as region growing, edge detection and mathematical morphology operations also requires considerable amounts of expert interactive guidance. Automating these model-free approaches is difficult because of the shape complexity and variability within and across individuals. In general, the underconstrained nature of the segmentation problem limits the efficacy of approaches that consider local information only. Noise and other image artifacts can cause incorrect regions or boundary discontinuities in objects recovered by these methods.

A deformable model based segmentation scheme, used in concert with image pre-processing can overcome many of the limitations of manual slice editing and traditional image processing techniques. These connected and continuous geometric models consider an object boundary as a whole and can make use of a priori knowledge of object shape to constrain the segmentation problem. The inherent continuity and smoothness of the models can compensate for noise, gaps and other irregularities in object boundaries. The parametric representations of the models also provide a compact, analytical description of object shape. These properties lead to a robust and elegant technique for linking sparse or noisy local image features into a coherent and consistent model of the object.

Among the first and primary uses of deformable models in medical image analysis was the application of deformable contour models, such as snakes (Kass et al., 1988), to segment structures in 2D images (Berger, 1990; Cohen, 1991; Ueda and Mase, 1992; Rougon and Prêteux, 1993; Cohen and Cohen, 1993; Leitner and Cinquin, 1993; Carlbom et al., 1994; Viergever et al., 1995; Davatzikos and Prince, 1995). Typically users initialized a deformable model near the object of interest and allowed it to deform into place. Users could then use the interactive capabilities of these models and manually fine-tune them. Once the user is satisfied with the result on an initial image slice, the fitted contour model may then be used as the initial boundary approximation for neighboring slices. These models are then deformed into place and again propagated until all slices have been processed. The resulting sequence of 2D contours can then be connected to form a continuous 3D surface model (Lin and Chen, 1989; Chang et al., 1991; Cohen, 1991; Cohen and Cohen, 1993).

The application of snakes and other similar deformable contour models to extract regions of interest is not without limitations. For example, snakes were designed as interactive models. In non-interactive applications, they must be initialized close to the structure of interest to guarantee good performance. The internal energy constraints of snakes can limit their geometric flexibility and prevent a snake from representing long tube-like shapes or shapes with significant protrusions or bifurcations. The topology of the structure of interest must be known in advance since classical deformable models are parametric and are incapable of topological transformations without additional machinery.

Various methods have been proposed to improve and further automate the deformable contour segmentation process. Cohen and Cohen (1993) used an internal inflation force to expand a snake model past spurious edges towards the real edges of the structure, making the snake less sensitive to initial conditions and inflation forces were also employed (Terzopoulos et al., 1988). Amini et al. (1990) used dynamic programming to carry out a more extensive search for global minima. Poon et al. (1994) and Grzeszczuk and Levin (1994) minimized the energy of active contour models using simulate annealing which is known to give global solutions and allows the incorporation of non-differentiable constraints.

Poon et al. (1994) also used a discriminant function to incorporate region based image features into the image forces of their active contour model. The discriminant function allows the inclusion of additional image features in the segmentation and serves as a constraint for global segmentation consistency (i.e., every image pixel contributes to the discriminant function). The result is a more robust energy functional and a much better tolerance to deviation of the initial guess from the true boundaries. Other researchers (Rougon and Prêteux, 1991; Chakraborty and Duncan, 1994; Chakraborty et al., 1995; Herlin et al., 1992; Gauch et al., 1994; Mangin et al., 1995) have also integrated region-based-information into deformable contour models in an attempt to decrease sensitivity to insignificant edges and initial model placement.

Recently, several researchers (Leitner and Cinquin, 1991; Caselles et al., 1993; Malladi et al., 1995; Whitaker, 1994; Caselles et al., 1995; McInerney and Terzopoulos, 1995; Sapiro et al., 1995) have been developing topology independent shape modeling schemes that allow a deformable contour or surface model to not only represent long tube-like shapes or shapes with bifurcations, but also to dynamically sense and change its topology.

INCORPORATING APRIORI KNOWLEDGE

In medical images, the general shape, location and orientation of objects is known and this knowledge may be incorporated into the deformable model in the form of initial conditions, data constraints, constraints on the model shape parameters or into the model fitting procedure. The use of implicit or explicit anatomical knowledge to guide shape recovery is especially important for robust automatic interpretation of medical images. For automatic interpretation, it is essential to have a model that not only describes the size, shape, location and orientation of the target object but that also permits expected variations in these characteristics. Automatic interpretation of medical images can relieve clinicians from the labor intensive aspects of their work while increasing the accuracy, consistency and reproducibility of the interpretations.

A number of researchers have incorporated knowledge of object shape into deformable models by using deformable shape templates. These models usually use “hand-crafted” global shape parameters to embody a priori knowledge of expected shape and shape variation of the structures and have been used successfully for many applications of automatic image interpretation. The idea of deformable templates can be traced to the early work on spring loaded templates by Fischler and Elshlager (1973). An excellent example in computer vision is the work of Yuille et al. (1992) who constructed deformable templates for detecting and describing features of face, such as the eye. In medical image analysis Lipson et al. (1990) note that axial cross sectional images of the spine yield approximately elliptical vertebral contours and consequently extract the contours using a deformable ellipsoidal template.

Several researchers cast the deformable model fitting process in a probabilistic framework and include prior knowledge of object shape by incorporating prior probability distributions on the shape variables to be estimated (Vemuri and Radisavljevic, 1994; Staib and Duncan, 1992; Worring et al., 1993). For example, Staib and Duncan (1992) use a deformable contour model on 2D echocardiograms and MR images to extract the LV of the heart and the corpus callosum of the brain, respectively. This closed contour model is parameterized using an elliptic Fourier decomposition and a priori shape information is included as a partial probability expressed through the likelihood of each model parameter. The model parameter probability distributions are derived from a set of example object boundaries and serve to bias the contour model towards expected or more likely shapes.

Székely et al. (1996) have also developed Fourier parameterized models. They have added also elasticity to their models to create Fourier snakes in 2D and elastically deformable Fourier surface models in 3D. By using this Fourier reparameterization followed by a statistical analysis of a training set, they have defined mean organ models and their Eigen deformations. An elastic fit of the mean model in the subspace of eigenmodes restricts possible deformations and finds an optimal match between the model surface and boundary candidates.

Cootes et al. (1994) and Hill et al. (1993) presented a statistically based technique for building deformable shape templates and used these models to segment various organs from 2D and 3D medical images. The statistical parameterization provides global shape constraints and allows the model to deform only in ways implied by the training set. The shape models represent objects by sets of landmark points which are placed in the same way on an object boundary in each input image.

The increasingly important role of medical imaging in the diagnosis and treatment of disease has opened an array of challenging problems centered on the computation of accurate geometric models of anatomic structures from medical images. Deformable models offer an attractive approach to tackle such problems because these models are able to represent the complex shapes and broad shape variability of anatomical structures. Deformable models overcome many of the limitations of traditional low-level image processing techniques by providing compact and analytical representations of object shape, by incorporating anatomic knowledge and by providing interactive capabilities. The continued development and refinement of deformable models is an important area of research into the foreseeable future (McInerney and Terzopoulos, 1996).

INTRODUCTION TO GRADIENT VECTOR FLOW (GVF)

The Gradient Vector Flow (GVF) (Xu, 2000) solves problems associated with initialization of the active contour and poor convergence to boundary concavities. The GVF is computed as a diffusion of the gradient vectors of a graylevel or binary edge map derived from the image. It differs fundamentally from traditional deformable model external forces in that it cannot be written as the negative gradient of a potential function and the corresponding deformable model is formulated directly from a dynamic force equation rather than a energy minimization formulation. The GVF has a larger capture range and is able to move deformable models into boundary concavities (Xu and Prince, 2000).

FORMULATION OF ACTIVE CONTOUR MODELS

An Active Contour Model can be represented by a curve c, as a function of its arc length τ,

Image for - Review of Deformable Curves-A Retro Analysis
(1)

To define a closed curve c(0) is set to equal c(1). A discrete model can be expressed as an ordered set of n vertices vi = (xi,yi)T with v = (v1,…,vn). The large number of vertices required to achieve accuracy could lead to high computational complexity and numerical instability (Rueckert, 1997).

Mathematically, an active contour model can be defined in discrete form as a curve x(s) = [x(s), y(s), sε[0, 1] that moves through the spatial domain of an image to minimize the energy functional

Image for - Review of Deformable Curves-A Retro Analysis
(2)

where α and β are weighting parameters that control the active contour’s tension and rigidity, respectively (Xu and Prince, 1997). The first order derivative discourages stretching and the second order derivative discourages bending. The weighting parameters of tension and rigidity, viz., α and β govern the effect of the derivatives on the snake. The external energy function Eext is derived from the image so that it takes on its smaller values at the features of interest such as boundaries and guides the active contour towards the boundaries. The external energy is defined by

Image for - Review of Deformable Curves-A Retro Analysis
(3)

where, Gσ(x,y) is a two-dimensional Gaussian function with standard deviation σ, I(x,y) represents the image and κ is the external force weight. This external energy is specified for a line drawing (black on white) and positive κ is used. A motivation for applying some Gaussian filtering to the underlying image is to reduce noise.

An active contour that minimizes E must satisfy the Euler Equation

Image for - Review of Deformable Curves-A Retro Analysis
(4)

where, Fint = αx″ (s) – βx″″(s) and Fext = ΔEext comprise the components of a force balance equation such that

Fint + Fext = 0
(5)

The internal force Fint discourages stretching and bending while the external potential force Fext drives the active contour towards the desired image boundary. Equation 4 is solved by making the active contour dynamic by treating x as a function of time t as well as s. Then the partial derivative of x with respect to t is then set equal to the left hand side of Eq. 4 as follows

Image for - Review of Deformable Curves-A Retro Analysis
(6)

A solution to Eq. 6 can be obtained by discretizing the equation and solving the discrete system iteratively (Kass, 1987). When the solution x(s,t) stabilizes, the term xt(s,t) vanishes and a solution of Eq. 4 is achieved.

Traditional active contour models suffer from a few drawbacks. Boundary concavities leave the contour split across the boundary. Capture range is also limited. Methods suggested to overcome these difficulties, namely multiresolution methods (Leroy et al., 1996), pressure forces (Cohen, 1991), distance potentials (Cohen and Cohen, 1993), control points (Davatzikos and Prince, 1995), domain adaptivity (Davatzikos and Prince, 1994), directional attractions (Abrantes and Marques, 1996) and solenoidal fields (Prince and Xu, 1996), however solved one problem but introduced new ones (Xu and Prince, 2000). Hence, a new class of external fields called Gradient Vector Flow fields (Xu and Prince, 1998, 2000) was suggested to overcome the difficulties in traditional active contour models.

DISCUSSION

The authors have studied and examined the strengths of Gradient Vector Flow (GVF) Active Contours (Britto and Ravindran, 2005a). Extensive experimentation has shown that GVF Active Contours have very good potential as a segmentation tool for chromosome images (Britto and Ravindran, 2005b, 2006a, c, d). Further insights revealed that GVF Deformable curves are suitable as a diagnostic tool in the realm of human cytogenetics (Britto and Ravindran, In Press, 2006e). This study has hence yielded a very good insight into Deformable Curves, especially GVF Active Contours.

REFERENCES

1:  Amini, A.A., S. Tehrani and T.E. Weymouth, 1988. Using dynamic programming for minimizing the energy of active contours in the presence of hard constraints. Proceedings of the 2nd International Conference on Computer Vision, December 5-8, 1988, IEEE Computer Society, Washington, DC., USA., 95-99
Direct Link  |  

2:  Amini, A.A., T.E. Weymouth and R.C. Jain, 1990. Using dynamic programming for solving variational problems in vision. IEEE Trans. PAMI, 12: 855-867.

3:  Abrantes, A.J. and J.S. Marques, 1996. A class of constrained clustering algorithms for object boundary extraction. IEEE Trans. Image Process., 5: 1507-1521.
CrossRef  |  Direct Link  |  

4:  Berger, M.O., 1990. Snake growing. Proceedings of the 1st European Conference on Computer Vision, April 23-27, 1990, Springer-Verlag London, UK., pp: 570-572
Direct Link  |  

5:  Britto, A.P. and G. Ravindran, 2005. A review of deformable curves from the perspective of chromosome image segmentation. J. Med. Sci., 5: 363-370.
CrossRef  |  Direct Link  |  

6:  Britto, A.P. and G. Ravindran, 2005. Comparison of boundary mapping efficiency of gradient vector flow active contours and their variants on chromosome spread images. J. Applied Sci., 5: 1452-1460.
CrossRef  |  Direct Link  |  

7:  Britto, A.P. and G. Ravindran, 2006. Boundary mapping of chromosome spread images using optimal set of parameter values in discrete cosine transform based gradient vector flow active contours. J. Applied Sci., 6: 1351-1361.
CrossRef  |  Direct Link  |  

8:  Britto, A.P. and G. Ravindran, 2006. Detection of specific human chromosomal abnormalities using discrete cosine transform based gradient vector flow active contours. Biotechnology, 6: 111-117.
CrossRef  |  Direct Link  |  

9:  Britto, A.P. and G. Ravindran, 2006. Evaluation of standardization of curve evolution based boundary mapping technique for chromosome spread images. Inform. Technol. J., 5: 94-107.
CrossRef  |  Direct Link  |  

10:  Britto, A.P. and G. Ravindran, 2006. Segmentation of chromosome spread images using discrete cosine transform based gradient vector flow active contours: An analysis. J. Med. Sci., 6: 117-124.
CrossRef  |  Direct Link  |  

11:  Britto, A.P. and D.G. Ravindran, 2006. Medical imaging-a promising technology in the field of human cytogenetics and disease diagnosis. Inform. Technol. J., 5: 1122-1126.
CrossRef  |  Direct Link  |  

12:  Canny, J., 1986. A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell., 8: 679-698.
CrossRef  |  Direct Link  |  

13:  Carlbom, I., D. Terzopoulos and K.M. Harris, 1994. Computer assisted registration, segmentation and 3D reconstruction from images of neuronal tissue sections. IEEE Trans. Med. Imaging, 13: 351-362.

14:  Caselles, V., F. Catt, T. Coll and F. Dibos, 1993. A geometric model for active contours in image processing. Numerische Math., 66: 1-31.
CrossRef  |  

15:  Caselles, V., R. Kimmel and G. Sapiro, 1995. Geodesic active contours. Proceedings of the 5th International Conference on Computer Vision, June 20-23, 1995, Cambridge, MA., pp: 694-699

16:  Chakraborty, A., L. Staib and J. Duncan, 1994. Deformable boundary finding influenced by region homogeneity. Proceedings of the Computer Society Conference on Computer Vision and Pattern Recognition, June 21-23, 2004, Seattle, WA., USA., pp: 624-627
CrossRef  |  Direct Link  |  

17:  Chakraborty, A. and J. Duncan, 1995. Integration of boundary finding and region-based segmentation using game theory. Proceedinds of the 14th International Conference on Information Processing in Medical Imaging, June 1995, Kluwer Academic, Dordrecht, The Netherlands, France, pp: 189-200

18:  Chang, L., H. Chen and J. Ho, 1991. Reconstruction of 3D medical images: A nonlinear interpolation technique for reconstruction of 3D medical images. Comput. Vision Graphics Image Proc., 53: 382-391.

19:  Cohen, L.D., 1991. On active contour models and balloons. CVGIP: Image Understanding, 53: 211-218.
CrossRef  |  

20:  Cohen, L.D. and I. Cohen, 1993. Finite-element methods for active contour models and balloons for 2-D and 3-D images. IEEE Trans. Pattern Anal. Mach. Intel., 15: 1131-1147.
Direct Link  |  

21:  Cootes, T., A. Hill, C. Taylor and J. Haslam, 1994. The use of active shape models for locating structures in medical images. Image Vision Comput., 12: 355-366.

22:  Davatzikos, C. and J.L. Prince, 1994. Convexity analysis of active contour models. Proceedings of the Conference Infomation Science and System, pp: 581-587.

23:  Davatzikos, C. and J. Prince, 1995. An active contour model for mapping the cortex. IEEE Trans. Med. Imag., 14: 65-80.
CrossRef  |  Direct Link  |  

24:  Deriche, R., 1987. Optimal edge-detection using recursive filtering. Proceedings of the 1st International Conference on Computer Vision, June 1987, London, pp: 501-505

25:  Etoh, M., Y. Shirai and M. Asada, 1992. Contour extraction by mixture density description obtained from region clustering. Lecture Notes Comput. Sci., 588: 24-32.

26:  Fischler, M.A. and R.A. Elschlager, 1973. The representation and matching of pictorial structures. IEEE Trans. Computers, 22: 67-92.

27:  Gauch, J., H. Pien and J. Shah, 1994. Hybrid boundary-based and region-based deformable models for biomedical image segmentation. Proceedings of the Mathematical Methods in Medical Imaging III, July 8, 1994, San Diego, CA., SPIE, pp: 72-83

28:  Grzeszczuk, R. and D. Levin, 1994. Brownian strings: Segmenting images with stochastically deformable contours. Proceedings of the 3rd Conference on Visualization in Biomedial Computing, Rochester, MN, October 4-7, 1994, Bellingham, WA., pp: 72-89

29:  Guidry, D.L., 1997. Active contours: With application to motion artifact cancellation and segmentation in MRI. B.Sc. Thesis, University of Louisville.

30:  Herlin, I., C. Nguyen and C. Graffigne, 1992. A deformable region model using stochastic processes applied to echocardiographic images. Proceedings of the Conference on Computer Vision and Pattern Recognition, June 15-18, 1992, IEEE Computer Society Press, Los Alamitos, CA., pp: 534-539

31:  Hill, A., A. Thornham and C. Taylor, 1993. Model-based interpretation of 3D medical images. Proceedings of the 4th British Machine Vision Conference (BMV'93), Surrey, September 21-23, 1993, BMVA Press, UK., pp: 339-348

32:  Ivins, J. and J. Porril, 1993. Everything you always wanted to know about Snakes. AIVRU Technical Memo No. 86, Artificial Intelligence Vision Research Unit, University of Sheffield, England. http://www.rfai.li.univ-tours.fr/pagesperso/rousselle/docum/CA090.htm.

33:  Ivins, J.P., 1996. Statistical snakes: Active region models. Ph.D. Thesis, University of Sheffield, England.

34:  Karaolani, P., G.D. Sullivan, K.D. Baker and M.J. Baines, 1989. A finite element method for deformable models. Proceedings of 5th Alvey Vision Conference, pp: 73-78.

35:  Karaolani, P., G.D. Sullivan and K.D. Baker, 1990. Parabolic and hermite cubic finite elements: A flexible technique for deformable models. First BMVC, pp: 325-330.

36:  Karaolani, P., G.D. Sullivan and K.D. Baker, 1992. Active contours using finite elements to control local scale. Third BMVC, pp: 481-487.

37:  Kass, M., A. Witkin and D. Terzopoulos, 1987. Snakes active contour models. Proceedings of the 1st International Conference on Computer Vision, June 8-11, 1987, London, pp: 259-268

38:  Kass, M., A. Witkin and D. Terzopoulos, 1988. Snakes: Active contour models. Int. J. Comput. Vision, 1: 321-331.
CrossRef  |  Direct Link  |  

39:  Leitner, F. and P. Cinquin, 1991. Complex topology 3D objects segmentation. Proceedings of the Model-Based Vision Development and Tools, November 14, 1991, SPIE Bellingham, WA., pp: 16-26

40:  Leitner, F. and P. Cinquin, 1993. From Splines and Snakes to Snakes Splines. In: Geometric Reasoning, Perception to Action, Laugier, C. (Ed.). LNCS 708, Springer-Verlag, Berline, pp: 264-281

41:  Leroy, B., I.L. Herlin and L.D. Cohen, 1996. Multi-resolution algorithms for active contour models. Proceedings of 12th Internationl Conference on Analysis and Optimization of Systems Images, pp: 58-65.

42:  Leymarie, F. and M.D. Levine, 1990. New method for shape description based on an active contour model. SPIE Proc., 1192: 536-547.

43:  Leymarie, F. and M.D. Levine, 1992. Simulating the grassfire transform using an active contour model. IEEE Trans. PAMI, 4: 56-75.

44:  Lin, W. and S. Chen, 1989. A new surface interpolation technique for reconstructing 3D objects for serial cross-sections. Computer Vision Graphics Image Proc., 48: 124-143.

45:  Lipson, P., A. Yuille, D. Keefe, J. Cavanaugh, J. Taaffe and D. Rosenthal, 1990. Deformable templates for feature extraction from medical images. Proceedings of the 1st European Conference on Computer Vision, April 23-27, 1990, Springer-Verlag, London, UK., pp: 413-417
Direct Link  |  

46:  Malladi, R., J.A. Sethian and B.C. Vemuri, 1995. Shape modeling with front propagation: A level set approach. IEEE Trans. Pattern Anal. Mach. Intell., 17: 158-175.
CrossRef  |  Direct Link  |  

47:  Mangin, J., F. Tupin, V. Frouin, I. Bloch, R. Rougetet, J. Regis and J. Lopez-Krahc, 1995. Deformable topological models for segmentation of 3d medical images. Proceedings of the 14th Internationl Conference on Information Processing in Medical Imaging, June 21-23, 1995, Kluwer Academic, Dordrecht, The Netherlands, France, pp: 153-164

48:  Marr, D. and E. Hildreth, 1980. Theory of edge detection. Proc. R. Soc. Lond., 207: 187-217.
CrossRef  |  Direct Link  |  

49:  Martelli, A., 1972. Edge detection using heuristic search methods. CGIP, 1: 169-182.

50:  McInerney, T. and D. Terzopoulos, 1995. Topologically adaptable snakes. Proceedings of the 5th International Conference on Computer Vision, June 20-23, 1995, Cambridge, MA., USA., pp: 840-845
CrossRef  |  Direct Link  |  

51:  McInerney, T. and D. Terzopoulos, 1996. Deformable models in medical image analysis. Proceedings of the Workshop on Mathematical Methods in Biomedical Image Analysis, pp: 171-180.

52:  Carrato, S., A. Premoli and G.L. Sicuranza, 1991. Linear and nonlinear neural networks for image compression. Proceeding of the International Conference on Digital Signal Processing.

53:  Cottrell, G.W. and P. Munro, 1988. Principle components analysis of images via back propagation. Visual Commun. Image Process., 88: 1070-1077.

54:  Dony, R.D. and S. Haykin, 1995. Neural network approaches to image compression. IEEE Proc., 83: 288-303.
CrossRef  |  

55:  Kono, R., M. Arai and H. Imai, 1990. Image compression using neural network with learning capability of variable function of a neural unit. Visual Commun. Image Process., 90: 69-75.

56:  Namphol, A., S. Chin and M. Arozullah, 1996. Image compression with a hierarchical neural network. IEEE Trans. Aerospace Elect. Syst., 32: 326-338.
CrossRef  |  

57:  Russo, L.E. and C.E. Real, 1992. Image compression using outer product neural network. Proceedings of the International Conference on Acoustic, Speech and Signal Processing ICASSP-92, March 23-26, 1992, San Francisco, CA, USA., pp: 377-380

58:  Sonehara, N., M. Kawato, S. Miyake and K. Nakane, 1989. Image data compression using neural network model. Proceedings of the IJCNN International Joint Conference, June 18-22, 1989, Washington, DC., USA., pp: 35-41
CrossRef  |  

59:  Vilvovic, I., 2006. An experience in image compression using neural networks. Proceedings of the ELMAR 48th International Symposium on Multimedia Signal Processing and Communications, June 7-9, 2006, Zadar, Croatia, pp: 95-98
CrossRef  |  

©  2022 Science Alert. All Rights Reserved