Research of parallel algorithms of image segmentation using computing on graphical processor

Authors

  • Руслан Богданович Тушницький Lviv Polytechnic National University S.Bandery, 12, Lviv, 79013, Ukraine
  • Ілля Ярославович Кожух Lviv Polytechnic National University S.Bandery, 12, Lviv, 79013, Ukraine

DOI:

https://doi.org/10.15587/1729-4061.2013.12373

Keywords:

Analysis of histograms, segmentation, clustering, computation on GPU, image processing, parallel computing, comparison of algorithms

Abstract

Segmentation is one of the wide used methods of image processing, but with increase of amounts of collections and sizes of images, segmentation requires more processing time. Therefore, the actual problem is to improve the speed of the segmentation; and the appropriate solution is parallelization. Although, there is a number of parallel algorithms, their correct comparison is impossible because of different conditions of results obtaining.

The aim of the study is to develop parallel algorithms for image segmentation, based on different approaches to the segmentation; and to compare them with analogues and with each other in the same conditions. This permits to determine whether parallelization is appropriate and to achieve a common goal – to increase the speed.

Fulfilling the task, we have analyzed a domain of the segmentation, principles of operation of GPU and CUDA technologies, used to implement the parallelization. Based on this we have chosen two approaches to the segmentation - histogram analysis and clustering. To compare these approaches, we have developed a software tool, in which the sequential and parallel algorithms for each of them are implemented. Using it, we have studied the algorithms action, comparing their quality and speed.

The article studies in detail the dependence of speed increase on images size and the number of segments

Author Biographies

Руслан Богданович Тушницький, Lviv Polytechnic National University S.Bandery, 12, Lviv, 79013

 

PhD, Senior lecturer

Software Department

Ілля Ярославович Кожух, Lviv Polytechnic National University S.Bandery, 12, Lviv, 79013

Postgraduate student

Software Department

