• Users Online: 111
  • Print this page
  • Email this page

 Table of Contents  
Year : 2021  |  Volume : 11  |  Issue : 4  |  Page : 285-290

Brain tumor segmentation using graph coloring approach in magnetic resonance images

1 Department of Management, Ferdowsi University of Mashhad, Iran
2 Department of Management, Central Tehran Branch, Islamic Azad University, Tehran, Iran

Date of Submission29-Jun-2020
Date of Decision23-Sep-2020
Date of Acceptance18-Apr-2021
Date of Web Publication20-Oct-2021

Correspondence Address:
Rouholla Bagheri
Department of Management, Ferdowsi University of Mashhad
Login to access the Email id

Source of Support: None, Conflict of Interest: None

DOI: 10.4103/jmss.JMSS_43_20

Rights and Permissions

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.

Keywords: Brain tumor, graph coloring, magnetic resonance imaging, segmentation

How to cite this article:
Bagheri R, Monfared JH, Montazeriyoun MR. Brain tumor segmentation using graph coloring approach in magnetic resonance images. J Med Signals Sens 2021;11:285-90

How to cite this URL:
Bagheri R, Monfared JH, Montazeriyoun MR. Brain tumor segmentation using graph coloring approach in magnetic resonance images. J Med Signals Sens [serial online] 2021 [cited 2022 May 24];11:285-90. Available from: https://www.jmssjournal.net/text.asp?2021/11/4/285/328733

  Introduction Top

Accurate segmentation of brain tumors is important in diagnosing cancer, planning treatment, and evaluating the outcome of treatment. Because manual division of brain tumors is difficult,[1] a lot of effort has been devoted to developing methods for dividing semi-automatic or automatic brain tumors. Most studies of segmentation of brain tumors focus on glioma, which is the most common brain tumor in adults and can be processed using magnetic resonance imaging (MRI) imaging with different sequences.[2] The segmentation of glioma using MRI data may be challenging for the following reasons: first, glioma may look similar to gliosis and stroke in MRI data.[3] Second, glioma may appear in any position of the brain with a variety of shapes, appearances, and sizes. Third, instead of replacing them, the glioma attacks the surrounding brain tissue, creating fuzzy boundaries,[4] and fourth, MRI data inconsistency exacerbates this problem. Automatic segmentation of glioma may be a useful tool for reducing tumor localization errors. In heterogeneous tumors, such as glioma, this distinction cannot be made with routine MRI techniques.[5] There are many approaches to tissue segmentation in MRI like region-based and contour-based approaches.[6],[7] There are two major approaches for brain tumor segmentation with MRI, consisting of supervised and unsupervised approaches. Supervised segmentation approaches need manually labeled images which may be hard to achieve, but unsupervised approaches do not need these manual labels. However, as a limitation, using these approaches may be challenging via variation of pixel brightness and localization of tumor lesion.[8] Another limitation of these approaches is their low accuracy in comparison with supervised approaches.[9]

Graph coloring performs as accuracy better in automatically segmenting images based on the region-based approach among various techniques of unsupervised image segmentation, which means the better accuracy and sensitivity of the localization the tumor.[10],[11],[12] Graph theory approaches play an important role in image segmentation, in which various graphical algorithms are used to solve many problems by different graph coloring techniques.[13] In graph-based algorithms, an image can be displayed as a graphic in which each pixel is considered as a node, and these algorithms describe the result between the graph nodes and the range of colors to divide the pixels.[14] Graph's theoretical approach organizes the elements of the image into efficient mathematical structures, which makes the formulation of the problem more flexible and the resources more computational.[15] Recently, there is growing interest in using graph theory in medical image segmentation.[16]

In this study, we will introduce a novel graph coloring method that uses the combination of unsupervised features of image segmentation as graph coloring and supervised feature as a threshold to develop the accuracy of segmentation for glioma segmentation in T1-enhanced MRI and investigate the performance of this approach for glioma segmentation.

  Materials and Methods Top


Since the aim of this study is glioma segmentation in brain MRI, multiparametric MRI of MICCAI BraTS challenge dataset was a good choice. This dataset clinically acquired 3T preoperative multimodal MRI scans of glioblastoma with pathologically confirmed diagnosis contained T1 weighted, T2 weighted, FLAIR, and T1 gadolinium (Gd)-enhanced image and were acquired with different clinical protocols and various scanners from 19 institutions,[17] as illustrated in [Figure 1].
Figure 1: Multiparametric magnetic resonance imaging of BraTS native (T1) and postcontrast T1-weighted (T1Gd), T2-weighted (T2), and T2 fluid-attenuated inversion recovery volumes

Click here to view

This dataset contained 262 high-grade and 199 low-grade brain tumor images. Each image consists of 155 slices, and the size of each slice is 240 × 240.

All the imaging datasets have been segmented manually, by one to four raters, following the same annotation protocol, and their annotations were approved by experienced neuroradiologists. Annotations comprise the GD-enhancing tumor and necrotic tumor, as illustrated in [Figure 2].
Figure 2: An example of rater's annotation for respective to Figure 1

