A Modified Adaptive Fuzzy C-Means Clustering Algorithm For Brain MR Image Segmentation

A Modified Adaptive Fuzzy C-Means Clustering Algorithm For Brain MR Image Segmentation

M. Ganesh, V. Palanisamy

Electronics and Communication Engineering, Info Institute of Engineering, Coimbatore, Tamilnadu, India.

Abstract

Fuzzy c-means (FCM) clustering has been widely used in image segmentation. However, in spite of its computational efficiency and wide spread popularity, the FCM algorithm does not take the spatial information of pixels into consideration, and hence may result in low robustness to noise and less accurate segmentation. In this paper, a modified adaptive fuzzy c-means clustering (AFCM) algorithm is presented for fuzzy segmentation of magnetic resonance (MR) images. To estimate the intensity inhomogeneity, the global intensity is introduced into the coherent local intensity clustering algorithm and takes the local and global intensity information into account. The proposed method has been successfully applied to recorded MR images with desirable results. Our results show that the proposed AFCM algorithm can effectively segment the test images and MR images. Comparisons with other FCM approaches based on number of iterations and time complexity demonstrate the superior performance of the proposed algorithm.

1. Introduction

   All manuscripts must be in English. These guidelines include complete descriptions of the fonts, spacing, and related information for producing your proceedings manuscripts. Magnetic resonance (MR) imaging has several advantages over other medical imaging modalities, including high contrast among different soft tissues, relatively high spatial resolution across the entire field of view and multi-spectral characteristics. Therefore, it has been widely used in quantitative brain imaging studies. Quantitative volumetric measurement and three-dimensional (3D) visualization of brain tissues are helpful for pathological evolution analyses, where image segmentation plays an important role. The size alterations in brain tissues often accompany various diseases, such as schizophrenia [1]. Thus, estimation of

   tissue sizes has become an extremely important aspect of treatment which should be accomplished as precisely as possible. This creates the need to properly segment the brain MR images into gray matter (GM), white matter (WM) and cerebrospinal fluid (CSF) and also to identify tumors or lesions, if present [2].

   The main difficulties in brain segmentation are the intensity inhomogeneities and noise. In fact, intensity inhomogeneity occurs in many real-world images from different modalities [3, 4]. In particular, it is often seen in medical images, such as X-ray radiography/ tomography and MR images. For example, the intensity variation across the image, which arises from radio-frequency (RF) coils or acquisition sequences. Thus the resultant intensities of the same tissue vary with the locations in the image. The noise in MR images is distributed and can affect significantly the performances of classification methods. The best solutions consist of either filtering the image prior to classification or embedding spatial regularization inside the classifier itself.

   Segmentation subdivides an image into different regions or objects based on the information found about objects in imaging data. In the segmentation of medical images, the objective is to identify different regions, organs and anatomical structures from data acquired via MRI or other medical imaging technique. Initially segmentation has been done based manually by human experts. But manual segmentation is a difficult and time consuming task, which makes an automated breast cancer segmentation

   1. method desirable. The automated segmentation

   2. of MR images into anatomical tissues, fluids, and structures is an interesting field in medical image analysis. Automatic tumor segmentation based on

   artificial intelligence [10] techniques was proposed to improve the edge detection accuracy.

   In the last decades, fuzzy segmentation algorithms, especially the fuzzy c-means algorithm (FCM), have been broadly used in the image segmentation [9] and such a success mostly attributes to the introduction of fuzziness for the belongingness of each image pixel. Fuzzy c-means [14] allows for the ability to make the clustering methods able to retain more information from the original image than the crisp or hard segmentation methods [8]. Clustering is used to panel a set of given observed input data vectors or image pixels into clusters so that components of the same cluster are similar to one another than to members of other clusters where the number of clusters is usually predefined or set by some weight criterion or a priori knowledge. Fuzzy c-means segmentation [17] methods are having significant profit in segmentation of medical images, because they could retain a lot more information from the original image than hard c-means segmentation methods. The main advantage in fuzzy c- means algorithm is it allows pixels to belong to multiple clusters with reasonable degrees of membership grades. However, there are some disadvantages in using fuzzy c-means; the membership of an object has not strong enough or significantly high for a particular cluster, it means that the equation of calculating membership is not an effective, and sometimes the equation for updating prototypes has incapable to work with data which greatly affected by noise. Thus the equation for updating prototypes leads the result of clustering might be uncorrected. The main reason for underlying drawbacks of above is, fuzzy c- means employs based on existed Euclidean distance measures.

   Computer aided brain tumor segmentation system is an important application in medical image analysis. Developing a medical image analysis system not only can lighten the workload and decrease the errors of the doctors, but also can provide a quantitative measure about variation of the brain tumor throughout its whole therapeutic treatment. However, it is still a difficult problem to automatically segment brain tumor regions from MRI multi-sequences because of many existing types of tumors with morphological variability, a variety of shapes and appearance properties among

   individuals, the deformation near the structures in the brain which results in an abnormal geometry also for healthy tissues, and lack of prior knowledge about them. Therefore, it is practically meaningful to focus on semi-automatic or fully-automatic segmentation methods on multiple MRI scans for medical research, disease monitoring, therapeutic control and so on. Different MRI sequences from different excitations can respectively provide different and partly independent information about different tissues, and reflect pathologic information about the tumors in the brain. As a tumor consists of different biologic tissues, one type of MRI cannot give complete information about abnormal tissues. Combining different complementary information can enhance the segmentation of the tumors. Therefore, radiology experts always combine the multi-spectral MRI information of one patient to make a decision on the location, extension, prognosis and Clustering is a process of classifying objects or patterns in such a way that the samples in the same group are more similar than the samples in different groups.

   Based on the fuzzy theory, Zadeh [5] proposed the fuzzy clustering method, which produces the idea of partial membership of belonging. As a soft clustering method, fuzzy clustering has been extensively studied and successfully applied to image segmentation. One of the most important and widely used fuzzy clustering methods is the fuzzy c-means (FCM) algorithm, which was first proposed by Dunn [6] and promoted as the general FCM clustering algorithm by Bezdek [7]. The main purpose of the FCM algorithm is to make the vector space of a sample point be divided into a number of sub-spaces in accordance with a distance measure [8]. However, the FCM algorithm does not take the local spatial property of images into consideration, and hence suffers from high sensitivity to noise. To improve its robustness, many modifications to the FCM algorithm that incorporate spatial information into clustering have been proposed. Pham et al. [8] supplemented the FCM objective function with a penalty term and resulted in spatially smoothed membership functions.

