Brain Tumor Segmentation Using Graph Coloring Approach in Magnetic Resonance Images

Rouholla Bagheri, Jalal Haghighat Monfared, Mohammad Reza Montazeriyoun

DOI: 10.4103/jmss.JMSS_43_20


It is important to have an accurate and reliable brain tumor segmentation for cancer diagnosis and treatment planning. There are few unsupervised approaches for brain tumor segmentation. In this paper, a new unsupervised approach based on graph coloring for brain tumor segmentation is introduced. In this study, a graph coloring approach is used for brain tumor segmentation. For this aim, each pixel of brain image assumed as a node of graph and difference between brightness of a couple of pixels considered as edge. This method was applied on T1-enhanced magnetic resonance images of low-grade and high-grade patients. Since a rigid graph was needed for graph coloring, edges must be divided into existing or nonexisting edge using a threshold. The value of this threshold has affected the accuracy of image segmentation, so the choice of the optimal threshold was important. The optimal value for this threshold was 0.42 of maximum value of difference of brightness between pixels that caused the 83.62% of correlation accuracy. The results showed that graph coloring approach can be a reliable unsupervised approach for brain tumor segmentation. This approach, as an unsupervised approach, shows better accuracy in comparison with neural networks and neuro-fuzzy networks. However, as a limitation, the accuracy of this approach is dependent on the threshold of edges.


Brain tumor, graph coloring, magnetic resonance imaging, segmentation

Full Text:



Bauer S, Wiest R, Nolte LP, Reyes M. A survey of MRI-based medical image analysis for brain tumor studies. Phys Med Biol 2013;58:R97-129.

Zhao X, Wu Y, Song G, Li Z, Zhang Y, Fan Y. A deep learning model integrating FCNNs and CRFs for brain tumor segmentation. Med Image Anal 2018;43:98-111.

Goetz M, Weber C, Binczyk F, Polanska J, Tarnawski R, Bobek-Billewicz B, et al. DALSA: Domain adaptation for supervised learning from sparsely annotated MR images. IEEE Trans Med Imaging 2016;35:184-96.

Goetz M, Weber C, Bloecher J, Stieltjes B, Meinzer HP, Maier-Hein K. Extremely randomized trees based brain tumor segmentation. Proceeding of BRATS challenge-MICCAI. 2014 Sep 14:006-11.

Allahverdi A, Akbarzadeh S, Moghaddam AK, Allahverdy A. Differentiating Tumor and Edema in Brain Magnetic Resonance Images Using a Convolutional Neural Network. Front Biomed Technol 2018;5:44-50.

Kapur T, Eric W, Grimson L, Kikinis R, Wells WM. Enhanced spatial priors for segmentation of magnetic resonance imagery. InInternational Conference on Medical Image Computing and Computer-Assisted Intervention. Springer, Berlin, Heidelberg. 1998. p. 457-468.

Bullmore E, Brammer M, Rouleau G, Everitt B, Simmons A, Sharma T, et al. Computerized brain tissue classification of magnetic resonance images: A new approach to the problem of partial volume artifact. Neuroimage 1995;2:133-47.

Atlason HE, Love A, Sigurdsson S, Gudnason V, Ellingsen LM. SegAE: Unsupervised white matter lesion segmentation from brain MRIs using a CNN autoencoder. Neuroimage Clin 2019;24:102085.

Juan-Albarracín J, Fuster-Garcia E, Manjón JV, Robles M, Aparici F, Martí-Bonmatí L, et al. Automated glioblastoma segmentation based on a multiparametric structured unsupervised classification. PLoS One 2015;10:e0125143.

Thakur GK, Priya B, Pawan Kumar S. A novel fuzzy graph theory-based approach for image representation and segmentation via graph coloring. J Appl Secur Res 2019;14:74-87.

Gómez D, Montero J, Yáñez J, Poidomani C. A graph coloring approach for image segmentation. Omega 2007;35:173-83.

Yáñez J, Muñoz S, Montero J. Graph coloring inconsistencies in image segmentation. In Computational Intelligence In Decision And Control 2008. p. 435-40.

Makrogiannis S, Economou G, Fotopoulos S, Bourbakis NG. Segmentation of color images using multiscale clustering and graph theoretic region synthesis. IEEE Trans Syst Man Cybern A Syst Hum 2005;35:224-38.

Yuan X, Guo J, Hao X, Chen H. Traffic sign detection via graph-based ranking and segmentation algorithms. IEEE Trans Syst Man Cybern Syst 2015;45:1509-21.

Chang H, Chen Z, Huang Q, Shi J, Li X. Graph-based learning for segmentation of 3D ultrasound images. Neurocomputing. 2015;151:632-44.

Chen X, Pan L. A survey of graph cuts/graph search based medical image segmentation. IEEE Rev Biomed Eng 2018;11:112-24.

Menze BH, Jakab A, Bauer S, Kalpathy-Cramer J, Farahani K, Kirby J, et al. The multimodal brain tumor image segmentation benchmark (BRATS). IEEE Trans Med Imaging 2015;34:1993-2024.

Mehta RC, Pike GB, Haros SP, Enzmann DR. Central nervous system tumor, infection, and infarction: Detection with gadolinium-enhanced magnetization transfer MR imaging. Radiology 1995;195:41-6.

Farjam R, Parmar HA, Noll DC, Tsien CI, Cao Y. An approach for computer-aided detection of brain metastases in post-Gd T1-W MRI. Magn Reson Imaging 2012;30:824-36.


  • There are currently no refbacks.