Building a Quadtree

Question

I'm attempting to use a quadtree (a 4-ary tree) to hold the information in a given BMP.
I'm struggling to figure out how to build the tree given any BMP.

Basically the structure is such that every leaf represents a pixel. Each Node has 4 pointers each of which point to one of the four remaining quadrants in the image. Thus each node divides the current picture into 4 parts. By the time you are at the leaf you are at one specific pixel.

I'm not sure how to go about building a tree to map a certain image. Assuming that the image has dimensions which are powers of two, what should I do. I understand that a recursive function could probably do this most elegantly but I'm struggling to figure out how to keep track of where in the image I am going to be.

This is in C++ and currently my quadtree.h file includes a Node* root where a node is defined as being a structure with a pixel element and 4 pointers to other nodes. Each inner node (non leaf node) should hold the average value of all the 4 RGB values it leads to.

I'm attempting to make an algorithm, but I think I might need to include a struct or two in the .h file. Is there a better/more clean way to solve this problem?

Answer 1

well, depending on how you have your Bitmap data stored you might do things differently. Are you reading it from a file and dropping it straight into your tree? If so, .BMP files (if I recall correctly) tell you their width and height right at the top, so you could actually use that to figure out exactly how many levels you'll have, which might help you build something.

Also, depending how big your images are, you could store all of the pixels in a 2D array of nodes and have the tree sort of "sit on top of" the array, so that your leaves were in the array and everything else is elsewhere. If you were to do that you could write some nested loops that'd go through and grab groups of four nodes, calculate their average, and lump 'em together, and then do the same thing with the nodes it's just created. This would probably be faster than building the tree from the top down, because you'll never be averaging more than four pixels, whereas building from the top down would need to average more than four pixels every step except the last one.

If you don't want to do it in an array, the easiest thing, to my mind, would be to have each node keep track of its x,y coordinates. That would allow you to do basically the same thing as with the array, but you wouldn't just be plugging in indexes.

Is this helpful? How are you storing the Bitmaps? What is the end goal?

Answer 2

STANN is the best open source implementation at the moment.

http://sites.google.com/a/compgeom.com/stann/

Word to the wise, use Bern et al's quadtree construction algorithm and forgo the funky tree operations.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

1. Sort all your points in morton order.
2. Calculate the quadtree box length between each pair of consecutive points.
3. Do an all nearest largest values computation to find parents/siblings.

I am developing a library right now for OpenCl. I'll post a link once I finish testing it.