Menu
I understand how quad trees work on square images (by splitting the image until the section is a single colour, which is stored in the leaf node).
What happens if the image has one dimension longer that the other, you may end up with a 2x1 pixel area as the smallest sub unit, making it difficult to use quadtree division methods to store a single colour. How would you solve this issue?
855
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
The beauty called a quadtree Trees generally have internal nodes (nodes that have at least one child) and leaf nodes which have no children. These nodes holds data that are ordered in a hierarchical order. A quadtree is a tree data structure in which each node has zero or four children.
Thm. A quadtree of depth d storing n points has O((d+1)n) nodes. Proof: Every internal node represents a square with at least 2 points in it.
At the time of storing every node corresponding to a subdivided cell, we may end up storing a lot of empty nodes. Cutting down on the size of such sparse trees is possible by only storing subtrees whose leaves have interesting data (i.e. "important subtrees").
You could pad the image until it is an equal and power of two size. While it may add some extra memory requirements, the increase shouldn't be that large.
The 2x1 example would be padded to a standard 2x2 and store the real size or use a special value for padded nodes so you can restore the original size.
74
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
