Agent Based Segmentation of the MRI Brain Using a Robust C-Means Algorithm

Show more

Received 23 June 2016; accepted 7 August 2016; published 10 August 2016

1. Introduction

The brain is the most mysterious and complex organ in the human body. To explore its structure and understand how it functions, several medical imaging techniques have been developed. Magnetic Resonance Imaging (MRI) is the most useful technique that helps to visualize, in a non-invasive way, the brain tissues as well as tumors with a fine resolution. Segmentation of the MR brain images is a primordial step that aims to extract the most relevant information, which in turn helps physicians to interpret these images.

Given the importance of segmenting the MR brain images, this topic has received further consideration from many researchers [1] , where a big bunch of researchers have adopted the fuzzy clustering techniques and more specifically the fuzzy c-means algorithm (or FCM) [2] - [4] . Despite its high accuracy to cluster fuzzy data, c-means becomes poor in the presence of noise. Therefore, it has been extended and modified in a variety of ways. The majority of researchers have tried to modify directly the objective function either by including a new term or by using a different distance metric. Actually, to deal with noise and reduce the effect of intensity inhomogeneity, M. N. Ahmed et al. extended the FCM to the new one FCM_S by introducing a new term that includes the neighborhood information [5] . In order to speed up the clustering process and extract non-Euclidean structures, S. Chen and D. Zhang extended the FCM_S algorithm to five new versions by simplifying the objective function and using kernel methods [6] . J. Wang et al. proposed a modified FCM algorithm that handles noise by using a novel distance measurement that includes local and non-local information [4] . To improve the segmentation accuracy of the MRI brain images and reduce the impact of noise and intensity inhomogeneity, Zexuan Ji et al. proposed a robust spatially constrained fuzzy c-means algorithm (RSCFCM) based on a new spatial factor that works as a linear filter for smoothing and restoring images corrupted by noise [7] .

To segment an MRI image, all the aforementioned methods have shown their strength in both accuracy and speed terms, although, in case of a 3D MRI brain, it is obviously noticeable that these methods lose their fastness because of the huge amount of data. To cope with this last limitation, the suppressed versions [8] of the c-means algorithm could help to speed up the clustering process. However, these versions require the adjustment of other parameters, which is undesirable. Thus, this work relies on the agent technology as an alternative solution to faster the segmentation process.

Generally, the agent technology has been used as a problem-solving technique in a wide range of application domains such as industry [9] and computer science [10] . Behind this powerful technology, there is a large literature about theories and methods of designing agent-based and multi-agent systems. To help understand the key concepts of this modern technology and how to go from theory to practice, these articles [11] - [16] represent an important integral documentation.

Our intention in this paper is to provide a fast and robust system for segmenting a set of MR brain images. The proposed multi-agent system (MAS) gets its robustness from the robust fuzzy c-means algorithm (RFCM) [6] . Whereas it obtains its fastness first from the beneficial properties of agents, such as autonomy, social ability and reactivity [11] ; and second from the propagation of information, where the clustering result of a given slice is used to initialize the clustering of the next one.

This article is structured into several parts. Section 2 describes the standard FCM and the RFCM algorithms. The proposed MAS is presented in Section 3. Experimental results on synthetic data are reported in Section 4. Section 5 is dedicated for some concluding remarks.

2. Fuzzy Clustering Algorithms

Clustering is a very important task in various application fields such as data mining, bioinformatics, image segmentation [17] [18] , pattern recognition [19] and marketing. It is the process of grouping an unlabeled data into the most homogeneous groups or clusters as much as possible [20] - [22] , such as the data within the same cluster are the most similar, and data from different clusters are the most dissimilar. It is an unsupervised classification method, because it does not have any previous knowledge about the data structure.

This work is mainly interested in the fuzzy clustering approach and more specifically the c-means [2] [23] algorithm.

2.1. Standard Fuzzy C-Means Algorithm: FCM

