Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
K.Selvanayaki1, Dr.P.Kalugasalam2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
The Segmentation is a fundamental technique used in image processing to extract suspicious regions from the given image. In this paper proposes the meta-heuristic methods such as Ant Colony optimization (ACO), genetic algorithm (GA) and Particle swarm optimization (PSO) for segmenting brain tumors in 3D magnetic resonance images. Here this paper is divided into two stages. In the first stage preprocessing and enhancement is performed using tracking algorithms. These are used to preprocessing to suppress artifacts, remove unwanted skull portions from brain MRI and these images are enhanced using weighted median filter. The enhanced technique is evaluated by Peak Signal-to-Noise Ratio (PSNR) and Average Signal-to-Noise Ratio (ASNR) for filters. In the Second stage of the intelligent segmentation is three algorithms will be implemented for identifying and segmenting of suspicious region using ACO, GA and PSO, and their performance is studied. The proposed algorithms are tested with real patients MRI. Results obtained with a brain MRI indicate that this method can improve the sensitivity and reliability of the systems for automated detection of brain tumors .The algorithms are tested on 21 pairs of MRI from real patient‘s brain database and evaluate the performance of the proposed method.
Keywords |
| Brain Tumor, Magnetic Resonance Image (MRI), Preprocessing and Enhancement, Segmentation, Meta heuristic algorithm, Ant Colony optimization (ACO), genetic algorithm (GA) and Particle swarm optimization (PSO). |
INTRODUCTION |
| Brain Tumor is one of the most aggressive and lethal of malignancies, made even more difficult to treat by the fact that most anticancer drugs have a hard time even getting to the tumors. A national survey, based on a probability sample of patients admitted to short-term hospitals in the United States during 2000 to 2010 with a discharge diagnosis of an intracranial neoplasm, was conducted in above 200 hospitals. The annual incidence was estimated at 17,000 for primary intracranial neoplasm‘s and 17,400 for secondary intracranial neoplasms—8.2 and 8.3 per 100,000 US population, respectively. Rates of primary intracranial neoplasm are increased steadily with advancing age. The age-adjusted rates were higher among men than among women (8.5 versus 7.9 per 100,000). However, although men were more susceptible to gliomas and neuronomas, incidence rates for meningiomas and pituitary adenomas were higher among women. This intelligent system uses medical images as a input to analyses tumor tissue from MRI brain Images. Medical imaging is an important topic which is generally recognized as key to better diagnosis and patient care. It has experienced an explosive growth over the last few years due to imaging modalities such as X-rays, computed tomography (CT), magnetic resonance (MR) imaging, and ultrasound. Currently, MRI is the most sensitive imaging test of the head (particularly in the brain) in routine clinical practice.MR images of the brain and other cranial structures are clearer and more detailed than with other imaging methods. This detail makes MRI an invaluable tool in early diagnosis and evaluation of many conditions, including tumors. |
| Overview and Merits of Metaheuristic Algorithms: |
| Recently, many researchers have focused their attention on a new class of algorithms, called metaheuristics. A metaheuristic is a set of algorithmic concepts that can be used to define heuristic methods applicable to a wide set of different problems. In other words, a metaheuristic is a general algorithmic framework, which can be applied to different optimization problems with relatively few modifications to make them, adapted to a specific problem. The use of metaheuristics has significantly increased the ability of finding very high-quality solutions to hard, practically relevant combinatorial optimization problems in a reasonable time. This is particularly true for large and poorly understood problems. Several meta-heuristics, such as genetic algorithm and simulated annealing, have been proposed to deal with the computationally intractable problems. Ant colony optimization (ACO) is a new metaheuristic developed for composing approximate solutions. The ant algorithm was first proposed by Coloni et al., (1991) and has been receiving extensive attention due to its successful applications to many combinatorial optimization problems. Like genetic algorithm and simulated annealing approaches, the ant algorithms also foster its solution strategy through use of nature metaphors. This paper presents an automatic segmentation of brain magnetic resonance images using ant colony optimization, genetic algorithm and particle swarm optimization technique. |
| Overview of Ant Colony Optimization: |
| Ant Colony Optimization (ACO) metaheuristic; a recent population-based approach, is inspired by the observation of real ants colony and based upon their collective foraging behavior. Real ants are capable of finding the shortest path from a food source to the nest without using visual cues.Ants are moving on a straight line that connects a food source to their nest is a pheromone trail. Pheromone is a volatile chemical substance lay down by ants while walking, and each ant probabilistically prefers to follow a direction rich in pheromone. This elementary behavior of real ants can be used to obtain optimum value from a population. In ACO, solutions of the problem are constructed within a stochastic iterative process, by adding solution components to partial solutions. Each individual ant constructs a part of the solution using an artificial pheromone, which reflects its experience accumulated while solving the problem, and heuristic information dependent on the problem. |
| Overview of Genetic Algorithm: |
| A genetic algorithm is an iterative procedure that involves a population of individuals, each one represented by a finite string of symbols, known as the genome, encoding a possible solution in a given problem space. This space, referred to as the search space, comprises all possible solutions to the problem at hand. The standard genetic algorithm proceeds as follows: an initial population of individuals is generated at random or heuristically. Every evolutionary step, known as a generation, the individuals in the current population are decoded and evaluated according to some predefined quality criterion, referred to as the fitness, or fitness function. To form a new population, individuals are selected according to their fitness. Thus, high-fitness individuals stand a better chance of âÃâ¬Ãâreproducing‘, while low-fitness ones are more likely to disappear. Then crossover is performed with the probability pc between two selected individuals, called parents, by exchanging parts of their genomes to form two new individuals, called offspring. Next, the mutation operator is introduced to prevent premature convergence to local optima by randomly sampling new points in the search space. Flipping bits at random carries it out; with some small probability pm. Genetic algorithms are stochastic iterative processes that are not guaranteed to converge. The Termination condition may be specified as some fixed, maximal number of generations or as the attainment of an acceptable fitness level. |
| Overview of Particle Swarm Optimization: |
| Particle swarm optimization (pso) is one of the modern heuristic algorithms that can be applied to non linear and non continuous optimization problems. It is a population-based stochastic optimization technique for continuous nonlinear functions.PSO learned from the scenario and used it to solve the optimization problems. Particle Swarm Optimization is an optimization technique which provides an evolutionary based search. This search algorithm was introduced by Dr Russ Eberhart and Dr James Kennedy in 1995. The term PSO refers to a relatively new family of algorithms that may be used to find optimal or near to optimal solutions to numerical and qualitative problems. |
| Overview of Intelligent System: |
| Segmentation is a process that separates objects in an image. The texture based segmentation starts with a user defined training area, where texture characteristics are calculated and then applied as a pixel classifier to other pixels in one cross-section image or the entire volume to separate them into groups. While image texture has been defined in many different ways, a major characteristic is the repetition of a pattern or patterns over a region. The pattern may be repeated exactly, or as a set of small variations on the theme, possibly a function of position. For medical images, because objects are normally certain type of tissues, such as blood vessels, brain tissue, bones and etc .In this intelligent segmentation describes the application of a proposed technique such as ant colony system, genetic algorithm, particle swarm optimization (ACO-GA-PSO) is implemented for the segmentation of suspicious region from Brain MRI. In this work, initially the brain MR images are preprocessed and enhanced by weighted median filter to remove the high frequency components (ie.noise) from the image. Then the skull regions are eliminated. Second the suspicious regions are extracted from background tissue using three algorithms (ACO-GA-PSO) one by one. Finally the algorithms are evaluated. The following figure 1 describes the structure of intelligent system. |
 |
