Quadtree: Exploring Hierarchical Data Structures for Image Analysis

By Fouad Sabry

What is Quadtree

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 data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Quadtree

Chapter 2: Octree

Chapter 3: R-tree

Chapter 4: Binary tree

Chapter 5: B-tree

Chapter 6: AVL tree

Chapter 7: Red-black tree

Chapter 8: Binary search tree

Chapter 9: Binary heap

Chapter 10: Segment tree

(II) Answering the public top questions about quadtree.

(III) Real world examples for the usage of quadtree in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Quadtree.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 14, 2024

Book preview

Chapter 1: Quadtree

The data structure of a quadtree is a tree in which each internal node has exactly four offspring. Quadtrees are the two-dimensional equivalent of octrees and are typically used to partition a two-dimensional space into four quadrants or sections. The information associated with a leaf cell varies by application, but a leaf cell is a unit of interesting spatial information..

The partitioned zones may have arbitrary or square or rectangular shapes. 1974 saw the designation of this data structure as a quadtree by Raphael Finkel and J.L. Bentley. Q-tree is another term for a similar partitioning scheme. All types of quadtrees have certain characteristics:

They break space down into flexible cells.

Each compartment (or receptacle) has a maximum capacity. When the bucket's maximum capacity is reached, it separates.

The tree directory conforms to the quadtree's spatial decomposition.

A tree-pyramid (T-pyramid) is a full tree; every node of the T-pyramid contains four child nodes, with the exception of leaf nodes; all leaves are on the same level, which corresponds to individual pixels in a picture. Similar to how a complete binary tree can be stored compactly in an array, tree-pyramid data can be stored compactly in an array as an implicit data structure.

Quadtrees can be categorized based on the types of data they represent, such as areas, points, lines, and curves. Quadtrees can also be categorized based on whether the shape of the tree is independent of the processing order. The subsequent are frequent forms of quadtrees:.

The region quadtree illustrates a two-dimensional partition of space by decomposing the region into four equal quadrants, subquadrants, etc., with each leaf node carrying data relating to a particular subregion. Each node in the tree has either precisely four children or none (a leaf node). This decomposition method (i.e. subdividing subquadrants as long as there is relevant data in the subquadrant for which greater refinement is sought) makes the height of quadtrees sensitive to and dependent on the spatial distribution of interesting areas in the space being decomposed. The region quadtree is a variant of the trie data structure.

A region quadtree with a depth of n may be used to represent an image consisting of 2n × 2n pixels, where every pixel is either 0 or 1.

The root node represents the totality of the image region.

If pixels in any region are not fully 0s or 1s, the region is considered invalid, It is segmented.

This is an application, Each leaf node represents a block of pixels consisting entirely of 0s or 1s.

Note the possible space savings when these trees are utilized for image storage; a common characteristic of visual depictions is the presence of numerous large areas with the same color value throughout.

Instead of storing a large 2-D array of every pixel in an image, a smaller array is used, A quadtree can capture the same information at possibly many more division levels than pixel-resolution sized cells.

Tree resolution and size are limited by pixel and picture dimensions.

A region quadtree may also be used to represent a data field with changeable resolution. For instance, a quadtree may be used to record the temperatures in a region, with each leaf node storing the average temperature for the subregion it represents.

The point quadtree

Following is how point quadtrees are built. Given the next point to insert, the corresponding cell is located and the point is added to the tree. The new point is inserted so that the cell containing it is partitioned into quadrants by the vertical and horizontal lines that pass through it. Cells are hence rectangular, but not always square. Each node in these trees holds one of the input points.

Due to the fact that the partition of the plane is determined by the order of point insertion, the height of the tree is sensitive and depends on insertion order. Inserting in a wrong order may result in a tree whose height is proportional to the number of input points (at which point it becomes a linked-list). Preprocessing can be used to generate a tree with balanced height if the point set is static.

A node of a point quadtree is similar to a node of a binary tree, with the primary distinction being that it has four pointers (one for each quadrant) as opposed to two (left and right) like in a conventional binary tree. In addition, a key is typically divided into two components that refer to x and y coordinates. Consequently, a node contains the following data::

four pointers: quad[‘NW’], quad[‘NE’], quad[‘SW’], and quad[‘SE’]

point; which contains in turn:

identifier; typically stated as x, y coordinates

a value, such as a name

Point-region (PR) quadtrees resemble region quadtrees quite closely. The difference lies in the type of cell-related data saved. In a region quadtree, a value that applies to the full area of a leaf cell is kept. However, the cells of a PR quadtree hold a list of points that reside within a leaf cell. As previously stated, the height of trees employing this decomposition approach is dependent on the spatial distribution of the points. Similar to the point quadtree, the PR quadtree may have a linear height when a bad set is provided.

Edge quadtrees (similar to PM quadtrees) are employed to hold lines as opposed to points. Cells are subdivided to an extremely fine resolution in order to approximate curves, precisely till there is a single line segment per cell. Edge quadtrees will continue to divide until they reach their maximum level of decomposition near corners/vertices. This may lead to severely imbalanced trees that negate the goal of indexing.

