octree color quantization
Author
hi!!
i want to implementin octree color quantization algorithm in c++ or opengl.but first of all i m having problem in understanding this algorithm.if anybody can suggest some good stuff to read it from,i'll be obliged.second problem is how to read image in c++ or opengl.
plzzz help me out.
Here's one way that has worked quite well for me. I made it up so there may be better methods in the literature.
I'll assume you're working with RGB colours, where each component is in [0,255].
Once you have your image, think of the colours of the pixels as 3D coordinates.
Start with an initial leaf encompassing [0,255] on every axis. Subdivide the most heavily populated leaf. Keep doing this until you have 256 leaves (assuming you want a 256 colour quantization).
Take a colour from each leaf using some kind of average. A rounded mean shouldn't be too bad.
You could experiment with median cuts, rather than a classical octree, also.
As for reading images in the first place, this isn't something that OpenGL provides. There are numerous C and C++ libraries available, however. Google will help you here. I will suggest jpegxx for reading JPEG images though, because I wrote it :)
I'll assume you're working with RGB colours, where each component is in [0,255].
Once you have your image, think of the colours of the pixels as 3D coordinates.
Start with an initial leaf encompassing [0,255] on every axis. Subdivide the most heavily populated leaf. Keep doing this until you have 256 leaves (assuming you want a 256 colour quantization).
Take a colour from each leaf using some kind of average. A rounded mean shouldn't be too bad.
You could experiment with median cuts, rather than a classical octree, also.
As for reading images in the first place, this isn't something that OpenGL provides. There are numerous C and C++ libraries available, however. Google will help you here. I will suggest jpegxx for reading JPEG images though, because I wrote it :)
Well thats funny, I just turned in a project last night for a class on that. I had a rough time finding quality information about it so I'll try to explain it.
The main goal is to end up with a palette of the most important colors, and when the tree is built it is very fast to lookup which color in the palette most closely corresponds to any given color, which is useful for image conversion to a lower bit depth.
Each node needs to know about the RGB values as well as the number of times that color appears in the image, and also a palette index. So a node could look like this:
First you need to construct the tree by inserting all the RGB values into it. You start at the root node and get an index into the child node that this color should go to. The index is computed as the binary representation 00000RGB, where R,G,B are the bit values for each component, starting first with the most significant bit (7 in this case). So basically if the bit you are on is set in R,G or B component, you set it in the index. Since there is 3 bits you are setting the value ranges from 0-7, which is why an octree is used. So using this index you go to the child node (create one if it doesn't exist yet) and repeat this process with the next bit level. For each node you pass through, increment the reference count. When you reach 0 for the bit level, you stop and the node is a leaf. Add the r,g,b values to the current ones in that node. Once you've done that with all the RGB values for the image your tree is done.
Here's how I compute the index:
The next step is to reduce the number of leaf nodes to equal the number of palette entries you want (256 for 8bit). You can do this by choosing some minimum number of references you want a node to contain, and traverse the tree and reduce those nodes that do not have enough references, and continue doing this with ever increasing minimum reference values until there is the right number of leaf nodes. This eliminates the least important colors. To remove a node, simply add the RGB values to those of its parent and delete it. If it's not a leaf you should go all the way to the leaf nodes and and propagate the colors up from there.
Then you want to build a palette. You just traverse the tree and when a leaf is found, you add a new palette entry and cache the palette index at the node. The color for that entry is found by dividing the RGB values by the reference count.
At this point is is very fast to do a palette lookup for a given color. Just traverse the tree using the same index technique as when you were inserting colors, and when you hit a node that has a palette index you return that palette color.
One note on optimizing. It is very slow to continually count the total leaves during reduction, so you should keep a counter for the number of leaf nodes throughout the whole process.
Hope that helps :)
The main goal is to end up with a palette of the most important colors, and when the tree is built it is very fast to lookup which color in the palette most closely corresponds to any given color, which is useful for image conversion to a lower bit depth.
Each node needs to know about the RGB values as well as the number of times that color appears in the image, and also a palette index. So a node could look like this:
struct node{ long r,g,b,references; int paletteIndex; node* pChildNodes[8]; node* pParent;};First you need to construct the tree by inserting all the RGB values into it. You start at the root node and get an index into the child node that this color should go to. The index is computed as the binary representation 00000RGB, where R,G,B are the bit values for each component, starting first with the most significant bit (7 in this case). So basically if the bit you are on is set in R,G or B component, you set it in the index. Since there is 3 bits you are setting the value ranges from 0-7, which is why an octree is used. So using this index you go to the child node (create one if it doesn't exist yet) and repeat this process with the next bit level. For each node you pass through, increment the reference count. When you reach 0 for the bit level, you stop and the node is a leaf. Add the r,g,b values to the current ones in that node. Once you've done that with all the RGB values for the image your tree is done.
Here's how I compute the index:
int getIndex(int r, int g, int b, int level){ int index=0; int bit = 1<<level; if((r&bit) == bit) index |= (1<<2); if((g&bit) == bit) index |= (1<<1); if((b&bit) == bit) index |= (1<<0); return index;}The next step is to reduce the number of leaf nodes to equal the number of palette entries you want (256 for 8bit). You can do this by choosing some minimum number of references you want a node to contain, and traverse the tree and reduce those nodes that do not have enough references, and continue doing this with ever increasing minimum reference values until there is the right number of leaf nodes. This eliminates the least important colors. To remove a node, simply add the RGB values to those of its parent and delete it. If it's not a leaf you should go all the way to the leaf nodes and and propagate the colors up from there.
Then you want to build a palette. You just traverse the tree and when a leaf is found, you add a new palette entry and cache the palette index at the node. The color for that entry is found by dividing the RGB values by the reference count.
At this point is is very fast to do a palette lookup for a given color. Just traverse the tree using the same index technique as when you were inserting colors, and when you hit a node that has a palette index you return that palette color.
One note on optimizing. It is very slow to continually count the total leaves during reduction, so you should keep a counter for the number of leaf nodes throughout the whole process.
Hope that helps :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
