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 language | English |
---|---|
Title of host publication | Intelligent Computing and Internet of Things |
Subtitle of host publication | 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 |
Editors | Zhile Yang, Dongsheng Yang, Kang Li, Minrui Fei, Dajun Du |
Publisher | Springer-Verlag |
Pages | 468-477 |
Number of pages | 10 |
Volume | 924 |
ISBN (Print) | 9789811323836 |
DOIs | |
Publication status | Published - 2018 |
Event | 1st 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 2018 → 23 Sep 2018 |
Publication series
Name | Communications in Computer and Information Science |
---|---|
Volume | 924 |
ISSN (Print) | 1865-0929 |
Conference
Conference | 1st International Conference on Intelligent Manufacturing and Internet of Things, IMIOT 2018 and International Conference on Intelligent Computing for Sustainable Energy and Environment, ICSEE 2018 |
---|---|
Country/Territory | China |
City | Chogqing |
Period | 21/09/2018 → 23/09/2018 |
Keywords
- Data processing
- FPGA acceleration
- K-means clustering
- Unsupervised machine learning
ASJC Scopus subject areas
- Computer Science(all)
- Mathematics(all)
- Electrical and Electronic Engineering
- Signal Processing
Fingerprint
Dive into the research topics of 'A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images'. Together they form a unique fingerprint.Student theses
-
A soft coprocessor approach to the development of image and video processing applications on FPGAs
Author: Deng, T., Jul 2020Supervisor: McAllister, J. (Supervisor) & Woods, R. (Supervisor)
Student thesis: Doctoral Thesis › Doctor of Philosophy