An FPGA Implementation of K-Means Clustering for Color Images Based on Kd-Tree

Published 1 January 2006

Takashi Saegusa, Tsutomu Maruyama

DOI10.1109/fpl.2006.311268

Citations37

TL;DR

In this paper, an FPGA implementation of k-means clustering for color images is described and the performance for 512 times 512 and 640 times 480 pixel images (24-bit full color RGB) is more than 30 fps.

Abstract

K-means clustering is a very popular clustering technique, which is used in numerous applications. In the simple k-means clustering algorithm, each point in the dataset is compared with centers of all clusters. This comparison is a very time consuming task, particularly for large dataset and large number of clusters. In order to achieve high performance, we need to filter out clusters which have to be compared with each point efficiently. In this paper, we describe an FPGA implementation of k-means clustering for color images. In our implementation, clusters are filtered out using kd-trees which are dynamically generated on the FPGA in each iteration of k-means clustering. With one XC2V6000, the performance for 512 times 512 and 640 times 480 pixel images (24-bit full color RGB) is more than 30 fps, and 20 - 30 fps for 756 times 512 pixel images in average when dividing to 256 clusters

Keywords

Computer Science

IEEE Transactions on Pattern Analysis and Machine IntelligenceAn efficient k-means clustering algorithm: analysis and implementation

5,568 Citations2002Tapas Kanungo, David M. Mount +4 more

This work presents a simple and efficient implementation of Lloyd's k-means clustering algorithm, which it calls the filtering algorithm, and establishes the practical efficiency of the algorithm's running time.

Algorithmic transformations in the implementation of K- means clustering on reconfigurable hardware

126 Citations2001Mike Estlick, Miriam Leeser +2 more

In mapping the k-means algorithm to FPGA hardware, this work examined algorithm level transforms that dramatically increased the achievable parallelism and also examined the effects of using fixed precision and truncated bit widths in the algorithm.

Hyperspectral images clustering on reconfigurable hardware using the k-means algorithm

47 Citations2004A.Gda.S. Filho, Alejandro C. Frery +7 more

An automatic and parameterized implementation for hyperspectral images has been developed in a hardware/software codesign approach and an unsupervised clustering technique k-means that uses the Euclidian distance to calculate the pixel to centers distance was used as a case study to validate the methodology.

Fast and Exact Out-of-Core K-Means Clustering

41 Citations2005Anurag Goswami, Ruoming Jin +1 more

This paper presents a new algorithm which typically requires only one or a small number of passes on the entire dataset, and provably produces the same cluster centers as reported by the original k-means algorithm.

Real-time K-Means Clustering for Color Images on Reconfigurable Hardware

36 Citations2006Tsutomu Maruyama

It is shown that real-time k-means clustering can be realized for large size color images and large number of clusters using an off-the-shelf FPGA (field programmable gate arrays) board.

IEEE Transactions on Circuits and Systems for Video TechnologyHardware-driven adaptive k-means clustering for real-time video imaging

25 Citations2005B. Maliatski, Orly Yadid-Pecht

IEEE Transactions on Circuits and Systems for Video TechnologyHardware-driven adaptive k-means clustering for real-time video imaging

24 Citations2005B. Maliatski, Orly Yadid-Pecht

A new adaptive k-means clustering algorithm for real-time video imaging is presented, where a weighted contribution of both pixel intensity and distance between the pixels is used for cluster identification.