Hello everybody. It’s been quiet in this blog for almost three years now, so it was high time I dropped by here. I’m also glad here still are people reading these old post, and also contacted me by email, and sorry to those who I haven’t responded.
Since this is a blog dedicated to programming in the first place, specially for visual stuff like image processing, I’m also going to add some code and a demo here.
Color Quantization of an image means finding its most common, dominant colors and converting the output to use only these. For a fast performance my implementation first analyses each of the rgb-channels separately, then splits the entire (3D) space into clusters, uses these as bins for a 3D histogram. Finally the bins are clustered to desired amount of colors, and the altered output image is calculated.
Here is a histogram of a typical image’s green channel. We can by looking at it conclude that here are two major peaks, one at the black end and other at the middle tones. I’m using k-means clustering for the process. The general idea is to divide the distribution into separated masses, e.g. the columns in the image at right. The process is to first choose the clusters, in these case by dividing the color range of 0 to 255 to equal parts. The histogram values are each added to the nearest cluster. After that the new centroid of each cluster is updated. The process is repeated until it converges. In a one dimensional case like this, the sample space is only a integer range a 0 to 255 the update is simple: at current situation only the values at the edges are checked. The centroids of these columns should be a good estimate for the distribution of the histogram, since in this histogram there are less bright colors the last column is wider than the others.
Let’s remember that looking at the channels doesn’t of course solve the actual problem but gives a good approximation of how the color range is distributed in the RGB-space. Now that we know how the color ranges are distributed along each channel we can apply the same division to the entire rgb-space. Here’s images illustrating the process. The topmost one shows the color space distribution of an unmanipulated image, the middle one the result after the separation by channel, and the last is the result after the final clustering:
The final task is to map the colors of the input image into this new color space. In my code I’m using lookup tables, so the performance should be relatively fast.
Color Quantization has been a relatively popular subject of studies, and there’s plenty of solutions from different approaches … etc … but hey! About now it’s the time for the actual demo:
You can test it for different levels of color, or upload an image of your own.
For your additional reading:
ColorThief by Lokesh Dhakar