K-Means Clustering Applications in Digital Signal Processing

by Sara Wendte

Introduction

K-means clustering is a simple unsupervised learning method. This method can be applied to implement color quantization in an image by finding clusters of pixel values. Another useful application would be automatic classification of phonemes in a speech signal by finding clusters of formant values for different speakers.

Theory

Color Quantization Application

In image processing, a common problem is determining how to compress an image without losing essential information. This is particularly relevant for color images, since they require the storage of three parallel matrices to store information for the red, green, and blue components in the image. Using k-means, combinations of colors can be quantized into a certain number of levels. In the context of k-means, these color levels would be the centroid. For each pixel, the closest centroid is determined by treating each pixel as a vector of <r,g,b> and using the distance formula to find the distance between the pixel and each centroid. The algorithm assigns each centroid a color value that represents the average of all the pixels that were closest to that centroid.

The images below show the result of using K-means to quantize a color image. The image that is quantized with 256 levels is almost indistinguishable from the original.