An Effective Method for Segmentation of MR Brain Images Using the Ant Colony Optimization Algorithm

Introduction

Medical image segmentation is an important tool in image analysis. The results of image segmentation are generally used as input to subsequent processing algorithms for calculation of different imaging properties such as volume of data, determination of boundaries of objects for quantitative assessment, and measures of shape or feature classification. Often, segmentation algorithms are computationally intensive requiring powerful processing engines and lengthy computation times. In clinical practice, such algorithms typically require manual intervention, lack automation, are time consuming, and inconvenient to operations and medical imaging workflow.

An algorithm that may have potential for use in medical images is the ant colony optimization (ACO) algorithm. The ant colony optimization algorithm has been used by Tao et al. [1] to perform object segmentation, improving results using fuzzy entropy criteria. Yang and Zhuang have presented an improved model of the ACO algorithm [2], and for proving the capability of this model, they used it for solving agent routing problems and demonstrated algorithm robustness, self-adaptation, and parallelism. Others have adapted the ACO method to solve sequential ordering problems [3], data mining [4], project management problems [5], image object edge enhancement [6], face recognition [7], multilevel thresholding [8], and image segmentation [9] in the field. In this paper, we propose adapting the ACO algorithm to improve the segmentation of MRI brain images into gray matter, white matter, and cerebrospinal fluid. We show improved processing speed of our modified ACO algorithm by decreasing the time to approach an ideal response. Our method is demonstrated on a set of four MRI images, and results are compared to other optimization algorithms including the genetic algorithm (GA) [10] and the particle swarm optimization (PSO) algorithm [11].

Ant Colony Algorithm

The ant colony optimization algorithm (ACO) was introduced in 1997 for the first time as a multi-agent method for solving optimization problems such as the traveling salesman problem by Dorigo and Gambardell [11]. The algorithm was inspired from studies and observations on real-world behavior of ants of a colony. The study illustrates that ants have social life and generally their behavior is geared for survival of the colony as a whole, rather than an individual or a subset of the colony.

The unique characteristic of ants is their behavior in the process of searching for their food. In particular, they search by finding the shortest path between the food source and their nest. This behavior originated from a type of mass intelligence among ants, in which elements demonstrate a random behavior. There is no direct communication among them, but their communication is only indirect. Ants leave a chemical substance called a pheromone in their path of movement, and although the substance evaporates rapidly, for short periods of time, it remains and can be recognized on the ground as a trace of the ant and the path that they have taken. Basically, each ant chooses the path of greatest pheromone trace, in other words, an ant tracks the path that the most other ants have passed through, and assumes that this most traveled path has the best source of food. This simple scheme is an effective mechanism for finding the optimal solution or best path selection.

In many optimization problems that use the ant colony optimization algorithm, the convergence is acquired using the analogy to pheromone trace tracking. For cases in which convergence in value is the item to be considered, the algorithm is run to an optimal value. For cases in which the aim of the solution is attaining convergence, the probability of the algorithm to generate an optimized solution is calculated.

Methods

Proposed Segmentation Method

Medical image segmentation using the ant colony optimization algorithm can be considered a process in which ants are looking for similar pixels (defined as food sources with specified features) by using vector features that are not identical. These food sources are considered as threshold limits for image segmentation, and the optimal value of this threshold limit is being acquired after implementation of the algorithm. The ACO algorithm runs automatically without the need for any manual operator interaction.

To begin the whole image is divided into N × N windows. It was experimentally determined by applying the ACO algorithm to three MR images of 1.5- and 3-T MR systems that setting N equal to 3 achieves excellent results and computationally is more efficient than when using larger window sizes such as 5 × 5 or 7 × 7.

All ants are propagated uniformly and randomly on the whole MR image space (search space) to perform the search activity. For each of the targeted windows, a histogram curve is plotted based on the amount of pheromone trace, which for the case of application to medical image segmentation, is analogous to groups of image pixels containing all, some, or none of the object within the 3 × 3 search window. Thus, there are three possible scenarios for each window in the entire image:

• The entire window falls in background (which is completely black).

• The entire window falls in target.

• The window falls at the boundary of target and in background.

In the first case in which the search window falls entirely within the image background, after plotting the histogram curve, no change is observed from any ant so that the search process is performed in this area just in the first iteration, and all the energy of ants is applied for target segmentation in the following iterations. So, as stated above, the entire ant’s focus would be in the second mode. It should be noted that the novelty of our method is in the way that a specified ant is determined for each window and how the histogram curve is stored in its memory.

As previously mentioned, ants are placed randomly in the first pixel, and the intensity of that pixel and that pixel’s surrounding or eight nearest neighboring pixels are stored in the ant’s memory. After storing the intensity information of each window, the search ant shares its information with the ant that has the histogram curve in its memory. The most accurate threshold in intensity variation of neighboring pixels is determined from this master histogram. This computation is done according to the following equations:

