Call for Paper

CAE solicits original research papers for the July 2023 Edition. Last date of manuscript submission is June 30, 2023.

Read More

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

SocButtons v1.5

Anuradha M. G. Basavaraj L.. Published in Image Processing.

FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis
Communications on Applied Electronics
Year of Publication: 2019
Publisher: Foundation of Computer Science (FCS), NY, USA
Series: Volume 7 Number 30
Authors: Anuradha M. G. Basavaraj L.
10.5120/cae2019652832
Download full text

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

  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.

Keywords

Clustering, FPGA, Image segmentation, K-Means, Machine learning.