Help about Quadtree


Quadtree

Quadtree is a method for compressing bitmap images. A quadtree compression of an image is based on the observation that, if we select a pixel in the image at random, there is a good chance that its neighbors will have the same color. The quadtree method, thus, scans the bitmap, area by area, looking for areas full of identical pixels.

The input consists of bitmap pixels, and the output is a tree(a quadtree where a node is either a leaf or has exactly four children). The size of the quadtree depends on the complexity of the image. The method starts by building 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 are the same color) is saved as a leaf child of the root. A non-uniform quadrant is saved as an interior node of the root. Any non-uniform quadrants are then recursively divided into four smaller subquadrants that are saved as four sibling nodes of the quadtree.

The order in which the quadrants are inspected in this package is the following:
upper-left, upper-right, lower-left, lower-right.


E-mail comments or suggestions about Quadtree to khuri@cs.sjsu.edu or joy@mathcs.sjsu.edu