A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images

Tiantai Deng*, Daniel Crookes, Fahad Siddiqui, Roger Woods

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

142 Downloads (Pure)

Abstract

As an unsupervised machine-learning algorithm, K-means clustering for images has been widely used in image segmentation. The standard Lloyd’s algorithm iteratively allocates all image pixels to clusters until convergence. The processing requirement can be a problem for high-resolution images and/or real-time systems. In this paper, we present a new histogram-based algorithm for K-means clustering, and its FPGA implementation. Once the histogram has been constructed, the algorithm is O(GL) for each iteration, where GL is the number of grey levels. On a Xilinx ZedBoard, our algorithm achieves 140 FPS (640 × 480 images, running at 150 MHz, 4 clusters, 25 iterations), including final image reconstruction. At 100 MHz, it achieves 95 FPS. It is 7.6 times faster than the standard Lloyd’s algorithm, but uses only approximately half of the resources, while giving the same results. The more iterations, the bigger the speed-up. For 50 iterations, our algorithm is 10.2 times faster than the Lloyd’s approach. Thus for all cases our algorithm achieves real time performance whereas Lloyd’s struggles to do so. The number of clusters (up to a user-defined limit) and the initialization method (one of three) can be selected at runtime.

Original languageEnglish
Title of host publicationIntelligent Computing and Internet of Things
Subtitle of host publicationFirst International Conference on Intelligent Manufacturing and Internet of Things and 5th International Conference on Computing for Sustainable Energy and Environment, Chongqing, China, September 21-23, 2018
EditorsZhile Yang, Dongsheng Yang, Kang Li, Minrui Fei, Dajun Du
PublisherSpringer-Verlag
Pages468-477
Number of pages10
Volume924
ISBN (Print)9789811323836
DOIs
Publication statusPublished - 2018
Event1st International Conference on Intelligent Manufacturing and Internet of Things, IMIOT 2018 and International Conference on Intelligent Computing for Sustainable Energy and Environment, ICSEE 2018 - Chogqing, China
Duration: 21 Sep 201823 Sep 2018

Publication series

NameCommunications in Computer and Information Science
Volume924
ISSN (Print)1865-0929

Conference

Conference1st International Conference on Intelligent Manufacturing and Internet of Things, IMIOT 2018 and International Conference on Intelligent Computing for Sustainable Energy and Environment, ICSEE 2018
CountryChina
CityChogqing
Period21/09/201823/09/2018

    Fingerprint

Keywords

  • Data processing
  • FPGA acceleration
  • K-means clustering
  • Unsupervised machine learning

Cite this

Deng, T., Crookes, D., Siddiqui, F., & Woods, R. (2018). A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images. In Z. Yang, D. Yang, K. Li, M. Fei, & D. Du (Eds.), Intelligent Computing and Internet of Things: First International Conference on Intelligent Manufacturing and Internet of Things and 5th International Conference on Computing for Sustainable Energy and Environment, Chongqing, China, September 21-23, 2018 (Vol. 924, pp. 468-477). (Communications in Computer and Information Science; Vol. 924). Springer-Verlag. https://doi.org/10.1007/978-981-13-2384-3_44