K-means Clustering for Image Segmentation Using Approximate Booth Multiplier

K-means clustering is an unsupervised learning algorithm that assigns unlabeled data to different clusters depending on the similarity rather than predefined labels. It finds application in data analysis, classification, fault detection, etc. In this paper, we employ approximate computing to reduce the computational requirement for K-means clustering algorithm. Approximate computing uses error resilient applications and reduces the computational complexity by using the ability to tolerate some level of erroneous output. It allows errors in outputs in order to achieve faster processing and lower power consumption rather than producing exact outputs, as conventional computing does. Here, approximation is done in the Euclidean distance calculation stage of K-means clustering. The distance calculation incorporates a 16-bit modified booth multiplier that uses inexact 4:2 compressors for the reduction stage of partial products. The circuit complexity is reduced by using compressors to approximate certain sets of partial products in the multiplication stage. The approximate K-means clustering implementation is used for image segmentation. The effectiveness of this approach is evaluated with standard quality matrices like Silhouette score, Davies-Bouldin index, and Calinski-Harabasz index and all the three metrics shows less than 10% drop on average.