Segmentation of Magnetic Resonance Brain Imaging Based on Graph Theory

Document Type : Original Paper


1 Department of Electrical Engineering, Mashhad Branch, Islamic Azad University, Mashhad, Iran

2 Department of Electrical Engineering, Khomeinishahr Branch, Islamic Azad University, Isfahan, Iran


Introduction: Segmentation of brain images especially from magnetic resonance imaging (MRI) is an essential requirement in medical imaging since the tissues, edges, and boundaries between them are ambiguous and difficult to detect, due to the proximity of the brightness levels of the images.
Material and Methods: In this paper, the graph-based method is proposed to solve the segmentation of MRI brain images wherein a weighted undirected graph is assigned to the image with each edge of the graph corresponding to an image pixel. The edge weight between two nodes demonstrated the similarity between two pixels of the image. Thereafter, a cost function, such as relative extremes and turning point, was assigned to the graph, which matched the derivation of the function. Minimization of this cost function, which was equivalent to the shortest path in a graph, led to image segmentation.
Results: The advantageof the graph method over other methods is the simultaneous construction of spatial information at a high rate. Moreover, this method is implemented on the pixels in the space and can partition MRI brain images with low error in an effort to improve the previous methods. The comparisons demonstrated that the accuracy of the MRI brain image segmentation would be improved through the application of the present method.
Conclusion: The obtained results of the current study indicated the high accuracy of the proposed method (about 97.5%), compared to other similar methods. Therefore, this method can accurately distinguish various types of brain MRI tissues and have clinical applications.


Main Subjects



    1. Strang G. Linear Algebra and Its Applications (4th ed.); 2005.
    2. Gonzalez R, Richard E. Woods, Digital Image Processing (2nd ed.); 2002.
    3. Despotović I, Goossens B, Philips W. MRI segmentation of the human brain: challenges, methods, and applications. Computational and mathematical methods in medicine. 2015;2015.
    4. Vaezi M, Kai Chua C, Meng Chou S. Improving the process of making rapid prototyping models from medical ultrasound images. Rapid Prototyping Journal. 2012;18(4):287-98.
    5. Hao J, Shen Y, Xu H, Zou J. Interfacial gradient priors-based geodesic geometric flows for 3D medical image segmentation. COMPEL-The international journal for computation and mathematics in electrical and electronic engineering. 2010;29(2):505-14.
    6. Polakowski WE, Cournoyer DA, Rogers SK, DeSimio MP, Ruck DW, Hoffmeister JW, et al. Computer-aided breast cancer detection and diagnosis of masses using difference of Gaussians and derivative-based feature saliency. IEEE transactions on medical imaging. 199;16(6):811-9.
    7. Bai Z, Yang Z, Wu J, Chen Y. Region localization based on rotational invariant feature and improved self organized map. In2008 3rd International Conference on Intelligent System and Knowledge Engineering. 2008;1:703-6.
    8. Zoroofi RA, Mizuno YM, Shinosaki K, Ukai S, Ishii R , Keserci B, et al. Automated Segmentation of the Brain in MRI. Proceeding of JAMIT. 2000;58-65.
    9. Jianhua L, Yi-Wen W, Yi C, Guocheng W. Adaptive Segmentation Method for 2-D Barcode Image Base on Mathematic Morphological. Research Journal of Applied Sciences, Engineering and Technology. 2013;6:3335-42. 
    10. Leela GA, Kumari HV. Morphological approach for the detection of brain tumour and cancer cells. Journal of electronics and communication engineering research. 2014;2(1):07-12.
    11. Glasbey CA, Horgan GW. Image analysis for the biological sciences. Chichester: Wiley; 1995.
    12. Somasundaram K, Genish T. Binarization of mri with intensity inhomogeneity using k-means clustering for segmenting hippocampus. The International Journal of Multimedia & Its Applications. 2013;5(1):11.
    13. Vijay J, Subhashini J. An efficient brain tumor detection methodology using K-means clustering algorithm. In2013 International Conference on Communication and Signal Processing. 2013; 653-7.
    14. Bleau A, Leon LJ. Watershed-based segmentation and region merging. Computer Vision and Image Understanding. 2000;77(3):317-70.
    15. Singhai PP, Ladhake SA. Brain tumor detection using marker based watershed segmentation from digital mr images. International Journal of Innovative Technology and Exploring Engineering (IJITEE) ISSN. 2013:2278-3075.
    16. Mustaqeem A, Javed A, Fatima T. An efficient brain tumor detection algorithm using watershed & thresholding based segmentation. International Journal of Image. Graphics and Signal Processing. 2012;4(10):34.
    17. Balafar MA, Ramli AR, Saripan MI, Mashohor S. Review of brain MRI image segmentation methods. Artificial Intelligence Review. 2010;33(3):261-74.
    18. Khayati R, Vafadust M, Towhidkhah F, Nabavi M. Fully automatic segmentation of multiple sclerosis lesions in brain MR FLAIR images using adaptive mixtures method and Markov random field model. Computers in biology and medicine. 2008;38(3):379-90.
    19. Węgliński T, Fabijańska A. Brain tumor segmentation from MRI data sets using region growing approach. InPerspective Technologies and Methods in MEMS Design. 2011:185-8.
    20. Dubey RB, Hanmandlu M, Gupta SK, Gupta SK. Region growing for MRI brain tumor volume analysis RB Dubey1, M. Hanmandlu2, SK Gupta3 and SK Gupta4. Indian Journal of Science and Technology. 2009;2(9).
    21. Kamdi S, Krishna RK. Image segmentation and region growing algorithm. International Journal of Computer Technology and Electronics Engineering (IJCTEE). 2012;2(1).
    22. Havaei M, Davy A, Warde-Farley D, Biard A, Courville A, Bengio Y, et al. Brain tumor segmentation with deep neural networks. Medical image analysis. 2017;35:18-31.
    23. Masoumi H, Behrad A, Pourmina MA, Roosta A. Automatic liver segmentation in MRI images using an iterative watershed algorithm and artificial neural network. Biomedical signal processing and control. 2012;7(5):429-37.
    24. Khodadadi H, Razavi SE, Ahmadi-Noubari H. A comparison between neural networks and wavelet networks in nonlinear system identification. Research Journal of Applied Sciences, Engineering and Technology. 2012;4(9):1021-6.
    25. Tatiraju S, Mehta A. Image Segmentation using k-means clustering, EM and Normalized Cuts. Department of EECS. 2008;1:1-7.
    26. Wu Z, Leahy R. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis & Machine Intelligence. 1993;1(11):1101-13.
    27. Grady L, Schwartz EL. Isoperimetric graph partitioning for image segmentation. IEEE transactions on pattern analysis and machine intelligence. 2006; 28(3):469-75.
    28. Couprie C, Grady LJ, Najman L, Talbot H. Power watersheds: A new image segmentation framework extending graph cuts. random walker and optimal spanning forest. InICCV. 2009;9:731-8.
    29. Fahad A, Morris T. A faster graph-based segmentation algorithm with statistical region merge. InInternational Symposium on Visual Computing. 2006:286-93.
    30. Leo Grady. Random Walks for Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2006; 28(11): 1768–83.
    31. Menze BH, Jakab A, Bauer S, Kalpathy-Cramer J, Farahani K, Kirby J, et al. The multimodal brain tumor image segmentation benchmark (BRATS). IEEE transactions on medical imaging. 2014;34(10):1993-2024.
    32. Ungru K, Jiang X. Dynamic programming based segmentation in biomedical imaging. Computational and Structural Biotechnology Journal. 2017;15:255-64.