C-means is the best-known fuzzy clustering algorithm that is based on the fuzzy sets theory [24] to create homogeneous clusters. This algorithm considers the clustering as an optimization problem where an objective

function must be minimized. It takes as input the data set, the number of clusters C, and mini-

mizes iteratively the following objective function:

. (1)

is the Euclidean distance, m is the fuzziness exponent and it is always upper than one [25] [26] . is the fuzzy partition matrix that satisfies the following condition:

The minimization of the objective function presented in Equation (1) is carried out by updating iteratively the fuzzy partition matrix and the cluster centers as follows:

(2)

. (3)

Algorithm Steps

Step 0. Fix the clustering parameters (the converging error, the fuzziness exponent m and the number of clusters C), input the dataset I and initialize the clusters centers randomly.

RETEAT

Step 1. Update the partition matrix using Equation (2).

Step 2. Update the clusters centers using Equation (3).

UNTIL:

2.2. Robust Fuzzy C-Means Algorithm: RFCM

As the objective function (Equation (1)) is free of spatial information, the standard c-means is highly sensitive to noise and outliers. To overcome this drawback, many researchers have introduced the spatial information in different ways [5] [27] [28] . Thus, Songcan Chen and Daoqiang Zhang proposed a robust fuzzy c-means algorithm (RFCM) [6] which is a direct extension of the standard c-means where the objective function was modified as follows:

(4)

is the median value of the neighbors within a specified window around. is a parameter that controls the tradeoff between noise elimination and detail preserving. In other words, has to be chosen large enough to eliminate noise and small enough to preserve details [6] . As the standard c-means algorithm, the RFCM algorithm minimizes the objective function (Equation (4)) by updating iteratively the fuzzy partition matrix and the cluster centers as follows:

(5)

. (6)

Algorithm Steps

Step 0. Fix the clustering parameters (the converging error, the fuzziness exponent m, the number of clusters C and the new parameter), input the dataset I and initialize randomly the clusters centers.

Step 1. Compute the median filtered image.

REPEAT

Step 2. Update the partition matrix using Equation (5).

Step 3. Update the clusters centers using Equation (6).

UNTIL:

3. Multi-Agent-System Based on a Robust C-Means Algorithm: RFCM_MAS

In terms of clustering accuracy, different extensions of the c-means algorithm with spatial information [4] - [6] , [27] [28] have shown their strength in MRI image segmentation. However, in the running times point of view, they are not fast enough, especially when the dataset under consideration is a set of MR brain slices. Combining the main idea of the suppressed versions [8] with a robust c-means algorithm could help to speed up the segmentation process. Although, the suppressed versions [8] require the adjustment of a parameter that balance between the fastness of the hard clustering and the robustness of the fuzzy clustering, which makes the algorithm more parameter-dependent.

In order to provide an MRI segmentation system that is strong enough in terms of accuracy and running times, this work takes advantage from the agent technology along with the accuracy of the RFCM algorithm presented in Section 2. Actually, this work proposes a multi-agent system that takes as input a series of MR brain images, segments them using the RFCM algorithm into three clusters; white matter, gray matter and cerebrospinal fluid; and returns the result through its output.

The proposed MAS (Figure 1) is composed of three agents; one leader and two workers; that cooperate together and communicate; by exchanging ACL (Agent Communication Language) messages; through a shared memory (SM) to achieve the final segmentation of the brain.

The leader agent works as an interface between the user and the worker agents. Its tasks are summarized as follows:

・ Gets the 3D MRI brain and makes it available in the SM.

・ Initializes the clustering parameters.

・ Creates the worker agents, notifies them to start their partial segmentation tasks and waits for their replays.

・ When the leader agent receives the workers replies, it gathers their partial results in order to form the global one and returns it through the system’s output.

We distinguish between two worker agents that act separately and concurrently, the WorkerUp and the WorkerDown. The WorkerUp (resp. WorkerDown) agent segments the half part of the brain from the middle horizontal slice to the top (resp. the bottom) one.