| Previous Approaches to Segmentation: |
| The initial objective of MRI brain image segmentation is to partition of the given MRI brain image into non-intersecting regions describing real anatomical structures. Over the last decade, many methods have been proposed to tackle this problem.A partial list includes surface model, Deformable and dynamic Contour model, Iteretive growing model. One of the earliest approaches to segmentation of brain MRI was presented by Aaron et al.[1] who used a new, general-purpose segmentation tool that relies on interactive deformable models implemented as level sets. The interactive rates for solving the level-set PDE give the user immediate feedback on the parameter settings, and thus users can tune three separate parameters and control the shape of the model in real time. Ahmed et al[2]. demonstrate the qualitatively and quantitatively that the physiologically based algorithm outperforms two classical segmentation techniques. Angela et al[4]. |
| Developed a gamma camera based on a multi-wire proportional chamber equipped with a high rate, digital electronic read-out system for imaging applications in nuclear medicine. Azadeh[5] presents our proposed methods and results for the analysis of the brain spectra of patients with three tumor types (malignant glioma, astrocytoma, and oligodendroglioma). Benedicte et al[6] report describes initial use of an accumulating healthy database currently comprising 50 subjects aged 20–72. Bricq[7] presents a unifying framework for unsupervised segmentation of multimodal brain MR images including partial volume effect, bias field correction, and information given by a probabilistic atlas. Chan et al[8] presents a two-step method, which combines region and contour deformation, to locate the boundary of an object from a designated initial boundary plan. Chunyan et al[9] presents deformable model-based method is adapted in the system. And by the graphic user interface, the segmentation can be intervened by user interactively at real time. Corina et al[10] focuses on the automated extraction of the cerebrospinal fluid-tissue boundary, particularly around the ventricular surface, from serial structural MRI of the brain acquired in imaging studies of aging and dementia. |
| Dana et al[11] proposes a variational brain tumor segmentation algorithm that extends current approaches from texture segmentation by using a high dimensional feature set calculated from MRI data and registered atlases. Dimitris et al[13] presents several hybrid deformable methods we have been developing for segmentation and registration. These methods include metamorphs, a novel shape and texture integration deformable model framework and the integration of deformable models with graphical models and learning methods. Elizabeth et al[14]reports to detect and quantify tortuosity abnormalities on high-resolution MRA images offers a new approach to the noninvasive diagnosis of malignancy. Erik et al[15] integrates automatic segmentation based on supervised learning with an interactive multi-scale watershed segmentation method. |
| The combined method automatically provides an initial segmentation that applies the building blocks that the user can use in the interactive method. Guido et al[17] uses an EM-type algorithm that includes tissue classification, inhomogeneity correction and brain stripping into an iterative optimization scheme using a mixture distribution model. Hamarneh et al[18] introduces the use of physics-based shape deformation within the deformable organisms framework, yielding additional accuracy,robustness, and reliability by allowing intuitive real-time user guidance and interaction when necessary. Hideki et al[19] used region segmentation techniques to extract boundaries of the brain tumor and edematous regions. Iftekharuddin et al[20] presents Two novel fractal-based texture features are exploited for pediatric brain tumor segmentation and classification in MRI. |
| One of the two texture features uses piecewise-triangular-prism-surface-area (PTPSA) algorithm for fractal feature extraction. Jason[21] focused formulation for incorporating soft model assignments into the calculation of affinities, which are traditionally model free. Jayaram et al[23] described a framework for evaluating image segmentation algorithms. Image segmentation consists of object recognition and delineation. Jeffreyet al [24] introduced an automated method using probabilistic reasoning over both space and time to segment brain tumors from 4D spatio-temporal MRI data. Kabir etal[26] addressed in this paper is the automatic segmentation of stroke lesions on MR multi-sequences. Lesions enhance differently depending on the MR modality and there is an obvious gain in trying to account for various sources of information in a single procedure. Kai et al[27]specified a semi-automated method has been developed for brain tumor and edema segmentation that will provide objective, reproducible segmentations that are close to the manual results. |
PREPROCESSING AND ENHANCEMENT |
| Image Acquisition: |
| Preprocessing and enhancement techniques are used to improve the detection of the suspicious region from Magnetic Resonance Image (MRI).These techniques are applied to all types of scan images like MRI images of head, body and knee. The images were acquired on a Siemens MAGNETOM1 1.0 tesla MRI system. The images were digital and 256 X 256 pixels in size. The gray scale was quantized into 12 bits, which allowed 4096 different pixel intensities. A 3D FLASH technique was used to generate 64 or 128 contiguous thin slices. The MR images were transferred to a KONTRON MIPRON2 image processing workstation, and existing enhancement techniques were applied. The workstation used eight bits for each pixel, or 256 intensity levels. A software program compressed the 12 bit magnetic resonance images linearly to a maximum intensity of 255. |
| Preprocessing and Enhancement: |
| Preprocessing and enhancement techniques are used to improve the detection of the suspicious region from Magnetic Resonance Image (MRI).This section presents the gradient-based image enhancement method for brain MR images which is based on the first derivative and local statistics. The preprocessing and enhancement method consists of two steps; first the removal of film artifacts such as labels and X-ray marks are removed from the MRI using tracking algorithm. Second, the removal of high frequency components using weighted median filtering technique. It gives high resolution MRI compare than median filter, Adaptive filter and spatial filter. The performance of the proposed method is also evaluated by means of peak single-to noise-ratio (PSNR), Average Signal-to-Noise Ratio (ASNR).The following figure 2 displays brain MRI from preprocessing and enhancement stage. |
| Algorithm |
| Weighted Median Filter: |
| Weighted Median (WM) filters have the robustness and edge preserving capability of the classical median filter. WM filters belong to the broad class of nonlinear filters called stack filters. This enables the use of the tools developed for the latter class in characterizing and analyzing the behavior and properties of WM filters, e.g. noise attenuation capability. The fact that WM filters are threshold functions allows the use of neural network training methods to obtain adaptive WM filters. The Applications of WM is speech processing, adaptive weighted median and optimal weighted median filters for image and image sequence restoration, weighted medians as robust predictors in DPCM code and Quincunx coding, and weighted median filters in scan rate conversion in normal TV and HDTV systems. The weighted median filter determines noise points in image through noise detection. It adjusts the size of filtering window adaptively according to number of noise points in window, the pixel points in the filtering window are grouped adaptively by certain rules and gives corresponding weight to each group of pixel points according to similarity, finally the noise detected are filtering-treated. The evaluation criteria for weighted Median filtering is considered as follows: |
| Performance Evaluation: |
| Karnan et al used Contrast, Contrast Improvement Index (CII), background noise level, Peak Signal-to-Noise Ratio (PSNR), and Average Signal-to-Noise Ratio (ASNR) to evaluate the enhancement performance. The definitions of contrast and CII are defined as, |
| CII = C Processed / C Original (1) |
| C processed and C original = Contrasts of MRI |
 |
 |