Click here to view

As we will use one of these MRI sequences and as mentioned in some studies, T1 (Gd) shows the best discrimination between enhancing and necrotic tumors;[18],[19] the T1 (Gd) will be used for this study.


As described above, the goal of this study is tumor segmentation in brain MRI using graph coloring approach. The original idea for this method came from the fact that in image segmentation, pixels are placed in a class that is similar in terms of brightness. Now, if the image is considered as a graph in which the neighborhood is not based on geographical coordinates but on the difference in brightness, we can say that the image can be segmented by using graph coloring. Therefore, in this study, we will first create an image graph and then use the graph coloring method to segment the image. Therefore, in the continuation of this section, we will first explain the method of creating a graph of the brightness specifications of pixels, and then, we will explain how to segment the image using graph coloring. This approach is briefly illustrated in [Figure 3].
Figure 3: Flowchart of this study

Click here to view

Graph creating

An image can be converted to a G (V, E) graph by considering the brightness of the pixels so that V represents the set of nodes and E represents the edge between the nodes. In the image graph, each pixel of the image is known as the node, and the edge between the nodes indicates the similarity of brightness between the pixels. Therefore, pixels whose brightness is less spaced will have a stronger edge coefficient and those that are farther apart will have a lower edge coefficient. Therefore, the following steps will be performed to create this graph.

  1. Making a brightness distance matrix
  2. Normalize the brightness distance matrix
  3. Build a neighborhood matrix using the brightness distance matrix
  4. Structuring the graph.

The first step in building a matrix is the spacing of the indicators. Therefore, by having n pixels, we will have a distance of n × n matrix, the value of each of which is calculated as follows.

Where D (i, j) indicates the difference in brightness between the pixels i and j and Br (i) indicates the brightness of the pixel i.

In the next step, this matrix must be normalized so that all its numbers are between zero and one, which will be done using Eq. 2.

Where Dn (i, j) is the line i and the column j is the normal matrix of the distance between the light and the minD and maxD are the minimum and maximum distances of the brightness, respectively.

The next step in building a neighborhood matrix is to use a brightness distance matrix, so, those pixels which are more similar in term of brightness have a stronger neighborhood, and parts that are more spaced in terms of the index have a weaker neighborhood. To achieve this matrix, the neighborhood matrix derivatives are calculated as follows.

Where N (i, j) is the line of the ith row and the jth column is the neighborhood matrix. By constructing this matrix, the graph can be structured in such a way that there is an edge between the vertices that have a value between zero and one, in this way, there is an edge between the nodes that have a value between zero and one, and if this value is higher than a predefined threshold, there is an edge between these two nodes, and if it is less than this threshold, there is no edge.

Graph coloring

Since in this study, neighborhood neighbors do not necessarily mean their proximity physically, and based on their characteristics, the neighborhood is defined, so this type of neighborhood is somehow considered an irregular neighborhood. The following is a graphic coloring method based on this type of neighborhood.

  1. Graph matrix structuring: To structure the graph matrix, an n × n matrix will be constructed in which n is the number of vertices of the graph and all its nodes are zero except for the nodes in which the two nodes are adjacent to each other. Therefore, the graph matrix drivers will be calculated as follows

  2. Sort the matrix structure: The next step is to arrange the graph matrix so that the line with the corresponding vertex with the most neighbor is at the top of the matrix and the line with the corresponding vertex with the least neighborhood is at the bottom of the matrix
  3. Primary structure of the color matrix: Creating a matrix with 1 row and n columns as the color matrix of the vertices, at this stage we refer to all vertices of the same color (color number 1)
  4. Determining the flag of the nodes: Now for the nodes in the matrix arranged, we compare them with the previous nodes so that the second node in this matrix is compared with the first node, the third node is compared with the second and first nodes, and the fourth node is compared with the node. The third, second, and first are compared, and so on until we reach the last node, and we adopt a flag for each node. Now, if each node is compared to its previous node or nodes, if it is the same color and neighbor as at least one of its previous nodes, its flag will be one, otherwise it will be zero
  5. Improving the color matrix: In this step, a number is added to the color matrix drive of each vertex whose flag is 1, and then we go to step 4. This operation is performed until The color matrix changes.

Constructing complementary matrix

Since in the picture, the pixels that are on the same level in terms of brightness will be neighbors in the neighborhood matrix, and we want these pieces to have the same color, and on the other hand, in “Graph coloring” section, it was explained that neighborhood neighbors cannot be the same color. Therefore, a complementary graph must be created to determine the color for the image graph. A graph is a complement to a graph whose community creates a complete graph with the original graph. Therefore, the complementary graph, where the main graph has a ridge, lacks a ridge, and where it does not have a ridge, will include a ridge. Therefore, the complement graph is defined as follows.

Where EC is a complementary matrix.

MATLAB 2015b was used on a Pc with Intel® Core i5-7400 CPU at 3.00 GHz processor and 4 GB installed memory.

  Conclusion Top

