Introduction
Octrees are like standard trees, except that each of their nodes can contain up to eight leaves and that they're often used in color quantization. They're easy to implement and understand. The color is added into tree, based on its R,G,B bits, which makes index 0-7 (000-111 on R,G,B). Maximal level is 7, tree can contain up 8 levels (0-7). For the first level (0), the MSBs from R,G,B are taken and corresponding node index is calculated. For next levels, the next bits from next positions are taken and index is calculated, ending with LSBs on 7.th level.
After the tree was filled up, we start merging. We merged least reference count leaves into their parent node. Leaf by leaf. When all leaves are merged, their parent node becomes the leaf itself and the process is repeated. Although there are thoughts that merging can occur before the tree was filled, I do not recommend it.
Important
This is not an image producer, this is a palette producer, which means, that there is only GetPalette
function, returning palette created in unsigned chars, in order R, G, B.
The Idea
The main purpose is to bring up a few improvements over standard octrees, seen around here. Improvements are:
- Exact colors count can be obtained - main improvement (see background)
- We can spend a lot of iterations by stripping unnecessary bits from R,G,B even before color is added to tree - lesser improvement
- We calculate minimal reference count and start merging from that value - lesser improvement
Background
For a brief (and very short) description on octrees, see Wiki.
There is a good article on color quantization here on CodeProject, with screenshots and brief description for each stated. Here: A simple - yet quite powerful - palette quantizer in C#.
The article also says, that "Also upto 8 leaves may be reduced at once, leaving us at the worst with 248 colors in the palette (which is not quite optimal)." which is not true, you can get any colors count that you want (within a reason, of course). I want to prove that.
In Focus
So how to obtain the exact colors count? Easily, just stop merging when the desired colors count-1 is reached. Create a new plain leaf and, of course, give the "merged" values back into that newly created leaf. You will end up with exactly the colors count that you wanted.
The Algorithm (In Short)
- For every pixel in the image
- Get R,G and B values
- Continually take bits from R,G and B, from each, take one, start from MSB, end with LSB
- Make index from those bits (ranging from 0-7)
- Traverse the tree along the path made from indices, creating new leaves where it is necessary (leaves then become nodes, if containing child)
- On each node, you encounter, increment references count
- On the end of the path, increment also pixel count and add color into that leaf
- Back to 1
Merging for Exact Colors Count
Merge leaves as usual, leaf by leaf, node by node. But merge leaves into their parent node (their pixel count, sums of red, green and blue). When you reach one less colors count than wanted, create a new leaf, "vomit" merged values from parent node into that new leaf. That's all. You will end up with exactly the colors count that you wanted.
- Calculate min. reference count (by rushing over all nodes and leaves) - optional
- Merge leaves into their parent node, leaf by leaf, node by node
- Stop merging when desired colors count-1 is reached
- Create new leaf under current parent, "vomit" merged values from parent into that leaf
- Increment colors count and exit
void OctreeColorReduction::MergeLeast(node *n, int mincount) {
if (n->references_count > mincount) return; if (colorsCount == desiredColorsCount) return; for (register int i = 0; i < 8; i++) {
if ((n->child[i]!=0) && (n->child[i]->childrencount > 0)) { MergeLeast(n->child[i], mincount); }
else { if((n->child[i] != 0) && (n->references_count <= mincount) ) { n->pixel_count+=n->child[i]->pixel_count; n->R_sum += n->child[i]->R_sum; n->G_sum += n->child[i]->G_sum; n->B_sum += n->child[i]->B_sum;
delete n->child[i]; n->child[i] = 0; n->childrencount--; colorsCount--; if (colorsCount < desiredColorsCount) { n->child[i] = new node(this);
n->child[i]->R_sum = n->R_sum;
n->child[i]->G_sum = n->G_sum;
n->child[i]->B_sum = n->B_sum;
n->child[i]->pixel_count = n->pixel_count;
n->childrencount++;
colorsCount++;
break; }
}
}
}
if (n->childrencount == 0)
colorsCount++; }
What is Bits Stripping, Is That Necessary?
Bits stripping means, that from each red, green and blue channel we strip off bits, starting from LSB, up to strip count. The bits are nulled and later the small compensation is given, to minimalize the information loss:
static int StripAddRed[9] =
{0, 0, 1, 2, 4, 8, 16, 32, 64}; static int StripAddGreen[9] =
{0, 0, 2, 2, 4, 6, 12, 12, 32}; static int StripAddBlue[9] =
{0, 1, 2, 4, 8, 16, 32, 64, 128};
iR>>=StripR; iR<<=StripR; iG>>=StripG; iG<<=StripG;
iB>>=StripB; iB<<=StripB;
iR+=StripAddRed[StripR]; iG+=StripAddGreen[StripG];
iB+=StripAddBlue[StripB];
For example Blue: on 0 strip, the 0 is added. On 1 strip, 1 is added, on 2 strip, 2 is added, on 3 strip, 4 is added. We strip off three bits from blue and add 4 for compensation.
So Is It Necessary?
It is not necessary, of course, and if you want the best quality, this (option) is not for you. But consider that: the bits stripping in ratio 3 2 3 for R G B can reduce colors from 140 thousand into 4 thousand in a moment, and there is almost no visual information loss, if ever. The speed can boost up by 10x or more.
My experiments showed that stripping by 3 2 3 is fairly good on image quality, but 3 2 4 can cause minor visible artefacts, and I do not recommend that.
You can experiment on your own.
We Calculate Minimal Reference Count?
Yes. After the tree was filled, we rush over all nodes and their leaves, seeking for minimal reference count (times, that node or leaf was passed). We start merging from that value and every iteration we add that value to minimum reference count. For example: minimal reference count is 10, because there is no 1-9 reference count on any node/leaf, so we start merging from 10. Next iteration we start with 20, then 30 and so on.
The Code
- bmp.h - Header for bitmap file
- strip.h - Header for strip and compensation
- main.cpp - Example program
- ocr_good_color.cpp - octree itself
The main class is OctreeColorReduction
in ocr_good_color.cpp. The most important public
function in this class is GetPalette
.
BYTE *GetPalette(BYTE *src, int srclen, int desiredColorsCount,
int maxDepth, int StripR, int StripG, int StripB);
The parameters are:
src
- Source buffer filled with unsigned chars srclen
- Source buffer length desiredColorsCount
- Exact colors count you want maxDepth
- Maximal depth of the tree in bits (1-7) StripR
, StripG
, StripB
- Number of bits, that you want to "throw away" on R,G and B
You should call the:
getColorsCount();
function to ensure, that you've got exact colors count. Testing showed that you always get colors count equal to desired colors count.
Besides the above, and its constructor and destructor, you can call the:
getMemoryUsed();
function, to see, how many bytes were used by the tree.
Feedback
Please feel free to provide any feedback for improvements on the article or on the code, which are presented here.
Points of Interest
Notes
- The image input requested by the example application MUST be a windows compatible 24-bit bitmap.
- I recommend to use the
GetPalette()
function with the following parameters:
GetPalette(src, srclen, desiredColorsCount,
5, 3, 2, 3);
History
- 12.9.2010 - First publication