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 :D
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! :o)
Has anyone done something like this before? Muchos gracias...