Analysis of Segmentation Parameters Effect towards Parallel Processing Time on Fuzzy C Means Algorithm

Cepi Ramdani; Indah Soesanti; Sunu Wibirama

doi:10.22146/ijitee.35025

Analysis of Segmentation Parameters Effect towards Parallel Processing Time on Fuzzy C Means Algorithm

https://doi.org/10.22146/ijitee.35025

Cepi Ramdani^(1*), Indah Soesanti⁽²⁾, Sunu Wibirama⁽³⁾

(1) Department of Electrical Engineering and Information Technology, Universitas Gadjah Mada
(2) Department of Electrical Engineering and Information Technology, Universitas Gadjah Mada
(3) Department of Electrical Engineering and Information Technology, Universitas Gadjah Mada
(*) Corresponding Author

Abstract

Fuzzy C Means algorithm or FCM is one of many clustering algorithms that has better accuracy to solve problems related to segmentation. Its application is almost in every aspects of life and many disciplines of science. However, this algorithm has some shortcomings, one of them is the large amount of processing time consumption. This research conducted mainly to do an analysis about the effect of segmentation parameters towards processing time in sequential and parallel. The other goal is to reduce the processing time of segmentation process using parallel approach. Parallel processing applied on Nvidia GeForce GT540M GPU using CUDA v8.0 framework. The experiment conducted on natural RGB color image sized 256x256 and 512x512. The settings of segmentation parameter values were done as follows, weight in range (2-3), number of iteration (50-150), number of cluster (2-8), and error tolerance or epsilon (0.1 – 1e-06). The results obtained by this research as follows, parallel processing time is faster 4.5 times than sequential time with similarity level of image segmentations generated both of processing types is 100%. The influence of segmentation parameter values towards processing times in sequential and parallel can be concluded as follows, the greater value of weight parameter then the sequential processing time becomes short, however it has no effects on parallel processing time. For iteration and cluster parameters, the greater their values will make processing time consuming in sequential and parallel become large. Meanwhile the epsilon parameter has no effect or has an unpredictable tendency on both of processing time.

Keywords

FCM, Processing Time. Segmentation Parameters, Parallel Processing, Fuzzy C Means

Full Text:

PDF

References

[1] P. N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, Boston: Pearson Addison-Wesley, 2006.

[2] H. Shaaban, A. Habib, F. Obaid, “Performance Evaluation of K-Mean and Fuzzy C-Mean Image Segmentation Based Clustering Classifier”, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 6, No. 12, pp.176-183, 2015.

[3] M. Al-Ayyoub, A. M. Abu-Dalo, Y. Jararweh, M. Jarrah, and M. Al Sa’D, “A GPU-based Implementations of the Fuzzy C-Means Algorithms for Medical Image Segmentation,” Journal of Supercomputing, Vol. 71, No. 8, pp. 3149–3162, 2015.

[4] W. Cai, S. Chen, and D. Zhang, “Fast and Robust Fuzzy C-Means Clustering Algorithms Incorporating Local Information for Image Segmentation,” Pattern Recognition, Vol. 40, Issue 3, pp. 825–838, 2007.

[5] M. A. Balafar, “Fuzzy C-mean Based Brain MRI Segmentation Algorithms,” Artificial Intelligence Review, Vol. 41, No. 3, pp. 441–449, 2014.

[6] H. Li, Z. Yang, and H. He, “An Improved Image Segmentation Algorithm Based on GPU Parallel Computing,” Journal of Software, Vol. 9, No. 8, pp. 1985–1990, 2014.

[7] M. A. Shehab, M. Al-Ayyoub, and Y. Jararweh, “Improving FCM and T2FCM Algorithms Performance Using GPUs for Medical Images Segmentation,” 6th International Conference on Information and Communication Systems, ICICS 2015, 2015, pp. 130–135.

[8] M. A. Alsmirat, Y. Jararweh, M. Al-Ayyoub, M. A. Shehab, and B. B. Gupta, “Accelerating Compute Intensive Medical Imaging Segmentation Algorithms Using Hybrid CPU-GPU Implementations,” Multimedia Tools and Applications, Vol. 76, No. 3, pp. 3537–3555, 2017.

[9] M. Al-Ayyoub, M. A. Shehab, Q. Yaseen, and Y. Jararweh, “Accelerating Clustering Algorithms Using GPUs,” Conference: 2016 IEEE High Performance Extreme Computing Conference (HPEC-2016), 2016, pp. 1–2.