Since graph coloring is a time-consuming process, at the first step, we selected the location of tumor in image and cropped the region of tumor, as illustrated in [Figure 4]. This localization was done by ourselves base on prior knowledge about tumor location. According to the MRI images and specifications and based on images' evaluation information, the tumor span was selected by the operator. In fact, the location selection depends on the operator's knowledge and perception.
Figure 4: Cropped region of tumor

Click here to view

For proving and investigating the effect of image size on run time of graph coloring, a n × n image was selected for graph coloring and run time of this algorithm was computed for varying number of pixels. For this aim, MATLAB 2015b was used on a Pc with Intel® Core i5-7400 CPU at 3.00 GHz processor and 4 GB installed memory. As it is an obvious increment of image size, it causes an exponentially increment of run time, as illustrated in [Figure 5].
Figure 5: Effect of image size on graph coloring run time

Click here to view

At the second step, distances between pixels are calculated and a threshold must be considered for making graph. In this step, the value of threshold is considered as 0.4. Distances and threshold are shown in [Figure 6].
Figure 6: Distances between pixels and used threshold

Click here to view

Using these features and graph coloring approach, the segmented image is achieved, and for comparison between the segmented image and original labels of pixels, the correlation is used. Using this threshold, the correlation is 82% and results are illustrated in [Figure 7].
Figure 7: A comparison between the introduced approach and artificial neural networks and neuro-fuzzy system

Click here to view

For more investigation, threshold must be alternated, so this value alternated between 0.33% and 58% and correlation is evaluated and results are shown in [Figure 6].

As shown in [Figure 8], there is a mid-range threshold that can make high-quality segmentation and the best correlation is 83.63%.
Figure 8: Relation between thresholds in correlation

Click here to view

In this study, a new semi-automatic brain tumor segmentation based on a graph coloring approach has been introduced. This approach used each pixel as a node of a graph and using these nodes, distances between brightness used as edges between nodes and at next step, the rigid graph was structured using this graph and a a 40% threshold. The complementary of this graph was colored and segmented the image. Using correlation between segmented image and original segmented tissue performance of this approach was evaluated [Figure 7]. The result shows this approach as a cornerstone of graph coloring can be reliable. It would be called a cornerstone because in this study the brightness was just used as a simple feature of image, and on the other hand, T1 (Gd) MRI image was used. So it would be expected using combination of other types of MRI images and more complex feature of image, may could improve the results.

Moreover, one of the most important problems of unsupervised approaches for image segmentation is their accuracy. For evaluating the performance of introduced approach, its performance compared with two common supervised approaches contained artificial neural networks and neuro-fuzzy system and their results are shown in [Table 1]. Artificial neural network is a multilayer perceptron with one hidden layer and 5 neurons and neuro-fuzzy system is Sugeno type with 5 membership functions.
Table 1: A comparison between the introduced approach and artificial neural networks and neuro-fuzzy system

Click here to view

As it is shown in [Table 1], the performance of introduced approach as an unsupervised approach is better than these two common supervised approaches.

The limitation of the graph coloring method is time-consuming. As it is shown in [Figure 5], running time of this method is exponentially related to size of image, so for bigger region of tumor, it would be more time-consuming, so for overcoming this problem, it would be needed more preprocessing for extracting most important pixels or dividing the region into several parts. For feature studies, it would be suggested to use more reliable and complex features of image instead of brightness, such as continuous wavelet and combination of other types of MRI images.

Financial support and sponsorship


Conflicts of interest

There are no conflicts of interest.

  References Top

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.  Back to cited text no. 1
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.  Back to cited text no. 2
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.  Back to cited text no. 3
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.  Back to cited text no. 4
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.  Back to cited text no. 5
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.  Back to cited text no. 6
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.  Back to cited text no. 7
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.  Back to cited text no. 8
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.  Back to cited text no. 9
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.  Back to cited text no. 10
Gómez D, Montero J, Yáñez J, Poidomani C. A graph coloring approach for image segmentation. Omega 2007;35:173-83.  Back to cited text no. 11
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.  Back to cited text no. 12
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.  Back to cited text no. 13
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.  Back to cited text no. 14
Chang H, Chen Z, Huang Q, Shi J, Li X. Graph-based learning for segmentation of 3D ultrasound images. Neurocomputing. 2015;151:632-44.  Back to cited text no. 15
Chen X, Pan L. A survey of graph cuts/graph search based medical image segmentation. IEEE Rev Biomed Eng 2018;11:112-24.  Back to cited text no. 16
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.  Back to cited text no. 17
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.  Back to cited text no. 18
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.  Back to cited text no. 19


  [Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6], [Figure 7], [Figure 8]

  [Table 1]


Similar in PUBMED
   Search Pubmed for
   Search in Google Scholar for
 Related articles
Access Statistics
Email Alert *
Add to My List *
* Registration required (free)

  In this article
   Materials and Me...
   Article Figures
   Article Tables

 Article Access Statistics
    PDF Downloaded63    
    Comments [Add]    

Recommend this journal