Posted by: pixelero | November 12, 2014

Just saying Hi, or Color Quantization using Histogram!

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.

Green channel histogram Clustered histogram

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:

Original RGB-space
Space divided by channels
Clustered result

Depending on the desired number of colors, the channels are divided to a maximum of eight clusters. Now stepping into the 3D, the maximum of bins is 8x8x8 = 512, and for the performance of a contemporary computer that should not be a challenge. Even as my implementation is very brute force, for every color bin it loops through all the centroids. However let’s remember, just as the images show, in a usual case of an input images, many areas in the rgb-space remain empty. In this demo I’m using javascript, for a flash implementation amount less than 256 would be an ideal solution: e.g. pack the entire color space to a single channel.

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:

Original Image Image with seven dominant colors

You can test it for different levels of color, or upload an image of your own.

Javascript source code

For your additional reading:
http://en.wikipedia.org/wiki/Image_segmentation#Clustering_methods
http://en.wikipedia.org/wiki/Image_segmentation#Histogram-based_methods
http://en.wikipedia.org/wiki/K-means_clustering
ColorThief by Lokesh Dhakar

Advertisements

Responses

  1. This whole blog business is very sad. Few people read, even less reply.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: