Thread: Octree colour quantization

Hello,

I wrote a program that counts the number of colours in a 24-bit raw image by sorting them into an octree, which has nodes that look like this:-

Code:

typedef struct TAGoctree {
	unsigned long value;	//The colour
	unsigned long count;	//Number of them in image
	int leaf;	//Is this a leaf node?  (Also general flag)
	int level;	//At what tree depth/level is this node?
	struct TAGoctree *children[8];	//Meet the family
} node;

The value of leaf is 0 for those nodes at levels 0-7 and 1 for those at level 8 (The maximum depth, with 16777216 possible nodes). It's helluva fast

Now I'm trying to work out a method with which I can reduce the number of colours in the image by combining the values of the leaf node children of a level 7 node and setting leaf to 2 for these redundant colours, so the later search function will go down a level in order to find the replacement colour for a given original colour. I've tried:-

Code:

void FoldTree(node *parent, int *curlevel, int *count, int nColours)
{
	int i, nChilds = 0, bLevel = 0;
	node *current = parent;

	while (*count > nColours)
	{
		if (current->level != *curlevel)
		{
			for (i=0;i<8;i++)
			{
				if (current->children[i])
				{
					if (current->children[i]->level == *curlevel)
						bLevel = 1;

					FoldTree(current->children[i], curlevel, count, nColours);
				}

			}

			if (bLevel)
				(*curlevel)--;

		}
		else
		{
			for (i=0;i<8;i++)
			{
				if (current->children[i])
				{
					if (*count > nColours)
					{
						current->value += current->children[i]->value;
						current->count += current->children[i]->count;
						current->children[i]->leaf = 2;
						nChilds++;
						(*count)--;
					}

				}

			}

			current->value /= nChilds;
			break;
		}

	}

}

But this doesn't seem to give the desired effect. When the function ends count is usually nowhere near nColours and it seems a single node at each level has had its leaf set to 2, which causes all manner of havoc for my search function (It ends up going down to level -1, KABOOM! )

Has anyone done something like this before? Muchos gracias...

Octree Color Quantization
google

gg

Well, that helped a little bit, but now I'm a bit stuck. I need to find the node that has the child with the lowest count in the tree. So far, I've come up with this function:-

Code:

node *FindLowestNodeParent(node *parent, unsigned long *nCountToBeat)
{
	int i;

	for (i=0;i<8;i++)
	{
		if (parent->children[i])
		{
			if (parent->children[i]->count > 0 && parent->children[i]->count < *nCountToBeat)
				*nCountToBeat = parent->children[i]->count;
			else if (parent->children[i]->leaf)
				parent = FindLowestNodeParent(parent->children[i], nCountToBeat);
		}

	}

	return parent;
}

In this situation, I'm using the leaf member to determine if a child node has any children of its own. However, this seems to result in the function returning the same node over and over again, even when all of its children have been deleted. Help?