Trying to understand Quadtree concept and apply it to storing coloring info of an image

Question

I've read so many articles, but none seem to answer this question. Or maybe I'm just not understanding. I'm attempting to build a quadtree so that it can represent an image. The leaf nodes are to hold pixels, and non-leaf nodes will hold the average value pixel of its children.

My question is:

How does it work that the leaf nodes only hold pixels? Why don't the other nodes hold pixels? And how do we know how many times to subdivide our original root node to represent that given image? Do we just subdivide it n times, where n is the height and width (for a square)?

Edit: So how do I keep track of leaf nodes, so I know when to add pixels at that location? Right now I have a helper function that divides the regions for me, keeping track of width and height.

Evzone

Take a sheet of checkered paper. The pre-printed squares are your pixels. Draw one big rectangle. Subdivide it into four even rectangles and repeat recursively until you reach the size of a pixel. How many times did you need to subdivide it? What are pixels? - color information! If inner nodes store the average color of their children, they basically "hold pixels". – Fabrice

Answer 1

Quadtrees work best for square images whose size is a power of 2 (for example, most textures). You shouldn't think of each node as representing a "pixel". Instead, think of it as representing a "square block of pixels of size 2^k". In the case of final leaves, k is 0, so each leaf node represents a square block of pixels of size 1, that is, a single pixel. Internal nodes in the tree represent increasingly large sections of image.

Apotheosis

Answer 2

Why do only leaf nodes hold pixels? Ask yourself if a non-leaf node held a pixel, then what would its children hold? Since you can't subdivide a pixel, the answer is obviously nothing -- there can be no such nodes.

How do we know how many times to subdivide? Well, there are multiple ways to do it, of course, depending on why you're building the quadtree. In general, the areas of the image with more entropy -- more "detail" -- should be subdivided more, while the lower-entropy, "flatter" areas can be divided less. There are a number of different algorithms for choosing when and where to subdivide. Generally, they compare pixel values within a region, and split when the differences are above some threshold.

Ponce

A node can hold a pixel colour that is the synthesis of its children's colours. That's extremely useful for progressive rendering. – Buckboard

Answer 3

how does it work that the leaf nodes only hold pixels? Why dont the other nodes hold pixels?

This depends on what you're using the Quadtree for. You can link any kind of information to the other nodes, f.e. a pointer to the upper-left corner and the width/height of the rectangle this node describes, but you won't need it in most cases (or need things like the average values you can precompute to speed things up).

And how do we know how many times to subdivide our original root node to represent that given image?

With every subdivision, you half the width and height of a region, so for a square image of size n you'll need to subdivide log2(n) times, for a non-square image of size n*m you'll need at most max(log2(n), log2(m)) steps.

Louielouis

Answer 4

I think the best way to answer your question is to answer two questions that you didn't ask.

• What is a quadtree?
• How can this be applied to modelling systems of erratic density?

A quadtree is a binary tree in two dimensions. That's why there are (up to) four children for every non-leaf node. This allows you to apply an index to a plane just as a database uses a binary-tree or some variation thereof to index a single dimension, with the same highly advantageous sparse phase space representation properties.

The application of this to image compression and progressive display is pretty obvious: if you do a tree-walk limited to a depth of n then you get 4^n items of picture info spanning the entire image space. If you one level deeper, each pixel splits into four. JPEG2000 works like this, if I recall correctly. I said "items of picture info" because they need not be single bit; items could be 32bit ARGB or any other property (or properties) describing the space at that point.

Buckboard