Review on graph theory-based image segmentation with its methods
DOI:
https://doi.org/10.29304/jqcsm.2024.16.21541Keywords:
image segmentation, graph theory, graph cut, Pyramid-basedAbstract
In areas of digital image processing and computer vision, image segmentation is defined as a crucial process that divides an image into many segments for more straightforward and accurate object analysis. Making use of graph-based techniques as an effective tool for segmenting images has drawn more consideration recently. Since graph-based techniques are attractive and increasingly prevalent and can designate image properties, in this article, some of the primary graph-based techniques have been presented. This scheme utilizes graph theory to create a graph depiction of an image in which each pixel is represented as a node and the edges show the degree of similarity between two pixels. When items are represented by vertices and an edge connects them, a graph may be used to depict the relationship between them. To divide a graph into sub-graphs that reflect significant items of interest, this study explores some graph theoretical approaches for image segmentation, including minimum spanning tree, pyramid-based, graph cut-based, and interactive image segmentation and their employing in significant image processing fields such as medical image analysis for infection diagnosis, and remote sensing.
Downloads
References
P. Wang, Z. Wei, W. Cui, and Z. Lin, “A minimum spanning tree based method for UAV image segmentation,” ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 3, pp. 111–117, 2016.
P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” International journal of computer vision, vol. 59, pp. 167–181, 2004.
P. Shivhare and V. Gupta, “Review of image segmentation techniques including pre & post processing operations,” International Journal of Engineering and Advanced Technology, vol. 4, no. 3, pp. 153–157, 2015.
A. Fabijanska, “Graph Convolutional Networks for Semi-Supervised Image Segmentation,” IEEE Access, vol. 10, pp. 104144–104155, 2022.
S. D. Kapade, S. M. Khairnar, and B. S. Chaudhari, “A new particle swarm intelligence-based graph partitioning technique for image segmentation,” Journal of Electrical Systems and Information Technology, vol. 7, pp. 1–13, 2020.
K. S. Camilus and V. K. Govindan, “A review on graph based segmentation,” International Journal of Image, Graphics and Signal Processing, vol. 4, no. 5, p. 1, 2012.
T. H. Le, S.-W. Jung, K.-S. Choi, and S.-J. Ko, “Image segmentation based on modified graph-cut algorithm,” Electronics letters, vol. 46, no. 16, pp. 1121–1123, 2010.
M. Sato, H. Aomori, and T. Otake, “Automation and acceleration of graph cut based image segmentation utilizing U-net,” Nonlinear Theory and Its Applications, IEICE, vol. 15, no. 1, pp. 54–71, 2024.
S. Vicente, V. Kolmogorov, and C. Rother, “Graph cut based image segmentation with connectivity priors,” in 2008 IEEE conference on computer vision and pattern recognition, IEEE, 2008, pp. 1–8.
B. Basavaprasad and S. H. Ravindra, “A survey on traditional and graph theoretical techniques for image segmentation,” Int. J. Comput. Appl, vol. 975, p. 8887, 2014.
M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” Journal of Experimental Algorithmics (JEA), vol. 23, pp. 1–22, 2018.
J. Bragantini and A. X. Falcao, “Interactive image segmentation: From graph-based algorithms to feature-space annotation,” in Anais Estendidos do XXXV Conference on Graphics, Patterns and Images, SBC, 2022, pp. 48–54.
G. Song, H. Myeong, and K. M. Lee, “Seednet: Automatic seed generation with deep reinforcement learning for robust interactive segmentation,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 1760–1768.
Z. Lin, Z. Zhang, L.-Z. Chen, M.-M. Cheng, and S.-P. Lu, “Interactive image segmentation with first click attention,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2020, pp. 13339–13348.
K. Sofiiuk, I. A. Petrov, and A. Konushin, “Reviving iterative training with mask guidance for interactive segmentation,” in 2022 IEEE International Conference on Image Processing (ICIP), IEEE, 2022, pp. 3141–3145.
D. Kaliyaperumal, “Analysis in Algorithms of Spanning Tree to Reduce the Distance Between the,” no. December, 2021.
R. Marfil, L. Molina-Tanco, A. Bandera, J. A. Rodríguez, and F. Sandoval, “Pyramid segmentation algorithms revisited,” Pattern Recognition, vol. 39, no. 8, pp. 1430–1451, 2006.
X. Li, Y. Yang, Q. Zhao, T. Shen, Z. Lin, and H. Liu, “Spatial pyramid based graph reasoning for semantic segmentation,” in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 8950–8959.
X. Chen and U. Bagci, “3D automatic anatomy segmentation based on iterative graph‐cut‐ASM,” Medical physics, vol. 38, no. 8, pp. 4610–4622, 2011.
Y. Yang, H. T. Li, Y. S. Han, and H. Y. Gu, “High resolution remote sensing image segmentation based on graph theory and fractal net evolution approach,” The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 40, pp. 197–201, 2015.
W. Ju, D. Xiang, B. Zhang, L. Wang, I. Kopriva, and X. Chen, “Random walk and graph cut for co-segmentation of lung tumor on PET-CT images,” IEEE Transactions on Image Processing, vol. 24, no. 12, pp. 5854–5867, 2015.
R. Alshehhi and P. R. Marpu, “Hierarchical graph-based segmentation for extracting road networks from high-resolution satellite images,” ISPRS journal of photogrammetry and remote sensing, vol. 126, pp. 245–260, 2017.
D. Ren, Z. Jia, J. Yang, and N. K. Kasabov, “A practical grabcut color image segmentation based on bayes classification and simple linear iterative clustering,” IEEE Access, vol. 5, pp. 18480–18487, 2017.
Q. Zheng, S. Warner, G. Tasian, and Y. Fan, “A dynamic graph cuts method with integrated multiple feature maps for segmenting kidneys in 2D ultrasound images,” Academic radiology, vol. 25, no. 9, pp. 1136–1145, 2018.
T. Siriapisith, W. Kusakunniran, and P. Haddawy, “Pyramid graph cut: Integrating intensity and gradient information for grayscale medical image segmentation,” Computers in Biology and Medicine, vol. 126, p. 103997, 2020.
U. Sekar, R. R. Mohan, and M. V. S. Reddy, “Implementation and quality measures of graph theory model based image segmentation process in medical application,” in Journal of Physics: Conference Series, IOP Publishing, 2021, p. 12128.
R. Bagheri, J. H. Monfared, and M. R. Montazeriyoun, “Brain tumor segmentation using graph coloring approach in magnetic resonance images,” Journal of Medical Signals and Sensors, vol. 11, no. 4, p. 285, 2021.
A. Aflalo, S. Bagon, T. Kashti, and Y. Eldar, “Deepcut: Unsupervised segmentation using graph neural networks clustering,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2023, pp. 32–41.
S. V Belim and S. Y. Belim, “Images Segmentation Based on Cutting the Graph into Communities,” Algorithms, vol. 15, no. 9, p. 312, 2022.
S. Mayala, I. Herdlevær, J. B. Haugsøen, S. Anandan, S. Gavasso, and M. Brun, “Brain tumor segmentation based on minimum spanning tree,” Frontiers in Signal Processing, vol. 2, p. 816186, 2022.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Noor Khalid Ibrahim, Narjis Mezaal Shati
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
