Abstract

Partitioning the image into meaningful groups is one of the major task in image analysis which can be achieved using the unsupervised clustering algorithm. K-means algorithm is one of the popular unsupervised clustering algorithm. The K-means algorithm is time-consuming and requires intensive computation for a large data set as the input is compared with all the centroids. Also, the data needs to be stored internally due to iterative re-assignment process. An architecture to enhance the speed of clustering operation using minimal hardware for K-means clustering without any internal storage is proposed and implemented using Virtex 6 FPGA. A new methodology is proposed to reduce the distance computation. The performance of the architecture is 203fps for a grayscale image size of 256X256 and 102fps for a grayscale image of size 512X512. This shows that the proposed architecture can be used for real time image segmentation.

References

• J. B. MacQueen, 1967 “Some methods for classification and analysis of multivariate observation”, In: Le Cam, L.M., Neyman, J. (Eds.), University of California.
• Yang, Bo, Xiao Fu, Nicholas D. Sidiropoulos, and Mingyi Hong. "Towards k-means-friendly spaces: Simultaneous deep learning and clustering." In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 3861-3870. JMLR. Org, 2017.
• Windarto, Agus Perdana. "Implementation of Data Mining on Rice Imports by Major Country of Origin Using Algorithm Using K-Means Clustering Method." International Journal of Artificial Intelligence Research 1, no. 2 (2017).
• Jiang, Xiaoping, Chenghua Li, and Jing Sun. "A modified K-means clustering for mining of multimedia databases based on dimensionality reduction and similarity measures." Cluster Computing (2017): 1-8.
• G. d. S. Filho, A. C. Frery, C. C. de Araújo, H. Alice, J. Cerqueira,J. A. Loureiro, M. E. de Lima, M. d. G. S. Oliveira, and M. M. Horta, “Hyperspectral images clustering on reconfigurable hardware using the K-means algorithm,” in Proc. Symp. Integr. Circuits Syst. Des., Sep.2003, pp. 99–104.
• Saegusa T, Maruyama T.: ‘An FPGA implementation of real-time K-means clustering for color images’. Journal of Real-Time Image Processing. 2007 Dec 1; 2(4):309-18.
• Maruyama, Tsutomu. "Real-time k-means clustering for color images on reconfigurable hardware." In 18th International Conference on Pattern Recognition (ICPR'06), vol. 2, pp. 816-819. IEEE, 2006.
• Chen, Tse-Wei, and Shao-Yi Chien.: "Bandwidth adaptive hardware architecture of K-means clustering for video analysis." IEEE transactions on very large scale integration (VLSI) systems 18, no. 6 (2009): 957-966.
• Chen, Tse-Wei, and Shao-Yi Chien. "Flexible hardware architecture of hierarchical K-means clustering for large cluster number." IEEE transactions on very large scale integration (VLSI) systems 19, no. 8 (2010): 1336-1345.
• T.-W. Chen, Y.-L. Chen and S.-Y. Chien, “Fast image segmentation based on K-Means clustering with histograms in HSV color space,” in Proceedings of IEEE International Workshop on Multimedia Signal Processing, Oct. 2008, pp. 322–325.
• AC Frery, CCde Araujo, H Alice “Hyperspectral images clustering on reconfigurable hardware using the K-Means algorithm” in Proc. IEEE Int. Symp. Circuits Syst., Sep 2003, pp. 94–104
• B. Maliatski and O. Yadid-Pecht, “Hardware-driven adaptive K-means clustering for real-time video imaging,” IEEE Trans. Circuits Syst.Video Technol., vol. 15, no. 1, pp. 164–166, Jan. 2005.
• Huang and D.-H. Liu, “Segmentation of color image using EM algorithm in HSV color space,” in Proceedings of IEEE International Conference on Information Acquisition, Jul. 2007, pp. 316–319.
• S. J. Redmond, C. Heneghan, “A method for initializing the K-means clustering algorithm using kd-trees. Science direct”, Pattern Recognition Letters 28 (2007) 965–973
• T.-W. Chen, C.-H. Sun, J.-Y. Bai, H.-R. Chen, and S.-Y. Chien, “Architectural analyses of K-Means silicon intellectual property for image segmentation,” in Proc. IEEE Int. Symp. Circuits Syst., May 2008, pp. 2578–2581.
• Anuradha, M. G., and L. Basavaraj. "Design and Implementation of High Speed VLSI Architecture of Online Clustering Algorithm for Image Analysis." Data Engineering and Intelligent Computing. Springer, Singapore, 2018. Pp. 197-206.