Abstract: This study proposes DCT (Discrete Cosine Transform) based NGVF (Gradient Vector Flow in Normal Direction) Active Contours. Extensive research has been done on DCT based GVF Active Contours and the strengths of DCT based GVF Active Contours have been established. NGVF, the recent improvement to the GVF Active Contour has faster convergence speed towards the concavity and bigger time step. It also has the capability to enter into long, thin indention and provide a good contour. Based on the strength of the DCT based GVF Active Contours and the foundational strength of the NGVF, the study propose the DCT based NGVF Active Contours. Experimental testing and validation experiments support the proposed DCT based NGVF Active Contours, which is expected to be a good segmentation technique.
INTRODUCTION
This study proposes DCT based NGVF Active Contours. The DCT based NGVF Active Contours has its foundation derived from NGVF Active Contours (Jifeng et al., 2007) and extensive research carried out in the area of image segmentation using GVF Active Contours (Britto and Ravindran, 2005a, b, 2006a-e, 2007a, b).
The forthcoming data introduce the GVF Active Contours and their formulation, DCT based GVF Active Contour followed by discussion on the NGVF Active Contours. The research then propose DCT based NGVF Active Contours, followed by experimental testing and validation.
Active contours are used extensively in computer vision and image processing applications, particularly to locate object boundaries. The main advantage of Active Contours is the ability to generate closed parametric curves from images. Problems associated with initialization and poor convergence to concave boundaries, however, have limited their utility.
To overcome these difficulties in initialization and poor convergence to object boundaries, an external force model was suggested that used a convex combination of the usual external force and a new force derived from an estimate of the local curvature of the object boundary.
This force simultaneously pulled the snake toward the boundary and into the concave region (Prince and Xu, 1996). This was later improved by Xu and Prince (1998) to form the Gradient Vector Flow (GVF) field.
The resulting formulation produces external force fields that had both irrotational and solenoidal components (Xu and Prince, 1998), which had a large capture range overcoming the difficulty associated with initialization of Active Contours and it was also able to provide good convergence to concave boundaries.
Jinshan and Acton (2004) have given an improved form of the GVF field, called the Discrete Cosine Transform (DCT) based GVF.
Extensive experimentation and analysis on the chromosome spread image segmentation performance of DCT based GVF Active Contours has been performed and it is thus established that the DCT based GVF Active Contours are an efficient segmentation technique for chromosome images (Britto and Ravindran, 2005a, b, 2006a-e, 2007a, b).
An improvement for the GVF Active Contours called NGVF (GVF in the Normal direction) has been proposed (Jifeng et al., 2007). The NGVF has faster convergence speed towards the concavity and bigger time step. It also has the capability to enter into long, thin indention and provide a good contour.
The study propose DCT based NGVF Active Contours based on the strengths of GVF Active Contours and NGVF.
ACTIVE CONTOUR MODELS
Active Contours also called as Snakes or Deformable Curves, first proposed by Kass et al. (1987) are energy minimizing contours that apply information about the boundaries as part of an optimization procedure.
They are generally initialized by automatic or manual process around the object of interest. The contour then deforms itself iteratively from its initial position in conformity with the nearest dominant edge feature, by minimizing the energy composed of the Internal and external forces, converging to the boundary of the object of interest.
The Internal forces computed from within the Active Contour enforce smoothness of the curve and External forces that are derived from the image help to drive the curve toward the desired features of interest during the course of the iterative process.
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. The energy function is thus minimized, making the model active.
FORMULATION OF ACTIVE CONTOUR MODELS
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 as vi = (xi,yi)T with v = (v1,… ,vn). The large number of vertices required to achieve any predetermined 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) = [x9s), y(s)], sε[0,1] that moves through the spatial domain of an image to minimize the ener gy functional
(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 while the second order derivative discourages bending.
The weighting parameters of tension and rigidity govern the effect of the derivatives on the snake.
The external energy function Eext is derived from the image so that it takes on smaller values at the features of interest such as boundaries and guides the active contour towards the boundaries. The external energy is defined by:
Eext = κ| Gσ
(x,y)* I(x,y)| |
(3) |
| Where |
| Gσ (x,y) | = | A two-dimensional Gaussian function with standard deviation |
| σ, I(x,y) | = | Represents the image and |
| κ | = | 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.
αx″ (s)-βx″O (s)-L
Eext = 0 |
(4) |
where, Fint = αx″ (s)-βx″O (s) and Fext = -L 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:
xt(s,t) = αx″ (s,t)-βx″O
(s,t)-L Eext |
(6) |
A solution to Eq. 6 can be obtained by discretizing the equation and solving the discrete system iteratively (Kass et al., 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. Hence a new external force was developed (Prince and Xu, 1996).
Three guiding principles led to the development of the new external force.
| • | The first aim was the ability to add the new force to the existing force. Since the existing force was the gradient of a scalar function (the energy Eext), it was an irrotational (curl-free field). According to the Helmholtz theorem, the other fundamental field component was a solenoidal (divergence-free) field. Therefore, the new field was chosen to be solenoidal. |
| • | The second aim was that the new field should not disturb the equilibrium contours of the external energy in the absence of internal forces. Therefore, the new field should be zero whenever the field -L Eext is zero. |
| • | The third aim wanted the field to point toward the apex of concave boundary regions, a feature defined by the object boundary curvature. Therefore, the new field was made to use a measure of boundary curvature in its definition (Prince and Xu, 1996). This was later improved by Xu and Prince (1997) to form the Gradient Vector Flow (GVF) field. Xu and Prince (1997) presented a new external force, called Gradient Vector Flow (GVF), which was computed as a diffusion of the gradient vectors of a gray-level or binary edge map derived from the image. The resultant field had a large capture range and forces the active contours into concave regions (Xu and Prince, 1998, 2000). |
The overall approach was to define a new non-irrotational external force field, called as the GVF field.
The earlier idea of constructing a separate solenoidal field from an image and adding it to a standard irrotational field was improved and a more natural approach was designed in which the external force field is designed to have the desired properties of both large capture range and presence of forces that point into boundary concavities.
The resulting formulation produces external force fields that had both irrotational and solenoidal components (Xu and Prince, 1998).
GRADIENT VECTOR FLOW (GVF) ACTIVE CONTOURS
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 GVF field Active Contours compared to traditional energy minimizing active contours (Xu and Prince, 1998, 2000).
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 GVF active contour model thus has a large capture range and is insensitive to the initialization of the contour. Hence the contour initialization is flexible.
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. Information regarding whether the initial contour should expand or contract need not be given to the GVF active contour model.
The GVF is very useful when there are boundary gaps, because it preserves the perceptual edge property of active contours (Kass et al., 1987; Xu and Prince, 1998).
The GVF field is defined as the equilibrium solution to the following vector diffusion equation (Xu and Prince 2000):
ut = g(|L f| )∇
2u- h(|L f| )(u-L f) |
(7a) |
u(x,0) = ∇ f(x) |
(7b) |
| Where |
| ut | = | Denotes the partial derivative of u(x,t) with respect to t, |
| L 2 | = | The Laplacian operator (applied to each spatial component of u separately) and |
| f | = | 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(|L f| )∇ 2u produces a smoothly varying vector field and hence called as the smoothing term, while h(|L f| )(u-L 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 chosen15 as g(|L f|) = μ and h(|L f| ) = |L f| 2. g(· ) is constant here and smoothing occurs everywhere, while h(·) grows larger near strong edges and dominates at boundaries.
Hence, the GVF field is defined as the vector field v(x,y) = [u(x,y),v(x,y)] that minimizes the energy functional:
ε∫∫μ(u x2+uy2+vx2+vy2)+|L
f| 2| v-L f| 2 dxd |
(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 (Xu and Prince, 1998).
DISCRETE COSINE TRANSFORM (DCT) BASED GVF ACTIVE CONTOURS
The transform of an Image yields more insight into the properties of the image. The Discrete Cosine Transform has excellent energy compaction. Hence, the DCTpromises better description of the image properties.
The DCT is embedded into the GVF Active Contours. When the image property description is significantly low, this helps the contour model to give significantly better performance by utilizing the energy compaction property of the DCT.
The 2D DCT is defined as:
(11) |
The local contrast of the Image at the given pixel location (k,l) is given by:
(12) |
where,
(13) |
and
(14) |
Here, wt denotes the weights used to select the DCT coefficients. The local contrast P(k,l) is then used to generate a DCT contrast enhanced image (Jinshan and Acton, 2004), which is then subject to selective segmentation by the energy compact gradient vector flow active contour model using Eq. 8.
NGVF ACTIVE CONTOURS
NGVF is an improved external force field for active contour model (Jifeng et al., 2007). Based on analyzing the diffusion process of the GVF and three interpolation functions, it has been found that the generation of GVF contains diffusions in two orthogonal directions along the edge of image, one is the tangent direction and the other is the normal direction. Moreover, the diffusion in the normal direction plays the key role on the diffusion of GVF, while the diffusion in the tangent direction has little effect.
So the GVF in the normal direction (NGVF) is taken as a new force field to study. Experiment results with several test images revealed that, compared with GVF, NGVF can enter into long, thin indention and had faster convergence speed towards the concavity and bigger time step (Jifeng et al., 2007).
NGVF is differentiated from GVF by diffusion term and can be also considered as a special case of GVF force field. Moreover, compared with GVF, NGVF can enter into long and thin concavity. It is important that bigger time step makes NGVF more effective than GVF in some cases. In addition, the interpolation function is associated with diffusion process of force field, helping to provide some insights to construct better force fields. The formulation of the NGVF is given by Jifeng et al. (2007).
DCT BASED NGVF ACTIVE CONTOURS
The DCT based GVF Active Contours have been proved to yield efficient segmentation results using standard characterized parameter values for the formulation of the Active Contours. Also, the DCT based GVF Active Contours have been found to be robust, yielding accurate and efficient segmentation results under varying conditions (Britto and Ravindran, 2005a, b, 2006a-e, 2007a, b).
The NGVF (Jifeng et al., 2007) has faster convergence speed towards the concavity and bigger time step. It also has the capability to enter into long, thin indention and provide a good contour.
The local contrast term in Eq. 12 is used to generate a DCT contrast enhanced image, which is then be subject to segmentation using the NGVF Active Contours, giving rise to the formulation of the new hybrid technique DCT based NGVF Active Contours.
Both the base techniques viz., DCT based GVF Active Contours and NGVF Active Contours are both very strong techniques, the DCT based NGVF Active Contours will have the combined strengths of the base techniques.
The new proposed DCT based NGVF Active Contours is expected to emerge as a good technique for image segmentation.
EXPERIMENTAL TESTING OF THE NEW TECHNIQUE
The new technique DCT based NGVF Active Contours was tested with a few chromosome image samples. The segmentation results obtained on testing chromosome image samples are shown in Fig. 1.
Initial testing of DCT based NGVF Active Contours for Chromosome image segmentation has yielded very good segmentation (Fig. 1; Sample 1-3).
| Fig. 1: | DCT based NGVF Active Contour segmented chromosome image sample
1-13. Sample 4-13: show successful segmentation of samples of chromosome
images. The red contour indicates the converged DCT based NGVF Active Contour |
| Table 1: | Tabulation of error obtained as a difference between contour axes and chromosome image axes |
These initial results support the primary hypothesis that the strengths of the DCT based GVF Active Contours and the strengths of the NGVF Active Contours would be present together collectively in the proposed new hybrid technique of DCT based NGVF Active Contours.
EXPERIMENTAL VALIDATION AND DISCUSSION
The next step is the validation of the proposed technique. A challenging segmentation task was devised to test the suitability of DCT based NGVF active contours for chromosome segmentation.
Table 1 indicates error measures that are obtained as a difference between contour axes and the chromosome image axes which yields the diametric error. The radial error is obtained by dividing the diametric error by 2.
The DCT based GVF standardized characterized parameter values were used directly in the DCT based NGVF active contour formulation without any modifications. Such a DCT based NGVF active contour formulation will surely be subjected to the strictest test because characterization of parameters had been done for the DCT based GVF Active Contours, which implies that the parameters have been characterized including both the tangential and normal components but the DCT based NGVF uses solely the normal diffusion components. Therefore, the parameters for the active contour formulation will be a compromise of the tangential and normal diffusion operations. Stating on strict terms, the parameters used could be a choice, but certainly not an optimum parameter set characterized for the normal component of diffusion alone. Therefore, there should be a lot of difficulty introduced due to such a parameter choice.
Also, the chromosome spread images offer a host of inherent obstacles to successful segmentation in terms of:
| • | Variable shape caused due to imaging conditions. |
| • | Bending effects. |
| • | Variable separation between adjacent chromosomes. |
This has been the experimental conditions under which the DCT based GVF active contours have been tested for suitability for segmenting chromosome spread images. The degree of difficulty both inherent and introduced will surely make this test of suitability as a reliable assessment.
The results indicate that the segmentation has been successful in the midst of so much of inherent and introduced difficulty to segmentation using DCT based NGVF Active Contours. Also, the tabulation of the error measures also indicates successful segmentation. Since the contour thickness is 1 pixel and the iterative step size is also 1 pixel, an error measure of 1 pixel is acceptable. Including the possible error of 1 pixel, the balance error is only a fraction greater than 1, which may be reduced by characterization. Hence, the errors obtained are acceptable subject to the experimental conditions.
The significant points to be noted from the results are that:
| • | Segmentation has been successful |
| • | Error measures are acceptable |
| • | Characterization and standardization has been done only for DCT based GVF but not DCT based NGVF, but still successful segmentation and acceptable error measures have been obtained. |
| • | Characterization of parameters for DCT based NGVF Active Contours might yield better and more accurate segmentation results for chromosome image segmentation. |
These results support the suitability of DCT based NGVF Active Contours for segmentation of chromosome images.
CONCLUSION
This research has proposed a new technique DCT based NGVF Active Contours. Experimental testing and validation has also been done. The results of the testing and validation experiments show that the new technique DCT based NGVF Active Contours has got very good potential for emerging as an efficient segmentation technique. Future research will concentrate on elucidating the strengths of the new DCT based NGVF Active Contours.
ACKNOWLEDGMENTS
The authors express their thanks to Dr. Michael Difilippantonio (Staff Scientist at the Section of Cancer Genomics, Genetics Branch/CCR/NCI/NIH, Bethesda MD); Prof. Ekaterina Detcheva (Artificial Intelligence Department, Institute of Mathematics and Informatics, Sofia, Bulgaria); Prof. Ken Castleman and Prof. Qiang Wu (Advanced Digital Imaging Research, Texas); Wisconsin State Laboratory of Hygiene (http://worms.zoology.wisc. edu/zooweb/Phelps/karyotype.html) and the Genomic Centre for Cancer Research and Diagnosis (GCCRD) (http://www.umanitoba.ca/institutes/manitoba_institute_cell_biology/GCCRD/GCCRD_Homepage.htm) for providing chromosome spread images. The authors thank Prof. Ning Jifeng, Xidian University, Shaanxi, China.