Octree Color Palette

• Download bin - 11.78 KB
• Download source - 6.2 KB

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)

1. For every pixel in the image
2. Get R,G and B values
3. Continually take bits from R,G and B, from each, take one, start from MSB, end with LSB
4. Make index from those bits (ranging from 0-7)
5. Traverse the tree along the path made from indices, creating new leaves where it is necessary (leaves then become nodes, if containing child)
6. On each node, you encounter, increment references count
7. On the end of the path, increment also pixel count and add color into that leaf
8. 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.

1. Calculate min. reference count (by rushing over all nodes and leaves) - optional
2. Merge leaves into their parent node, leaf by leaf, node by node
3. Stop merging when desired colors count-1 is reached
4. Create new leaf under current parent, "vomit" merged values from parent into that leaf
5. Increment colors count and exit

void OctreeColorReduction::MergeLeast(node *n, int mincount) {
  // why do we need to merge by 8? Because there can be up to 8 of leaves.
  // What about to start merging leaves as usual, to parent node, but stop when
  // colors count-1 is reached. In that moment, create new leaf and vomit values from node
  // into that newly created leaf. Colors count will increase back to desired colors
  // count, resulting in giving us exactly the colors count we wanted.
  if (n->references_count > mincount) return;  // do not go, if ref. count is 
					// greater than wanted
  if (colorsCount == desiredColorsCount) return; // do not go, in case that 
					// desired colors count was reached
      for (register int i = 0; i < 8; i++) {
            if ((n->child[i]!=0) && (n->child[i]->childrencount > 0)) { // ak ma child 
						// a child este ma child
               // I know, that you will always go the one node with the least ref. count
               MergeLeast(n->child[i], mincount); // chod az
            }
            else {             // merge leaves into their parent node  
              if((n->child[i] != 0) && (n->references_count <= mincount) ) {  // merge
                   n->pixel_count+=n->child[i]->pixel_count;                  // this 
							// condition is needed,
                   n->R_sum += n->child[i]->R_sum;                            // because 
		      // what if child ref. count differs from ref count of its parent
                   n->G_sum += n->child[i]->G_sum;     // n is parent node
                   n->B_sum += n->child[i]->B_sum;
                   delete n->child[i];   // delete leaf
                   n->child[i] = 0;      // leaf does not exist anymore
                   n->childrencount--;   // childrens count in this parent has decreased
                   colorsCount--;  // it is necessary to decrement colorsCount
                   // this is always reached
                   if (colorsCount < desiredColorsCount) {   // do not merge anymore! 
					// You've reached the desired colors count-1
                      // vomit from parent
                      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; // jump off
                  }
              }
            }
    }
    if (n->childrencount == 0)
        colorsCount++;  	// you've removed the childs, but a new color was created 
			// (from parent into new leaf)
}    

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}; // array for information loss compensation
static int StripAddGreen[9] = 
	{0, 0, 2, 2, 4, 6,  12, 12,  32}; // array for information loss compensation
static int StripAddBlue[9]  = 
	{0, 1, 2, 4, 8, 16, 32, 64, 128}; // array for information loss compensation

      iR>>=StripR; iR<<=StripR;  	// strip to and fro to null bits
      iG>>=StripG; iG<<=StripG;
      iB>>=StripB; iB<<=StripB;
      iR+=StripAddRed[StripR];	// attempt to compensate the information loss 
				// by adding a small value
      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

• It seems that there is not a perfect optimized palette producer, as is stated in IN SEARCH OF THE OPTIMAL PALETTE
• See A simple - yet quite powerful - palette quantizer in C#, for more optimized palette producers, like Median cut.
• You can also look for dithering as an option to preserve the visual information, which is lost when decreasing bit depths of images

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, 
	/* maxdepth */5,  /* StripR*/ 3, /*StripG*/ 2, /* StripB */ 3);

History

• 12.9.2010 - First publication