
Research Article


Automatic Tissue Segmentation in Medical Images using Differential Evolution 

K. Karteeka Pavan,
V. Sesha Srinivas,
A. SriKrishna
and
B. Eswara Reddy



ABSTRACT

Segmentation of medical images is a challenging task and preprocessing step in medical diagnosis. Evolutionary algorithms such as Genetic Algorithms (GA) have been found to be effective in medical image segmentation. Almost all GAs are semiautomatic, requires either some parameters or domain knowledge such as number of segments, shape, texture etc. Differential Evolution (DE) is a simple and robust evolutionary algorithm and Automatic Clustering using Differential Evolution (ACDE) is a variant of DE. There is no study in medical image segmentation using ACDE. This study is made an attempt to extract the shape of the tissues in medical images automatically using ACDE. The performance of the ACDE algorithm in determining shape of breast cancer, lung tissues has been studied using different ultrasound images. The experimental results are compared with the regions identified by the radiologist and have demonstrated that the ACDE can extract shape of the tissues automatically (without domain knowledge) and helpful in operation surgery and radiology to cure diseases like breast cancer.





Received: November 06, 2011;
Accepted: March 20, 2012;
Published: June 19, 2012


INTRODUCTION
Clustering is a process of grouping similar elements used for image segmentation.
Medical Image segmentation is a challenging task and a preprocessing step in
medical diagnosis, planning of surgical operations and in radiation treatments.
Breast Cancer is one of the major causes of cancer deaths in women (Sheshadri
and Kandaswamy, 2006). Breast Cancer and Lung cancer can be determined from
ultrasound and xrays. Segmentation of such images is helpful for the early
detection of cancer and effective treatment.
Many segmentation methods are proposed for medicalimage data are either direct
applications or extensions of approaches from computer vision. Imagesegmentation
algorithms can be classified in many ways (Haralick and
Shapiro, 1985; Sarkar and Boyer, 1993; Zucker,
1976; Zhang et al., 2008) have presented
a number of image classification methods. Three broad classes of segmented algorithms
are manual, semiautomatic and automatic. Reviews of algorithms from each class
can be found in the studies of Clarke et al. (1995)
and Suetens et al. (1993). In order to overcome
the limitations of the traditional clustering algorithms many heuristic optimization
algorithms such as Genetic algorithms (Kharrousheh et
al., 2011), Particle Swarm Optimization (PSO) (Saadi
et al., 2010), Differential Evolution algorithms are proposed. TleloCuautle
et al. (2010) have studied the significance of evolutionary algorithms
in parameter optimization. Genetic Algorithms are found to be effective in image
segmentation (Maulik, 2009; Mahi
and Izabatene, 2011). Almost all GAs are semiautomatic and requires either
some parameters in advance or domain knowledge such as number of segments, shape,
texture etc. Differential Evolution is a recent simple evolutionary algorithm
for optimization (Adeyemo and Otieno, 2009). DE shares
many features of the Genetic Algorithms. DE has won the third place in the International
contest on Evolutionary Computation (Peng and Wang, 2010).
DE is a very fast and robust algorithm and performs well on synthetic, natural
and multispectral satellite images when compared with the other evolutionary
populationbased algorithms like Genetic Algorithm (GA) and PSO etc. (Das
et al., 2009; Liu and Li, 2011). Automatic
Clustering using Differential Evolution (ACDE), is a variant of DE. ACDE is
a DE/rand/1/Eitheror algorithm and determines the nearly optimal clusters automatically
(Das et al., 2008). There is no research found
in medical image segmentation using ACDE. This study is made an attempt to extract
the shape of the tissues in medical images automatically using ACDE. The performance
of the ACDE in extracting shapes of tissues has been studied using 5 breast
cancer images and two lung images. The experimental results have shown that
ACDE can determine the appropriate shapes by pixel intensity.
DIFFERENTIAL EVOLUTION SCHEME
Differential Evolution (DE) is the stochastic, populationbased optimization
algorithm (Price et al., 2005). It was developed
to optimize real (float) parameters of a real valued function. DE Algorithms
can be used in search of the global optimum, when objective function is nondifferentiable,
noncontinuous, nonlinear, noisy, flat, multidimensional, with many local
minima. DE also can be used when a problem is difficult or impossible to solve
analytically and the parameters are real (float) variables.
The difference between GA and DE is, GA relies on uniform crossover and DE
uses a non uniform crossover (Otieno and Adeyemo, 2010).
The parameter vector is called an individual (or chromosome, or genome). The
objective function is also called the fitness function. Figure
1 presents that the general scheme is the same for all EAs:
• 
Initialization  creation of a population of individuals 
• 
Mutation (and migration in multipopulation versions)random change of
the vector components (genes). It can be a singlepoint mutation, inversion,
translocation, deletion, etc 
• 
Recombination (crossover)merging the genetic information of two or more
parent individuals for producing one or more descendants 
• 
Selectionchoice of the best individuals for the next cycle 
• 
One cycle in the above scheme is called a generation. The solution is
found if some stopping criterion is met 
Procedure
Input: Randomly initialized position and velocity of the particles: x_{i}(0).
New offsprings are created using two main DE operators known as crossover and mutation.
AUTOMATIC CLUSTERING USING DIFFERENTIAL EVOLUTION
The classical DE (Price et al., 2005), is a populationbased
global optimization algorithm that uses a floatingpoint realcoded) representation.
Generation of F and Cr: The ith individual vector (chromosome) of the population at timestep generation) t has d components (dimensions), i.e.:
For each individual vector Z_{k}(t) that belongs to the current population, DE randomly samples three other individuals, i.e., Z_{i}(t), Z_{j}(t) and Z_{m}(t), from the same generation (for distinct k, i, j and m). It then calculates the (component wise) difference of Z_{i}(t) and Z_{j}(t), scales it by a scalar F (usually [0, 1]) and creates a trial offspring U_{i} (t+1) by adding the result to Z_{m}(t). Thus, for the nth component of each vector:
Cr [0, 1] is a scalar parameter of the algorithm, called the crossover rate.

