Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
|
M. A. Abdallah*, Ashraf Afifi, E. A .Zanaty Information Technology Département, College of Computers and Information Technology, Taif University, Taif, Saudi Arabia. |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
In this paper, we explore a new algorithm based on evolutionary algorithms and fusion concepts for improving medical image segmentation. The proposed approach starts by finding seeds that cover the image using genetic algorithm (GA). This initial partition is used as the seed to a computationally efficient region growing method to produce the closed regions. The average overlap metric (AOM) is used to classify these regions into groups based on the similarity criterion. The fusion modules are applied to each group to find the points that label the suite membership values. The different fusion rules will be applied to these groups to produce a set of chromosomes to select the best data in each chromosome to represent the final segment. To prove the efficiency of the proposed algorithm, the proposed algorithm will be applied to challenging applications: MRI datasets, 3D simulated MRIs, and gray matter/white matter of brain segmentations.
Keywords |
| Evolutionary algorithms, genetic algorithm, region growing, average overlap metric, decision fusion. |
INTRODUCTION |
| Image processing covers various techniques that are applicable to a wide range of applications. Image processing can be viewed as a special form of two-dimensional signal processing used to uncover information about images. Among various image processing tasks, segmentation can be viewed as the first essential and important step of low level vision [1]. Image segmentation is a process by which an image is partitioned into non-intersecting regions. These regions have two properties: (1) homogeneity within a region, i.e., the texture or color in a region should be as similar as possible, and (2) heterogeneity between the regions, i.e., texture or color that in one region should be distinct from those in another region. |
| A variety of approaches have been proposed for image segmentation [2-19]. Xu et al. [13] summarized these methods into two categories: (1) boundary detection-based approaches, which try to search closed boundary contours for segmenting an image, and (2) region clustering-based approach, which group „„similar‟‟ neighboring pixels into clusters. Cheriet et al. [5] proposed a modified Otsu‟s approach (Otsu, [20]) called recursive thresholding tech-nique (dynamic thresholding) for imagesegmentation. Grau et al.[8] proposed an improvement to the watershed transform that enables the introduction of prior information for medical image segmentation. Yan and Kassim [14] used minimal path deformable models incorporated with statistical shape priors to extract organ contours. Karayiannis and Pai [9] used a fuzzy algorithm for learning vector quantization in MRI segmentation. Fuzzy c-means clustering algorithms with spatial information were also proposed for medical image segmentation [3,6]. Recently, the Hopfield neural networks have been proposed as alternative approaches [2,4]. Among them, the segmentation using competitive Hopfield neural networks (CHNN) are formulated as a cost-function-minimization problem to perform gray level thresholding on the image histogram or the pixels‟ gray levels arranged in a one-dimensional array [2,4] |
| Even though many segmentation methods have been presented, most of them are still limited in two respects: First, the number of classes is predetermined, which implies that users must identify the number of regions beforehand. Second, most of the proposed methods need some prepro-cessing to reduce or remove the noise. Recently, to rectify these limitations, Felzenszwalb and Huttenlocher [7] proposed a graph-based image segmentation method, which obeys the properties of being neither too coarse nor too fine according to a particular region comparison function. In spirit of the segmentation property, an automatic hierarchical evolutionary based image segmentation approach is proposed in this paper. Unlike the conventional genetic algorithm [21], which uses a fixed or pre-defined chromosome and the phenotype structure, the hierarchical evolutionary algorithm (HEA) [22] can relax these constraints. The intrinsic property of the HEA is its ability to code the parameters of the considered problem in a hierarchical structure. This particular property makes it a potential technology for automatic medical image segmentation. |
| Recently, the researchers have shown that GAs have been found to be effective in medical image segmentation [23]. Lai and Chang [24] presented hierarchical evolutionary algorithms (HEA) for medical image segmentation. By means of a hierarchical structure in the chromosome, the approach can classify the image into appropriate classes and avoid the difficulty of searching for the proper number of classes. Karteeka et al. [25] studied medical image segmentation and attempted to extract the shape of the tissues in medical images automatically using automatic clustering using differential evolution. Karman [26] proposed face detection based on usage of Genetic algorithm for advance classification of cases and objects of the input image. He subdivided the image into “face” and “Non face” objects to accelerate face detection. For more recently, the use of the genetic model besides the active contour has been suggested [26]. A method based on hybrid genetic algorithm (GA) and active contour was presented to solve some of active contour problems for accurate medical ultrasound image segmentation [27]. Wang et al. [29] combined GA and fuzzy clustering in which the genetic algorithm is adopted to optimize the initial cluster center and then the fuzzy clustering is used for image segmentation. More discussions can be shown in [28] for the major applications of GAs to the domain of medical image segmentation. |
| Although the concept of HEA for infinite-impulse-response (IIR) filter was designed [17], as far as we know, no one has applied the HEA method to image segmentation. The main objective of our contribution is to successfully employ HEA in medical image segmentation without considering any auxiliary or extra medical image information, such as contextual or textual properties, in given medical images. On the other hand, when we apply this method, the number of clusters in the given image does not need to be known in advance. |
| To avoid the drawbacks of the previous work, this paper introduces a new combination between GA, seed region growing, average overlap metric (AOM) and fusion concepts to improve the quality of image segmentation and accelerate the search for finding the optima. The structure of our approach consists of four steps: finding the initial population, performing seed region growing, evaluating fitness function for each chromosome, and evolving the chromosomes. The initial population is randomly generated by uniform discrete image sampling. The proposed GA attempts to find out the optimal centroid for each region for fine segmentation result. The chromosome representation includes control genes, gray-levels genes, and x and y-axis values of the gray level. The gray-level genes with control-genes equal to one and with x and y-axis values are centroid of the clusters. Then, the initial population is passed to the seed region growing with initial seed (with location (x,y)). |
| The fitness function is improved by considering the covered and uncovered data for quantitative measure of a segmentation result. Then, AOM method is used to classify the output regions of seed region growing method into groups according to similarity measure. Since the seed region growing produces crisp outputs while the largest group of fusion methods combines soft decisions, Gaussian membership function is used to convert the hard decisions to soft. The different fusion rules are applied to these groups to produce segments of points that label the similar membership values. The proposed algorithm is applied to challenging applications: MRI datasets, 3D simulated MRIs, and gray matter/white matter of brain segmentations. The experimental results show that the proposed technique produces accurate and stable results. |
THE PROPOSED METHOD |
| The proposed method start by creating initial population and applying region growing algorithm based on seed estimation from chromosome such as described in [17]. Now, each chromosome includes a seed point which represents a segment. If we have n-population we can get <=n segments. |
| By applying AOM and fusion methods [18] to these segments, we can obtain the best segment which represents the candidate segment. |
| a. Creating candidate populations (IPS); |
| b. Seed region growing to isolate suitable regions; |
| c. AOM procedure for classifying regions; |
| d. Decision fusion for improving segmentation. |
| Decision fusion applied to each group |
 |
