PARALLEL K-MEANS CLUSTERING WITH NAÏVE SHARDING FOR UNSUPERVISED IMAGE SEGMENTATION VIA MPI

Öz

In digital image processing, image segmentation is an essential step in which an image is partitioned into groups of pixels. k-means clustering algorithm, which is often considered as fast and efficient, is one of the most widely used clustering algorithms to segment an image. However, as the problem size gets larger, the k-means starts to spend a significant amount of time to process. At this point, parallelization techniques should be applied to reduce the required time. Designing an efficient parallel and distributed model is not a trivial job since it should correspond to the parallel computer architecture and take communication and load balancing among processors into account. In this study, we propose a parallel and distributed k-means clustering algorithm with naive sharding centroid initialization for image segmentation. The proposed algorithm adopts the Message Passing Interface (MPI) standard to take advantage of the computational power of distributed computing nodes in a High Performance Computing Cluster. We demonstrate the parallel scalability of the proposed algorithm using up to 128 cores that achieves approximately 104 times faster clustering time.

Anahtar Kelimeler

• clustering
• image segmentation
• K-means clustering
• distributed memory
• parallel computing

DENETİMSİZ GÖRÜNTÜ BÖLÜTLEME İÇİN NAÏVE SHARDING İLE MPI KULLANARAK PARALEL K-MEANS KÜMELEMESİ

Öz

Dijital görüntü işlemede, görüntü bölütleme, görüntünün piksel gruplarına ayrıldığı önemli bir adımdır. Verimli bir kümeleme algoritması kabul edilen k-means algoritması, bir görüntüyü bölümlere ayırmak için en yaygın kullanılan kümeleme algoritmalarından birisidir. Bununla birlikte, problem boyutu büyüdükçe, k-means, görüntü işlemek için önemli miktarda zaman harcamaya başlar. Bu noktada, gerekli zamanı azaltmak için paralelleştirme teknikleri uygulanmalıdır. Verimli bir paralel ve dağıtılmış model tasarlamak, paralel bilgisayar mimarisini karşılayabilmesi ve işlemciler arasındaki iletişim ve yük dengelemesini dikkate alması nedeniyle önemli bir iştir. Bu çalışmada, görüntü bölütlemesi için naïve sharding kullanarak orta nokta belirleme ile paralel ve dağıtılmış bir k-means kümeleme algoritması öneriyoruz. Önerilen algoritma, Yüksek Performanslı Bilgi İşleme Kümesindeki dağıtılmış bilgi işleme düğümlerinin hesaplama gücünden yararlanmak için Mesaj Geçirme Arayüzü (MGA) standardını kullanır. 128 adede kadar çekirdek kullanarak 104.23 kat daha hızlı kümeleme süresi sağlayan önerilen algoritmanın paralel ölçeklenebilirliğini gösterdik.

Anahtar Kelimeler

• Kümeleme
• Görüntü Bölütleme
• K-means Kümeleme
• Dağıtılmış Bellek
• Paralel İşleme

Kaynakça

1. Backer, M., Tünnermann, J., Mertsching, B., 2013. Parallel k-means image segmentation using sort, scan and connected components on a gpu. Springer, Facing the multicore-challenge III, 108–120.
2. Bhimani, J., Leeser, M., Mi, N., 2015. Accelerating k-means clustering with parallel implementations and gpu computing. IEEE, 2015 IEEE High Performance Extreme Computing Conference (HPEC), 1–6.
3. Bose, S., Mukherjee, A., Chakraborty, S., Samanta, S., Dey, N., et al., 2013. Parallel image segmentation using multi-threading and k-means algorithm. IEEE, 2013 IEEE International Conference on Computational Intelligence and Computing Research, 1–5.
4. Delmerico, J. A., David, P., Corso, J. J., 2011. Building facade detection, segmentation, and parameter estimation for mobile robot localization and guidance. IEEE, 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1632–1639.
5. Dhanachandra, N., Manglem, K., Chanu, Y. J., 2015. Image segmentation using k-means clustering algorithm and subtractive clustering algorithm. Procedia Computer Science, 54, 764–771.
6. Dhillon, I. S., Modha, D. S., 2002. A data-clustering algorithm on distributed memory multiprocessors. Springer, Large-scale parallel data mining, 245–260.
7. Forouzanfar, M., Forghani, N., Teshnehlab, M., 2010. Parameter optimization of improved fuzzy c-means clustering algorithm for brain mr image segmentation. Engineering Applications of Artificial Intelligence, 23(2), 160–168.
8. Jain, A. K., Dubes, R. C., et al., 1988. Algorithms for clustering data, volume 6. Prentice hall Englewood Cliffs.

