Patrick's Playground

Details about K-Means Clustering on images:

Before the algorithm starts, the user needs to set a number of greyvalues (bins). The resulting image will contain that number of greyvalues.
With that number of bins (called ‘k’) the algorithm clusters the greyvalues of the image into k clusters and once the algorithm is terminated, every cluster will have its own greyvalue.
With starting the algorithm, you should set:

• How to define the ‘startingmeans’ of the clusters before the first iteration.
• What the stopping criteria are.

The Algorithm:

In short this is what the algorithm is supposed to do:
Initialize (so set k, set ‘startingmeans’, set stopping criteria)
Loop while termination condition isn’t met (

• For each pixel: assign the pixel to a class such that the distance from the pixel to the center (the mean) of a class is minimalized.
• For each class: recalculate the means of the class based on the pixels belonging to that class.

)

My implementation:

The user can set his k (which is fairly easy).
I’ve implemented 3 ways to choose the ‘startingmeans’ this far:

1. i mod k class: The pixel at index i is assigned to the class i modulo k
2. Distribute mean table over color space: According to the k that’s chosen the means are chosen so that the are spreaded equally over the complete color space of the image.
3. Random: Just as it says. Given a k, there will be chosen k random mean values.

The termination constraints are currently not visible for users and are set to:
Terminate after fewer than n pixels change classes after a recalculation of the means.
I’ve set my n to 300 which is pretty small if you are using images bigger than 512 by 512 pixels. Next to that, the algorithm will be terminated if there are more than j iterations needed to get a stable result (in the meanings of that there are not more than n pixels changing classes after a recalculation of the means). My j is currently set to 50. Most of the times the algorithm terminates because of less than 300 pixels have changed classes.

Now that we’ve seen how the parameters of the algorithm are set, let’s have a look how I’ve implemented the algorithm in terms of code and decisions I’ve made.

I’ve devided the code over 3 classes:

1 to build the JDialog which is needed to ask for the input of the user concerning the way the algorithm needs to be initiated.
One with the actual algorithm and the last class is a clusterclass.

Because the class with the JDialog is not that interesting, we’ll focus on the other two classes.

The ClusterClass is pretty simple: it only holds a mean, an upperbound and a lowerbound.
I’ve chosen for the fact that this class holds the bounds because at the initialization of the algorithm, there are k classes which are created (and put into an ArrayList). You can let each class hold it’s own pixels which are belonging to that class, but if your k grows and the image is big, the complete image will be twice in the memory: as the original image and all pixels will be part of one of the clusterclasses as well. Instead of that I’ve chosen to hold the bounds of that class so that if I’m checking pixelvalues, it can also check to which class it belongs in the same for-loop.

As mentioned earlier: a pixel belongs to a class if the distance from that pixelvalue to the mean of a class is minimized. Because my ClusterClasses hold their upper- and lowerbound, a pixelvalue has to lay between the bounds to be part of that class. The bounds are simply calculated by checking which mean is the nearest (but have a lower value for the lowerbound and a higher bound for the upperbound). The bound can simply be calculated by taking the mean of these two means.
After every pixel is assigned to a class (In my case: it can check to which class it belongs). The means of the classes can be recalculated by taking the sum of all the pixelvalues belonging to that clusterclass and divide this sum by the number of pixels in the clusterclass.
After the recalculations of the means, the upper- and lowerbounds need to be recalculated as well.
After this iteration, the termination condition has to be checked. If the condition isn’t met, another iteration follows. If the condition is met, the clusters are set and the colors of the image can be recalculated.

And now shortly in JAVA:

public KMeansAction:

initialize
calculateBounds
while (not_terminated) do:

• recalculateMeans
• recalculateBounds
• checkTermination

processImage

private void processImage:

// This works for 8-bit greyscale images
// It calculates the greyvalues that will occur in the resulting image
delta = 255 / ( k – 1)
for every pixel do:
for every class do:
if a pixel belongs to that class then

// set the greyvalue of that pixel to the index of the class in the list times delta

greyvalue = classindex * delta
// then set the rgbvalue of that pixel to the greyvalue
newImage.setRGB(pixel location, greyvalue)

NOTE (August 7, 2009): I’ve found the source code and put it in this blogpost.