An Overview of Parallel Computing Models for Image Segmentation with Ncut

Authors

  • Nhu Y Tran Industrial University of Ho Chi Minh City, Vietnam https://orcid.org/0000-0002-8588-0355
  • Trung Hieu Huynh Industrial University of Ho Chi Minh City, Vietnam
  • The Bao Pham Sai Gon University, Ho Chi Minh City, Vietnam

Corressponding author's email:

ptbao@sgu.edu.vn

DOI:

https://doi.org/10.54644/jte.2024.1370

Keywords:

Parallel model, Parallel computing, GPU, CPU, Ncut

Abstract

Image segmentation is a prerequisite in most image processing applications. There are lots of methods for image segmentation, and there are also numerous methods to evaluate the results of such segmentations. Among them, the Ncut algorithm by J. Shi using graph theory has significantly improved the efficiency of digital image processing. Most of the results indicate that the partitions of the image are all according to human vision. However, with a large image set, the algorithm will compute at a low speed; it takes time and high memory usage for the computation. The parallel model is a model that scientists are interested in and use to improve performance in image segmentation with large-size images. The article summarizes the overview of parallel models in image segmentation and the comments and evaluations for a few parallel models on the Ncut algorithm. Experimental results reveal that the time required to compute eigenvalues in the Ncut algorithm when executed in parallel on a GPU is significantly lower compared to execution on a CPU. Furthermore, as image sizes increase, the execution time on the GPU only marginally increases in comparison to CPU execution, while still yielding similar image segmentation results.

Downloads: 0

Download data is not yet available.

Author Biographies

Nhu Y Tran, Industrial University of Ho Chi Minh City, Vietnam

Tran Nhu Y. 2008: BSc degree in Mathematics and Computer Science, University of Science, Vietnam National University-Ho Chi Minh, Vietnam. 2013: MSc degree in Mathematics and Computer Science, University of Science, Vietnam National University-Ho Chi Minh, Vietnam. 2005 to now: Lecturer at Information Technology Faculty, University of Industry and Trade, Vietnam. Research interests: computer vision, image segmentation.

Email: ytn@hufi.edu.vn. ORCID: https://orcid.org/0000-0002-8588-0355

Trung Hieu Huynh, Industrial University of Ho Chi Minh City, Vietnam

Huynh Trung Hieu received a Bachelor's and Master's degree from the Ho Chi Minh City University of Technology in 1998 and 2003, and then obtained a PhD in Computer Engineering from Chonnam National University, South Korea in 2009. Currently, he is an associate professor and works at the Ho Chi Minh City University of Industry. He is a member of IEEE and IEICE. His research focuses on artificial intelligence and its applications in medical data analysis. Email: hthieu@ieee.org. ORCID: https://orcid.org/0000-0002-2097-0704

The Bao Pham, Sai Gon University, Ho Chi Minh City, Vietnam

Pham The Bao. 1995: B.S., 2000: MSc., 2009: Ph.D. degree in Computer Science from University of Science, Vietnam.

1995 ~ 2018: Lecturer and Professor in Department of Computer Science, Faculty of Mathematics & Computer Science, University of Science, Vietnam. 2007 ~ 2016: Vice Dean Faculty of Mathematics & Computer Science and head of Computer Science Department, University of Science, Vietnam. 2019 to now: Professor in Department of Computer Science, and Dean of Information Science Faculty, Sai Gon University, Vietnam. Chair of IC-IP Lab. Research interests: Image processing & pattern recognition, intelligent computing.

Email: ptbao@sgu.edu.vn. ORCID: https://orcid.org/0000-0002-4847-4366

References

Z. Lv, Y. Hu, and H. Zhong, “Parallel K-Means Clustering of Remote Sensing Images Based on MapReduce,” in Proc. WISM 2010: Web Information Systems and Mining, International Conference on Web Information Systems and Mining, Springer, Berlin, Heidelberg, vol. 6318, 2010, pp. 162-170.

B. Liu, S. He, and D. He, “A Spark-Based Parallel Fuzzy C -Means Segmentation Algorithm for Agricultural Image Big Data,” IEEE access, vol. 7, pp. 42169-42180, 2019.

J. Cao, L. Chen, and M. Wang, “Implementing a Parallel Image Edge Detection Algorithm Based on the Otsu-Canny Operator on the Hadoop Platform,” Computational Intelligence and Neuroscience, 2018, doi: 10.1155/2018/3598284.

D. P. Augustine and P. Raj, “Performance Evaluation of Parallel Genetic Algorithm for Brain MRI Segmentation in Hadoop and Spark,” Indian Journal of Science and Technology, vol. 9, no. 48, 2016, doi: 10.17485/ijst/2016/v9i48/140123.

M. N.t Akhtar, J. M. Saleh, and H. Awais, “Map-Reduce based tipping point scheduler for parallel image processing,” Expert Systems with Applications, vol. 139, 2020, doi: 10.1016/j.eswa.2019.112848.

N. Wang, F. Chen, and B. Yu, “Segmentation of large-scale remotely sensed images on a Spark platform: A strategy for handling massive image tiles with the MapReduce model,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 162, pp. 137-147, 2020.

J. Sirotković, H. Dujmić, and V. Papić, “K-means image segmentation on massively parallel GPU architecture,” in Proc. 35th International Convention MIPRO, Opatija, Croatia, 2012, pp. 489-494.

Q. B. Baker and K. Balhaf, “Exploiting GPUs to accelerate white blood cells segmentation in microscopic blood images,” in Proc. 8th International Conference on Information and Communication Systems (ICICS), Irbid, Jordan, 2017, pp. 136-140.

