Archives of Medicine

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

References

1. Miller BL, Boeve BF (2016) The behavioral neurology of dementia. Cambridge University Press.
2. Bouzin C, Saini ML, Khaing KK, Ambroise J, Marbaix E, et al. (2016) Digital pathology: Elementary, rapid and reliable automated image analysis. Histopathol 68: 888-896.
3. Orrison WW, Lewine J, Sanders J, Hartshorne M (2017) Functional brain imaging. Elsevier Health Sciences.
4. Asbury C (2011) Brain imaging technologies and their applications in neuroscience. The Dana Foundation: 1-45.
5. Elazab A, Wang C, Jia F, Wu J, Li G, et al. (2015) Segmentation of brain tissues from magnetic resonance images using adaptively regularized kernel-based fuzzy-means clustering. Comput Math Methods Med: 485495.
6. Bakas S, Akbari H, Sotiras A, Bilello M, Rozycki M, et al. (2017) Advancing the cancer genome atlas glioma MRI collections with expert segmentation labels and radiomic features. Scientific data 4: 170117.
7. Yazdani S, Yusof R, Riazi A, Karimian A (2014) Magnetic resonance image tissue classification using an automatic method. Diagn pathol 9: 207.
8. Pereira S, Pinto A, Alves V, Silva CA (2016) Brain tumor segmentation using convolutional neural networks in MRI images. IEEE Trans Med Imaging 35: 1240-1251.
9. Despotovic I, Goossens B, Philips W (2015) MRI segmentation of the human brain: challenges, methods, and applications. Comput Math Methods Med: 450341.
10. Chen X, Shrivastava A, Gupta A (2014) Enriching visual knowledge bases via object discovery and segmentation. Proc IEEE Comput Soc Conf Comput Vis Pattern Recognit : 2035-2042..
11. Ahirwar A (2013) Study of techniques used for medical image segmentation and computation of statistical test for region classification of brain MRI. Int J Information Tech Comp Sci 5: 44.
12. Haeck T, Maes F, Suetens P (2015) Automated model-based segmentation of brain tumors in MR images. Proc BraTS Challenge: 25-28.
13. Pereira S, Pinto A, Alves V (2016) Brain tumor segmentation using convolutional neural networks in mri images. IEEE Trans Med Imaging 35: 1240-1251.
14. Cao Y, Huang DQ, Shih G, Prince MR (2016) Signal change in the dentate nucleus on T1-weighted MR images after multiple administrations of gadopentetate dimeglumine versus gadobutrol. Am J Roentgenol 206: 414-419.
15. Kushibar K, Valverde S, Gonzalez-Villa S, Bernal J, Cabezas M, et al. (2017) Automated sub-cortical brain structure segmentation combining spatial and deep convolutional features. Computer Vision Pattern Recognition: 1-10.
16. Rabeh BA, Benzarti F, Amiri H (2017) Segmentation of brain MRI using active contour model. Int J Imaging Syst Technol 27: 3-11.
17. Banerjee S, Mitra S, Shankar BU (2018) Automated 3D segmentation of brain tumor using visual saliency. Information Sci 424: 337-353.
18. Thyreau B, Sato K, Fukuda H, Taki Y (2018) Segmentation of the hippocampus by transferring algorithmic knowledge for large cohort processing. Med Image Anal 43: 214-228.
19. Latha M,Surya R (2017) Brain tumour detection using neural network classifier and k-means clustering algorithm for classification and segmentation. Euro J Applied Sci 9: 66-71.
20. Hettiarachchi R, Peters J (2016) Voronoi region-based adaptive unsupervised color image segmentation. Computer Vision Pattern Recognition: 1-21.
21. Guo FF, Wang XX, Shen J (2016) Adaptive fuzzy c-means algorithm based on local noise detecting for image segmentation. IET Image Processing 10: 272-279.
22. Barrios JA, Villanueva C, Cavazos A, Colas R (2016) Fuzzy C-means Rule Generation for Fuzzy Entry Temperature Prediction in a Hot Strip Mill. J Iron Steel Res Int 23: 116-123.
23. Krishna PG, Bhaskari DL (2016) Fuzzy C-Means and Fuzzy TLBO for Fuzzy Clustering. Proc Second Int Conf Comp Comm Technol: 479-486.
24. Ghesmoune M, Lebbah M, Azzag H (2016) A new growing neural gas for clustering data streams. Neural Networks 78: 36-50.
25. Gharieb R, Gendy G, Selim H (2018) A Hard C-Means Clustering Algorithm Incorporating Membership KL Divergence and Local Data Information for Noisy Image Segmentation. Int J Pattern Recognit Artif Intell 32: 1850012.
26. Saha A, Das S (2017) Axiomatic generalization of the membership degree weighting function for fuzzy C means clustering: Theoretical development and convergence analysis. Information Sci 408: 129-145.
27. Arthur D, Vassilvitskii S (2007) K-means++: The advantages of careful seeding. Proc eighteenth annual ACM-SIAM symposium Discrete algorithm: 1027-1035.
28. Zhang X, Wang G, Su Q, Guo Q, Zhang C, et al. (2017) An improved fuzzy algorithm for image segmentation using peak detection, spatial information and reallocation. Soft Comput 21: 2165-2173.
29. Vishnuvarthanan G, Pallikonda Rajasekaran M, Vishnuvarthanan AN, Prasath AT, Kannan M (2017) Tumor detection in T1, T2, FLAIR and MPR brain images using a combination of optimization and fuzzy clustering improved by seedâ€Âbased region growing algorithm. Int J Imaging Syst Technol 27: 33-45.
30. Dalton L, Ballarin V, Brun M (2009) Clustering algorithms: On learning, validation, performance, and applications to genomics. Curr Genomics 10: 430-445.
31. Geweniger T, Fischer L, Kaden M, Lange M, Villmann T (2013) Clustering by fuzzy neural gas and evaluation of fuzzy clusters. Comput Intell Neurosci: 165248.
32. Grötschel M, Krumke SO, Rambau J (2013) Online optimization of large scale systems. Springer Science & Business Media.
33. Vergara JR, Estevez PA (2017) A strategy for time series prediction using Segment Growing Neural Gas. Self-Organizing Maps and Learning Vector Quantization, Clustering and Data Visualization (WSOM), 2017 12th International Workshop.
34. Liberty E, Sriharsha R, Sviridenko M (2016) An Algorithm for Online K-Means Clustering. 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX): 81-89.
35. Zhi X, Fan JI (2015) A New Algorithm for Discriminative Clustering and Its Maximum Entropy Extension. Intelligence Science Big Data Eng: 422-432.
36. Rajchl M, Baxter JS, McLeod AJ, Yuan J, Qiu W, et al. (2016) Hierarchical max-flow segmentation framework for multi-atlas segmentation with Kohonen self-organizing map based Gaussian mixture modeling. Med Image Anal 27: 45-56.
37. Du KL (2010) Clustering: A neural network approach. Neural Networks 23: 89-107.
38. Sun J, Xu B, Freelandâ€ÂGraves J (2016) Automated quantification of abdominal adiposity by magnetic resonance imaging. Am J Hum Biol 28: 757-766.
39. Ugarte V, Sinha U, Malis V, Csapo R, Sinha S (2016) 3D multimodal spatial fuzzy segmentation of intramuscular connective and adipose tissue from ultrashort TE MR images of calf muscle. Magn Reson Med 77: 870-883.
40. Chauhan AS, Pawar M (2016) A survey over various techniques used to cluster large scale data. International Res J Eng Technol 3: 981-984.
41. Zhou N, Yang T, Zhang S (2014) An improved FCM medical image segmentation algorithm based on MMTD. Comput Math Methods Med: 690349.
42. Tuan TM, Son HL (2017) Dental segmentation from X-ray images using semi-supervised fuzzy clustering with spatial constraints. Eng Appl Artif Intel 59: 186-195.
43. Xue LY, Lin JW, Cao RX, Yu (2017) Retinal blood vessel segmentation using saliency detection model and region optimization. J Algorithms Computation 12: 3-12.