Octree Colour Qunatisation

[h0ffman]

Hey guys

I've been reading up on Octree colour quantisation. I read this..

http://msdn.microsoft.com/en-us/library/aa479306.aspx

I understand it up to and including traversing the bits of each RGB element to produce a leaf node. The bit I'm having trouble understanding is what to do with it all after that...

As previously explained, when a color is inserted into an Octree, the nodes are traversed. When a leaf node is found, the count of pixels of this particular color is incremented in the node, and the red, green, and blue components are added to the R, G, and B values within the node. These numbers are used to produce an average color based on dividing each color value by the number of pixels of that color.

I take it the leaf node is the total result of the traversing?

help!

[ara]

The bit I'm having trouble understanding is what to do with it all after that...

At the end of the color insertion procedure, you will get an octree where the leaves tell you

• the number of pixels represented by the leaf
• the "average" color represented by the leaf

In general, you limit the size of the tree in advance, otherwise your tree would have as many leaves as different colors in your picture with every leaf representing exactly one color.
The next step is to reduce the number of leaves. For example, from 32768 leafs (maximum depth 5) to 64. By definition, leaves with a common parent represent similar colors. You can reduce such leaves to one single leaf by averaging their colors (it's a weighted average of course). The challenge is to find the best leaves for the reduction process. Read this:
http://git.hashcollision.org/project...on/article.pdf

Once your tree has the right size, you use the tree to map the original colors to the reduced set of colors.