Octree colour quantization

This is a discussion on Octree colour quantization within the C Programming forums, part of the General Programming Boards category; Hello, I wrote a program that counts the number of colours in a 24-bit raw image by sorting them into ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,262

    Question 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...

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662

  3. #3
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,262
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-24-2006, 07:36 PM
  2. Replies: 5
    Last Post: 03-01-2003, 03:52 PM
  3. DirectDraw colour matching
    By Hunter2 in forum Game Programming
    Replies: 2
    Last Post: 12-10-2002, 01:17 PM
  4. how to set the background colour of a static box?
    By Cobras2 in forum Windows Programming
    Replies: 2
    Last Post: 08-01-2002, 04:57 PM
  5. Colour theory... (weird title)
    By Magos in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2001, 03:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21