Variants on the basic K-means Algorithm

• On-the-fly k-means:

  This involves incrementally updating the means. After each pixel classification, update the means of the class the pixel came from, and the class the pixel is moving to.

  This is very expensive in hardware, since it requires 2 mean calculations for every pixel classification.

• 1-pass kmeans (the leader algorithm) :

  The basic k-means algorithm starts with the number of classes as a given, and iterates several times over image data. The 1-pass algorithm assigns each pixel to a class based on one decision. There is only one iteration through the data.

  Instead of starting with the number of classes, the 1-pass k-means algorithm starts with the maximum radius of a cluster, epsilon.

  Cluster center 1 is set to the values of pixel 1.

  For each pixel in the image:
  If this pixel is within epsilon of the centers of any existing class, then add that pixel to that class,
  else create a new class whose center is the values of this pixel.

  Note that, worst case, each pixel is a class, and the number of comparisons for the last pixel is equal to the number of pixels in the image. This worst case is unlikely to happen in practice.

  The one pass algorithm is good for running on a host, or for an implementation where k-means is a first step.

This page is maintained by Prof. Miriam Leeser
Last updated September 16, 1999.
Email: mel@ece.neu.edu