Color quantization with Kmeans in OpenCV

This is the last part of this series sharing some homework results proposed by a graduation computer vision class.

Illustration of matter organized in groups, also called clusters. (source)

Theory

For this last implementation we are going to be using a technique for data clusterization and with that generate new images with a reduced number of colors comparing to the original image.

Ok, first things first, quantization: is a way to represent data from a large set in a smaller set. This goal is usually useful for data compression, however can be used in digital images too; As stated on wikipedia, “Color quantization reduces the number of colors used in an image; this is important for displaying images on devices that support a limited number of colors and for efficiently compressing certain kinds of images.”

The quantization basically works by grouping color that look similar together. If we specify that we only want to show the picture in 4 colors, the quantization will try to see where each pixel color should fit in those four colors and then rearrange the image.

From the many quantization algorithms that there are, we will be working with one of the most used and famous one: Kmeans. The simple algorithm partitions the n-dimension space (of data) in Voronoi’s cells, each cell having an specific center. So, for example, if we have a many labels for a given data, but we want to represent them only by three unique groups, this algorithm finds how to.

Kmeans example (source)

The groups, called clusters in data analysis, are formed based on the distance in space from the sample to the cluster’s center (determined either by the user or randomly), the smallest distance tell the samples’ cluster.

The algorithm can be easily summarized by a few steps:

1. Pick a k as the number of clusters desired for the array x[i] of N samples i=1,2,⋯,N.
2. Choose c1, c2, ⋯, ck as the initial centers for each cluster.
3. Classify each sample x[i] calculating the minimum distance (i.g. euclidean distance) in space to each center.
4. Re-define each cluster center based on the step 3: for each cluster now full of samples, should there be another center points, the mean of all samples in space.
5. If the new means (centers) are consistent, didn’t change much, end of the algorithm. Otherwise, after redefining the new centers, reclassify the samples (back to step 3).

Another approach to this algorithm is to initialize the centers randomly. This way, the clusters will eventually converge to the clusters we expect by specifying the centers ourselves, however given after the algorithm runs for some rounds. This is a particularity of this algorithm, depending on the parameters it can present different result and may be unsatisfying.

First we will implement the algorithm with a few rounds and 8 clusters, so that our resulting image is represented only in 8 colors. The base image is from a plate of sushi made of many different colors.

The Kmeans is not implemented by hand, once again there is a buit-in function in openCV that does it for us. The documentation itself already has an example of image quantization through kmeans, however we are doing our implementation here to analyse results.

The function cv2.kmeans(float samples, k clusters, None, criteria, n rounds, way to initialize centers) is pretty straight forward explained in the documentation, but oddly for openCV 3+ the documentation does not specify a necessary argument, used in their examples, required in our implementation: the None argument is assumed None everywhere in the documentation and no mentioned anywhere what it should mean.

Even so, let’s get it working.

Implementation

First off we define two variables to determine the number of clusters and rounds. The n rounds it’s good to vary to see how quickly the algorithm converge, and not waste computation.

After reading the sushi image, in color, we generate a matrix of height*width (sushi size) lines by three columns so we can store every color from each color channel in a way that every line has a [B G R] value. note: need to be type float, int values will round the colors and affect the kmeans calc.

The kmeans function returns 3 results, which of we are going to use only labels e centers: labels is how every sample from “samples” is labeled, from 0 to NCLUSTERS, and centers where each label is centered in space. The criteria we pass is the criteria to stop the algorithm: (type of termination, n iterations, accuracy).

For the type of termination we chose to use cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, meaning that we want the algorithm to stop either if the accuracy is reached or the number of iterations has passed. For the flags argument was first implemented passing KMEANS_PP_CENTERS, calculating then the centers based on an algorithm proposed by Arthur2007. The rest of the parameters should be self explanatory.

The three lines of code following kmeans’ call are for creating a new image based on the clusters created for the colors (code took from the openCV documentation), and now we can see the results for the quantization with only NCLUSTERS colors possible.

Quantization with nclusters = 8

The result is a very interesting image, almost like a painting. To add more details to it (more colors) or not we only need to change a single parameter.

Quantization with nclusters = 4

Ok, now let’s analyse a little deeper. When the code shown above is executed it returns always the same image as result, great right? But as we discussed above this is a not a rule for the kmeans algorithm, this is assured by a set of parameters found for an specific problem. For this problem we first determined nrounds = 5, so the algorithm runs more than one time over the same data and that already assures most of the accuracy, but also the stopping criteria is responsible for this; it’s important to know when the algorithm is ready to stop.

For a last statement here, we ran the same algorithm but now with NROUNDS = 1 and the center initialization random (cv2.KMEANS_RANDOM_CENTERS), expecting the results to change from result to result.

The reason for this should be trivial, centers initialized randomly will attract different samples in space for every run and create different clusters data. By that meaning, on the image quantization perceptive, colorize the result image differently every time.

BUT, huge but needed, this was not the case. The algorithm didn’t show any randomness in results when applied to the new parameters and this is probably due to the library's implementation.

Discussion

First of all, the problem is big enough to be exposed to the randomness. There are many colors in the original image, and they should be grouped differently for different runs (I ran a lot of times).

Second of all, for testing sake, it was increased the number of clusters, so that maybe the with more frontiers the algorithm would get confused more often; and was reduced the accuracy on the stopping criteria, but nothing showed randomness in the results.

In conclusion, it was assumed after searching a lot for documentations and examples pointing out this randomness and never finding one, and also by existing a parameter which no one knows what it is in the function call, that the function has flaws in implementation OR in explanation by its official documentation online.

This should be my last post for this class as professor oriented kinda problems. However, I should be posting more about personal projects or other random studies/hobbies. Thank you so much for reading, leave a comment if you may! :)

All the codes can be found at my public repository at GitHub.