| The different components of the proposed method based on GAs are discussed as follows by using the image in Table 1. |
 |
| Chromosome Representation: |
| In our approach, we use a new extended hierarchical chromosome representation. The extended hierarchical chromosome is made up of four parts. The first part consists of series of binary digits (the total number of „„1‟‟ implicitly represents the number of regions). The second part consists of integer numbers (representing the representative gray levels). The third part contains the x-axis values of the gray level. Finally, the forth part contains the y-axis values of the gray level (i.e., the third and fourth parts resent the position of the gray level in the picture). The number of control genes is decided by a soft estimate of the upper bound of the number of regions. An example of the extended hierarchical chromosome structure in our approach is illustrated in Table 2. |
 |
| Initial Population: |
| A GA requires a population of potential solutions to be initialized at the beginning of the GA process. In our approach, we randomly select a set of gray levels from the image as the initial parametric genes and their x and y axis. As for the control genes, they are generated randomly from {0, 1}. For example, Table 3 shows an initial population of four individuals. |
 |
| A corroding to the initial population, the first chromosome gets three centers 1, 4, and 8. The second chromosome gets three centers 5, 2, and 6. The third chromosome gets two centers 10 and 6. The fourth chromosome gets two centers 4 and 6. |
| Evaluation Technique: The fitness/objective function is chosen depending on the problem to be solved, in such a way that the strings (possible solutions) representing good points in the search space have high fitness values. This is the only information (also known as the payoff information) that GAs use while searching for possible solutions. |
 |
