Araştırma Makalesi
BibTex RIS Kaynak Göster

Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP

Yıl 2016, Special Issue (2016), 6 - 11, 01.12.2016

Ali Sağlam Nurdan Akhan Baykan

https://doi.org/10.18100/ijamec.271038

Öz

In many image-processing applications, image segmentation is an
essential stage. In this stage, an image is partitioned into several regions
according to the similarity of its pixels. In addition to the accuracy of the
image segmentation, the speed is also very important for real-time image
processing applications. Many computer applications take advantages of the
multi-processor architecture to up to their running performance. However, to
run an algorithm as parallel is very difficult in many cases. Due to using the
same memory blocks, many conflicts might be happened between the processors.
Moreover, each process of one processor may depend on those of another
processor. For this reason, the algorithm to be parallelized must be suitable
to parallel. In addition, the processing traffic that is pursued by the
processors must be controlled within some parallel directives. In this paper,
we provide a parallel implementation to a hierarchical graph-based image
segmentation method by using its hierarchical processing steps. To achieve this
goal, we utilize the OpenMP (Open Multi-Processing) Library to run the
segmentation process as parallel on images of different sizes from the INRIA
Holidays dataset. The experimental results show that the parallel
implementation of the algorithm is more effective than the serial type
according to processing time.

Anahtar Kelimeler

Parallel programming Image segmentation Graph OpenMP

