 Open Access
 Total Downloads : 3046
 Authors : M. Ganesh, V. Palanisamy
 Paper ID : IJERTV1IS8668
 Volume & Issue : Volume 01, Issue 08 (October 2012)
 Published (First Online): 29102012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A Modified Adaptive Fuzzy CMeans Clustering Algorithm For Brain MR Image Segmentation
M. Ganesh, V. Palanisamy
Electronics and Communication Engineering, Info Institute of Engineering, Coimbatore, Tamilnadu, India.
Abstract
Fuzzy cmeans (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 cmeans 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.

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 multispectral characteristics. Therefore, it has been widely used in quantitative brain imaging studies. Quantitative volumetric measurement and threedimensional (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 realworld images from different modalities [3, 4]. In particular, it is often seen in medical images, such as Xray radiography/ tomography and MR images. For example, the intensity variation across the image, which arises from radiofrequency (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

method desirable. The automated segmentation

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 cmeans 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 cmeans [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 cmeans 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 cmeans 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 cmeans; 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 multisequences 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 semiautomatic or fullyautomatic 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 multispectral 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 cmeans (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 subspaces 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.


Related Work

Conventional FCM clustering algorithm
Multiresolution segmentation is a bottom up region merging technique starting with onepixel
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, multiresolution 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 nonsupervised. 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 imagesegmentation
2.2. Kernel FCM (KFCM)
When applying the KFCM framework in imagesegmentation 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 imagesegmentation 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 multiplekernel 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 Gaussiankernelbased
k wbk

wbk

wbk
(10)
KFCMF 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 MKFCMKbased 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 userdefined 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 MKFCMbased imagesegmentation 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 imagesegmentation algorithms are inherently
better than other KFCMbased 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 twotexture imagesegmentation
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.



Proposed Algorithm
The FCM clustering algorithm was first proposed by Dunn et. al. [12] and promoted as the general fuzzy cmeans 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 subspaces 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.

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 FCMtype 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 tradeoff 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.

Conclusion
A modified adaptive fuzzy cmeans 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 910 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
[1] Ho BC. MRI brain volume abnormalities in young, nonpsychotic relatives of schizophrenia probands are associated with subsequent prodromal symptoms, Schizophrenia Research 2007; 96(1):113.[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.

Awate S, Tasdizen T, Foster N, Whitaker R, Adaptive Markov modeling for mutualinformationbased, unsupervised MRI braintissue classification, Medical Image Analysis 2007;10(5):72639.

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

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

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.

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

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

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).

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

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

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.

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

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

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

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.

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

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