Quadtrees

Defintion

Quadtrees represent a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants and so on until the contents of the cells meet some criterion of data occupancy. The resolution (cell size) of the grid varies depending on the data density.

Quadtree indexing

On one side, the quadtree solution is widely used to solve spatial indexing problems. As shown in the next lesson (Data Compression), another application field of this technique is the data compression. The quadtree compression technique is the most common compression method applied to raster data.

The pattern of the linear quadtree numbering sequence is that of a Peano curve, which is one of a variety of space-filling curves that may be of interest for indexing spatial data, whereby cells that are adjacent in space are more likely to have similar spatial index addresses that in column or row ordering schema. Hence, data that are close in space are close in the storage system.

Peano curve

The first use of this particular numbering sequence for spatial indexing is usually attributed to Morton (1966), and it is sometimes referred to variously as Morton sequence, Morton matrix or Morton numbering, while individual addresses may be called Morton number. An important property of Morton number is that they can be generated by alternating successive bits of each of the binary representations of the x and y coordinates of the lower left corner of the cell to which they refer. The process is called bit interleaving (Jones 1997).

Bit interleaving process

In the example above the quadtree address 37 is obtained by two steps:

Convertion of the decimal coordinates (4,3) to binary (100, 011).
The bit-interleaving process produces the binary number (100101), which converted to decimal is 37.

An example

Considering a picture as a matrix A whose dimension is a power of 2, say 2ⁿ, this can be subdivided into four square matrices A₀, A₁, A₂, A₃, , whose dimensions are half of A. This process can be repeated recursively n times, until the pixels within a quadrant are all of the same value (homogeneity criterion). The levels can be numbered, starting with zero for the whole picture, down to n for the single pixel. A particular square may be labeled with one of the symbols 0, 1, 2, or 3, concatenated to the label of its predecessor square. In this way, single pixels will have labels that are n characters long. We can express this arrangement as a tree, whose nodes correspond to the squares. Nodes are connected if one of the corresponding squares immediately contains the other. The root of the tree corresponds to the whole picture, the leaves to the single pixels, and all other nodes have down degree 4.

Quadtree indexing

Since the k^th-level contains 4k squares, the tree has a total of:

nodes. Therefore, there are approximately 33% more nodes than pixels.
The following figure shows the addressing notation for a 8x8 picture:

Adressing notation