2. Related Work

   1. Conventional FCM clustering algorithm

      Multiresolution segmentation is a bottom up region merging technique starting with one-pixel

      objects. In numerous subsequent steps, smaller image objects are merged into bigger ones. Throughout this pair wise clustering process, the underlying optimization procedure minimizes the weighted heterogeneity of resulting image objects, where n is the size of a segment and h an arbitrary definition of heterogeneity [3]. In each step, that pair of adjacent image objects is merged which stands for the smallest growth of the defined heterogeneity. If the smallest growth exceeds the threshold defined by the scale parameter, the process stops. Doing so, multi-resolution segmentation is a local optimization procedure. The entropy based methodology for segmentation of satellite images is performed as follows. Images are divided into square windows with a fixed size L, the entropy is calculated for each window, and then a classification methodology is applied for the identification of the category of the respective windows. The classification approach can be supervised or non-supervised. Supervised classification

      needs a training set composed by windows whose

      constraint for the optimization problem and it reduces heterogeneity most over the scene following a pure quantitative criterion. Its main disadvantage is that it does not use the treatment order and builds first segments in regions with a low spectral variance leading to an uneven growth of the image objects over a scene. It also causes an unbalance between regions of high and regions of low spectral variance. Comparison of global mutual fitting to local mutual fitting results show negligible quantitative differences, the former always performs the most homogeneous merge in the local vicinity following the gradient of the degree of fitting. The growth of image objects happens simultaneously as well in regions of low spectral variance as in regions of high spectral variance.

      KFCM confines that the prototypes in the kernel space are actually mapped from the original data space or the feature space. That is, the objective function is defined as

      classes are previously known (prototypes), such as rural and urban areas.

      Given a data set X = {x1,x2,.xn}, where the data point xj Rp(j = 1, . . . , n), n is the number of data, and p is the input dimension of a data point, traditional FCM [3] groups X into c clusters by minimizing the weighted sum of distances between the

      c n 2

      Q u

      m

      ij (xj ) (oi

      i1 j 1

      The objective function in (6) is then reformulated as

      Q u (1 k(x , o ))

      c n

      m

      ij j i

      (2)

      (3)

      data and the cluster centers or prototypes defined as

      i1

      j 1

      Q u

      m

      c n 2

      ij xj oi

      i1 j 1

      (1)

      Here, (1 k(xj , oi )) can be considered as a robust distance measurement derived in the kernel space.

      Here, is the Euclidean distance. uij is the membership of data x j belonging to cluster i, which is represented by the prototype oi .The constraint on

      c

      2.3. Multiple KFCM (MKFCM)

      The application of multiple or composite

      kernels in the FKCM has its advantages. In addition to the flexibility in selecting kernel functions, it also

      uij is

      uij 1

      i1

      and m is the fuzzification coefficient.

      offers a new approach to combine different information from multiple heterogeneous or homogeneous sources in the kernel space. Specifically, in image-segmentation

      2.2. Kernel FCM (KFCM)

      When applying the KFCM framework in image-segmentation problems, the multiresolution segmentation may end up with local optimization procedure. Global mutual fitting is the strongest

      problems, the input data involve properties of image pixels sometimes derived from very different sources. Therefore, we can define different kernel functions purposely for the intensity information and the texture information separately, and we then combine these

      kernel functions and apply the composite kernel in MKFCM to obtain better image-segmentation results. Examples that are more visible could be found from multitemporal remote sensing images. The pixel information in these images inherits from different temporal sensors. As a result, we can define different kernels for different temperature channels and apply the combined kernel in a multiple-kernel learning

      algorithm.

      k2 is a polynomial kernel for the spatial information

      k2(xi, xj) = (xi xj + d)2 (8)

      If kcom = k1 + k2 is the composite kernel, the minimized objective function of the MKFCM is derived as

      c n

      2

      Q um (x ) o (9)

      The general framework of MKFCM aims to minimize the objective function

      ij com j i

      i1 j 1

      Q u

      m

      c n 2

      ij com (xj ) com (oi

      i1 j 1

      (4)

      For example, the input image x j is set to be xj

      = [xj, xj, sj ] R3, the same as the third variant of MKFCM, then the composite kernel is designed as

      To enhance the Gaussian-kernel-based

      k wbk

      • wbk

      • wbk

      (10)

      KFCM-F by adding a local information term in the objective function

      c n c n

      ij j i uij (1 k(x j ,oi )) (5)

      L 1 1 2 2 3 3

      The MKFCM algorithm evaluates the centroids so as to minimize the influence of outliers. Unlike FCM, it does not attempt fuzzification for elements having membership values above the

      i1 j1

      i1 j1

      calculated threshold. This reduces the computational

      where xj is the intensity of pixel j. In the new objective function, the additional term is the weighted sum of differences between the filtered intensity xj (the local spatial information) and the clustering prototypes. The differences are also measured using the kernel- induced distances. Such kind of enhanced KFCM- based algorithm is denoted as AKFCM (with A standing for additional term).

      It is worth noting that k1or k2 in the first variant of MKFCM-K-based image segmentation can be changed to any other Mercer kernel function for the information related to image pixels. This empowers the flexibility to the segmentation algorithm in kernel function selections and combinations. For example, a composite kernel that joins different shaped kernels can be defined as

      kcom = k1 + k2 (6)

      where k1 is still the Gaussian kernel for pixel intensities

      k1(xi, xj) = exp(|xi xj |2/r2) (7)

      burden compared to FCM; also there is an absence of external user-defined parameters. The removal of this initial trial and error factor makes MKFCM more robust, as well as insensitive to the fluctuations in the incoming data. The elevation and reduction of the membership values to 1 and 0, respectively, results in contrast enhancement in the observability of the incoming data. This helps in focusing on the ambiguous boundary region; thereby gaining in terms of the quality of segmentation.

      To further improve the performance of segmentation, MKFCM that linearly combines three kernels, i.e., the first two kernels are the kernels for intensities and the local spatial informaion. To sum up, the merit of MKFCM-based image-segmentation algorithms is the flexibility in selections and combinations of the kernel functions in different shapes and for different pieces of information. After combining the different kernels in the kernel space, there is no need to change the computation procedures of MFKCM. This is another advantage to reflect and fuse the image information from multiple heterogeneous or homogeneous sources. MKFCM- based image-segmentation algorithms are inherently

      better than other KFCM-based image segmentation methods. We can demonstrate the MKFCMs significant flexibility in kernel selections and combinations and the great potential of this flexibility could bring to image segmentation problems. In the MKFCM framework, we can easily fuse the texture information into segmentation algorithms by just

      membership function matrix U = [uik]c×n. We represent typicality by tik, tik [0, 1] and the typicality matrix by T

      = [tik]c×n. According to the definition of the theory, we have c i=1uik = 1 for every pixel in the image.

      The objective function to be minimized is:

      MAFCM F ik T ik k i ik

      c n c n

      adding a kernel designed for the texture information in

      the composite kernel. As in the satellite image-

      J (C um C t ) I

      v 2 (1t )

      (11)

      segmentation and two-texture image-segmentation

      i1 k1

      i1 k1

      problems, simply adding a Gaussian kernel function of the texture descriptor in the composite kernel of MKFCM leads to better segmentation results.

3. Proposed Algorithm

   The FCM clustering algorithm was first proposed by Dunn et. al. [12] and promoted as the general fuzzy c-means clustering algorithm by Bezdek et. al. [13]. The main purpose of FCM algorithm is to make the vector space of a sample point be divided into

   a number of sub-spaces in accordance with distance

   where V ={v1,v2,..vi} is the characterized intensity center. The parameters CF >0, CT >0, m>1, > 1, the i

   > 0 are user defined constants. The constants CF and CT define the relative importance of fuzzy membership and typicality values in the objective function. Note that uik has the same meaning of membership as that in FCM. Similarly, tik has the same interpretation of typicality as in PCM. Let, the objective function of PFCM can get the minimum by updating the membership U, the typicality T and the cluster centres V as follows:

   measure [13]. However, FCM algorithm fails to deal with significant properties of images, since neighbour pixels are strongly correlated, which leads to strong

   1/( m1) 1

   c

   u Dik

   ik

   D

   (12)

   noise sensitivity. To overcome this weakness, Krishnapuram and Keller [11] proposed a new

   j 1 jk

   t 1

   ik 1 ((C / )D

   )1/( 1)

   (13)

   clustering algorithm named PCM. PCM relaxes the column sum constraint of fuzzy membership matrix in FCM and introduces a possibilistic partition matrix, so that possibilistic memberships may reflect the typical data points to their clusters. Compared with FCM,

   T i ik

   n

   F ik T ik k

   (C um C t )I

   n

   vi k 1

   F ik T ik

   (C um C t )

   (14)

   PCM can effectively eliminate the influence of noise and outliers on clustering results.

   To overcome the weaknesses of the original PCM algorithm combined the objective functions of PCM and FCM into a new objective function was

   i is defined as

   k 1

   u D

   n

   m

   ik ik

   (15)

   presented [18] to provide an improved version, called PFCM, which can be interpreted as PCM and FCM,

   i k 1

   n

   u

   m ik

   respectively, in some special cases where some proper parameters were adopted. So, PFCM can inherit the merits of both clustering algorithms. The algorithm divides the data set I = {I1, I2. In} into c clusters and n is the number of all the pixels in the image. Let the membership function uik, uik [0, 1] show the degree of the pixel Ik, k=1, 2. . . n belonging to cluster i(1ic). Then the result can be denoted by a matrix of fuzzy

   k 1

   The intensity Ik at location k far away from the neighbourhood centre should have less influence in the clustering criterion function than the locations close to the neighbourhood centre.

4. Experimental Results

   This research work presents the modified AFCM based segmentation and for synthetic images and MR images. We test and compare the proposed method (MAFCM) with some other reported algorithms on several synthetic images and synthetic brain MR images from two aspects. The performance of FCM-type algorithms depends on the initialization, this paper does the initialization and iterations depend upon the input images and choose the one with the best objective function value. This increases the reliability of comparison results acquired in the simulations. The main goals of an image segmentation algorithm are optimization of segmentation accuracy and its efficiency. Considering accuracy, the proposed method is concentrated on obtaining a robust segmentation for noisy images) and a correct detection of small regions.

   Generally, incorporating of spatial information into the segmentation process will dramatically increase the algorithms computational complexity. To compare the computational complexity of the FCM, KFCM, MKFCM and MAFCM segmentation algorithms to the 512 ×512 Lena image and cameraman image. Each segmentation was and the computational complexity of each algorithm was measured in terms of the average iteration number and average running time. The test images lena and cameraman are segmented and the results are shown Fig. 1.

   In this paper, the parameter is a constant, which controls the influence of the global intensity force and local intensity force. When the intensity inhomogeneity is severe, the bias estimation relies on the local intensity force. In such case, we should choose small , as the weight of the global intensity force.

   (a) (b)

   (c) (d)

   Fig.1 a) Original lena image b) Original cameraman image c) Segmented lena image d) segmented cameraman image.

   Otherwise, the bias field estimation may perform poorly. For images with minor inhomogeneity, the accuracy of segmentation relies on the global intensity force. In this case, we can use relatively larger, as the weight of global intensity. Thus, the global intensity reduces the misclassification for the pixels around the edges. The modified AFCM has been applied to segment the images shown in Fig. 2.

   (a) (b)

   (c) (d)

   Fig. 2 (a) and (c) Original MR images (b) and (d) segmented images

   The quantitative comparison of the accuracy of those segmentation results was given in Table 1. It reveals that our MAFCM algorithms achieve not only the highest accuracy in all three cases, but also the best robustness to noise. This experiment demonstrates again that the proposed algorithm has a better ability to resist the influence of noise.

   Table1. No. of iterations and time complexity of the proposed algorithm

   Image	Initial Cluster Centre Value	Final Cluster Centre Value	No. of Iterations	Time Consumption (sec)
   Lena	74.21	159.04	15	32
   Cameraman	21.23	201.22	10	21
   MRI1	51.24	223.14	9	19
   MRI1	51.71	221.64	9	18

   The size of image patches is an important parameter in our MAFCM algorithm. It determines how much spatial information wil be used, and hence represents a trade-off between the image information and the spatial smoothness constraint.

   Table2. Comparison between the proposed algorithm with other FCM algorithms

   size. The test images are generated by adding zero- mean Gaussian noise with different STD to the synthetic image. Comparison between the proposed algorithm with other FCM algorithms based on number of iterations as shown in Fig 3 and also based on time required for segmentation as shown in Fig 4. It reveals that the accuracy of the algorithm decreases with the increase of the level of noise for all size of image patches.

   FCM KFCM MKFCM MAFCM

   40

   35

   No. of iterations

   30

   25

   20

   15

   10

   5

   0

   0 50 100 150 200 250

   Cluster value

   Fig. 3 Comparison based on number of iterations

   50

   FCM

   40 KFCM

   Time consumption

   MKFCM

   30 MAFCM

   20

   Algorithm	Final Cluster Centre Value	No. of Iterations	Time Consumption (sec)
   FCM	234.65	40	45
   KFCM	219.76	28	42
   MKFCM	225.94	25	30
   Proposed	221.64	12	15

   10

   0

   0 5 10 15 20 25 30 35 40 45

   No. of Iterations

   Fig. 4 Time consumption of various schemes based on number of iterations

   Table 2 shows the segmentation accuracy of the MAFCM algorithm with image patches of different

   Generally, incorporating of spatial information into the segmentation process will dramatically increase the algorithms computational complexity. To compare the computational complexity of the FCM,

   KFCM, MKFCM and our MAFCM algorithms, we applied each of these four segmentation algorithms to the 512 × 512 Lena image. Each segmentation was performed 20 times, and the computational complexity of each algorithm was measured in terms of the average iteration number and average running time.

