The week's pick
Reseach Article
FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis
| Communications on Applied Electronics |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 7 - Number 30 |
| Year of Publication: 2019 |
| Authors: Anuradha M. G. Basavaraj L. |
10.5120/cae2019652832
|
Anuradha M. G. Basavaraj L. . FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis. Communications on Applied Electronics. 7, 30 ( Aug 2019), 5-10. DOI=10.5120/cae2019652832
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.
Index Terms
Keywords