انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

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.

The 8×8 bitmap in 4.148a produces the 21-node quadtree of 4.148b. Sixteen nodes are leaves (each containing the color of one quadrant, 0 for white, 1 for black), and the other five (the gray circles) are interior nodes containing four pointers each. The quadrant numbering used is   The size of a quadtree depends on the complexity of the image

The size of a quadtree depends on the complexity of the image. Assuming a bitmap size of 2^N×2^N, one extreme case is where all the pixels are identical. The quadtree in this case consists of just one node, the root. The other extreme case is where each quadrant, even the smallest one, is nonuniform. The lowest level of the quadtree has, in such a case,

2ⁿ × 2ⁿ = 4ⁿ nodes. The level directly above it has a quarter of that number (4^n-1), and the level above that one has 4^n-2 nodes. The total number of nodes in this case is:

4⁰+4¹+? ? ?+4^n-1+4ⁿ = (4ⁿ⁺¹?1)/3 ? 4N(4/3) ? 1.33×4N = 1.33(2N ×2N). In this worst case the quadtree contains about 33% more nodes than the number of pixels (the bitmap size). Such an image therefore generates considerable expansion when converted to a quadtree.