An FPGA Implementation of K-Means Clustering for Color Images Based on Kd-Tree
An FPGA Implementation of K-Means Clustering for Color Images Based on Kd-Tree
复制标题
DOI：
10.1109/fpl.2006.311268
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
Takashi Saegusa;T. Maruyama
中科院分区：
文献类型：
--
作者：
Takashi Saegusa;T. Maruyama
K-means聚类是一种非常流行的聚类技术，在许多应用中都有使用。在简单的k-means聚类算法中，数据集中的每个点与所有聚类的中心进行比较。这种比较是一项非常耗时的任务，特别是对于大型数据集和大量集群。为了获得高性能，我们需要过滤掉需要与每个点进行比较的簇。在本文中，我们描述了一种用于彩色图像的k-means聚类的FPGA实现。在我们的实现中，使用k-means聚类的每次迭代在FPGA上动态生成的kd树来过滤集群。一台XC2V6000，对于512倍512和640倍480像素的图像（24位全彩色RGB），分割到256个集群时，平均性能在30 fps以上，对于756倍512像素的图像，平均性能在20 - 30 fps之间
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