1

2

where i identifies the ant that holds in memory the information about a desired pixel and its surrounding pixels in the selected window, t is the number of iterations in the process of implementing the algorithm, W represents the selected window for the search process in the image, and D is the number of pixels in the window W. The constraint that assures that the ant in the window in the first iteration does not arrive into the next window until the process of segmentation in every window has been completed.

If we assume that C_i is the center of the ith window, Ant_i places the ant in the C_i window, (a_i, b_j) is the pixel location of Ant_i, and (c_i, d_j) represents the position of ith window; under these conditions, each of the following equations must be met in each window:

3

where N is the window size, a_i is the line upon which the ant is situated, c_i is the central line of the window, b_i is the column in which the ith ant is situated, and d_i is the central column of the window.

When the entire image is covered by searching ants and information for the whole image (intensity of the entire desired image pixels) is saved in the histogram-storing ant’s memory, the “food sources”—which are analogous to the different types of brain tissue white matter (WM), gray matter (GM), and cerebrospinal fluid (CSF)—are then defined by the optimum results of the ACO algorithm. After defining the “food” in the memory of ants, they get involved in the task of finding pixels with the similar features to the food. A constraint is that the motion of each ant from one pixel to another is ruled by the law of transition probability, thus affecting the movement of other ants, and can be expressed by the following equation:

4

where I represents all of the pixels in the image to be searched in the optimization process, and if {(i, j)∉I}, it is concluded that {P_i,j = 0}. In the above equation, τ_i,j represents the amount of pheromone or the image intensity for a given pixel located at i and J and τ_i,j(t) represents the pheromone or pixel intensity for a given pixel i and J per iteration. Fi,j(τ_i,j(t)) is defined by the following equation:

5

where α, β are weighting coefficients with the constraint that {α, β > 0}, and ϑ is related to pheromone trail update and is defined as follows:

6

where ρ is the reduction rate of pheromone quantity as the search goes forward for and {θ > 1} where θ is a constant parameter. In Eq. (5), ζ_i represents the features of the image (e.g., intensity) and has a determinant role in the convergence rate for pixel segmentation. This value is calculated for each pixel of each window and is expressed with the following equation:

7

where N is the number of pixels in each window, η_i is threshold limit for each window, and ζ_i evaluates the predetermined desired feature of each image to be tracked or searched for, which in this case represents pixel intensity. This method that is constrained to follow the newest law of movement transition in evaluating various parameters results in a considerable improvement in the algorithm implementation process. As previously mentioned, at the beginning of implementation of the algorithm, the algorithm defines many ants to be used for the segmentation process—which is a computationally intensive process—but by requiring this unique rule of update, the convergence time is minimized.

After the algorithm optimization has converged and the final criterion has been verified, segmentation of the image is complete and all of the pixels in the image are placed into one of three categories consisting of either WM, GM, or CSF. The ACO algorithm requires that the final result be achieved with minimal error as determined by comparing the manual segmentation of brain tissues by a neuroradiologist specialist, with the automated extraction of tissues by the computer ACO algorithm.

In addition, the Euclidean distance criterion must be met as applied to each two neighboring pixels such that their intensities are compared as follows: if two neighboring pixels meet the minimum distance constraint and have the same pixel intensity (or have similarity in low tolerance), then they are considered as belonging to the same class (same tissue WM, GM, CSF), but if the two neighboring pixels have a very different intensity, then they are considered as being located at the boundary of and belonging to different classes. The distance criterion is defined as follows:

8

where d_i,j is the distance criterion, and {p_i, p_j} represents the intensity of two neighboring pixels i and J.

The characteristics of the computer on which the algorithms were run are as follows: Macintosh operating system, two 2.93 GHz 6-Core Intel processors, 64 GB random access memory, and an ATI Radeon HD 5870 1 GB graphics card.

Experimental Results

In order to evaluate the performance of our proposed method, a set of brain MRI images from Namazi Hospital of Shiraz in Iran has been used. We have also compared the results obtained and the computational iterations using the proposed algorithm with those using the GA and PSO algorithms. Table 1 shows the parameters measured for each algorithm in our experiments including the number of iterations required for each algorithm to converge and the computation time required to obtain the final results for our segmentation algorithm as compared with other commonly used algorithms. The obtained results demonstrate that our proposed algorithm has better performance than the other algorithms. Table 2 shows the CS measure for each image [12], which is used to evaluate the validity of a segmentation scheme. The smaller the CS measure represents the better segmentation. Table 3 shows the cost or computational time for each algorithm, which is calculated as the time for the algorithm to achieve its best/optimal convergence result. Our ACO method took less time or lower cost than the other optimization methods to achieve its best result. Image results are also shown in Fig. 1 displaying the segmentation of gray matter, white matter, and cerebrospinal fluid achieved by the ACO algorithm, and Figs. 2, 3, and 4 show the segmentation of white matter, removal of white matter, and brain extraction achieved by the ACO algorithm as compared with GA and PSO algorithms. Figures 5 and 6 show a magnification of key areas to demonstrate the differences in performance of the final results of GA, PSO, and ACO algorithms for images 2 and 3, respectively. Figures 7, 8, and 9 show the convergence rate (error against FEs) of all segmentation algorithms for images 2, 3, and 4, respectively.

