Quadtrees

Quadtrees
A quadtree compression of a bi-level image is based on the principle of image compression which states; If we select a pixel in the image at random, there is a good chance that its immediate neighbors will have the same or similar color. The quadtree method scans the bitmap, area by area, looking for areas composed of identical pixels (uniform areas).
The input consists of bitmap pixels, and the output is a tree (a quadtree, where
each node is either a leaf or has exactly four children). The size of the quadtree depends on the complexity of the image. For complex images, the tree may be bigger than the original bitmap, resulting in expansion. The method starts by constructing a single node, the root of the final quadtree. It divides the bitmap into four quadrants, each to become a child of the root. A uniform quadrant (one where all the pixels have the same color) is saved as a leaf child of the root. A nonuniform quadrant is saved as an (interior node) child of the root. Any nonuniform quadrants are then recursively divided into four smaller subquadrants that are saved as four sibling nodes of the quadtree. Figure 4.148 shows a simple example.