Low Cost and High-Speed Implementation of K-Means Algorithm for Image Analysis

Abstract

Introduction: An image contains various patterns which need to be divided for further analysis. The categorization of patterns can be carried out using unsupervised clustering algorithm of which K-Means is the most popular and efficient algorithm. However, the algorithm takes more time to divide the image into various groups as it is iterative and is computationally intensive.

Objectives: Hence introduced a new technique and have devised a new architecture to accelerate the K-Means operation. The technique uses image intensity levels without the spatial information to accelerate the clustering operation. In any image, regardless of its pixel count, the intensity values are always between 0 and 255. Once these intensity values are initially read for an image, subsequent clustering iterations only use the frequency of each intensity level and 256 intensity levels to cluster.

Methods: This approach minimizes storage requirements and speeds up the algorithm. Absolute distance is used to compare the distance between the input image pixel and the cluster center to further accelerate the operation. An integer divider is employed to calculate the cluster center. Its architecture is designed to function within a single clock cycle, enhancing the overall speed of the operation

Results: Experimental results show efficacy of the proposed architecture in speeding up the operation. When implemented on a Virtex-6 FPGA, the hardware accelerator can process 405 image frames per second for images of size 256 x 256. To adapt the design for a more cost-effective FPGA with fewer logic gates, parallel computations were reduced, allowing implementation on a Spartan 3 FPGA.

Conclusions: The modified design processes 106 images per second on the Spartan 3, making it a compelling solution for clustering images with both low cost and high speed.