It is obviously noticeable that sharing the brain slices between two agents and segment them separately and

concurrently could reduce the time complexity to 50%, although, it is best to reduce it as much as possible. To this end, the worker agents use the propagation of information during the segmentation process. Indeed, each worker agent preserves the clustering results of a given slice to initialize the clustering of the next one. That way, the clustering algorithm is necessarily initialized close to the search solution, which speeds up the segmentation

process. When the worker agents are notified by the leader agent, they perform the following tasks:

・ Segment the middle slice using the RFCM algorithm.

・ For each slice, the correspondent worker agent initializes the RFCM algorithm based on the clustering results of the previous slice and performs the clustering process.

Figure 1. The MAS’s architecture.

・ When a worker agent finishes its tasks correctly, it informs the leader agent.

For simplification, the proposed system is going to be noted in the rest of this paper as RFCM_MAS. It was implemented on the JADE middleware [29] .

4. Experimental Results

This section is for demonstrating the efficiency of the proposed system compared to the FCM and RFCM algorithms. To do so, we use T1-weighted 1mm MR images of a normal brain brought from the BrainWeb Simulated Brain Database [30] as testing data. To evaluate the robustness to noise, we use the misclassification rate (MCR) index defined as follows:

All the experiments were performed on an Intel (R) Core (MT) i7 (4.4 GHz) machine under Windows 7 professional. The clustering parameters for the three methods were fixed as follows:.

As has been mentioned before, the proposed MAS gets its robustness from the RFCM algorithm. To prove this result, we test the RFCM_MAS system and the standard FCM algorithm on the 90^{th} MRI slice of the testing data corrupted by Gaussian noise. Actually, the segmentation results presented in Figure 2 and Table 1 show that the standard FCM algorithm could not deal with noise, whereas the RFCM_MAS system succeeded to some extent to handle noisy pixels, this is owing to the spatial information included into the objective function (Equation (4)).

To help understand how the proposed system saves time, we consider the segmentation of the eleven middle slices of a normal human brain. The segmentation states of our system RFCM_MAS are summarized in Table 2. To segment this set of slices, the RFCM_MAS system proceeds as follows:

・ Step 1: Segment the middle slice slice_91 using the RFCM algorithm. For this first slice, the cluster centers are initialized randomly to (0, 115, 230).

・ Step 2: The WorkerUp (WorkerDown respectively) agent segments in a sequential order, the slices from Slice_92 to slice_96 (from slice_90 to slice_86 respectively). In this case, each worker agent uses the final cluster centers of the current slice to initialize the clustering of the next one.

From the numerical results depicted in Table 2, we remark that segmenting the middle slice slice_91 required the biggest number of iterations and the largest amount of time. This is due to the random initialization where the cluster centers were initialized far from the searched ones. However, the number of iterations and the running times required to segment all the other slices are smaller to some extent and very close to each other, this is

Figure 2. Segmentation results. (a) The 90^{th} slice corrupted by noise. (b) The FCM result. (c) The RFCM_MAS’s result.

Table 1. Misclassification rates of the 90^{th} slice (%).

owing to the propagation of information where the cluster centers were initialized close to the searched ones.

It is important to point out that the sum of the elementary running times required to segment all the slices is 3.397 seconds, which doubles the running time performed by the RFCM_MAS system. This is due to the fact that the worker agents work concurrently. From these valuable remarks, we deduce the strength of the proposed system to save time.

In order to prove the fastness of our system against the FCM and the RFCM algorithms, we test the three methods on some series of MRI slices. In each experiment we increase the number of the input slices. The required running times are presented in Figure 3.

From Figure 3, we notice that the three methods require more processing time as the number of the input slices increases. Besides, the increase rate of the running times required by the proposed system RFCM_MAS is the smallest and it is constant, which explains the linearity of the blue curve. We could also remark that the proposed system saves up to 80% of running times compared to FCM and RFCM algorithm, which proves its fastness.