Fig. 1: 
General evolutionary algorithm scheme 
If the new offspring yields a better value of the objective function, it replaces
its parent in the next generation; otherwise, the parent is retained in the
population, i.e.:
where, f(•) is the objective function to be maximized. To improve
the convergence properties of DE, we have tuned its parameters in two different
ways here. In the original DE, the difference vector (Z_{i}(t)Z_{j}(t))
is scaled by a constant factor F. The usual choice for this control parameter
is a number between 0.4 and 1. We propose to vary this scale factor in a random
manner in the range (0.5, 1) by using the relation:
where, r and (0, 1) is a uniformly distributed random number within the range [0, 1]. The mean value of the scale factor is 0.75. Pseudo code of the ACDE: The pseudo code for the complete ACDE algorithm is given here. Step 1: Initialize each chromosome to contain K number of randomly selected cluster centers and K (randomly chosen) activation thresholds in [0, 1]. Step 2: Find out the active cluster centers in each chromosome. Step 3: For t = 1 to t_{max} do
• 
For each data vector Xp, calculate its distance metric d(Xp,
m_{i, j}) from all active cluster centers of the ith chromosome
V_{i} 
• 
Assign Xp to that particular cluster center m_{i, j} 
Where:
• 
Check if the number of data points that belong to any cluster
center m_{i,j} is less than 2. If so, update the cluster centers
of the chromosome using the concept of average described earlier 
• 
Change the population members according to the DE algorithm outlined in
the above equations. Use the fitness of the chromosomes to guide the evolution
of the population 
Step 4: Report as the final solution the cluster centers and the partition obtained by the globally best chromosome (one yielding the highest value of the fitness function) at time t = t_{max}.
We have used CS measure as the fitness function. Chou et
al. (2004) have proposed the CS measure for evaluating the validity
of a clustering scheme. The centroid of a cluster is computed by averaging the
elements that belong to the same cluster using:
where,
is the distance between X_{i} and X_{j} i.e., the difference
of two pixel intensities and
is the distance between two cluster centroids. CS measure is a function of the
ratio of the sum of withincluster distance to betweencluster distance. The
cluster configuration that minimizes CS is taken as the optimal number of clusters,
k.
EXPERIMENTAL RESULTS
The performance of ACDE has been studied using ultrasound breast cancer tissue
images. The extracted shapes of tissues are compared with shape specified by
a radiologist and with the chain optimization (Rahnamayan
and Mohamad, 2010). The ultrasound images are taken from (Rahnamayan
and Mohamad, 2010). The Fig. 2 shows the sample of original
ultrasound images, tissue segmentation (green) as specified by the radiologist
and the corresponding tissue segmentation (red) results of Chain optimization
(Rahnamayan and Mohamad, 2010).
As the ACDE results different clusters in different independent runs, the Table 1 shows different segmented regions for a given medical image. The experimental results demonstrated that the extracted shape of tissues is insensitive to the number of clusters.
Canny edge detection method is applied to the clustering solutions of ACDE
to identify the segments and the segmented regions for sample images are included
in the Fig. 2.
Table 1: 
Original Images and corresponding output images of ACDE 

*Segments determined out of total given segments 

Fig. 2(ac): 
(a) Four test ultrasound breast cancer images, (b) The green
segmentation has been performed by a radiologist and the red one by the
chain optimization (5) and (c) Segmented regions from ACDE 
The resultant segments of ACDE are compared with the chain optimization and
with the segments identified by radiologists. The results of ACDE demonstrated
that the ACDE can determine the shape of the tissues as specified by the radiologist.
CONCLUSION Almost all existing clustering algorithms for medical image segmentation require domain knowledge and some parameters in advance. ACDE is the automatic clustering using differential evolution on real valued data sets. Here, we have applied the ACDE on medical images and the experimental results have proved that ACDE accurately identifies the shape of the tissues in medical images and is insensitive to the number of clusters. The results are helpful in medical diagnosis, radiology. Determining shapes of tissues from the medical images using multi objective optimization is our future endeavor.