The polygonal map quadtree (or PM Quadtree) is a variant of quadtree used to hold groups of potentially degenerate polygons (meaning that they have isolated vertices or edges). A significant distinction between PM quadtrees and edge quadtrees is that the cell under examination is not partitioned if the segments within the cell intersect at a vertex.

There are three primary kinds of PM Quadtrees, which differ based on the data stored in each black node. PM3 quadtrees can hold an arbitrary number of non-intersecting edges and a single point at most. PM2 quadtrees are identical to PM3 quadtrees with the exception that all edges must terminate at the same position. PM1 quadtrees are similar to PM2 quadtrees, but black nodes may include a point and its edges or only a set of edges that share a point, but a point and a set of edges that do not contain the point are not permitted.

This section provides a summary of a chapter from Sariel Har-book. Peled's.

If we were to store every node corresponding to a subdivided cell, the storage need would be prohibitive, We may wind up storing a substantial number of empty nodes.

We can reduce the size of these sparse trees by saving only the subtrees whose leaves include interesting data (i.e.

significant subbranches).

We can actually reduce the size much more.

When we retain just essential subtrees, The procedure of pruning may leave long routes in the tree with degree two intermediary nodes (a link to one parent and one child).

It turns out that we only need to store the node u at the beginning of this path (and associate some meta-data with it to represent the removed nodes) and attach the subtree rooted at its end to u .

When given poor input points, it is nevertheless possible for these compressed trees to have a linear height.

Although a substantial amount of the tree is pruned during this compression,, Logarithmic-time search is still possible, insertion, and deletion by the use of Z-order curves.

The Z-order curve maps each cell of the full quadtree (and hence even the compressed quadtree) in O(1) time to a one-dimensional line (and maps it back in O(1) time too), establishing a complete order on the elements.

Therefore, We can store the quadtree in an ordered set data structure (in which we store the nodes of the tree).

We must state a reasonable assumption before we continue: we assume that given two real numbers {\displaystyle \alpha ,\beta \in [0,1)} expressed as binary, we can compute in O(1) time the index of the first bit in which they differ.

We also assume that we can compute in O(1) time the lowest common ancestor of two points/cells in the quadtree and establish their relative Z-ordering, and we can compute the floor function in O(1) time.

With these premises, point location of a given point q (i.e.

determining the cell that would contain q ), insertion, and deletion operations can all be performed in O(\log {n}) time (i.e.

time required to perform a search within the underlying ordered set data structure).

To perform a point location for q (i.e.

find the corresponding cell in the compressed tree):

Find the existing cell in the compressed tree that comes before q in the Z-order.

Call this cell v .

If {\displaystyle q\in v} , return v .

Else, find what would have been the lowest common ancestor of the point q and the cell v in an uncompressed quadtree.

Call this ancestor cell u .

Find the existing cell in the compressed tree that comes before u in the Z-order and return it.

Without delving into specifics, to do insertions and deletions, we first perform a point placement for the item to be inserted or deleted, and then insert or remove it. Care must be made to reshape the tree as necessary by adding or removing nodes.

Image representation

Bitmap and its compressed quadtree representation

Image processing

Mesh generation

Spatial indexing, point-based and range-based searches

Two-dimensional collision detection efficiency

View data frustum culling for terrain

Sparse data storage, such as format information for a spreadsheet or matrix calculations

Multidimensional field solution (computational fluid dynamics, electromagnetism)

Program for Conway's Game of Life simulation.

State estimation

Quadtrees are also utilized in fractal picture analysis.

Maximum disjoint sets

Quadtrees, namely the region quadtree, have adapted themselves nicely to applications in image processing. Although region quadtrees and the image processing procedures done on them are equally applicable to color images, we will restrict our discussion to binary image data.

A benefit of employing quadtrees for picture processing is that set operations such as union and intersection may be performed rapidly and easily. Given two binary images, the image union (also known as overlay) produces an image in which a pixel is black if one of the input images contains a black pixel at the same place. In other words, a pixel in the output image is only white if the matching pixel in both input images is white; otherwise, it is black. Instead of doing the operation pixel-by-pixel, we can efficiently compute the union by using the quadtree's capacity to represent multiple pixels with a single node. For the purposes of the following explanation, if a subtree contains both black and white pixels, we shall claim that the subtree's root is gray.

The algorithm works by traversing the two input quadtrees ( T_{1} and T_{2} ) while building the output quadtree T .

Informally, the algorithm is described as follows:.

Consider the nodes {\displaystyle v_{1}\in T_{1}} and {\displaystyle v_{2}\in T_{2}} corresponding to the same region in the images.

If v_{1} or v_{2} is black, the corresponding node is created in T and is colored black.

If one is black and the other is gray, just one is black, Underneath the gray node will be a subtree.

This subtree is unnecessary to navigate.

If v_{1} (respectively, v_{2} ) is white, v_{2} (respectively, v_{1} ) and the subtree underneath it (if any) is copied to T .

If both v_{1} and v_{2} are gray, then the corresponding children of v_{1} and v_{2} are considered.

While the algorithm is effective, It does not ensure a minimum-sized quadtree by itself.

For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size {\displaystyle 2^{k}\times 2^{k}} with its complement.

The outcome is a massive black square that should be represented by a