Table 2. The segmentation states of the RFCM_MAS system.

Figure 3. Running times performed by the three methods on a simulated normal brain.

5. Conclusion

In this article, we got benefits from a robust c-means algorithm (RFCM) and the agent technology in order to furnish a fast and robust multi-agent system for MRI segmentation of the brain. In the experimental part, the proposed MAS proved its robustness to noise and its fastness compared to the standard FCM and the RFCM algorithms. In fact, the propagation of information between slices and the concurrency between agents drastically reduced the number of iterations and therefore the computational time. For these special thanks, our future work will focus on enhancing the segmentation accuracy and extending the proposed MAS in order to extract tumors.

References

[1] Pham, D.L., Xu, C. and Prince, J.L. (2000) Current Methods in Medical Image Segmentation 1. Annual Review of Biomedical Engineering, 2, 315-337.

http://dx.doi.org/10.1146/annurev.bioeng.2.1.315

[2] Bezdek, J.C., Ehrlich, R. and Full, W. (1984) FCM: The Fuzzy C-Means Clustering Algorithm. Computers & Geosciences, 10, 191-203.

http://dx.doi.org/10.1016/0098-3004(84)90020-7

[3] Clark, M.C., Hall, L.O., Goldgof, D.B., Clarke, L.P., Velthuizen, R.P. and Silbiger, M.S. (1994) MRI Segmentation Using Fuzzy Clustering Techniques. IEEE Engineering in Medicine and Biology Magazine, 13, 730-742.

http://dx.doi.org/10.1109/51.334636

[4] Wang, J., Kong, J., Lu, Y., Qi, M. and Zhang, B. (2008) A Modified FCM Algorithm for MRI Brain Image Segmentation Using Both Local and Non-Local Spatial Constraints. Computerized Medical Imaging and Graphics, 32, 685-698.

http://dx.doi.org/10.1016/j.compmedimag.2008.08.004

[5] Ahmed, M.N., Yamany, S.M., Mohamed, N., Farag, A.A. and Moriarty, T. (2002) A Modified Fuzzy C-Means Algorithm for Bias Field Estimation and Segmentation of MRI Data. IEEE Transactions on Medical Imaging, 21, 193-199.

http://dx.doi.org/10.1109/42.996338

[6] Chen, S. and Zhang, D. (2004) Robust Image Segmentation Using FCM With Spatial Constraints Based on New Kernel-Induced Distance Measure. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34, 1907-1916.

http://dx.doi.org/10.1109/TSMCB.2004.831165

[7] Ji, Z., Liu, J., Cao, G., Sun, Q. and Chen, Q. (2014) Robust Spatially Constrained Fuzzy C-Means Algorithm for Brain MR Image Segmentation. Pattern Recognition, 47, 2454-2466.

http://dx.doi.org/10.1016/j.patcog.2014.01.017

[8] Fan, J.-L., Zhen, W.-Z. and Xie, v(2003) Suppressed Fuzzy C-Means Clustering Algorithm. Pattern Recognition Letters, 24, 1607-1612.

http://dx.doi.org/10.1016/S0167-8655(02)00401-4

[9] Pechoucek, M. and Marik, V. (2006) Review of Industrial Deployment of Multi-Agent Systems. Gerstner Laboratory, Agent Technology Group, Department of Cybernetics, Czech Technical University in Prague, Czech Republic and Rockwell Automation Research Center, Prague, Czech Republic.

[10] Beer, M.D., Fasli, M. and Richards, D. (2011) Multi-Agent Systems for Education and Interactive Entertainment Design, Use and Experience. Information Science Reference, Hershey, PA.

http://dx.doi.org/10.4018/978-1-60960-080-8

[11] Wooldridge, M.J. (1992) The Logical Modelling of Computational Multi-Agent Systems. Citeseer.

[12] Ferguson, I.A. (1992) Touring Machines: An Architecture for Dynamic, Rational, Mobile Agents. University of Cambridge, UK.

