Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP

Ali Sağlam [1] , Nurdan Akhan Baykan [2]


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.
Parallel programming, Image segmentation, Graph, OpenMP
  • [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.
Subjects Engineering
Journal Section Research Article
Authors

Orcid: orcid.org/0000-0003-2980-9666
Author: Ali Sağlam
Institution: SELCUK UNIV
Country: Turkey


Author: Nurdan Akhan Baykan
Institution: SELCUK UNIV
Country: Turkey


Dates

Publication Date : December 1, 2016

Bibtex @research article { ijamec271038, journal = {International Journal of Applied Mathematics Electronics and Computers}, issn = {}, eissn = {2147-8228}, address = {}, publisher = {Selcuk University}, year = {2016}, volume = {}, pages = {6 - 11}, doi = {10.18100/ijamec.271038}, title = {Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP}, key = {cite}, author = {Sağlam, Ali and Baykan, Nurdan Akhan} }
APA Sağlam, A , Baykan, N . (2016). Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers , (Special Issue-1) , 6-11 . DOI: 10.18100/ijamec.271038
MLA Sağlam, A , Baykan, N . "Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP". International Journal of Applied Mathematics Electronics and Computers (2016 ): 6-11 <https://dergipark.org.tr/en/pub/ijamec/issue/25619/271038>
Chicago Sağlam, A , Baykan, N . "Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP". International Journal of Applied Mathematics Electronics and Computers (2016 ): 6-11
RIS TY - JOUR T1 - Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP AU - Ali Sağlam , Nurdan Akhan Baykan Y1 - 2016 PY - 2016 N1 - doi: 10.18100/ijamec.271038 DO - 10.18100/ijamec.271038 T2 - International Journal of Applied Mathematics Electronics and Computers JF - Journal JO - JOR SP - 6 EP - 11 VL - IS - Special Issue-1 SN - -2147-8228 M3 - doi: 10.18100/ijamec.271038 UR - https://doi.org/10.18100/ijamec.271038 Y2 - 2016 ER -
EndNote %0 International Journal of Applied Mathematics Electronics and Computers Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP %A Ali Sağlam , Nurdan Akhan Baykan %T Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP %D 2016 %J International Journal of Applied Mathematics Electronics and Computers %P -2147-8228 %V %N Special Issue-1 %R doi: 10.18100/ijamec.271038 %U 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 (December 2016): 6-11 . https://doi.org/10.18100/ijamec.271038
AMA Sağlam A , Baykan N . Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers. 2016; (Special Issue-1): 6-11.
Vancouver Sağlam A , Baykan N . Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP. International Journal of Applied Mathematics Electronics and Computers. 2016; (Special Issue-1): 11-6.