Abstract: This study surveys deformable curves (active contours) with the aim of identifying a suitable type of deformable curve for the task of chromosome image segmentation. Deformable curves offer a unique and powerful approach to segmentation. They are capable of accommodating variability of biological structures. Deformable curves also support interactive mechanisms that permit expert interaction during the process. The objective of this was to to study the theoretical frameworks of different active contour models, classify the methods according to several properties and compare their properties. This study reviews the deformable curves and their application specifically to the task of chromosome image segmentation.
INTRODUCTION
Medical imaging allows scientists to view anatomical structures within the human body in a non-invasive way. The technological advances within medical imaging and medical image analysis had a great impact on medicine, in both clinical and research applications. It has expanded beyond simple visualization of anatomic structures and become a tool in surgical planning and simulation, intra-operative navigation, diagnosis, tracking the progress of a disease, etc. The problem of extracting meaningful information from images is one of the most important and challenging problem in image analysis.
Segmentation is thus a fundamental problem in human and computer vision. Low-level segmentation by the human visual system has been explained by numerous theories, most remarkably by Marr and Hildreth[1]. There are many theories in computer vision based on edge detection, that have led to the development of image segmentation algorithms, like the canny edge detector[2]. These image segmentation algorithms consider only local information around each pixel and though they perform well, they are unable to provide descriptions of image features that are required by high-level processes and human users of interactive systems. Even if they are able to provide descriptions of image features to high-level processes, mistakes and errors are propagated without any facility for correction. A better strategy to avoid error propagation is to provide several interpretations of image data, from which a high-level process or human user can choose. Deformable models provide one way of generating these alternatives and model-based vision is now firmly established as a robust method for automatic segmentation even in challenging situations.
Deformable models generally make some assumption about the shape of the features being modeled[3]. One of the key issues in the formulation of deformable models is the model specificity - 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 should not be too flexible or too constrained. Deformable models interact with images in a dynamic manner. An energy functional is defined to give a measure of fit between the model and image. 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 initially. In this study, a review of deformable models was done from the perspective of human chromosome image segmentation.
DEFORMABLE MODELS
This review is constrained to chromosome image segmentation and hence concentration is applied to 2D deformable models called deformable curves or Active Contours or Snakes. Montanari[4] and Martelli[5] pioneered the idea of edge detection by optimizing models of curve contrast and smoothness. A major breakthrough was developed active contour models or Snakes[6].
An active contour or snake is an elastic curve driven by energy generated from an image. A potential field is generated by processing the image and the deformable model is constrained to lie in this potential field. The gradient of this image energy generates a spatially varying force which makes the model active. Minima in the edge energy correspond to features such as lines or terminations, although most active contour models use some measure of edge energy. Active contours also incorporate additional regularizing constraints[7,8], which ensure that the models remain smooth and continuous, with limitations to the amount of bending. However, the models incorporate no shape knowledge and hence are free to take on any shape.
Figure 1 shows the movement of an active contour from the initial position, through an intermediate position, to the boundary or edge of the object by minimizing the energy function governing the formulation of the active contour.
MATHEMATICAL FOUNDATIONS
The mathematical foundations of deformable models represent the confluence o f geometry, physics and approximation theory[9].
| Fig. 1: | Movement of deformable curve (or active contour or snake) from initial position to boundary (Courtesy: Ivins, J.P.[3]) |
Geometry serves to represent object shape, physics imposes constraints on how the shape may vary over space and time and optimal approximation theory provides for the mechanisms for fitting the models to measured data.
Deformable model geometry employ geometric representations that involve many degrees of freedom, such as splines. The degrees of freedom are governed by physical principles that bestow meaningful behaviour upon the geometric substrate and are not allowed to evolve independently. Deformable models are viewed as elastic bodies, which respond naturally to applied forces and constraints. The name “Deformable models” arises from the use of elasticity theory at the physical level, generally within a lagrangian dynamics setting. The energy grows monotonically as the model deforms away from a specified rest shape, including terms that constrain the smoothness or symmetry of the model. In the lagrangian setting, the deformation energy gives rise to elastic forces internal to the model.
Taking a physics-based approach 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.
The partial differential equation governing the active contour model, has been implemented using implicit finite difference method[10], dynamic programming[11], finite element method[12] and Fourier spectral method[13].
DEFORMABLE CURVE (ACTIVE CONTOUR) FORMULATION
A deformable curve or active contour is a curved defined within the domain of an image. The properties of the active contour and its behaviour are specified by the energy functional. A partial differential equation controlling the snake causes it to evolve so as to reduce the energy. The physical analogy can be extended and the motion of the active contour can be viewed as an influence of the simulated forces acting on it.
The edge map of the image can be viewed as a landscape on which the active contour can slither. The force acting on the active contour drives it across the landscape attempting to reach the energy equilibrium. The force has two components: one governing the behaviour of the active contour (preserving the original shape and developing corners) and the other governing the movement of the active contour. The curve should approximate the boundary of the object of interest in the image. The boundary can be recognized as low values of the negative edge map. Therefore, the equilibrium equation should be formulated such that the curve tends to minimize the term involving the negative edge map, ie., the potential energy of the dynamic system.
An active contour model can be represented by a curve c, as a function of its arc length τ,
| (1) |
with τ = [0…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[14]. 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:
| (2) |
where, α and β are weighting parameters that control the active contour’s tension and rigidity, respectively[15]. 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 :
| (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 Eq.:
| (4) |
where, Fint = αx”(s) - βx””(s) and Fext = -∇Eext comprise the components of a force balance equation such that
| (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:
| (6) |
A solution to Eq. 6 can be obtained by discretizing the equation and solving the discrete system iteratively[16]. When the solution x(s,t) stabilizes, the term xt(s,t) vanishes and a solution of Eq. 4 is achieved.
CLASSIFICATION OF ACTIVE CONTOURS
Active contour models can be classified according to several criteria. They can be classified as free form and limited form active contour models. In free form active contour models[11,12,16-24] there is no global structure of the contour; it is constrained only by continuity and smoothness constraints. These models do not use apriori information about the shape in a direct manner but use it to adjust the model parameters so that the contour possesses properties like elasticity and rigidness that enable it to converge to the boundary of the object of interest.
The limited form active contour models use apriori information about the geometrical shape directly. This information is available in the form of a sketch or a parameter vector that encodes the shape of interest. The geometric shape of the contour is adjusted by varying the parameters. Limited form active contour models[25-37] cannot take any arbitrary shape. The variability of the shape is limited by the prototype template.
Active contour models can also be classified according to the utilization of image information to align the active contour with the object of interest. They can be classified as region-based models and boundary-based models. Region-based models derive a contour representation from the segmentation of the image into well-defined regions. Each pixel is examined to determine whether the pixel is inside an object, outside the object, or at the object boundary. A pixel belongs to the boundary if it is in the object region and has neighboring pixels in the background. This segmentation is then used to produce an image force field which aligns the active contour with the object of interest.
Edge-based methods use a continuous approximation of the original image intensity function so that the boundary can be characterized by a differential property. A pixel belongs to the boundary if it is a local maximum of the image gradient. In this boundary detection process, the fact that these boundary points constitute a closed geometric contour is not taken into account. Image force field for the edge based methods is easily computed from a potential energy function. In region based methods, computation for the image force field is complicated as the potential energy function cannot be used as it defines only boundaries and is therefore not a function in the image plane which is required for the image segmentation. Hence, the scope of region based methods is limited.
Active contour models can also be classified as parametric active contours and non-parametric active contours. This classification can be ambiguous in some cases. A parametric active contour is a contour that is represented by a small number of parameters that capture the shape of the object. If the parameterization is achieved by expressing the curve in terms of a basis, where the discrete function representing the curve is expressed as a weighted sum of a set of known functions, distinction between parametric and non-parametric contours is clear. First, there is a parameter space different from the physical space where the curve is initially defined. Second, different bases give parameter spaces with different properties and third, some of the operations that are performed on the contour are can be defined in the parameter space. Examples of such parameterizations are fourier, B-spline and wavelet representation.
If on the other hand, the parameters are some characteristic points on the contour in the physical space, as it is the case in the point distribution model[13], there is no distinct parameter space. In addition, the parameter vector is just a set of points of the contour which are sufficient do describe the shape of the curve. This set can be extended to contain all contain all contour points available if the shape is very complex. In this case, there is no clear distinction between the parametric and non-parametric representation.
Another classification can be made based on the model definition framework as physical active contours and statistical active contours. These two classes are actually equivalent and they differ in interpretation of the terms in the model[13].
CHROMOSOME SPREAD IMAGES
Figure 2 shows a metaphase chromosome spread image. The chromosome spread images were obtained using the following general procedure. About 5 mL of blood was removed from the patient. If a fetus was being karyotyped, amniotic fluid was removed from the amniotic sac which surrounds the fetus during development.
| Fig. 2: | Metaphase chromosome spread image (Courtesy:http://aspin.asu.edu/geneinfo/genes.htm) |
| Fig. 3: | Chromosome spread image sample (Courtesy: Dr. Michael Difilippantonio) |
| Fig. 4: | Chromosome spread image sample (Courtesy: Prof. Ken Castleman and Prof. Qiang Wu) |
| Fig. 5: | Chromosome spread image sample (Courtesy: Dr. Ekaterina Detcheva) |
| Fig. 6: | Chromosome spread image sample (Courtesy: Wisconsin State Laboratory of Hygiene) |
This was done with the aid of a large syringe and ultrasound picturing. There were cells which have come off the fetus in this fluid. The white blood cells were removed from the blood or the living cells were removed from the amniotic fluid. These cells are then cultured in a medium in which they undergo mitosis. Mitosis is stopped at metaphase using colchicine (prevents mitotic spindle from forming)[38]. Cells are centrifuged and lysed to release chromosomes. Chromosomes were then stained and photographed. Figure 3-6 viewed under a microscope which was specially adapted with a camera to take a picture of the chromosomes from one of the cells[39].
CHARACTERISTICS OF CHROMOSOME SPREAD IMAGES
The banding pattern present in the chromosomes gives rise to higher contrast compared to the outer edges. This characteristic causes the segmentation technique to misclassify the banding as a boundary.
The chromosome images in the chromosome spread image have variability in shape and size due to the nature of the spread image. Also, the spatial distribution of the chromosomes is random accompanied by uneven spacing between adjacent chromosomes. Hence, each chromosome in a chromosome spread image becomes a unique sample demanding unique values of the parameters governing the segmentation scheme.
The small object size of the chromosomes causes stringent requirements in the formulation of the segmentation scheme for chromosome spread images.
The chromosomes in the spread image (at 72 pixels per inch resolution) can have a minor axis length varying between 13 and 50 pixels approximately and major axis length varying between 23 and 130 pixels approximately. This data specified for the axis length range is with specific reference to the datasets made available for this study.
GRADIENT VECTOR FLOW ACTIVE CONTOURS
The characteristics of the chromosome spread images when studied in conjunction with the different classes of active contour models, suggest that parametric active contour models would be a better choice as a suitable segmentation tool for chromosome spread images.
Parametric active contours synthesize parametric curves within an image domain and allow them to move toward desired features, usually edges. Typically, the curves are drawn toward the edges by potential forces, which are defined to be the negative gradient of a potential function. Additional forces, such as pressure forces[18], together with the potential forces comprise the external forces. There are also internal forces designed to hold the curve together (elasticity forces) and to keep it from bending too much (bending forces).
There are two key difficulties with parametric active contour algorithms. First, the initial contour must, in general, be close to the true boundary or else it will likely converge to the wrong result. Several methods have been proposed to address this problem including multiresolution methods, pressure forces and distance potentials. The basic idea is to increase the capture range of the external force fields and to guide the contour toward the desired boundary. The second problem is that active contours have difficulties progressing into boundary concavities. There is no satisfactory solution to this problem, although pressure forces, control points, domain-adaptivity, directional attractions and the use of solenoidal fields have been proposed. However, most of the methods proposed to address these problems solve only one problem while creating new difficulties. For example, multiresolution methods have addressed the issue of capture range, but specifying how the snake should move across different resolutions remains problematic. Another example is that of pressure forces, which can push an active contour into boundary concavities, but cannot be too strong or weak edges will be overwhelmed. Pressure forces must also be initialized to push out or push in, a condition that mandates careful initialization[19].
Gradient Vector Flow (GVF) active contours were formulated to utilize the benefit of parametric active contour formulation while at the same time to overcome the difficulties posed by parametric active contour formulation[15,19].
Gradient Vector Flow (GVF) active contours use Gradient Vector Flow fields obtained by solving a vector diffusion equation that diffuses the gradient vectors of a gray-level edge map computed from the image. The GVF active contour model cannot be written as the negative gradient of a potential function. Hence it is directly specified from a dynamic force equation, instead of the standard energy minimization network.
The external forces arising out of GVF fields are non-conservative forces as they cannot be written as gradients of scalar potential functions. The usage of non-conservative forces as external forces show improved performance of Gradient Vector Flow field active contours compared to traditional energy-minimizing active contours[15,19].
The GVF field points towards the object boundary when very near to the boundary, but varies smoothly over homogeneous image regions extending to the image border. Hence the GVF field can capture an active contour from long range from either side of the object boundary and can force it into the object boundary. The gradient vectors are normal to the boundary surface but by combining laplacian and gradient the result is not the normal vectors to the boundary surface. As a result of this, the GVF field yields vectors that point into boundary concavities so that the active contour is driven through the concavities. Hence, the GVF active contour model is insensitive to the initialization of the contour and it is able to move into boundary concavities.
Information regarding whether the initial contour should expand or contract need not be given to the GVF active contour model. The GVF active contour model has a large capture range. The GVF is very useful when there are boundary gaps, because it preserves the perceptual edge property of active contours[10,19]. Also, the GVF provides for flexible initialization of the initial contour.
The GVF field is defined as the equilibrium solution[40] to the following vector diffusion equation,
| (7a) |
| (7b) |
where, ut denotes the partial derivative of u(x,t) with respect to t,∇2 is the laplacian operator (applied to each spatial component of u separately) and f is an edge map that has a higher value at the desired object boundary. The functions in g and h control the amount of diffusion in GVF. In Eq. 7, g(|∇f |)∇2u produces a smoothly varying vector field and hence called as the “smoothing term”, while h(|∇f |)(u-∇f) encourages the vector field u to be close to∇ f computed from the image data and hence called as the data term. The weighting functions g(•) and h(•) apply to the smoothing and data terms, respectively and they are chosen as[19] g(|∇f |)=ì and h(|∇f |)=|∇f |2. g(•) is constant here and smoothing occurs everywhere, while h(•) grows larger near strong edges and dominates at boundaries. Hence, the Gradient Vector Flow field is defined as the vector field v(x,y)=[u(x,y),v(x,y)] that minimizes the energy functional
| (8) |
The effect of this variational formulation is that the result is made smooth when there is no data.
When the gradient of the edge map is large, it keeps the external field nearly equal to the gradient, but keeps field to be slowly varying in homogeneous regions where the gradient of the edge map is small, i.e., the gradient of an edge map ∇f has vectors point toward the edges, which are normal to the edges at the edges and have magnitudes only in the immediate vicinity of the edges and in homogeneous regions f is nearly zero. μ is a regularization parameter that governs the tradeoff between the first and the second term in the integrand in Eq. 8. The solution of Eq. 8 can be done using the Calculus of Variations and further by treating u and v as functions of time, solving them as generalized diffusion equations[19].
The GVF Active contour is governed by the following parameters, namely, σ, μ, α, β and k. σ determines the Gaussian filtering that is applied to the image to generate the external field. Larger value of σ will cause the boundaries to become blurry and distorted and can also cause a shift in the boundary location. However, large values of σ are necessary to increase the capture range of the active contour. μ is a regularization parameter in Eq. 8 and requires a higher value in the presence of noise in the image. α determines the tension of the active contour and β determines the rigidity of the contour. The tension keeps the active contour contracted and the rigidity keeps it smooth. α and β may also take on value zero implying that the influence of the respective tension and rigidity terms in the diffusion equation is low. κ is the external force weight that determines the strength of the external field that is applied.
CONCLUSIONS
The ever increasing role of medical imaging in automated processing of patient image data has opened up an array of challenging problems centered on the computation of accurate models of anatomical structures. With specific reference to the task of segmentation in chromosome spread images, Gradient vector flow active contours show much promise for efficient segmentation which can be attributed to the strengths of deformable curves in segmentation and to the inherent strengths that arise out of the Gradient vector flow active contour formulation. Investigations on the segmentation of chromosome spread images using Gradient vector flow active contours will yield valuable insight into their performance and will also shed light on possible improvement of this segmentation technique for application to chromosome spread images.
ACKNOWLEDGMENTS
The authors extend their heartfelt thanks to Dr. Michael Difilippantonio, Staff Scientist at the Section of Cancer Genomics, Genetics Branch/CCR/NCI/ NIH, Bethesda MD; Prof. Ekaterina Detcheva at the Artificial Intelligence Department, Institute of Mathematics and Informatics, Sofia, Bulgaria; Prof. Ken Castleman and Prof. Qiang Wu, from Advanced Digital Imaging Research, Texas and Wisconsin State Laboratory of Hygiene--http://worms.zoology.wisc.edu/zooweb/Phelps/karyotype.html for their help in providing chromosome spread images.