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

Tiantai Deng; Daniel Crookes; Fahad  Siddiqui; Roger Woods

doi:10.1007/978-981-13-2384-3_44

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

School of Electronics, Electrical Engineering and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

444 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 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	https://doi.org/10.1007/978-981-13-2384-3_44
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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-981-13-2384-3_44Licence: Unspecified

A New Real-time FPGA-based Implementation of K-means Clustering for Images
Copyright 2018 Springer. This work is made available online in accordance with the publisher’s policies. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 831 KBLicence: Unspecified

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

Deng, Tiantai ; Crookes, Daniel ; Siddiqui, Fahad ; Woods, Roger. / A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images. 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. editor / Zhile Yang ; Dongsheng Yang ; Kang Li ; Minrui Fei ; Dajun Du. Vol. 924 Springer-Verlag, 2018. pp. 468-477 (Communications in Computer and Information Science).

@inproceedings{c0a9b9d370a843ba8bd0a72b4e9d9e88,

title = "A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images",

abstract = "As an unsupervised machine-learning algorithm, K-means clustering for images has been widely used in image segmentation. The standard Lloyd{\textquoteright}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{\^A} ×{\^A} 480 images, running at 150{\^A} MHz, 4 clusters, 25 iterations), including final image reconstruction. At 100{\^A} MHz, it achieves 95{\^A} FPS. It is 7.6 times faster than the standard Lloyd{\textquoteright}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{\textquoteright}s approach. Thus for all cases our algorithm achieves real time performance whereas Lloyd{\textquoteright}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.",

keywords = "Data processing, FPGA acceleration, K-means clustering, Unsupervised machine learning",

author = "Tiantai Deng and Daniel Crookes and Fahad Siddiqui and Roger Woods",

year = "2018",

doi = "10.1007/978-981-13-2384-3_44",

language = "English",

isbn = "9789811323836",

volume = "924",

series = "Communications in Computer and Information Science",

publisher = "Springer-Verlag",

pages = "468--477",

editor = "Zhile Yang and Dongsheng Yang and Kang Li and Minrui Fei and Dajun Du",

booktitle = "Intelligent Computing and Internet of Things",

note = "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 ; Conference date: 21-09-2018 Through 23-09-2018",

}

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, Communications in Computer and Information Science, vol. 924, Springer-Verlag, pp. 468-477, 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, 21/09/2018. https://doi.org/10.1007/978-981-13-2384-3_44

A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images. / Deng, Tiantai; Crookes, Daniel; Siddiqui, Fahad ; Woods, Roger.

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. ed. / Zhile Yang; Dongsheng Yang; Kang Li; Minrui Fei; Dajun Du. Vol. 924 Springer-Verlag, 2018. p. 468-477 (Communications in Computer and Information Science; Vol. 924).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Deng, Tiantai

AU - Crookes, Daniel

AU - Siddiqui, Fahad

AU - Woods, Roger

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Data processing

KW - FPGA acceleration

KW - K-means clustering

KW - Unsupervised machine learning

UR - http://www.scopus.com/inward/record.url?scp=85053925839&partnerID=8YFLogxK

U2 - 10.1007/978-981-13-2384-3_44

DO - 10.1007/978-981-13-2384-3_44

M3 - Conference contribution

AN - SCOPUS:85053925839

SN - 9789811323836

VL - 924

T3 - Communications in Computer and Information Science

SP - 468

EP - 477

BT - Intelligent Computing and Internet of Things

A2 - Yang, Zhile

A2 - Yang, Dongsheng

A2 - Li, Kang

A2 - Fei, Minrui

A2 - Du, Dajun

PB - Springer-Verlag

T2 - 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

Y2 - 21 September 2018 through 23 September 2018

ER -

Deng T, Crookes D, Siddiqui F , Woods R. A New Real-Time FPGA-Based Implementation of K-Means Clustering for Images. In Yang Z, Yang D, Li K, Fei M, Du D, editors, 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. Springer-Verlag. 2018. p. 468-477. (Communications in Computer and Information Science). https://doi.org/10.1007/978-981-13-2384-3_44

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

A soft coprocessor approach to the development of image and video processing applications on FPGAs

Cite this

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

UN SDGs

Access to Document

Other files and links

Fingerprint

Student theses

A soft coprocessor approach to the development of image and video processing applications on FPGAs

Cite this