Research Article - (2018) Volume 10, Issue 3
Siyah Mansoory M1, Allahverdy A2, Behboudi M3 and Refahi S4*
1Department of Biomedical Engineering, School of Medicine, Kermanshah University of Medical Sciences, Kermanshah, Iran
2 Department of Radiology, Mazandaran University of Medical Sciences, Sari, Mazandaran, Iran
3 Department of Statistics, Science and Research Branch, Islamic Azad University, Tehran, Iran
4 Department of Medical Physics, Faculty of Medicine, Ardabil University of Medical Sciences, Ardabil, Iran
Corresponding Author:
Soheila Refahi
Department of Medical Physics
Faculty of Medicine, Ardabil University of Medical Sciences, Ardabil, Iran.
Tel: +98-9144142689
E-mail: s.refahi@arums.ac.ir
Received date: April 25, 2018; Accepted date: April 28, 2018; Published date: May 04, 2018
Citation: Mansoory MS, Allahverdy A, Behboudi M, Refahi S (2018) Performance Evaluation of MRI Tumor Segmentation Using Clustering Algorithms. Arch Med. Vol.10 No.3:11 doi: 10.21767/1989-5216.1000271
Background: Magnetic resonance imaging (MRI) segmentation assumes great importance in research and clinical applications. The brain segmentation using MRI is challenging due to a significant amount of noise caused by operator performance, scanner, and the environment, which can lead to serious inaccuracies with segmentation. Evaluations of segmentation results in medical imaging are caused by the absence of a gold standard. So, the performance evaluation of these methods would be necessary.
Methods: In this paper, the performance of clustering algorithms such as Fuzzy C-Means (FCM), Hard C-Means (HCM), and Neural Gas (NG) for tumor detection is evaluated on 100 downloaded images. For this purpose, we evaluated these 3 algorithms under noise condition, convergence speed. Compared with manual segmentation by an expert radiologist, sensitivity, specificity, and accuracy are calculated for each segmentation methods.
Results: It can be stated, based on the results, that among the HCM and NG algorithms, the highest degree of accuracy and robustness to noise belongs to FCM. Moreover, optimum convergence rate and iteration need to gain final result using FCM algorithm.
Conclusion: All the quantitative performance analysis and visual comparisons clearly demonstrated the superiority of FCM algorithm for MRI-based tumor detection.
Keywords
Fuzzy C-means; Hard C-means; Neural Gas; Tumor Segmentation
Introduction
Brain imaging is playing an intensifying role in neuroscience and experimental medicine [1]. The quantity of data created by imaging increasingly surpasses the capacity for expert visual analysis, resulting in an increasing need for automated image analysis [2].
Magnetic resonance imaging (MRI) is an advanced, regularly used medical imaging technique [3]. It can quantitatively offer rich information about human anatomy in two or three dimensions in a noninvasive way [4]. Brain tissue segmentation of magnetic resonance (MR) images means to postulate the tissue type for each pixel in a 2D data set, respectively, on the origin of information available from both MR images and the prior knowledge of the brain [5]. Segmentation is an important preprocessing step in many medical researches and clinical claims, including quantification of tissue volume, and visualization and analysis of anatomical structures [6]. Unfortunately, intensity inhomogeneity in MR images, which can alter the absolute intensity for a specified tissue class in different positions, is a main problem to any automatic methods for MR image segmentation and make it challenging to obtain accurate segmentation results [7,8].
The separation of image pixels into non-overlapping, consistent regions which, in regard to some conditions related to gray level texture and/or intensity, appear to have homogeneity is referred to as image segmentation [9].
Most segmentation approaches contain a model which is derived from knowledge about the problem, from sample images and from information about the segments to be extracted [10]. The current segmentation methods in the field of medical image processing use several models to describe segments [11]. It may contain knowledge about models from the image formation process, of topological and of geometric theories [11]. It is the goal of the assessment process to study whether the model information is appropriate and sufficient for the description of the reality [12].
The brain segmentation using MR images is challenging [13]. The primary methods have majorly concentrated on the brain MR images segmented into grey matter (GM), white matter (WM), and cerebral-spinal fluid (CSF). The purpose is that these tissue classes can be recognized based on their characteristic signal intensity in weighted (T1 or T2) MR images [14]. The segmentation of subcortical structures (thalamus, caudate, putamen, etc.) is naturally more challenging since the signal intensity solely is not satisfactory to discriminate between different subcortical grey matter structures [15]. However, subcortical structures have typical shapes and spatial relations with each other. Thus segmentation algorithms for these structures usually integrate a priori information about their probable location and shape [16]. Manual and semi-automatic segmentations of these structures developed explicitly for neuroanatomical segmentation [17], in which the user specifies two coordinates for the segmentation of the caudate, and which needs a bounding box and the position of two seeds for the segmentation of the hippocampus and amygdale [18].
Studies have specified on supervised and unsupervised pattern recognition methods MRI brain segmentation [19]. Many segmentation techniques have been established on regionbased segmentation using feature vector clustering [20] and the adaptive c-means clustering algorithm [21]. Although these studies have revealed that some results are in visual agreement with an expert’s judgment, a number of factors may decrease the possibility classifiers.
In particular, precise and reliable methods for segmentation (categorizing image regions) are key conditions for the extraction of qualitative or quantitative information from images.
In this paper, we try to evaluate the performance of clustering algorithms such as Fuzzy C-Means [22], Hard C-Means [23], and Neural Gas [24] for tumor detection. For this purpose, we used three steps. First, we evaluated these three algorithms under noise condition. Then we compared the results of tumor segmentation with region-growing algorithm, and finally compared them manually with the results of segmentation.
Methods
All the downloaded images were given to an expert radiologist.
Manual segmentation of images, based on radiologist comments, is considered as a gold standard of this study.
The images were given to 2016 MATLAB software, and to evaluate the segmentation algorithms, the images were segmented using Hard C-means, Fuzzy C-means, Neural Gas algorithms.
The Algorithm of Hard C-means
Often referred to as k-means clustering or Lloyd algorithm, hard c-means clustering [23] problem optimizes the cost function below:
(1)
In this function, if the symbol for the cluster having the prototype vi is xk and hik=0, then hik=1, while ||.||A represents the generalized norm defined as follows:
(2)
In the above equation, A symbolizes a positive definite square matrix. Defined as the following equation, each vector xk is allocated to closely one cluster at a time.
(3)
To evade the trivial minimum of the cost function JHCM, obtained when all hik values are determined to be zero, this limitation is
Applying the next alternating optimization (AO) scheme, the optimization of this cost function will be obtained: necessary.
1. With input vectors that are selected randomly, and differ from one another, initialize vi, i = 1…c. When there is wellposed problem, this will be likely to be feasible.
2. For each feature vector xk and cluster prototype vi, ||xk-vi||A should be minimal. hik=1 and hik=0 are initialized for any j.
3. In accord with the following formula, update the cluster prototypes:
(4)
To put it differently, set each cluster prototype equal to the mean of the vectors fitting to the cluster. On the ground that a cluster includes no elements, there may take place singularity in this formula, but, with appropriately selected initial prototypes, this is barely feasible [25,26].
1. Up to the time cluster prototypes converge, repeat the phases 2 and 3.
From the zero crossing of the derivative of JHCM with regard to vi, equation (4) is gained
The Algorithm of Fuzzy C-means
The following objective function is minimized by FCM [21,22] clustering:
(5)
In which the so-called fuzzyfication parameter is denoted by m, and the contrast (distance) between vector xk and cluster prototype vi is represented by dik. The behavior of the parameter is affected by the fuzzyfication exponent. To set m>1 is the sufficient condition for the convergence. The execution of the algorithm, as seen in the followings, is the easiest for m=2. That is why it is the most popular value applied in the literature.
Through alternate optimization of uik with vi fixed, and vi with uik fixed up to the extent cluster prototypes are stabilized, the objective function minimization (5) is acquired.
Some first order essential conditions of the optimum can be gotten from the zero crossings of the cost function’s partial derivatives with regard to uik and vi since the cost function is quadratic and each term has non-negative coefficient. Differentiating JFCM with regard to uik and equating it to zero leads to the trivial solution uik=0 for any i=1...c and k=1...n, which is improper as it provides no partitioning and contradicts the probability restriction. Such kinds of problems are described applying Lagrange multipliers. Instead of differentiating JFCM, we deliberate the following function:
(6)
in which the second term is clearly zero. Differentiating LFCM with regard to uik leads to the zero crossing condition muik m-1 d ik2=λk . Regarding the probability constraint λk ,λk can be excluded and the solution can be attained:
(7)
from the zero crossing condition of the partial derivative of LFCM or LFCM regarding vi, we can obtain the updated formula for the cluster prototypes; differentiating gives which results in:
(8)
Therefore, the cluster prototypes, in each iteration, are computed as weighted averages of the input feature vectors, where the the mth power of the equivalent degrees of memberships provides the weights.
A summary of the AO solution to the FCM problem is provided in the followings [26]:
1. Determine cluster prototypes with values different from one another. Not necessarily needed, more intuitive initialization is suggested [27].
2. Through equation (7), make the degrees of membership updated.
3. Through equation (8), make cluster prototypes updated.
4. Up to the time cluster prototypes are stabilized, repeat phases 2 and 3. It can be checked through comparing the sum of cycle-to-cycle norms of the variations of cluster prototype vectors with a pre-determined constant.
The Algorithm of Neural Gas
Given that {x (t)}, t =1, 2…l, are n-dimensional stochastic input data, the mean vector e and the covariance matrix of x(t) are defined through the followings:
(9)
(10)
The followings can define a traditional training algorithm of neural gas with Euclidean distance measure:
1. Determine the network of neural gas. From the user, then, obtain the following inputs:
• The number of previously determined neurons (clusters), in particular, the number of Clusters c.
• Randomly initialize weight vectors in the input space, W=[w1, w2… wc].
Primary learning ratio and final learning ratio e.g.,
The total number of training set N, and the maximum training epoch Ep with
The maximum number of iterations tmax=MN, set and final falling off
1. At time instant t in mth training epoch, set a sequential vector x(t). The whole training iteration phase is as follows:
(11)
1. Calculate the distance (e.g., Euclidean distance) between x(t) and wi as:
(12)
1. Calculate the neighborhood ranking ri (initial ri=0, i=1, 2, …, c) as follows, in which i=1, 2, …, numClusters and j = i, …, numClusters:
(13)
Associated with each wi, the number ri means the order that is gained as a result of the above sorting process.
1. Make the weight vectors wi updated as
(14)
The neighborhood function is:
(15)
In the above function, the decay constant η (t) and rate of learning η (t) are regarded as follows,
(16)
(17)
2. Rise t to t+1, and up to the time t=tmax, repeat the phases 2 to 6.
3. Applying the following criteria, label the input x(t) in the latest training epoch as one of the stabilized clusters consistent.
(18)
It should be noticed that, in a Euclidean sense, the Best-Matching- Unit (BMU) in the reasonable process is the winning neuron Cj with minimum neighborhood ranking r.
Results
In order to show the performance of our approach in terms of convergence speed, accuracy, and robustness against noise, our algorithm, in this part, was used for human brain MR data sets. In order for the comparison, we implemented the three algorithms FCM, HCM, and NG without incorporating any prior information about the number of clusters.
The experiment here is in accord with the 1 mm isotropic resolution datasets accessible on BrainWeb. These sets of data are MRI acquisition precise simulations with various levels of noise-intensity inhomogeneity. In addition, applied for the quantification of the performance of different classification algorithms, there exists a ground truth volume. 15 varied MRI volumes with noise levels ranging from 0% to 9%, and intensity homogeneity of 0% to 40% were applied in our experiments in order for the prior information about each class center to be obtained. Figure 1 shows the results of segmentation applying FCM, HCM, and NG.
Figure 1: The results of segmentation: (a) main image; (b) cluster 1 using FCM; (c) cluster 2 using FCM; (d) cluster 3 using FCM; (e) cluster 1 using NG; (f) cluster 2 using NG; (g) cluster 3 using NG; (h) cluster 1 using HCM; (i) cluster 2 using HCM; (j) cluster 3 using HCM.
In the first evaluation step, the distance function versus iteration was plotted. As it can be seen, this plot for FCM algorithm started at the lower value and with less iteration it will be converged. Following Figures 2-4 show the results.
Figure 2: Distance function vs. iteration for FCM.
Figure 3: Distance function vs. iteration for HCM.
Figure 4: Distance function vs.iteration for NG.
In the second step, we added noise to the main image, added noise had zero mean and the variances were changed between 0.001 to 0.01. To evaluate adding noise to image, we implemented the algorithm of Improved fuzzy c-means clustering (IFCM) [28]. IFCM has a good robustness to changing noise level until a threshold. The result of using this algorithm in a sample image is shown in the following Figures 5-7.
Figure 5: A sample noisy image.
Figure 6: The result of segmentation using FCM.
Figure 7: The result of segmentation using IFCM.
To evaluate the clustering algorithm in the presence of noise, we plotted the noise variance versus error. Error is the misclassified pixel in comparison to IFCM. The result is displayed in Figure 8.
Figure 8: Segmentation error of entire image for different algorithms in different noise levels.a
Evaluations of segmentation results in medical imaging are caused by the absence of a gold standard. Therefore, we can compute no absolute segmentation error with this method, but we have an opinion to what extent the result agrees with the manual segmentation [29].
All classification result could have an error rate and on occurrence will either fail to identify an abnormality, or identify an abnormality which does not exist. It is common to define this error rate by the terms “true and false positive” and “true and false negative”. These terms are used to measure the performance of the segmentation methods.
At the third level of the evaluation of the segmentation methods, we compared our result with manual segmentations verified by a radiologist to find sensitivity, specificity, and accuracy were calculated for each algorithm.
Sensitivity, specificity, and accuracy are calculated for segmentation. These terms are used to describe the clinical efficiency of segmentation methods in Figure 9.
Figure 9: Clinical efficiency of segmentation methods: (a) sensitivity; (b) precision; (c) specificity; (d) accuracy.
Discussion
Since the ground truth of segmentation for real MR images is not regularly obtainable, it is terrible to evaluate the segmentation performance quantitatively. This paper used three known clustering algorithms (Fuzzy C-Means, Hard C-Means, and Neural Gas) as the segmentation techniques for tumor detection in MRI images. Our purpose was to evaluate the performance of each of these algorithms to determine which one has the best performance in tumor detection.
According to reports, Hard clustering has a fast convergence and offers a partition of poor quality [30]. Followings are some reasons [31] why poor partition quality is offered:
• The fact that the convergence of prototypes is touched in a minimum of the cost function [32] cannot be made sure of. Once no change is there in the partitions within the most recent completed iteration, the algorithm terminates.
• The initialization of the cluster prototypes: In order to have at least one vector in any iteration, each cluster is comforted by the forenamed initialization technique. The primary vectors assigned to each clusters, however, are highly unlikely to have the ability to move to another cluster in any further iteration.
The neural gas, which encompasses a great number of advantages [33] such as a faster convergence to low distortion errors, then, lower distortion error than that resultant from k-means clustering [27,34], maximum-entropy clustering [35] and Kohonen's selforganizing map method [36], after that, following a stochastic gradient descent on an obvious energy surface, is a kind of soft single-layered competitive learning neural network. Regarding Euclidean data, which does not endure from the local minima problem like simple vector quantization or topological constraints like the self-organizing map [37], a very robust clustering method is established by Neural Gas (NG).
However, FCM is a clustering algorithm based on intensity, and non-robust to noisy images [38], it is a popular segmentation method for medical images [39]. A great number of proposed FCM-based algorithms have been created to compensate for this weakness. However, none of them are great [40]. Generally, to denote part of an image, one pixel is too small. It makes sense to come to the conclusion, supposing a pixel’s intensity completely differs from its juxtaposing pixels, that this pixel must be disturbed by noise. In the current paper, the performance of our approach is shown according to robustness against noise, convergence speed, and accuracy. From the results, it can be seen that the distance function versus iteration for FCM started at lower value and with less iteration it led to convergence. Second, we evaluated the behavior of these three algorithms when noise was added to the original images. In this state, the error rate for FCM showed that this algorithm is more robust to noise than others because, for changing noise variance, it had lower miss classified pixel. Finally, in comparison to manual segmentation done by a radiologist, sensitivity, specificity, and accuracy were calculated. For FCM algorithm and although in some situations, HCM and NG had good results, but FCM had the best result in all the circumstances which is in line with other studies [41-43].
Conclusion
The Evaluations of segmentation results in medical imaging are caused by the lack of a gold standard. Therefore, we cannot compute any absolute segmentation error.
In this paper, we evaluated the performance of some clustering algorithms which are used for tumor detection and segmentation in MRI images.
The capability of the clustering algorithms to detect tumor in MRI images and image segmentation without any prior information is the major contribution of the present paper.
It can be asserted, based on the results, the highest degree of accuracy and robustness among HCM and NG algorithms belongs to FCM. Moreover, it requires fewer numbers of iterations in order for the final result to be obtained and has the highest speed of convergence. Allowing semi-automatic tumor recognition in MRI, this result is regarded desirable for a computer system.
Acknowledgements
The authors thank the Department of Biomedical Engineering, School of Medicine, Kermanshah University of Medical Sciences, Kermanshah, Iran & Department of Medical Physics, Faculty of Medicine, Ardabil University of Medical Sciences, Ardabil, Iran.
Conflict of Interest
There is no conflict of interest to be declared.
Authors' Contributions
All of the authors contributed to this project and article equally. All the authors read and approved the final manuscript.
22531