M. Baydoun, M. Dawi, and H. Ghaziri, “Enhanced Parallel Implementation of the K-Means Clustering Algorithm,” in Proc. 3rd International Conference on Advances in Computational Tools for Engineering Applications (ACTEA), IEEE, 2016, doi: 10.1109/ACTEA.2016.7560102.

M. Dalvand, A Fathi, and A Kamran, “Flooding region growing: a new parallel image segmentation model based on membrane computing,” Journal of Real-Time Image Processing, vol. 18, pp. 37-55, 2021.

X. Wang, J. Pan, and S. Chu, “A Parallel Multi-Verse Optimizer for Application in Multilevel Image Segmentation,” IEEE Access, vol. 8, pp. 32018-32030, 2020.

Y. Chen, J. Tao, and L. Liu, “Research of improving semantic image segmentation based on a feature fusion model,” Journal of Ambient Intelligence and Humanized Computing, vol. 13, pp. 5033-5045, 2020.

L. Jiao, Y. Li, M. Gong, “Quantum-inspired immune clonal algorithm for global optimization,” IEEE Transaction on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 38, no. 5, pp. 1234-1253, 2008.

Y. Li, S. Feng, and X. Zhang, “SAR image segmentation based on quantum-inspired multiobjective evolutionary clustering algorithm,” Information Processing Letters, vol. 114, pp. 287-293, 2014.

D. P. Hudedagaddi and B. K. Tripathy, “Quantum inspired computational intelligent techniques in image segmentation,” Quantum Inspired Computational Intelligence, pp. 233-258, 2017.

S. Das, S. De, and S. Dey, “Magnetic Resonance Image Segmentation Using a Quantum‐Inspired Modified Genetic Algorithm (QIANA) Based on FRCM,” John Wiley & Sons, 2020, doi: 10.1002/9781119551621.ch8.

S. Yuan, C. Wen, and B. Hang, “The dual-threshold quantum image segmentation algorithm and its simulation,” Quantum Information Processing, vol. 19, no. 425, 2020, doi: 10.1007/s11128-020-02932-x.

J. Ghorpade, J. Parande, and M. Kulkarni, “GPGPU processing in cuda architecture,” Advanced Computing: An International Journal (ACIJ), vol. 3, no. 1, pp. 105-120, 2012.

J. I. Agulleiro, F. Vázquez, and E. M. Garzón, “Hybrid computing: CPU+GPU co-processing and its application to tomographic reconstruction,” Ultramicroscopy at SciVerse ScienceDirect, vol. 115, pp. 109-114, 2012.

J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” Pattern Analysis and Machine Intelligence, IEEE Transactions, vol. 22, no. 8, pp. 888-905, 2000.

H. X. Lou and Y. S. Yuan, “Image segmentation based on normalized cut and CUDA parallel implementation,” in Proc. 5th IET International Conference on Wireless, Mobile and Multimedia Networks (ICWMMN 2013), Beijing, China, 2013, doi: 10.1049/cp.2013.2410

J. Senthilnath, S. Sindhu, and S. N. Omkar, “GPU-based normalized cuts for road extraction using satellite imagery,” Journal of Earth System Science, vol. 123, pp. 1759-1769, 2014.

M. Naumov and T. Moon, “Parallel Spectral Graph Partitioning,” NVIDIA Technical Report, 2016. [Online]. Available: https://research.nvidia.com/sites/default/files/publications/nvr-2016-001.pdf.

B. Catanzaro, B. Y. Su, and N. Sundaram, “Efficient, High-Quality Image Contour Detection,” in Proc. the IEEE 12th International Conference on Computer Vision, Kyoto, Japan, 2010, doi: 10.1109/ICCV.2009.5459410.

Sattar and N. Safrin, "Parallel Algorithms for Scalable Graph Mining: Applications on Big Data and Machine Learning," University of New Orleans Theses and Dissertations, 2022. [Online]. Available: https://scholarworks.uno.edu/td/3014/.

W. Tao, H. Jin, and Y. Zhang, “Color Image Segmentation Based on Mean Shift and Normalized Cuts,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 37, pp. 1382-1389, 2007.

A. Fabjawska, “Normalized cuts and watersheds for image segmentation,” in IET Conference on Image Processing (IPR 2012), London, UK, 2012, doi: 10.1049/cp.2012.0440.

L. You, H. Jiang, and J. Hu, “GPU-accelerated Faster Mean Shift with euclidean distance metrics,” in Proc. the IEEE 46th Annual Computers, Software, and Applications Conference (COMPSAC), Los Alamitos, CA, USA, 2022, doi: 10.1109/COMPSAC54236.2022.00037.

S. Soor and B. S. D. Sagar, “Segmentation of Multi-Band Images Using Watershed Arcs,” IEEE Signal Processing Letters, vol. 29, pp. 2407-2411, 2022.

T. Cour, F. Benezit, and J. Shi, “Spectral segmentation with multiscale graph decomposition,” in Proc. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, CA, USA, 2005, doi: 10.1109/CVPR.2005.332.

S. D. Kapade, S. M. Khairnar, and B. S. Chaudhari, “Enhanced graph based normalized cut methods for image segmentation,” ICTACT journal on image and video processing, vol. 5, no. 2, pp. 907-911, 2014.

A. Challa, S. Danda, and B. S. D. Sagar, “Power Spectral Clustering,” Journal of Mathematical Imaging and Vision, vol. 62, pp.1195-1213, 2020.

https://ccia.ugr.es/cvg/dbimagenes/

Published

28-04-2024

How to Cite

Trần Như Ý, Huỳnh Trung Hiếu, & Phạm Thế Bảo. (2024). An Overview of Parallel Computing Models for Image Segmentation with Ncut. Journal of Technical Education Science, 19(2), 22–32. https://doi.org/10.54644/jte.2024.1370

Issue

Section

Research Article

Categories

Most read articles by the same author(s)