5. Conclusion

A modified adaptive fuzzy c-means clustering algorithm is presented for fuzzy segmentation of MR images that have been corrupted by intensity inhomogeneities and noise. We propose an adaptive method to compute the weights for the neighbourhood of each pixel in the image. The proposed adaptive method can not only overcome the effect of the noise effectively, but also prevent the edge from blurring. To address intensity inhomogeneity, the proposed algorithm introduces the global intensity into the algorithm and combines the local and global intensity information into account to ensure the smoothness of the derived optimal bias field and improve the accuracy of the segmentations. The proposed model can segment a brain MR mage in 9-10 iterations within 20 seconds. With good initialization, the model may need less iteration and can obtain results in less time. A variety of images, including synthetic images, synthetic brain MR images and real brain MR images are used to compare the performance of the proposed algorithm.

References

.[2] Sikka K, Sinha N, Singh PK, Mishra AK, A fully automated algorithm under modified FCM framework for improved brain MR image segmentation, Magnetic Resonance Imaging 2009;27(7):9941004.

1. Awate S, Tasdizen T, Foster N, Whitaker R, Adaptive Markov modeling for mutual-information-based, unsupervised MRI brain-tissue classification, Medical Image Analysis 2007;10(5):72639.

2. Wong W, Chung A, Bayesian image segmentation using local isointensity structural orientation, IEEE Transactions on Image Processing 2005; 14(10):151223.

