FPGA Implementation of Forgy’s K-Means Clustering for Real Time Image Analysis

Partitioning the image into meaningful groups is one of the major task in image analysis which can be achieved using the unsupervised clustering algorithm. K-means algorithm is one of the popular unsupervised clustering algorithm. The Kmeans algorithm is time-consuming and requires intensive computation for a large data set as the input is compared with all the centroids. Also, the data needs to be stored internally due to iterative re-assignment process. An architecture to enhance the speed of clustering operation using minimal hardware for K-means clustering without any internal storage is proposed and implemented using Virtex 6 FPGA. A new methodology is proposed to reduce the distance computation. The performance of the architecture is 203fps for a grayscale image size of 256X256 and 102fps for a grayscale image of size 512X512. This shows that the proposed architecture can be used for real time image segmentation.