References

  1. Kurugollu, F. Color image segmentation using histogram multithresholding and fusion [Текст] / F. Kurugollu, B. Sankur, A. E. Harmanci // Image and Vision Computing, Vol. 19, Issue 13. – 2001. – P. 915-928.
  2. Lopes, N. V. Automatic histogram threshold using fuzzy measures [Текст] / N. V. Lopes, P. A. Mogadouro do Couto, H. Bustince, P. Melo-Pinto // IEEE Transactions on Image Processing, Vol. 19, Issue 1. – 2010. – P. 199-204.
  3. Lezoray, O. Color image segmentation using morphological clustering and fusion with automatic scale selection [Текст] / O. Lezoray, C. Charrier // Pattern Recognition Letters, Vol. 30, Issue 4. – 2009. – P. 397-406.
  4. Chitade, A. Z. Colour based image segmentation using k-means clustering [Текст] / A. Z. Chitade, S. K. Katiyar // International Journal of Engineering Science and Technology, Vol. 2, Issue 10. – 2010. – P. 5319-5325.
  5. Wang, H. Generalizing edge detection to contour detection for image segmentation [Текст]/ H. Wang, J. Oliensis // Computer Vision and Image Understanding, Vol. 114, Issue 7. – 2010. – P. 731-744.
  6. Felzenszwalb, P. F. Efficient graph-based image segmentation [Текст] / P. F. Felzenszwalb, D. P. Huttenlocher // International Journal of Computer Vision, Vol. 59, Issue 2. – 2004. – P. 167-181.
  7. Espindola, G. M. Parameter selection for region-growing image segmentation algorithms using spatial autocorrelation [Текст] / G. M. Espindola, G. Camara, I. A. Reis, L. S. Bins, A. M. Monteiro // International Journal of Remote Sensing, Vol. 27, Issue 14. – 2006. – P. 3035-3040.
  8. Senthilkumaran, N. Edge detection techniques for image segmentation – A survey of soft computing approaches [Текст] / N. Senthilkumaran, R. Rajesh // International Journal of Recent Trends in Engineering, Vol. 1, Issue 2. – 2009. – P. 250-254.
  9. Chen, J. Adaptive perceptual color-texture image segmentation [Текст] / J. Chen, T. N. Pappas, A. Mojsilovic, B. E. Rogowitz // IEEE Transactions on Image Processing, Vol. 14, Issue 10. – 2005. – P. 1524-1536.
  10. Kozhuh, I. CBIR System Using CUDA Technology [Текст] / I. Kozhuh, R. Tushnytskyy // Proceedings of the VIIIth International Conference “Perspective Technologies and Methods in MEMS Design” (MEMSTECH’2012). – Lviv-Polyana, 2012. – P. 60-61.
  11. Zhang, H. Image segmentation evaluation: A survey of unsupervised methods [Текст] / H. Zhang, J. E. Fritts, S. A. Goldman // Computer Vision and Image Understanding, Vol. 110, Issue 2. – 2008. – P. 260-280.
  12. Gregg, C. Where is the data? Why you cannot debate CPU vs. GPU performance without the answer [Текст] // C. Gregg, K. Hazelwood. – ISPASS, Austin, 2011. – P. 134-144.
  13. Shams, R. Efficient histogram algorithms for NVIDIA CUDA compatible devices [Текст] / R. Shams, R. A. Kennedy. – ICSPCS, Gold Coast, 2007. – P. 418-422.
  14. Farivar, R. A parallel implementation of k-means clustering [Текст] / R. Farivar, D. Rebodello, E. Chan, R. Campbell. – International Conference on PDPTA, Las Vegas, 2008. – P. 340-345.
  15. Catanzaro, B. Efficient, high-quality image contour detection [Текст] / B. Catanzaro, B. Y. Su, N. Sundaram, Y. Lee, M. Murphy, K. Keutzer. – IEEE International Conference on Computer Vision, Kyoto, 2010. – P. 2381-2388.
  16. Vineeth, V. CUDA cuts: Fast graph cuts on the GPU [Текст] / V. Vineeth, P. J. Narayanan. – Workshop on Visual Computer Vision on GPUs, Anchorage, 2008. – P. 1-8.
  17. Test database (1000 test images) [Електронний ресурс] / J. Z. Wang Research Group]. – Режим доступу: http://wang.ist.psu.edu/~jwang/test1.tar (2013).
  18. Kurugollu, F., Sankur B., Harmanci A. E. (2001). Color image segmentation using histogram multithresholding and fusion. Image and Vision Computing, vol. 19, issue 13, 915–928.
  19. Lopes, N. V., Mogadouro do Couto, P. A., Bustince, H., Melo-Pinto P. (2010). Automatic histogram threshold using fuzzy measures. IEEE Transactions on Image Processing, Vol. 19, Issue 1, 199–204.
  20. Lezoray, O., Charrier C. (2009). Color image segmentation using morphological clustering and fusion with automatic scale selection. Pattern Recognition Letters, Vol. 30, Issue 4, 397–406.
  21. Chitade, A. Z., Katiyar, S. K. (2010). Colour based image segmentation using k-means clustering. International Journal of Engineering Science and Technology, Vol. 2, Issue 10, 5319–5325.
  22. Wang, H., Oliensis, J. (2010). Generalizing edge detection to contour detection for image segmentation. Computer Vision and Image Understanding, Vol. 114, Issue 7, 731–744.
  23. Felzenszwalb, P. F., Huttenlocher, D. P. (2004). Efficient graph-based image segmentation. International Journal of Computer Vision, Vol. 59, Issue 2, 167–181.
  24. Espindola, G. M., Camara, G., Reis, I. A., Bins, L. S., Monteiro A. M. (2006). Parameter selection for region-growing image segmentation algorithms using spatial autocorrelation. International Journal of Remote Sensing, Vol. 27, Issue 14, 3035–3040.
  25. Senthilkumaran, N., Rajesh, R. (2009). Edge detection techniques for image segmentation: A survey of soft computing approaches. International Journal of Recent Trends in Engineering, Vol. 1, Issue 2, 250–254.
  26. Chen, J., Pappas, T. N., Mojsilovic, A., Rogowitz, B. E. (2005). Adaptive perceptual color-texture image segmentation. IEEE Transactions on Image Processing, Vol. 14, Issue 10, 1524–1536.
  27. Kozhuh, I., Tushnytskyy, R. (2012). CBIR System Using CUDA Technology. Proceedings of the VIIIth International Conference “Perspective Technologies and Methods in MEMS Design” (MEMSTECH’2012), 60–61.
  28. Zhang, H., Fritts, J. E., Goldman, S. A. (2008). Image segmentation evaluation: A survey of unsupervised methods. Computer Vision and Image Understanding, Vol. 110, Issue 2, 260–280.
  29. Gregg, C., Hazelwood, K. (2011). Where is the data? Why you cannot debate CPU vs. GPU performance without the answer. ISPASS, Austin, 134–144.
  30. Shams, R., Kennedy, R. A. (2007). Efficient histogram algorithms for NVIDIA CUDA compatible devices. ICSPCS, Gold Coast, 418–422.
  31. Farivar, R., Rebodello, D., Chan, E., Campbell, R. (2008). A parallel implementation of k-means clustering. International Conference on PDPTA, Las Vegas, 340–345.
  32. Catanzaro, B., Su, B. Y., Sundaram, N., Lee, Y., Murphy, M., Keutzer, K. (2010). Efficient, high-quality image contour detection. IEEE International Conference on Computer Vision, Kyoto, 2381–2388.
  33. Vineeth, V., Narayanan, P. J. (2008). CUDA cuts: Fast graph cuts on the GPU. Workshop on Visual Computer Vision on GPUs, Anchorage, 1–8.
  34. Wang, J. Z. (2013). Test database (1000 test images). Electronic resource, http://wang.ist.psu.edu/~jwang/test1.tar.

Downloads

Published

2013-04-25

How to Cite

Тушницький, Р. Б., & Кожух, І. Я. (2013). Research of parallel algorithms of image segmentation using computing on graphical processor. Eastern-European Journal of Enterprise Technologies, 2(4(62), 59–64. https://doi.org/10.15587/1729-4061.2013.12373

Issue

Vol. 2 No. 4(62) (2013): Mathematics and cybernetics - fundamental and applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2014 Руслан Богданович Тушницький, Ілля Ярославович Кожух

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.