9. Joshi, M. N., 2003. Parallel k-means algorithm on distributed memory multiprocessors. Computer, 9.
10. Kantabutra, S., Couch, A. L., 2000. Parallel k-means clustering algorithm on nows. NECTEC Technical journal, 1(6), 243–247.
11. Khan, J. F., Bhuiyan, S. M., Adhami, R. R., 2010. Image segmentation and shape analysis for road-sign detection. IEEE Transactions on Intelligent Transportation Systems, 12(1), 83–96.
12. Mayo, M. M., 2016. An arithmetic-based deterministic centroid initialization method for the k-means clustering algorithm. Columbus State University ePress.
13. Ng, H., Ong, S., Foong, K., Goh, P., Nowinski, W., 2006. Medical image segmentation using k-means clustering and improved watershed algorithm. IEEE, 2006 IEEE Southwest Symposium on Image Analysis and Interpretation, 61–65.
14. Olson, C. F., 1995. Parallel algorithms for hierarchical clustering. Parallel computing, 21(8), 1313–1325.
15. Onder, A. S., Goksu, T., 2019. Real-time natural stone classification with opencl and performance analysis. Muhendislik Bilimleri ve Tasarim Dergisi, 7, 689 – 698.
16. Rasmussen, E. M., Willett, P., 1989. Efficiency of hierarchic agglomerative clustering using the icl distributed array processor. Journal of Documentation, 45(1), 1–24.
17. Sirotkovic,´ J., Dujmic,´ H., and Papic,´ V. (2012). K-means image segmentation on massively parallel gpu architecture. IEEE, 2012 Proceedings of the 35th International Convention MIPRO, 489–494.
18. Stoffel, K., Belkoniene, A., 1999. Parallel k/h-means clustering for large data sets. Springer, European Conference on Parallel Processing, 1451–1454.
19. Tu, Z., Chen, X., Yuille, A. L., Zhu, S.-C., 2005. Image parsing: Unifying segmentation, detection, and recognition. International Journal of computer vision, 63(2), 113–140.
20. Wang, H., Zhao, J., Li, H., Wang, J., 2008. Parallel clustering algorithms for image processing on multi-core cpus. IEEE, 2008 International Conference on Computer Science and Software Engineering, volume 3, 450–453.
21. Xu, S., Zhang, J., 2004. A parallel hybrid web document clustering algorithm and its performance study. The Journal of Supercomputing, 30(2), 117–131.
22. Yildiz, M. S., Kekezoglu, B., Isen, E., 2019. Determination of maintenance strategy for power transformers with k-means clustering method. Muhendislik Bilimleri ve Tasarim Dergisi, 7, 505 – 513.
23. Zhang, J., Wu, G., Hu, X., Li, S., Hao, S., 2011. A parallel k-means clustering algorithm with mpi. IEEE, 2011 Fourth International Symposium on Parallel Architectures, Algorithms and Programming, 60–64.
24. Zhao, W., Ma, H., He, Q., 2009. Parallel k-means clustering based on mapreduce. Springer, IEEE International Conference on Cloud Computing, 674–679.