Kaynakça

  • [1] R. Nikhil and K. Scansar, “A review on image segmentation techniques,” Pattern Recognition, vol. 26, no. 9. pp. 12771294, 1993.
  • [2] B. Peng, L. Zhang, and D. Zhang, “A survey of graph theoretical approaches to image segmentation,” Pattern Recognit., vol. 46, no. 3, pp. 10201038, 2013.
  • [3] W. Tao, H. Jin, and Y. Zhang, “Color image segmentation based on mean shift and normalized cuts.,” IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 37, no. 5, pp. 13821389, 2007.
  • [4] J. A. Bondy, Graph Theory With Applications. Oxford, UK, UK: Elsevier Science Ltd., 1976.
  • [5] C. T. Zahn, “Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters,” IEEE Trans. Comput., vol. C$-$20, no. 1, pp. 6886, 1971.
  • [6] O. J. Morris, M. D. J. Lee, and A. G. Constantinides, “Graph Theory for Image Analysis : An Approach Based on The Shortest Spanning Tree,” Commun. Radar Signal Process. IEE Proc. F, vol. 133, no. 2, pp. 146152, 1986.
  • [7] Y. X. V. Olman, D. Xu, “Solving data clustering problem as a string search problem,” in Proc. Conf. Stat. Data Mining Know. Dis., Chapman \& Hall CRC, 2003, pp. 417434.
  • [8] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888905, 2000.
  • [9] A. Saglam and N. A. Baykan, “Sequential image segmentation based on minimum spanning tree representation,” Pattern Recognit. Lett., Available online 16 June 2016, ISSN 0167-8655, http://dx.doi.org/10.1016/j.patrec.2016.06.001.
  • [10] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” Int. J. Comput. Vis., vol. 59, no. 2, pp. 167181, 2004.
  • [11] J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proc. Am. Math. Soc., vol. 7, no. 1, pp. 4848, 1956.
  • [12] Y. Haxhimusa and W. Kropatsch, “Segmentation graph hierarchies,” Lect. Notes Comput. Sci. 3138, pp. 343351, 2004.
  • [13] O. Borůvka, “O jistém problému minimálním,” Práce Morav. přírodovědecké společnosti, no. 3, pp. 3758, 1926.
  • [14] A. Marongiu, P. Burgio, and L. Benini, “Supporting OpenMP on a multi-cluster embedded MPSoC,” in Microprocessors and Microsystems, 2011, vol. 35, no. 8, pp. 668682.
  • [15] A. Saglam, Minimum Yayilan Agac Tabanli Sirali Goruntu Bolutleme (Minimum Spanning Tree-based Sequential Image Segmentation), Master thesis, Selcuk University, Turkey, 2016.
  • [16] M. Tepper, P. Musé, A. Almansa, and M. Mejail, “Boruvka meets nearest neighbors,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, vol. 8259 LNCS, no. PART 2, pp. 560567.
  • [17] L. Dagum, E. Rameshm, and R. Menon, “OpenMP: An Industry- Standard API for Shared- Memory Programming,” Comput. Sci. {\&} Eng. IEEE, vol. 5, no. 1, pp. 4655, 1998.
  • [18] S. Zhang, Z. Xia, R. Yuan, and X. Jiang, “Parallel computation of a dam-break flow model using OpenMP on a multi-core computer,” J. Hydrol., vol. 512, pp. 126133, 2014.
  • [19] W. Jeun, Y. Kee, and S. Ha, “Improving performance of OpenMP for SMP clusters through overlapped page migrations,” in International Workshop on OpenMP (IWOMP’06, 2006.
  • [20] B. Chapman, G. Jost, and R. Van Der Pas, Using OpenMP: Portable Shared Memory Parallel Programming, vol. 10. 2008.
  • [21] Vikas, N. Giacaman, and O. Sinnen, “Multiprocessing with GUI-awareness using OpenMP-like directives in Java,” Parallel Comput., vol. 40, no. 2, pp. 6989, 2014.
  • [22] R. Van Der Pas, “An Introduction Into OpenMP,” Eur. J. Surg., vol. 160, no. 3, pp. 145151, 2005.
  • [23] E. Ayguad, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, and G. Zhang, “The design of OpenMP tasks,” IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 3, pp. 404418, 2009.
  • [24] G. Bradski, “The OpenCV Library,” Dr Dobbs J. Softw. Tools, vol. 25, pp. 120125, 2000.
  • [25] H. Jegou, M. Douze, and C. Schmid, “Hamming embedding and weak geometric consistency for large scale image search,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2008, vol. 5302 LNCS, no. PART 1, pp. 304317.

Yıl 2016, Special Issue (2016), 6 - 11, 01.12.2016

Ali Sağlam Nurdan Akhan Baykan

https://doi.org/10.18100/ijamec.271038

Öz

Kaynakça

  • [1] R. Nikhil and K. Scansar, “A review on image segmentation techniques,” Pattern Recognition, vol. 26, no. 9. pp. 12771294, 1993.
  • [2] B. Peng, L. Zhang, and D. Zhang, “A survey of graph theoretical approaches to image segmentation,” Pattern Recognit., vol. 46, no. 3, pp. 10201038, 2013.
  • [3] W. Tao, H. Jin, and Y. Zhang, “Color image segmentation based on mean shift and normalized cuts.,” IEEE Trans. Syst. Man. Cybern. B. Cybern., vol. 37, no. 5, pp. 13821389, 2007.
  • [4] J. A. Bondy, Graph Theory With Applications. Oxford, UK, UK: Elsevier Science Ltd., 1976.
  • [5] C. T. Zahn, “Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters,” IEEE Trans. Comput., vol. C$-$20, no. 1, pp. 6886, 1971.
  • [6] O. J. Morris, M. D. J. Lee, and A. G. Constantinides, “Graph Theory for Image Analysis : An Approach Based on The Shortest Spanning Tree,” Commun. Radar Signal Process. IEE Proc. F, vol. 133, no. 2, pp. 146152, 1986.
  • [7] Y. X. V. Olman, D. Xu, “Solving data clustering problem as a string search problem,” in Proc. Conf. Stat. Data Mining Know. Dis., Chapman \& Hall CRC, 2003, pp. 417434.
  • [8] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888905, 2000.
  • [9] A. Saglam and N. A. Baykan, “Sequential image segmentation based on minimum spanning tree representation,” Pattern Recognit. Lett., Available online 16 June 2016, ISSN 0167-8655, http://dx.doi.org/10.1016/j.patrec.2016.06.001.
  • [10] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” Int. J. Comput. Vis., vol. 59, no. 2, pp. 167181, 2004.
  • [11] J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proc. Am. Math. Soc., vol. 7, no. 1, pp. 4848, 1956.
  • [12] Y. Haxhimusa and W. Kropatsch, “Segmentation graph hierarchies,” Lect. Notes Comput. Sci. 3138, pp. 343351, 2004.
  • [13] O. Borůvka, “O jistém problému minimálním,” Práce Morav. přírodovědecké společnosti, no. 3, pp. 3758, 1926.
  • [14] A. Marongiu, P. Burgio, and L. Benini, “Supporting OpenMP on a multi-cluster embedded MPSoC,” in Microprocessors and Microsystems, 2011, vol. 35, no. 8, pp. 668682.
  • [15] A. Saglam, Minimum Yayilan Agac Tabanli Sirali Goruntu Bolutleme (Minimum Spanning Tree-based Sequential Image Segmentation), Master thesis, Selcuk University, Turkey, 2016.
  • [16] M. Tepper, P. Musé, A. Almansa, and M. Mejail, “Boruvka meets nearest neighbors,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, vol. 8259 LNCS, no. PART 2, pp. 560567.
  • [17] L. Dagum, E. Rameshm, and R. Menon, “OpenMP: An Industry- Standard API for Shared- Memory Programming,” Comput. Sci. {\&} Eng. IEEE, vol. 5, no. 1, pp. 4655, 1998.
  • [18] S. Zhang, Z. Xia, R. Yuan, and X. Jiang, “Parallel computation of a dam-break flow model using OpenMP on a multi-core computer,” J. Hydrol., vol. 512, pp. 126133, 2014.
  • [19] W. Jeun, Y. Kee, and S. Ha, “Improving performance of OpenMP for SMP clusters through overlapped page migrations,” in International Workshop on OpenMP (IWOMP’06, 2006.
  • [20] B. Chapman, G. Jost, and R. Van Der Pas, Using OpenMP: Portable Shared Memory Parallel Programming, vol. 10. 2008.
  • [21] Vikas, N. Giacaman, and O. Sinnen, “Multiprocessing with GUI-awareness using OpenMP-like directives in Java,” Parallel Comput., vol. 40, no. 2, pp. 6989, 2014.
  • [22] R. Van Der Pas, “An Introduction Into OpenMP,” Eur. J. Surg., vol. 160, no. 3, pp. 145151, 2005.
  • [23] E. Ayguad, N. Copty, A. Duran, J. Hoeflinger, Y. Lin, F. Massaioli, X. Teruel, P. Unnikrishnan, and G. Zhang, “The design of OpenMP tasks,” IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 3, pp. 404418, 2009.
  • [24] G. Bradski, “The OpenCV Library,” Dr Dobbs J. Softw. Tools, vol. 25, pp. 120125, 2000.
  • [25] H. Jegou, M. Douze, and C. Schmid, “Hamming embedding and weak geometric consistency for large scale image search,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2008, vol. 5302 LNCS, no. PART 1, pp. 304317.
Toplam 25 adet kaynakça vardır.

Ayrıntılar

Konular Mühendislik
Bölüm Research Article
Yazarlar

Ali Sağlam

Nurdan Akhan Baykan

Yayımlanma Tarihi 1 Aralık 2016
Yayımlandığı Sayı Yıl 2016 Special Issue (2016)

Kaynak Göster

APA Sağlam, A., & Baykan, N. A. (2016). Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers(Special Issue-1), 6-11. https://doi.org/10.18100/ijamec.271038
AMA Sağlam A, Baykan NA. Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers. Aralık 2016;(Special Issue-1):6-11. doi:10.18100/ijamec.271038
Chicago Sağlam, Ali, ve Nurdan Akhan Baykan. “Parallelization of a Hierarchical Graph-Based Image Segmentation Using OpenMP”. International Journal of Applied Mathematics Electronics and Computers, sy. Special Issue-1 (Aralık 2016): 6-11. https://doi.org/10.18100/ijamec.271038.
EndNote Sağlam A, Baykan NA (01 Aralık 2016) Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers Special Issue-1 6–11.
IEEE A. Sağlam ve N. A. Baykan, “Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP”, International Journal of Applied Mathematics Electronics and Computers, sy. Special Issue-1, ss. 6–11, Aralık 2016, doi: 10.18100/ijamec.271038.
ISNAD Sağlam, Ali - Baykan, Nurdan Akhan. “Parallelization of a Hierarchical Graph-Based Image Segmentation Using OpenMP”. International Journal of Applied Mathematics Electronics and Computers Special Issue-1 (Aralık 2016), 6-11. https://doi.org/10.18100/ijamec.271038.
JAMA Sağlam A, Baykan NA. Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers. 2016;:6–11.
MLA Sağlam, Ali ve Nurdan Akhan Baykan. “Parallelization of a Hierarchical Graph-Based Image Segmentation Using OpenMP”. International Journal of Applied Mathematics Electronics and Computers, sy. Special Issue-1, 2016, ss. 6-11, doi:10.18100/ijamec.271038.
Vancouver Sağlam A, Baykan NA. Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers. 2016(Special Issue-1):6-11.

Creative Commons License

Address: Selcuk University, Faculty of Technology 42031 Selcuklu, Konya/TURKEY.