Applying a Median Cut color reduction algorithm's output palette to the source image

Question

So I'm beginning to look into "simple" color reduction to apply to images. I've spent the last day researching how this works, and managed to find what seems to be a decent algorithm to experiment with here: Median cut algorithm

The output here is a palette of n colors. I have yet to ensure this algorithm actually works, but I'm assuming it does. What I would like to do is take that output and apply it to the image that the palette was generated from.

I can't say I'm well versed in color compression formats and all the deep knowledge when it comes to images, but I'm wondering how I can apply the palette without having to start with an image format that comes with an indexed palette (i.e. GIF).

I'm thinking that for each pixel, I calculate the difference between the color of the current pixel and each color in the palette, and replace that pixel with the palette color of the least difference. Would this be a viable way to approach?

Note - I have looked into various libraries (ImageMagick), but these seem slightly overkill; the most I'll be doing with image manipulation will be reducing the color palette - nothing more complex than this. That's why I'm thinking implementing this algorithm would be the simplest approach for my needs.

Answer 1

I think its a viable way. The difference you calculate should be the Euclidean difference as showed here However you can do a little optimization. You don't need to calculate a new difference every time. For example you can populate a lookup table in order to use the right color directly if you already calculated it

Answer 2

The fastest method is to use an oct tree for color lookup.

The idea is you add all the palette color indexes to the oct tree, then ask the root node for the nearest color. When asked for the nearest color, each node (which has access to the palette) returns its own color index if it's at the deepest level or asks the corresponding child (to the requested color) for its nearest color index. If there is no corresponding child, it asks all of its children for the nearest color index and returns the one whose color has the smallest distance.

Basically, the oct tree will greatly minimize the number of distance comparisons that need to be made. This is sped up by precalculating all distances.

Here's my implementation... http://www.codeproject.com/Tips/1046574/OctTree-Based-Nearest-Color-Search