| In our method, we use α=1. |
| We apply our fitness function as follows. a. We first apply the seed region growing to identify a region for each center in the chromosome. Then we find the not cover region. |
 |
| b. According to our fitness function, fitness of the first chromosome is 142, the fitness of the second chromosome is 152, the fitness of the third chromosome is 82, and the fitness of the fourth chromosome is 126. |
| c. Then we apply the penalty, the fitness of the first chromosome is 142, the fitness of the second chromosome is 714, the fitness of the third chromosome is 1025, and the fitness of the fourth chromosome is 882. Table 6 shows the final fitness values. From Table 6, we can conclude that the penalty term enhanced the computation of the fitness values and identified in more accurate the best chromosome. |
 |
| Selection: The selection/reproduction process copies indi-vidual strings into a tentative new population, the mating pool, for genetic operations. The number of copies that an individual receives for the next generation is usually taken to be directly proportional to its fitness value; thereby mimicking the natural selection procedure. This scheme is commonly called the proportional selection scheme. Roulette wheel parent selection, stochastic universal se-lection, and binary tournament selection [18], [19] are some of the most frequently used selection procedures. In the commonly used elitist model of GAs, the best chromosome seen up to the last generation is retained either in the population, or in a location outside it. In our approach, we adopt the tournament selection method (Deb, 2001) because the time complexity of it is low. The basic concept of the tournament method is as follows: Randomly select a positive number Ntour of chromosomes from the population and copy the best fitted item from them into an intermediate population. The process is repeated P times, and here P is the population size. The algorithm of tournament selection is shown below. |
| Algorithm: Tournament selection |
| Input: Population P (size of P is Ppop), tournament size Ntour (a positive number) |
| Output: Population after selection P0 (size of P0 is also Ppop) |
| begin |
| for i =1 to Ppop do |
| P0 best fitted item among Ntour elements randomly selected from P; |
| return P0 |
| end |
| Table 7 shows the selected parents. |
 |
| Crossover: The main purpose of crossover is to exchange information between randomly selected parent chromosomes by recombining parts of their genetic information. Some other common crossover techniques are two-point crossover, multiple-point crossover, shuffleexchange crossover, and uniform crossover [21]. The successful operation of GAs depends a lot on the coding technique used to represent the problem variables. The building block hypothesis indicates that GAs work by identifying good building blocks, and by eventually combining them to get larger building blocks [18]. Unless good building blocks are coded tightly, the crossover operation cannot combine them together. Thus coding–crossover interaction is important for the successful operation of GAs. The crossover operator randomly pairs chromosomes and swaps parts of their genetic information to produce new chromosomes. We use the uniform crossover in the proposed approach. The uniform crossover is applied to the control genes as well as the parametric genes, simultaneously. Two chromosomes are randomly selected as parents from the current population. The crossover creates the offspring chromosome on a bitwise basis, copying each allele from each parent with a probability pi. The pi is a random real number uniformly distributed in the interval [0, 1]. Let P1 and P2 be two parents, and C1 and C2 are offspring chromosomes; the ith allele in each offspring is defined as C1(i)=P1(i) and C2(i) =P2(i) if pi 0.5; C1(i)=P2(i) and C2(i)=P1(i) if pi < 0.5 |
| An example of this operator is shown in Table 8. |
 |
| Mutation: Mutation is the process by which a random alteration in the genetic structure of a chromosome takes place. Its main objective is to introduce genetic diversity into the population. Mutating a binary gene involves simple negation of the bit, while that for real coded genes is defined in a variety of ways [19]. |
| The mutation operator is needed to explore new areas of the search space and helps the search procedure avoid sticking in local optima. Here we apply bit mutation to the control genes. This results in some bits in control genes of the children being reversed: „„1‟‟ is changed to „„0‟‟ and „„0‟‟ is changed to „„1‟‟. Either of these cases will change the number of regions. In the former, the associated parametric genes are disabled, while in the latter, the associated parametric genes are activated and the gene values are modified by randomly selecting a new gray level of the image. |
| Elitism: this step keeps the best chromosome form destroying. In this step, if the best chromosome of the previous population is fitter than the best chromosome of the current population then we exchange them. Then we replace the worst chromosome of the current population with the best chromosome of the current population. If the best chromosome of the previous population is not fitter than the best chromosome of the current population then we replace the worst chromosome of the current population with the best chromosome of the previous population. |
| Parameters of GA: There are several parameters in GAs that have to be tuned by the user. Some among these are the population size, probabilities of performing crossover and mutation (usually in the range [0.6–0.8] and less than 0.1, respectively), and the termination criteria. Most of such parameters in GAs are problem dependent, and no guidelines for their choice exist in the literature. Therefore, several researchers have also kept some of the GA parameters variable and/or adaptive. |
| In our experiments we adapted the parameters of the GA as follows. |
| popSize = 20; % Number of individuals (chromosomes). |
| maxGen = 50; % No. of generations |
| chromLen = 20; % % Length of chromosome. |
| Pm = 0.05; % Mutation rate |
| Px = 0.60; % Crossover rate |
| delta = 25; % the radius of the region |
AVERAGE OVERLAP METRIC (AOM) |
| The seed region growing algorithm gives us k of regions according to k initial population; some of these regions may contain small number of points (oversegmentation) due to the wrong seeds. We neglect a region that consists of number of pixels smaller than a prescribed value . Now, we have M regions ; 1,2,3,..., l R i M and we want to classify them into groups 1 2 { , ,.., } l l m L R R R , where ml is the number of region at each group, l=1 for the first group, l=2 for the second group, and etc.. To compare the performance of various outputs of seed region growing technique, several methods such as: average overlap metric [29], Dice similarity coefficient [30], and sensitivity and specificity [31] are used. In this section, we use average overlap metric (AOM) method which is more efficient and almost gives stable results, the reader can be shown [29] for more discussions. |
| To demonstrate the advantage of the proposed method in terms of accuracy, we use average overlap metric (AOM) as a metric to evaluate the performance of image segmentation algorithms [29]. The AOM is computed as follows: |
 |
| where i j R , R represent the two sets of R l N l ; 1,2,3,....., . This metric reaches a value of 1.0 for results that are very similar and is near 0.0 when it shares no similarly classified voxels. a. According to Zijdenbos‟ statement [32] AOM >0.70 indicates excellent agreement. After applying this algorithm k group ( k L ) of regions is given. |
| Decision Fusion |
| Once the set of segmentation has been created, an effective way of combining their outputs must be found. Fusion of multiple methods can be performed either at data level or at the decision level. We focus in this paper on decision fusion using parallel architectures. There are many decision fusion methods for each type of outputs. In this paper, we will use several of them, namely, the popular voting methods [8] for hard outputs and the minimum, maximum, median, and product rules [24] for soft outputs. The largest group of fusion methods combines soft decisions. Most popular among them are the minimum, maximum, mean, median and product fusion rules, which are defined as follows [28]- [30]. |
| a) Median rule: The rule assigns p to Ri region where |
 |
| These fusion schemes need no training in order to produce the output decision, while the others such as probabilistic product, weighted average, Dempster-shafer, and neural networks require training. |
EXPERIMENT ON MRIS |
| In this section, we experiment the proposed method using T1-weighted MR phantom with slice thickness of 1mm, slice#91, size is 129 129 pixels, as shown in Fig. (2). The test image is segmented at various noise levels 0%, 3%, and 6% using fusion voting, median, mean, maximum, minimum, product methods (see Fig. (2)). The comparison score S for each algorithm as proposed in [29] is defined as follows: |
 |
