Brain MRI Segmentation using Adaptive K-Means Clustering Algorithm

Brain MRI Segmentation using Adaptive K-Means Clustering Algorithm

G. Geethu Lakshmi, Assistant Professor,

Heera College Of Engineering and Technology, Trivandrum,

Kerala

Abstract A standard segmentation problem within Magnetic Resonance Imaging (MRI) is the task of labelling voxels according to their tissue type that are White Matter (WM), Gray Matter (GM), and Cerebrospinal fluid (CSF).Image segmentation provides volumetric quantification of cortical atrophy and thus helps in the diagnosis of degenerative diseases such as Epilepsy, Schizophrenia, Alzheimers disease, Dementia and Hydrocephalus.This work deals with comparison of segmentation results by applying K-Means algorithm after morphological skull stripping and also by using the Brain Extraction Tool(BET) for skull stripping. The results are compared using the parameters such as Mean Square Error(MSE), Peak Signal to Noise Ratio(PSNR) and percentage of area segmented.

Keywords Brain Segmentation, K-Means clustering, Brain Extraction tool, Morphological skull stripping

1. INTRODUCTION

   Image Segmentation is the area of image processing that has been identified as the key problem of medical image analysis and remains a popular and challenging area of research. The segmentation refers to the process of partitioning a digital image into multiple segments (sets of pixels, also known as super pixels).The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyse. Image segmentation is typically used to locate objects and boundaries (lines, curves.etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. In this paper two types of approach for segmentation is done and compared. Firstly a brain MRI is taken and its noises are removed using filters and also by using wavelet denoising and after that the skull is stripped using the morphological operations like erosion, dilation and then applied K-means Clustering algorithm. Then in the next approach of this paper comprises the skull stripping using Brain Extraction tool (BET) and applied K- Means Clustering Algorithm.

   Magnetic Resonance (MR) has become the main modality for brain imaging that facilitates safe, non-invasive assessment and monitoring of patients with neurodegenerative diseases such as Parkinsons disease, Alzheimers disease (AD), epilepsy, schizophrenia, and multiple sclerosis (MS). The ability to diagnose and characterize these diseases in vivo using MR image data

   promises exciting developments both toward understanding the underlying pathologies, as well as conducting clinical trials of drug treatments. One important biomarker that is often used to assess patients with neurodegenerative disease is brain tissue volume [9]. Segmenting subcortical structures from brain images is of significant practical importance, not only in atrophy quantification but also in detecting abnormal brain patterns [18], studying various brain diseases and studying brain growth [3].

   Previously, to measure various tissue volumes in MRI

   [16] head scans, manual CSF, WM and GM segmentations were often performed by skilled experts. Manual segmentation, however, is extremely time-consuming, mostly limited to 2-D slice-based segmentation, and prone to significant intra- and inter- variability. In particular, manual segmentation cannot be practically and efficiently performed in situations where precise measurements on a large number of scans are required, such as in clinical trials [2]. Therefore, a fully automatic, highly accurate, and robust tissue segmentation technique that provides systematic quantitative analysis of tissue volumes in brain MRI is an invaluable tool in many studies of neurodegenerative diseases. A wide variety of methods [19]have been proposed for automating the segmentation process [5] over the past decade that provided either semi- or fully automated frameworks for the segmentation of brain tissues [9].

   In the current scenario, there are strong demands to accomplish this task automatically by computer. However, several problems associated with the MRI images have to be addressed first, including noise [14]. In [3], a hybrid discriminative/generative model for brain subcortical structure segmentation is presented [3]. This method is not fully automatic because it involves few parameters that need manual specification. The main contribution of Huang et al., is employing an edge-based geodesic active contour [6] for the segmentation task by integrating both image edge geometry and voxel statistical homogeneity into a novel hybrid geometricstatistical feature to regularize contour convergence and extract complex anatomical structures [9]. The main contribution of the work in [14] is the combination of atlas registration, fuzzy connectedness (FC) segmentation, parametric bias field correction (PABIC) and Re-FC segmentation together to provide a fully automatic method

   [20] for brain MRI segmentation where each of the four steps provides improvements on the segmentation or on the MRI images.

   In [4][17], it is stated that segmentation [8] of MRI brain image [10] can be done using K-Means Clustering algorithm [13] [1][7] and also the skull stripping which is

   k

   k

   V

   i1

   xjSi

   (xj i)2

   (1)

   one of the step in Preprocessing[12] is done using BET tool as stated in [9] and also it is done using manual morphological operations as stated in [15].The comparative study based on the area segmented is stated in [13] and [15].The denoising technique and overall method for it is described [11].

2. METHOD

Before applying the K-Means Clustering algorithm for segmentation, firstly noises should be removed and also the skull should be stripped off.

1. Noise Removal

   Before the segmentation of brain MRI is done, the main step is to eliminate unwanted noises ,so for that we need to apply the Wavelet denoising method and need to apply the low pass Gaussian filter [6] for removing all unwanted noises. After this process all unwanted noise will get removed.

   1. Need for Noise Removal

      Since the brain MRI will be taken from different scanning machine, the chances of noises in those images will be more. So to avoid those noises is necessary, most of the time noise will be Gaussian. For the effective segmentation, Gaussian noise should be eliminated.

      Where there are k clusters Si, i = 1, 2…, k and is the centroid or mean point of all the points xj Si

      As a part of this project, an iterative version of the algorithm was implemented. The algorithm takes a 2 dimensional image as input. Various steps in the algorithm are as follows:

      Step 1. Compute the intensity distribution (also called the histogram) of the intensities.

      Step 2: Initialize the centroids with k random intensities

      Step 3. Repeat the following steps until the cluster labels of the image does not change anymore

      Step 4: Cluster the points based on distance of their intensities from the centroid intensities.

      c(i) : arg min x(i) j 2 ` (2)

      j

      Step 5. Compute the new centroid for each of the clusters.

2. Morphological Skull Stripping

   1C

   1. )

      jx(i )

      m

      m

      After the removal of noises morphological operations

      : i1

      (3)

      m

      m

      1 C

      1 C

      are applied on brain MRI to strip the skull apart. Fo that firstly convert the grey scale image to binary then image erosion is to be done and then find out the largest

      i

      i1

      1. ) j

   connected area. Then after that image dilation is done and then map to the grey scale, since the processing is done on grey scale. 2.

3. Skull stripped using Brain Extraction Tool

   The brain extraction tool is used to remove the skull from an image, leaving only the region occupied by actual brain tissue. It segments these by using the dark space between the skull and brain, occupied by the CSF. This tool comes from the external program FSL's toolkit. Thus, it will only appear if FSL is installed. (Such integration is easier on Unix systems at this point).The goal of the first brain extraction process is to remove most of the skull/throat/neck without loosing any brain tissue. This extraction will not be extremely accurate and may include more skull than desired in order to keep all of the brain tissue. The remainder of the skull can be removed in the second brain extraction using the same tool.

4. K-Means Clustering Algorithm

K-Means algorithm is an unsupervised clustering algorithm that classifies the input data points into multiple classes based on their inherent distance from each other. The algorithm assumes that the data features form a vector space and tries to find natural clustering in them. The points are clustered around centroids = 1 : : : k which are obtained by Minimizing the objective

Where k is a parameter of the algorithm (the number of clusters to be found), i iterates over the all the intensities, j iterates over all the centroids and are the centroid intensities.

As the algorithm is usually very fast, it is common to run it multiple times with different starting conditions. However, in the worst case, k-means can be very slow to converge: in particular it has been shown that there exist certain point sets, even in 2 dimensions, on which k-means takes exponential time that is 2 (n), to converge.

It is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data as well as in the iterative refinement approach employed by both algorithms. It is also referred to as Lloyd's algorithm. There is a modification to this algorithm which is K-Medoids.

1. EXPERIMENTS AND RESULTS

   The experimental results are specified in the following sections.

   1. Noise Removal

      The Figure 1 shows the noise removal for first brain MRI. In that Wavelet denoising and Gaussian filter is applied. The Figure 2 shows the noise removal for second brain MRI.

      Figure.1.Noise Removal of first brain MRI (a) Stretched original image.(b)Wavelet denoising. (c)Absolute difference (d) Deblurred image

      Figure.2.Noise Removal of Image 2 (a) Stretched original image.(b)Wavelet denoising. (c)Absolute difference (d) Deblurred image

   2. Morphological Skull Stripping

      The Figure 3 shows the Skull stripping for figure 1 after applying erosion and dilation. The Figure 4 shows the skull stripping for figure 2

      Figure.3.Skull Stripping for figure 1.(d). .(a)preprocessed original.(b)Binarized image.(c)Eroded image.(d)Object with maximum area (e)Dilated image.(f)Filled.(g)Skull stripped

      Figure.4.Skull Stripping for figure 2 (d) a)preprocessed original.(b)Binarized image.(c)Eroded image.(d)Object with maximum area (e)Dilated image.(f)Filled.(g)Skull stripped

   3. Skull stripped using Brain Extraction Tool

      The Figure 4 shows the stripping of skull using BET for image 1 and Figure 5 shows the stripping of image 2 using BET.

      Figure 5: Skull stripped using Brain Extraction Tool for figure 1.(d)

      Figure 6: Skull stripped using Brain Extraction Tool for figure 2.(d)

   4. Segmentation

   The Figure 6 shows the clustering of Brain MRI after using BET for skull stripping for image 1.The Figure 7 shows the clustering of the image using BET for skull stripping for image 2.The Figure 8 shows the clustering of MRI brain image after applying morphological skull

   stripping of Figure 1 (g) The Figure 9 shows the clustering of MRI brain image after applying morphological skull stripping. Figure 2 (g).

   Figure 7: Segmented image after Skull is stripped using BET for figure 5 (a)clustered CSF (CerebroSpinal Fluid) (b)Clustered Grey Matter(GM) (c) Clustered White Matter(WM)

   Figure 8: Segmented image after Skull is stripped using BET for figure 6.(a)clustered CSF (Cerebrospinal Fluid) (b)Clustered Grey Matter(GM)

   (c) Clustered White Matter(WM)

   Figure 9: Segmented image after Skull is stripped using morphological operations figure 1.(g) .(a)Original Image (b)Brain mask(c)clustered CSF (Cerebrospinal Fluid) (d)Clustered Grey Matter(GM) (e) Clustered White Matter(WM)

   Figure 10: Segmented image after Skull is stripped using morphological operations figure 2.(g) .(a)Original Image (b)Brain mask(c)clustered CSF (Cerebrospinal Fluid) (d)Clustered Grey Matter(GM)

   (e) Clustered White Matter(WM

2. PERFORMANCE EVALUATION

For the performance evaluation of segmentation three parameters are used here, Means Square Error (MSE), Peak Signal to Noise Ratio (PSNR) and percentage of area segmented.

A. Mean Square Error value

Mean Square Error Value (MSE) is a risk function, corresponding to the expected value of the squared error loss or quadratic loss. MSE measures the average of the square of the error. The error is the amount by which the estimator differs from the quantity to be estimated. The MSE is the cumulative squared error between the denoised image and the original image. This helps to find out how much error content is there in the image, if less then segmentation is almost right and the result should be accurate. But MSE value calculation should be accurate.

M

M

1

2

N

N

I (x, y) I '(x, y)

(4)

C. Area of segmentation

MN y1 x1

Where I(x,y) is the original image, I'(x,y) is the approximated version (which is actually the decompressed image) and M,N are the dimensions of the images. A lower value for MSE means lesser error

B. Peak Signal to Noise Ratio

Peak Signal to Noise Ratio (PSNR) is a ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation. Because many signals have a very wide dynamic range, PSNR is usually expressed in terms of the logarithmic decibel scale. PSNR is a measure of the peak error.

PSNR=10*log10 (512*512/MSE) (5)

Lower value for MSE means lesser error, and as seen from the inverse relation between the MSE and PSNR, this translates to a high value of PSNR. Logically, a higher value of PSNR is good because it means that the ratio of Signal to Noise is higher. Here, the 'signal' is the original image, and the 'noise' is the error in reconstruction.

The area used for segmentation of Brain MRI [25] is considered in such a way that the White matter should be greater than the Grey matter and cerebrospinal Fluid. The algorithm efficiency for segmentation is found out using the percentage of area segmented out of 512×512 array of brain MRI.This can be found out using the function in Matlab called bwarea(image).

White matter is one of the two components of the central nervous system and consists mostly of myelinated axons. Major portion of brain is always White matter when compared to Grey matter and cerebrospinal Fluid. Grey matter contains neural cell bodies, in contrast to white matter, which does not and mostly contains myelinated axon tracts. Cerebrospinal fluid (CSF) is a clear bodily fluid that occupies the subarachnoid space and the ventricular system around and inside the brain and spinal cord. The area covered is much lesser when compared to Grey Matter and White Matter. The results got ar plotted in chart and is evaluated and analysed using the tables.

TABLE I

PERFORMANCE EVALUATION USING K-MEANS CLUSTERING ALGORITHM

TABLE II

PERFORMANCE EVALUATION OF K-MEANS USING BRAIN EXTRACTION TOOL FOR SKULL STRIPPING

Comparative Analysis after applying K-Means Clustering Algorithm

Comparative Analysis after applying k-Means Clustering Algorithm using Brain extraction tool for skull stripping

100

80

60

40

20

0

Exp.1 Exp.2

MSE PSNR

Area Segmented(%)

100

80

60

40

20

0

Exp.1 Exp.2

MSE PSNR

Area Segmented(%)

Figure 10: Comparative analysis after applying k-Means Clustering Algorithm

Figure 11: Comparative analysis after applying Brain Extraction Tool for skull Stripping

In the first method K-Means Clustering Algorithm is applied after removing the noise and the skull stripping is done using the morphological operations. Here from this TABLE I, we can infer that, White matter is greater than grey

matter and cerebrospinal Fluid in two experiments. In the first experiment, almost 90% of the brain image got segmented in to white matter grey matter and cerebrospinal Fluid(CSF). But in the second experiment, almost 91.5% of the brain image got segmented.

In the second method K-Means Clustering algorithm is applied for segmentation, but the skull stripping is done using brain extraction tool. Here if refer to the TABLE II,it is evident that after using readymade tool the percentage of area segmented is high, which is almost 95%.

From this we can infer that the algorithm for segmenting MRI brain images is best if we use the K-Means Clustering Algorithm after applying Brain Extraction tool for Skull stripping.

III. CONCLUSION AND DISCUSSIONS

In this paper, we analysed the MRI DICOM brain images such as Axial, coronal, sagittal T1-weighted, T2- weighted, PD weighted. In this, we worked on image denoising techniques and morphological algorithms and connected component labelling to perform non brain portion removal. After that applied weighted k-means clustering technique and K-Means Clustering technique by applying skull stripping using manual method and also by using BET.

Thus calculated the area of regions of segmented tissues which is useful for the quantification of the data for the radiologists. According to the area, performance is evaluated and selected suitable clustering algorithm. Thus using this approach we found out that Weighted K-Means is the best algorithm. With a large number of variables, K-Means may be computationally faster than hierarchical clustering. But it does not work well with non-globular clusters. A study on various existing and published methods of segmenting the brain tissues of MRI and their performance evaluations are also carried out.

REFERENCES

1. Anil K. Jain, Data clustering: 50 years beyond K-means, Elsevier,

   Pattern Recognition Letters 31 (2010), pp.651-666, September 2009

2. Ahmed kharrat, Nacera Benamrane, Mohamed Ben Messaoud and Mohamed Abid,Detection of Brain Tumor in Medical Images, International Conference on Signals, Circuits and Systems,September 2009

3. Albert Huang and Rafeef Abugharbieh, Roger Tam,A Hybrid GeometricStatistical Deformable Model for Automated 3-D Segmentation in Brain MRI, IEEE Transactions on Biomedical Engineering, Vol. 56, No. 7, pp. 1838-1848, July 2009.

4. Bhagwati Charan Patel and Dr.G.R.Sinha ,AnAdaptiveK-means Clustering Algorithm for Breast Image Segmentation ,International Journal of Computer Applications, Number 4 – Article 7, pp.35- 38,November 2010

5. Dzung L.Pham, Chenyang Xu and Jerry L.Prince,Current methods in medical image segmentation, Annu.Rev.Biomed.Eng.2000

6. Gonzalez, Rafael C. & Woods, Richard E,Morphological Operations in Digital Image Processing, pp.519-560, Pearson Education.

7. Greg Hamerly and Charles Elkan,Learning the k in K-Means, University of California, San Diego.

8. Guellouma Younes, Cherroun Hadda and Ziadi Djelloul,Supervised learning and automatic recognition of asphalt pavement deteriorations, MASAUM Journal of Basic and Applied Sciences,

   Vol.1, No. 2, pp.254-259, September 2009

9. Guillermo N. Abras and Virginia L. Ballarin,A Weighted K-means Algorithm applied to Brain Tissue classification, JCS&T Vol. 5 No. 3,pp 121-126, October 2005.

10. Habib Zaidi, Torsten Rues ,Frederic Schoenahl, and Marie-Louise Montandon ,Comparative assessment of statistical brain MR image segmentation algorithms and their impact on partial volume correction in PET,Elsevier,NeuroImage 32(2006),pp.1591- 1607,May 2006

11. J.Jayal, K.Thanushkodi and M.Karnan, Tracking Algorithm for De- Noising of MR Brain Images,IJCSNS International Journal of Computer Science and Network Security, VOL.9 .No.11, pp.262-267,

    November 2009

12. Jean-Luc Starck, Emmanuel J. Candes, and David L. Donoho ,The Curvelet Transform for Image Denoising, IEEE transactions on Image Processing, Vol. 11, No. 6, pp.670-684, June 2002

13. Jose L.Marroquin and Federrico Girosi,Some Extensions of the K- Means Algorithm for Image segmentation and Pattern Classification, Massachusetts Institute of Technology Artificial Intelligence Laboratory, A.I. Memo No: 1390, C.B.C.I. Paper No. 079, pp.1-12, January 1993

14. Juan Ramon Jimenez-Alaniz, Veronica Medina-Banuelos, and and Oscar Yanez-Suarez,Data-Driven Brain MRI Segmentation Supported on Edge Confidence and A Priori Tissue Information,IEEE Transactions on medical imaging, VOL. 25, NO. 1, pp 74-83, January 2006.

15. Kavitha Nagarajan,Adaptive Clustering For Segmentation and Classification, Texas Tech University, May 2000

16. M. Stella Atkins and Blair T. Mackiewich, Fully Automatic Segmentation of the Brain in MRI, IEEE transactions on Medical Imaging, Vol. 17, No. 1, pp.98-107, February 1998

17. Max Mignotte,Segmentation by Fusion of Histogram-Based K- Means Clusters in Different Color Spaces, IEEE transactions on image processing, Vol. 17, No. 5, pp.780-787, May 2008

18. Nandita Pradhan1 and A.K. Sinha, Development of a composite feature vector for the detection of pathological and healthy tissues in FLAIR MR images of brain, ICGST-BIME Journal,Vol. 10, Issue 1,pp.261-265, December 2010

19. Nassir Salman,Image Segmentation Based on Watershed and Edge Detection Techniques,The International Arab Journal of Information Technology, Vol. 3, No. 2,pp.104-110, April 2006.

20. Nesrine Chehata,Nicolas David,Federic Breatr,Lidar Data Classification using Hierarchical K-Means Clustering, The International Archives of the Photogrammetry,Remote Sensing and spatial Information Sciences,vol.XXXVII,Part B3b,Beijing 2008.