CFP last date
28 May 2025
Call for Paper
June Edition
CAE solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 28 May 2025

Submit your paper
Know more
The week's pick
Responsive image
Property (Land) Registration Management Using Blockchain in Nigeria

A. Festus Osuolale Ojebiyi David-Daniel Seriki Oluwasogo
Random Articles
Reseach Article

FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis

by Anuradha M. G. Basavaraj L.
journal cover thumbnail

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

@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 = { Aug 2019 },
volume = { 7 },
number = { 30 },
month = { Aug },
year = { 2019 },
issn = { 2394-4714 },
pages = { 5-10 },
numpages = {9},
url = { https://www.caeaccess.org/archives/volume7/number30/857-2019652832/ },
doi = { 10.5120/cae2019652832 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-09-04T20:02:35.033619+05:30
%A Anuradha M. G. Basavaraj L.
%T FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis
%J Communications on Applied Electronics
%@ 2394-4714
%V 7
%N 30
%P 5-10
%D 2019
%I Foundation of Computer Science (FCS), NY, 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
  1. J. B. MacQueen, 1967 “Some methods for classification and analysis of multivariate observation”, In: Le Cam, L.M., Neyman, J. (Eds.), University of California.
  2. 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.
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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
  12. 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.
  13. 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.
  14. 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
  15. 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.
  16. 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

Computer Science
Information Sciences

Keywords

Clustering FPGA Image segmentation K-Means Machine learning.

Powered by PhDFocusTM