

SHORT COMMUNICATION 

Year : 2021  Volume
: 11
 Issue : 4  Page : 285290 

Brain tumor segmentation using graph coloring approach in magnetic resonance images
Rouholla Bagheri^{1}, Jalal Haghighat Monfared^{2}, Mohammad Reza Montazeriyoun^{2}
^{1} Department of Management, Ferdowsi University of Mashhad, Iran ^{2} Department of Management, Central Tehran Branch, Islamic Azad University, Tehran, Iran
Date of Submission  29Jun2020 
Date of Decision  23Sep2020 
Date of Acceptance  18Apr2021 
Date of Web Publication  20Oct2021 
Correspondence Address: Rouholla Bagheri Department of Management, Ferdowsi University of Mashhad Iran
Source of Support: None, Conflict of Interest: None
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 T1enhanced magnetic resonance images of lowgrade and highgrade 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 neurofuzzy 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:28590 
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:28590. Available from: https://www.jmssjournal.net/text.asp?2021/11/4/285/328733 
Introduction   
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 semiautomatic 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 regionbased and contourbased 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 regionbased 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 graphbased 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 T1enhanced MRI and investigate the performance of this approach for glioma segmentation.
Materials and Methods   
Dataset
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 T1weighted (T1Gd), T2weighted (T2), and T2 fluidattenuated inversion recovery volumes
Click here to view 
This dataset contained 262 highgrade and 199 lowgrade 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 GDenhancing tumor and necrotic tumor, as illustrated in [Figure 2].
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.
Segmentation
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].
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.
 Making a brightness distance matrix
 Normalize the brightness distance matrix
 Build a neighborhood matrix using the brightness distance matrix
 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 min_{D} and max_{D} 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 i^{th} row and the j^{th} 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.
 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
 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
 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)
 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
 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 i57400 CPU at 3.00 GHz processor and 4 GB installed memory.
Conclusion   
Since graph coloring is a timeconsuming 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.
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 i57400 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].
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].
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 neurofuzzy 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 midrange threshold that can make highquality segmentation and the best correlation is 83.63%.
In this study, a new semiautomatic 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 neurofuzzy system and their results are shown in [Table 1]. Artificial neural network is a multilayer perceptron with one hidden layer and 5 neurons and neurofuzzy system is Sugeno type with 5 membership functions.  Table 1: A comparison between the introduced approach and artificial neural networks and neurofuzzy 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 timeconsuming. 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 timeconsuming, 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
None.
Conflicts of interest
There are no conflicts of interest.
References   
1.  Bauer S, Wiest R, Nolte LP, Reyes M. A survey of MRIbased medical image analysis for brain tumor studies. Phys Med Biol 2013;58:R97129. 
2.  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:98111. 
3.  Goetz M, Weber C, Binczyk F, Polanska J, Tarnawski R, BobekBillewicz B, et al. DALSA: Domain adaptation for supervised learning from sparsely annotated MR images. IEEE Trans Med Imaging 2016;35:18496. 
4.  Goetz M, Weber C, Bloecher J, Stieltjes B, Meinzer HP, MaierHein K. Extremely randomized trees based brain tumor segmentation. Proceeding of BRATS challengeMICCAI. 2014 Sep 14:00611. 
5.  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:4450. 
6.  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 ComputerAssisted Intervention. Springer, Berlin, Heidelberg. 1998. p. 457468. 
7.  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:13347. 
8.  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. 
9.  JuanAlbarracín J, FusterGarcia 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. 
10.  Thakur GK, Priya B, Pawan Kumar S. A novel fuzzy graph theorybased approach for image representation and segmentation via graph coloring. J Appl Secur Res 2019;14:7487. 
11.  Gómez D, Montero J, Yáñez J, Poidomani C. A graph coloring approach for image segmentation. Omega 2007;35:17383. 
12.  Yáñez J, Muñoz S, Montero J. Graph coloring inconsistencies in image segmentation. In Computational Intelligence In Decision And Control 2008. p. 43540. 
13.  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:22438. 
14.  Yuan X, Guo J, Hao X, Chen H. Traffic sign detection via graphbased ranking and segmentation algorithms. IEEE Trans Syst Man Cybern Syst 2015;45:150921. 
15.  Chang H, Chen Z, Huang Q, Shi J, Li X. Graphbased learning for segmentation of 3D ultrasound images. Neurocomputing. 2015;151:63244. 
16.  Chen X, Pan L. A survey of graph cuts/graph search based medical image segmentation. IEEE Rev Biomed Eng 2018;11:11224. 
17.  Menze BH, Jakab A, Bauer S, KalpathyCramer J, Farahani K, Kirby J, et al. The multimodal brain tumor image segmentation benchmark (BRATS). IEEE Trans Med Imaging 2015;34:19932024. 
18.  Mehta RC, Pike GB, Haros SP, Enzmann DR. Central nervous system tumor, infection, and infarction: Detection with gadoliniumenhanced magnetization transfer MR imaging. Radiology 1995;195:416. 
19.  Farjam R, Parmar HA, Noll DC, Tsien CI, Cao Y. An approach for computeraided detection of brain metastases in postGd T1W MRI. Magn Reson Imaging 2012;30:82436. 
[Figure 1], [Figure 2], [Figure 3], [Figure 4], [Figure 5], [Figure 6], [Figure 7], [Figure 8]
[Table 1]
