A new real-time FPGA-based implementation of K-means clustering for images

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.