An FPGA implementation of real-time K-means clustering for color images |
| |
Authors: | Takashi Saegusa Tsutomu Maruyama |
| |
Affiliation: | (1) Systems and Information Engineering, University of Tsukuba, 1-1-1 Ten-nou-dai Tsukuba, Ibaraki 305-8573, Japan |
| |
Abstract: | K-means clustering is a very popular clustering technique, which is used in numerous applications. In the k-means clustering
algorithm, each point in the dataset is assigned to the nearest cluster by calculating the distances from each point to the
cluster centers. The computation of these distances is a very time-consuming task, particularly for large dataset and large
number of clusters. In order to achieve high performance, we need to reduce the number of the distance calculations for each
point efficiently. In this paper, we describe an FPGA implementation of k-means clustering for color images based on the filtering
algorithm. In our implementation, when calculating the distances for each point, clusters which are apparently not closer
to the point than other clusters are filtered out using kd-trees which are dynamically generated on the FPGA in each iteration
of k-means clustering. The performance of our system for 512 × 512 and 640 × 480 pixel images (24-bit full color RGB) is
more than 30 fps, and 20–30 fps for 756 × 512 pixel images in average when dividing to 256 clusters.
|
| |
Keywords: | K-means clustering Color images Real-time FPGA |
本文献已被 SpringerLink 等数据库收录! |
|