[13] Wooldridge, M. and Jennings, N.R. (1995) Intelligent Agents: Theory and Practice. Knowledge Engineering Review, 10, 115-152.

http://dx.doi.org/10.1017/S0269888900008122

[14] Franklin, S. and Graesser, A. (1997) Is It an Agent, or Just a Program? A Taxonomy for Autonomous Agents, In: Müller, J.P., Wooldridge, M.J. and Jennings, N.R., Eds., Intelligent Agents III Agent Theories, Architectures, and Languages, Springer, Berlin Heidelberg, 21-35.

http://dx.doi.org/10.1007/BFb0013570

[15] Jennings, N.R., Sycara, K. and Wooldridge, M. (1998) A Roadmap of Agent Research and Development. Autonomous Agents and Multi-Agent Systems, 1, 7-38.

http://dx.doi.org/10.1023/A:1010090405266

[16] Fabregues, A. and Sierra, C. (2014) HANA: A Human-Aware Negotiation Architecture. Decision Support Systems, 60, 18-28.

http://dx.doi.org/10.1016/j.dss.2013.05.017

[17] Pappas, T.N. (1992) An Adaptive Clustering Algorithm for Image Segmentation. IEEE Transactions on Signal Processing, 40, 901-914.

[18] Horvath, J. (2006) Image Segmentation Using Fuzzy C-Means. Proceedings of SAMI, 4th Slovakian-Hungarian Joint Symposium on Applied Machine Intelligence, 20-21 January 2006, Herlany, Slovakia, 144-151.

[19] Bezdek, J.C. (2005) Fuzzy Models and Algorithms for Pattern Recognition and Image Processing. Springer, New York.

[20] Haralick, R.M. and Shapiro, L.G. (1991) Computer and Robot Vision 1. Addison-Wesley, Reading.

[21] Lam, D. and Wunsch, D.C. (2014) Chapter 20—Clustering. Academic Press Library in Signal Processing, 1, 1115-1149.

http://dx.doi.org/10.1016/B978-0-12-396502-8.00020-6

[22] Rokach, L. and Maimon, O. (2005) Clustering Methods. In: Maimon, O. and Rokach, L., Eds., Data Mining and Knowledge Discovery Handbook, Springer, Berlin, 321-352.

http://dx.doi.org/10.1007/0-387-25465-X_15

[23] Ghosh, S. and Dubey, S.K. (2013) Comparative Analysis of K-Means and Fuzzy C-Means Algorithms. International Journal of Advanced Computer Science and Applications, 4, 35-38.

http://dx.doi.org/10.14569/IJACSA.2013.040406

[24] Dubois, D., Ostasiewicz, W. and Prade, H. (2014) History and Basic Notions.

[25] Bezdek, J.C. (1981) Pattern Recognition with Fuzzy Objective Function Algorithms. Springer US, Boston.

http://dx.doi.org/10.1007/978-1-4757-0450-1

[26] Ozkan, I. and Turksen, I.B. (2007) Upper and Lower Values for the Level of Fuzziness in FCM. Information Sciences, 177, 5143-5152.

http://dx.doi.org/10.1016/j.ins.2007.06.028

[27] Pham, D. (2001) Spatial Models for Fuzzy Clustering. Computer Vision and Image Understanding, 84, 285-297.

http://dx.doi.org/10.1006/cviu.2001.0951

[28] Szilagyi, L., Benyo, Z., Szilágyi, S.M. and Adam, H.S. (2003) MR Brain Image Segmentation Using an Enhanced Fuzzy C-Means Algorith. Engineering in Medicine and Biology Society, Proceedings of the 25th Annual International Conference of the IEEE, 1, 724-726.

[29] Bellifemine, F.L., Caire, G., Greenwood, D. and Wiley Inter Science (2007) Developing Multi-Agent Systems with JADE. John Wiley, Hoboken.

[30] Brainweb. Simulated Brain Database.

http://www.bic.mni.mcgill.ca/brainweb/