| Skull Removal from Brain MRI: |
| The human skull is a bony structure, part of the skeleton that is in the human head, the brain is enclosed by skulls, these are provides the fundamental security to brain which supports the structures of the face and forms a cavity for the brain. The third section of this automatic system explains the removal of skull portions from MR brain images. These skull portions are divided in to left, right and bottom of skull. The following table shows the tracking algorithm is used to remove unwanted portion of MRI that means left, right and top skull portions that are not required for further processing. The following table 1 shows the tracking algorithm for removal of skull portions on MRI. |
 |
SEGMENTATION USING ACO |
| Ant colony optimization (ACO) is a population-based meta heuristic that can be used to find approximate solutions to difficult optimization problems. In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants incrementally build solutions by moving on the graph. The solution construction process is stochastic and is biased by a pheromone model, that is, a set of parameters associated with graph components whose values are modified at runtime by the ants. . In this implementation, we are using 20 numbers of iterations. Select the image pixels, which are having optimum level, are stored as a separate image. The following algorithm shows Ant Colony Optimization for Brain Tumor Detection. |
| Step 1: Read the MRI image or the ROI image and stored in a two dimensional matrix. |
| Step 2: Pixels with same gray value are labeled with same number. |
| Step 3: For each kernel in the image, calculate the posterior energy U (x) value. |
| Step 4: The posterior energy values of all the kernels are stored in a separate matrix. |
| Step 5: Ant Colony System is used to minimize the posterior energy function. The procedure is as follows: |
| Step 6: Initialize the values of number of iterations (N), number of ants (K), initial pheromone value (T0),a constant value for pheromone update (ρ).[here,we are using N=20,K=10, T0=0.001 and ρ =0.9] |
| Step 7: Create a solution matrix (S) to store the labels of all the pixels, posterior energy values of all the pixels, initial pheromone values for all the ants at each pixels, and a flag column to mention whether the pixels is selected by the ant or not. |
| Step 8: Store the labels and the energy function values in S. |
| Step 9: Initialize the pheromone values, T0=0.001. |
| Step 9: Initialize the pheromone values, T0=0.001. |
| Step 10: Initialize all the flag values for all the ants with 0,it means that pixels is not selected yet,if it is set to 1 means selected. |
| Step 11: Select a random pixel for each ant, which is not selected previously. |
| Step 12: Update the pheromone values for the selected pixels by all the ants. |
| Step 13: Using GA, select the minimum value from the set, assign as local minimum (Lmin). |
| Step 14: Compare this local minimum (Lmin) with the global minimum (Gmin),if Lmin is less than Gmin,assign Gmin = Lmin. |
| Step 15:Select the ant,whose solution is equal to local minimum, to update its pheromone globally. |
| Step 16: Perform the steps (13) to (15) till all the image pixels have been selected and Perform the steps (7) to (16) for M times. |
| Step 17: The Gmin has the optimum label which minimizes the posterior energy function. |
| Step 18: Store the pixels has the optimum label in a separate image that is the segmented image. |
SEGMENTATION USING GENETIC ALGORITHM (GA) |
| Thangavel and Karnan(2005) said a genetic algorithm (GA) is an optimization technique for obtaining the best possible solution in a vast solution space. Genetic algorithms operate on populations of strings, with the string coded to represent the parameter set. The intensity values of the tumor pixels are considered as initial population for the genetic algorithm. The intensity values of the suspicious regions are then converted as 8 bit binary strings and these values are then converted as population strings and intensity values are considered as fitness value for genetic algorithm. Now the genetic operator‘s reproduction, crossover and mutation are applied to get new population of strings. The following steps describe genetic algorithm to find optimal threshold for detect the tumor tissue. |
| Algorithm of Genetic Algorithm |
| Step 1: Load the image the size is 256x256 (each element corresponds to a gray value Between 0 to 256 and their classes are determined. |
| Step 2: Divide the image to 3x3 labels (cells). |
| Step 3: Calculate the fitness value for all pixels in the label F(x) = 1/ (1+x2 ) |
| Step 4: Choose two parents randomly for crossover and mutation operation with crossover probability PC and mutation probability PM. Compute the fitness of parents and child. The fitness function is the normalized histogram function F(x). |
| Step 5: Initialize the local optimal value as a 0 |
| Step 6: Initialize the parents for find the cross over function i=x position, j = y position |
| 1. Pa= F(i-1,j-1), Pb=F(i+1,j+1) |
| 2. Pa= F(i,j-1), Pb=F(i,j+1) |
| 3. Pa= F(i-1,j), Pb=F(i+1,j), |
| 4. Pa= F(i-1,j+1), Pb=F(i+1,j-1) |
| Step 7: Calculate the child for the parent |
| C1=Pa – F(x) |
| C2 = F(x)-Pb |
| Step 8: Select a child for local update Selectchild = max (C1, C2) |
| Step 9: Select the local optimal value for find the optimal value for a label If ( LocalOptimal < SelectChild ) then LocalOptimal = SelectChild Else No change in LocalOptimal |
| After selection of local optimal elements are put in their respective labels. |
| Step 10: Repeat Step 6, 7, 8 and 9 for all elements until end of the label. |
| Step 11: Update optimal value for find Global Optimal LocalOptimal= LocalOptimal + Mutation |
| Step 12: Select the Global optimal value for find the optimal value for an image |
| If (GlobalOptimal < LocalOptimal) then GlobalOptimal= LocalOptimal Else No change in Global Optimal After selection of Global optimal elements are put in their respective labels. |
| Step 13: Repeat Step 2 to 12 for all elements until end of the label. |
| Step 14: Consider Global Optimal value is adaptive threshold for the segmentation |
SEGMENTATION USING PARTICLE SWARM OPTIMIZATION(PSO) |
| Particle swarm optimization (pso) is one of the modern heuristic algorithms that can be applied to non linear and non continuous optimization problems. It is a population-based stochastic optimization technique for continuous nonlinear functions. The particle swarm concept originated as a simulation of simplified social system. The original intent was to graphically simulate the choreography of bird of a bird block or fish school. However, it was found that particle swarm model can be used as an optimizer.PSO is initialized with a group of random particles (solutions) and then searches for optima by updating generations. In every iteration, each particle is updated by following two "best" values. The first one is the best solution (fitness) it has achieved so far. (The fitness value is also stored.) This value is called pbest. Another "best" value that is tracked by the particle swarm optimizer is the best value, obtained so far by any particle in the population. This best value is a global best and called gbest. When a particle takes part of the population as its topological neighbors, the best value is a local best and is called lbest. |
| Step 1: Load the image the size is 256x256 (each element corresponds to a gray value Between 0 to 256 and their classes are determined. |
| Step 2: Divide the image to 3x3(or) 5 x5(or)7 x7 labels etc. |
| Step 3: Initialize all particles inside the labels. |
| Step 4: Calculate the fitness value for all pixels in the label. |
| Step 5: Select the best optimum (pBest) value for the label. |
| If (fitness value<best fitness value (pBest) in history update current value =new pBest else current value= fitness value |
| After selection of current value elements are put in their respective labels. |
| Step 6: Repeat Step 4 and 5 for all elements until end of the label. |
| Step 7: Choose the particle with the best fitness value of all the particles as the gBest. |
| Step 8: Calculate particle velocity for each particle. |
| v [cp] = v[cp] + c1 * rand() * (pbest[p] - present[p]) + c2 * rand() * (gbest[p] - present[]) |
| v [cp] = current particle velocity, pbest[cp] =best fitness value, gbest[] = fitness values of the all particles, rand()= random number between (0,1), c1, c2 are learning factors. Usually c1 = c2 = 2. |
| Step 9: Update particle position for each particle according the given solution. |
| present[] = persent[] + v[] |
| persent[] is the current particle |
| After updation of velocity and position of each particle |
| Step 10: Go to step 2 for further labels. |
RESULTS AND EXPERIMENTS |
| The following intelligent system results show the Particle swarm optimization is an extremely simple and accurate algorithm for brain tumor detection. PSO gives 99.28% of accurate detection than ACO and GA.so seems to be effective for optimizing a wide range of functions. In past several years, PSO has been successfully applied in many research and application areas. It is demonstrated that PSO gets better results in a faster, cheaper way compared with other methods. Another reason that PSO is attractive is that there are few parameters to adjust. |
 |
 |
 |
 |
CONCLUSION |
| The Intelligent segmentation of brain tumor from Magnetic Resonance Images (MRI) described a gradient-based brain image segmentation using Ant colony optimization (ACO), Particle Swarm Optimization (PSO) and Genetic Algorithm (GA). Initially the preprocessing stages are finished through tracking algorithms. Next the processed brain MRI is segmented using Ant colony optimization algorithm, particle optimization and genetic algorithm. The merit of this intelligent segmentation is detecting and evaluating three major Meta heuristic algorithms and their performance for the segmentation of brain tumor tissue from brain MRI. We are generalizing this algorithm to suit for the brain MRI from any database and the statistical result shows the proposed PSO algorithm can perform better than ACO and GA algorithm for tumor detection and detection |
References |
|