Parallelization of a Hierarchical Graph-Based Image Segmentation using OpenMP

Abstract

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.

Keywords

• Parallel programming,Image segmentation,Graph,OpenMP

References

1. [1] R. Nikhil and K. Scansar, “A review on image segmentation techniques,” Pattern Recognition, vol. 26, no. 9. pp. 12771294, 1993.
2. [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. [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. [4] J. A. Bondy, Graph Theory With Applications. Oxford, UK, UK: Elsevier Science Ltd., 1976.
5. [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. [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. [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. [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. [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. [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. [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. [12] Y. Haxhimusa and W. Kropatsch, “Segmentation graph hierarchies,” Lect. Notes Comput. Sci. 3138, pp. 343351, 2004.
13. [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. [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. [15] A. Saglam, Minimum Yayilan Agac Tabanli Sirali Goruntu Bolutleme (Minimum Spanning Tree-based Sequential Image Segmentation), Master thesis, Selcuk University, Turkey, 2016.
16. [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. [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. [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. [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. [20] B. Chapman, G. Jost, and R. Van Der Pas, Using OpenMP: Portable Shared Memory Parallel Programming, vol. 10. 2008.
21. [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. [22] R. Van Der Pas, “An Introduction Into OpenMP,” Eur. J. Surg., vol. 160, no. 3, pp. 145151, 2005.
23. [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. [24] G. Bradski, “The OpenCV Library,” Dr Dobbs J. Softw. Tools, vol. 25, pp. 120125, 2000.
25. [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.