[10] N. Whitehead and A. F. Florea. (2011) Floating Point and IEEE-754 Compliance for NVIDIA GPUs, [Online], http://docs.nvidia.com/ cuda/floating-point/index.html, access date: 14 November 2017.

[11] L. Lalaoui, T. Mohamadi, and A. Djaalab, “New Method for Image Segmentation,” Procedia - Social and Behavioral Sciences, Vol. 195, pp. 1971–1980, 2015.

[12] M. S. H. Al-Tamimi and G. Sulong, “Tumor Brain Detection Through MR Images: A Review of Literature,” Journal of Theoretical and Applied Information Technology., Vol. 62, No. 2, pp. 387–403, 2014.

[13] N. A. Ali, B. Cherradi, A. El Abbassi, O. Bouattane, and M. Youssfi, “New Parallel Hybrid Implementation of Bias Correction Fuzzy C-Means Algorithm,” Proceedings - 3rd International Conference on Advanced Technologies for Signal and Image Processing, ATSIP 2017, Vol. 1, pp. 1–6, 2017.

[14] N. Aitali, B. Cherradi, and A. El Abbassi, “GPU Based Implementation of Spatial Fuzzy C-Means Algorithm for Image Segmentation,” Information Science and Technology, 2016 4th IEEE International Colloquium, 2016, pp. 460–464.

[15] M. Almazrooie, M. Vadiveloo, and R. Abdullah, “GPU-Based Fuzzy C-Means Clustering Algorithm for Image Segmentation,” Arxiv preprint arXiv:1201.2050, 2016, pp. 1–13.

[16] K.Chuang, H.Tzeng, S.Chen, J.Wu, T.Chen, “Fuzzy C-Means Clustering with Spatial Information for Image Segmentation,” Computerized Medical Imaging and Graphics, Vol. 30, pp. 9-15, 2006.

[17] E. Smistad, T. L. Falch, M. Bozorgi, A. C. Elster, and F. Lindseth, “Medical Image Segmentation on GPUs - A Comprehensive Review,” Medical Image Analysis, Vol. 20, No. 1, pp. 1–18, 2015.

[18] H. L. Khor, S. C. Liew, and J. M. Zain, “A Review on Parallel Medical Image Processing on GPU,” 2015 4th International Conference on Software Engineering and Computer Systems (ICSECS), Vol. 17, No. 8, pp. 45–48, 2015.

[19] P. Afshani and N. Sitchinava, “Sorting and Permuting without Bank Conflicts on GPUs,” 23rd Annual European Symposium, 2015, Vol. 9294, pp. 13–24.

[20] X. Mei and X. Chu, “Dissecting GPU Memory Hierarchy Through Micro benchmarking”, IEEE Transactions on Parallel and Distributed Systems, Vol. 28, No. 1, pp. 72–86, 2017.

[21] Will Landau, (2013) CUDA C: race conditions, atomics, locks, mutex, and warps, [Online], https://wlandau.github.io/gpu/lectures/cudac-atomics/cudac-atomics.pdf, Retrieved 28 June 2016.

[22] James Balfour, (2011) CUDA Threads and Atomics, [Online], https://mc.stanford.edu/cgi-bin/images/3/34/Darve_cme343_cuda_3 .pdf, Retrieved 14 November 2017.

[23] R. T. Wahyuni, D. Prastiyanto, and E. Supraptono, “Penerapan Algoritma Cosine Similarity dan Pembobotan TF-IDF pada Sistem Klasifikasi Dokumen Skripsi,” Jurnal Teknik Elektro Universitas Negeri Semarang, Vol. 9, No. 1, pp. 18–23, 2017.

[24] R. V. Imbar, Adelia, M. Ayub, and A. Rehatta, “Implementasi Cosine Similarity dan Algoritma Smith-Waterman untuk Mendeteksi Kemiripan Teks,” Jurnal Informatika, Vol. 10, No. 1, pp. 31–42, 2014.

[25] Sugiyamto, B. Surarso, and A. Sugiharto, “Analisa Performa Metode Cosine dan Jacard pada Pengujian Kesamaan Dokumen,” Jurnal Masyarakat Informatika, Vol. 5, No. 10, pp. 1–8, 2014.

DOI: https://doi.org/10.22146/ijitee.35025