REFERENCES 
1: Adeyemo, J.A. and F.A.O. Otieno, 2009. Multiobjective differential evolution algorithm for solving engineering problems. J. Applied Sci., 9: 36523661. CrossRef  Direct Link 
2: Kharrousheh, A., S. Abdullah and M.Z.A. Nazri, 2011. A modified tabu search approach for the clustering problem. J. Applied Sci., 11: 34473453. CrossRef 
3: Chou, C.H., M.C. Su and E. Lai, 2004. A new cluster validity measure and its application to image compression. Pattern Anal. Applied, 7: 205220. CrossRef 
4: Clarke, L.P., R.P. Velthuizen, M.A. Camacho, J.J. Heine and M. Vaidyanathan et al., 1995. MRI segmentation: Methods and applications. Magnetic Reson. Imag., 13: 343368. CrossRef  PubMed 
5: Haralick, R.M and L.G. Shapiro, 1985. Image segmentation techniques. Comput. Vision Graphics Image Process, 29: 100132. CrossRef 
6: Peng, L. and Y. Wang, 2010. Differential evolution using uniformquasiopposition for initializing the population. Inform. Technol. J., 9: 16291634. CrossRef  Direct Link 
7: Mahi, H. and H.F. Izabatene, 2011. Segmentation of satellite imagery using RBF neural network and genetic algorithm. Asian J. Applied Sci., 4: 186194. CrossRef  Direct Link 
8: Otieno, F.A.O. and J.A. Adeyemo, 2010. Strategies of differential evolution for optimum cropping pattern. Trends Applied Sci. Res., 5: 115. CrossRef  Direct Link 
9: Price, K.V., R.M. Storn and J.A. Lampinen, 2005. Differential Evolution: A Practical Approach to Global Optimization. Springer, Heidelberg, ISBN: 9783540209508, Pages: 538
10: Rahnamayan, S. and Z.S. Mohamad, 2010. Tissue segmentation in medical images based on image processing chain optimization. Proceedings of the International Workshop on Real Time Measurement, Instrumentation and Control [RTMIC], June 2526, 2010, IEEE NPSS Toronto, UOIT, Oshawa, ON, pp: 91 99 Direct Link 
11: Saadi, S., M. Bettayeb and A. Guessoum, 2010. Optimal approach for neutron images restoration using particle swarm optimization algorithm with regularization. J. Applied Sciences, 10: 517525. CrossRef  Direct Link 
12: Sarkar, S. and K.L. Boyer, 1993. Perceptual organization in computer vision: A review and a proposal for a classificatory structure. IEEE Trans. Syst. Man Cybernet., 23: 382399. CrossRef 
13: Sheshadri, H.S. and A. Kandaswamy, 2006. Computer aided diagnosis of digital mammograms. Inform. Technol. J., 5: 342346. CrossRef  Direct Link 
14: Suetens, P., E. Bellon, D. Vandermeulen, M. Smet, G. Marchal, J. Nuyts and L. Mortelmans, 1993. Image segmentation: Methods and applications in diagnostic radiology and nuclear medicine. Eur. J. Radiol., 17: 1421. PubMed 
15: Das, S., A. Abraham and A. Konar, 2009. Metaheuristic Clustering. Springer, Heidelberg, ISBN: 9783540921721, Pages: 254
16: Das, S., A. Abraham and A. Konar, 2008. Automatic clustering using an improved differential evolution algorithm. IEEE Trans. Syst. Man Cybernet. Part A: Syst. Hum., 38: 218237. CrossRef 
17: TleloCuautle, E., I. GuerraGomez, M.A. DuarteVillasenor, L.G. de la Fraga and G. FloresBecerra et al., 2010. Applications of evolutionary algorithms in the design automation of analog integrated circuits. J. Applied Sci., 10: 18591872. CrossRef  Direct Link 
18: Maulik, U., 2009. Medical image segmentation using genetic algorithms. IEEE Trans. Inform. Technol. Biomed., 13: 166173. CrossRef 
19: Liu, Y. and S. Li, 2011. A new differential evolutionary algorithm with neighborhood search. Inform. Technol. J., 10: 573578. CrossRef  Direct Link 
20: Zucker, S.W., 1976. Region growing: Childhood and adolescence. Comput. Graphics Image Process., 5: 382399. CrossRef 
21: Zhang, M., J. Shen and Z. Shang, 2008. Color image fuzzy classification algorithm with salient regions. Inform. Technol. J., 7: 560569. CrossRef  Direct Link 