| where A represents the set of pixels belonging to a class as found by a particular method and ref A represents the reference cluster pixels. |
 |
| Fig.(3) depicts the results of the proposed fusion methods. Table (9) shows the score S of the image using fusion voting, median, mean, maximum, minimum, product methods. It shows that mean and maximum methods achieve better accuracy than other methods with no noise (0%). For 3% noise, maximum method is the best. In the case of 6% noise, mean and maximum obtain the best accuracy. Product method is worst for all noise levels. |
 |
| Comparative results using experiments on the simulated 3D data: |
| To prove the efficiency of the proposed approach, we compare the accuracy of the proposed fusion voting, median, mean, maximum, minimum, product methods and the recent fuzzy methods k-means [27] and c-means [13] for a simulated volumetric MRIs data (with 3% noise) of ten slices from #82 to #91 (see Fig.(3)). These methods are applied to each slice individually and the mean segmentation accuracy is evaluated for each image. The upper part of the 1rd and 2rd row of Table (10) show the corresponding accuracy scores of the k-means and c-means after applying them on the ten slices. Obviously, c-means acquires the better segmentation performance than k-means, and the fusion methods gave the best accuracy. |
 |
| The lower part of Table (10) shows the performance of each fusion method on the simulated data. This table shows that the highest segmentation accuracy is obtained using the mean fusion rule. It gives an improvement about 1.6% over the accuracy of the best method and an improvement 9.8% and 13% over c-means and k-means methods respectively. It shows that the least performance is obtained applying product and the minimum fusion rules. |
 |
CONCLUSION |
| Structural MRI markers now support earlier and more-precise diagnosis and measurement of progression. The presence of atrophy of medial temporal structures is a partially validated candidate marker for early diagnosis of the disease. Rates of whole-brain and hippocampal atrophy are sensitive and powerful markers of progression of neurodegeneration and, as a result, are increasingly used, along with clinical metrics, as outcomes in clinical trials of potential disease-modifying therapies. Measures of cortical thinning and automated classification approaches that assess the overall pattern of atrophy seem to show promise for the Alzheimer‟s diagnosis. |
| For improving patient's diagnosis using of MRI images, in this paper, we have presented an approach which integrates GA, region growing, and average overlap metric (AOM) coefficient with fusion modules to increase segmentation accuracy compared to the existing methods. The presented algorithm pipelines can align an individual digital brain to a reference template on a voxel-by-voxel basis and automatically label brain structures without basis of prior knowledge of a digital atlas. The proposed approach starts by finding seeds that cover the image using GA algorithm. This initial partition is used as the seed to a computationally efficient region growing method to produce the closed regions. The average overlap metric (AOM) is used to classify these regions into groups based on the similarity criterion. The fusion modules are applied to each group to find the points that label the suite membership values. |
| Although the cost of the algorithm computation is not low; it is acceptable for accurate MRIs segmentation. The proposed voting, mean, minimum, maximum, median, and product have shown higher robustness to segment most of brain images data. The segmentation of the slice #91 shows that the mean and maximum methods have obtained the higher accuracy than others for 0% and 3% noise. For higher noise 6%, the median and mean methods have achieved the best accuracy. Despite the high noise, the proposed method has given acceptable results higher than 60% in the case of 9% noise. |
| For the simulated 3D data (brain volume consists of ten slices), the mean accuracy of the proposed algorithm have been evaluated and compared to fuzzy c-means and k-means methods. Although the diversity of applying the fusion modules, they have still achieved better results than fuzzy c-means and k-means methods i.e. maximum, mean, and median methods achieved an improvement about 10.0% and 13% over the average segmentation accuracy of fuzzy c-means and k-means respectively. |
References |
|