3. L.A. Zadeh, Fuzzy sets, Information and Control 8 (1965) 338435.

4. J.C. Dunn, A fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster, Journal of Cybemet 3 (1974) 3257.

5. J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, USA, 1981.

6. J.C. Bezdek, L.O. Hall, L.P. Clarke, Review of MR image segmentation techniques using pattern recognition, Medical Physics 20 (4) (1993) 10331048.

7. Xing, Y., Ou, Y., Englander, S., Schnall, M., & Shen, D. (2007). Simultaneous estimation and segmentation of T1 map for breast parenchyma measurement, In Fourth IEEE international symposium on biomedical imaging (pp. 332 335).

8. Clark, M. C., Hall, L. O., Goldgof, D. B., Velthuizen, R., Murtagh, F. R., & Silbiger, M. S.(1998),Automatic tumor segmentation using knowledge-based techniques, IEEE Transactions on Medical Imaging, 117, 187201.

9. Krishnapuram R, Keller JM,The possibilistic c-means algorithm: insights and recommendations, IEEE Transactions on Fuzzy Systems 1996; 4(3):38395.

10. Dunn JC, A fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster, Journal of Cybernet 1974; 3(3):3257.

11. Bezdek JC,Pattern recognition with fuzzy objective function algorithms, Norwell,MA, USA: Kluwer Academic Publishers; 1981.

12. Bezdek JC, Hall LO, Clarke LP, Review of MR image segmentation techniques using pattern recognition, Journal of Cybernet 1999; 20(4):103348.

13. Chen, W., Giger, M. L., & Bick, U. (2006), A fuzzy c- means (FCM)-based approach for computerized segmentation of breast lesions in dynamic contrast-enhanced MR Images,. Academic Radiolory, 13(1), 6372.

14. Ketsetzis, G., & Brady, M. (2004), Automatic segmentation of T1 parametric maps of breast MR images via a hidden Markov random field, In Proceedings of medical image understanding and analysis.

15. K.S. Chuang, H.L. Tzeng, S.W. Chen, J. Wu, T.J. Chen, Fuzzy c-means clustering with spatial information for image segmentation, Computerized Medical Imaging and Graphics 30 (1) (2006) 915.

16. Pal NR, Pal K, Keller JM, Bezdek JC,A possibilistic fuzzy c-means clustering algorithm, IEEE Transactions on Fuzzy Systems 2005;13(4):51730.