Call for Paper
CAE solicits original research papers for the July 2023 Edition. Last date of manuscript submission is June 30, 2023.
FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis
Anuradha Basavaraj M G L.. FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis. Communications on Applied Electronics 7(30):5-10, August 2019. BibTeX
@article{10.5120/cae2019652832, author = {Anuradha M. G. Basavaraj L.}, title = {FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis}, journal = {Communications on Applied Electronics}, issue_date = {August 2019}, volume = {7}, number = {30}, month = {Aug}, year = {2019}, issn = {2394-4714}, pages = {5-10}, numpages = {6}, url = {http://www.caeaccess.org/archives/volume7/number30/857-2019652832}, doi = {10.5120/cae2019652832}, publisher = {Foundation of Computer Science (FCS), NY, USA}, address = {New York, USA} }
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.
Keywords
Clustering, FPGA, Image segmentation, K-Means, Machine learning.