Discussion

The segmentation of an image can be seen as its separation into homogeneous regions. These regions contain discrete objects of interest or some parts of them. In order to identify these regions, we use some discriminant features of those objects such as pixel intensity, to differentiate one region or object from another. To segment out these feature-identified regions from others in an image, clustering algorithms are used. Many clustering algorithms have been tested for the segmentation of medical images such as CT and MRI [13–15].

Additionally, algorithms that are designed and implemented for the purpose of data clustering can be modified for use in medical image segmentation and, in most cases, have a much better performance than sophisticated methods solely introduced for image segmentation. The GA and PSO algorithms that have been selected for comparison with the proposed method (ACO) come from the clustering algorithms set.

The advantages of these algorithms are:

• High precision in reaching an ideal clustering.

• Ease of implementation.

• Potential methods for performance acceleration.

• Threshold selection is done in real time.

• They are less sensitive to initialization errors.

• They typically have higher segmentation accuracy.

• The quality and the stability of image segmentation are very high.

• They require less computation time or performance cost.

In addition to the aforementioned advantages of clustering algorithms, our proposed ACO algorithm has an adaptive evaporation rate of pheromone that yields excellent results in finding locally optimum thresholds.

Researchers have often tried to combine different optimization algorithms (GA, PSO, ACO, artificial bee colony, etc.) in order to compensate for deficiencies in one method that may be lessened by combination with another approach. Among these attempts, others [1] have combined ACO with fuzzy C-means (FCM) and shown improved ability of finding the local optimum threshold values in images by the proper selection of initial classes. However, this algorithm suffers from increased complexity, increased number of required constraints, and more costly computation time of reaching the final response as its characteristics. Saha and Bandyopadhyay [16] in another method implemented the combination of GA and FCM and got an ideal segmentation by calculating the optimum number of clusters (WM, GM, CSF) achieving image segmentation with minimum interference. Yousefi et al. [15] reach an ideal medical image segmentation by combination of the social algorithm and MRF. The advantage of this method is that the iteration does not get stuck in local regions. The associated disadvantage is its high complexity and lack of generalization for use across all MRI systems. Also, in combining GA and PSO algorithms for tissue segmentation of MR images with an artificial neural network algorithm, we have noticed that although the error rate is decreased significantly, the time cost of reaching a final result is very high and largely unacceptable for clinical applications.

In this paper, we try to segment magnetic resonance images for which the extraction of GM, WM, CSF, and skull is so difficult due to the closeness of pixel intensities in the boundary of adjacent regions. We compared our proposed ant colony optimization algorithm with the PSO and GA algorithms due to their better performance among other clustering and segmentation algorithms. As can be seen from Figs. 7, 8, and 9 and Tables 2 and 3, the GA could not produce an ideal segmentation. Although the GA may achieve acceptable results for some special cases, for general cases, it is not able to correctly segment all tissue regions, i.e., GM, WM, CSF, and skull. As also can be observed from Figs. 2, 3, and 4, the GA has had difficulties in segmenting CSF and WM in the middle of the image. In some parts of the image in Fig. 2 (in top left and top right), the GM regions have been misclassified as WM regions, and some WM points have been classified as CSF. This is also true for Fig. 4 for extracted brain. By studying Fig. 4, we can see that the GA removed only small regions belonging to the skull. The GA also produced the significant errors in segmenting the images in Figs. 7, 8, and 9. Thus, the GA is not optims 7 to 9. The ACO algorithm has a higher convergence rate and also less error as compared to other algorithms in brain image segmentation results. In addition, the segmentation process takes significantly less time to be performed as can be seen in the computational cost metric of Table 2.

Conclusion

The accurate segmentation of brain tissues including WM, GM, and CSF in brain MR images is critical to subsequent processing algorithms and advanced image analysis. Most methods used currently are manual, computationally intensive, and inefficient and often require specially trained personnel to perform such tasks. This may not be practical particularly in urgent cases; thus, a more automated and efficient algorithm could be important for more widespread clinical implementation.

In this paper, we proposed a new algorithm based on the ant colony optimization algorithm that is designed to achieve ideal results for the segmentation of medical MR images and to do so in a computationally efficient fashion. We tested the proposed method on four kinds of images and showed the segmentation results and computational performance of our algorithm as comparing favorably with other similar segmentation algorithms including the GA and the PSO algorithms.