Image Processing Using Quadtrees

An efficient method for the compression and manipulation of raster images

Raj Kumar Dash

Raj is studying in the masters of computer science program at the University of Guelph in Ontario. He is a main designer for a new GIS package, and is the assistant editor for id Magazine. You can contact him at raj@snowhite.cis.uoguelph.ca.

There are a variety of methods for processing raster images, including the use of numeric quadcodes to represent a data structure known as the "quadtree." While fractal compression and its cousins provide greater space savings, quadtrees (a term I'll use in the general sense) provide reasonable savings and retain an image's hierarchical information without loss of detail. This means you can perform image-processing operations on a quadtree and transfer the results of those operations when converting the quadtree back into a raster image. These characteristics are particularly useful when you're processing several images too large for storage in main memory. Still, there is one limitation: Quadtrees require that source images have a size of 2ⁿx2ⁿ pixels (where n=0,1,2,_). This limitation isn't serious, and I'll present a workaround.

Additionally, large sparse matrices can be compressed using quadtrees since they are effectively the same as a bitmap. Take, for example, a square, sparse matrix that represents the node connections of a large computer network. If the network has many nodes, and if the connections tend to cluster mainly in local groups, then a quadtree is an ideal structure for storing compressed link information for the network. A link between two computers is indicated by a black node. The lack of such a link is indicated by a white node.

Quadtrees

A quadtree can be represented as either a tree data structure or a linked list. To produce a quadtree, you recursively split an image of 2ⁿx2ⁿ pixels into quadrants and subquadrants until all the pixels in a subquadrant are of the same color, or the subquadrant is 1-pixelx1-pixel. (If the size condition of 2ⁿx2ⁿ doesn't hold, you can't partition the image into successive quadrants and subquadrants.)

Figure 1 shows how to derive a quadtree from an image, illustrating that quadcoding is particularly useful for compressing images containing large, homogeneous blocks of color. In Figure 1(a), the image has both single black and larger black quadrants. Figure 1(b) is the same, but the thickness of the grid lines indicate the level of the corresponding quadrant. In Figure 1(c), NW, NE, SW, and SE represent the northwest, northeast, southwest, and southeast quadrants, respectively. Each black circle represents either a single black pixel or a subquadrant of black pixels (and likewise for the white circles). A white square indicates that its component subquadrants are not all the same color. (Li and Loew use the term, "elementary squares" to describe any subimage of the size 2^mx2^m, where the full image is 2ⁿx2ⁿ and nm0. I'll use the term, "quadrant" to mean the same thing, but where m1.) Images that have a large number of individual pixels (m=0) take more space in quadtree format than an image of equal size with large quadrants; see Figure 2. This is because of the increased number of quad partitions. Apart from this limitation, quadtrees produce compression ratios of 20--90 percent, depending on the contents of an image. The image in Figure 2 has no homogeneous subquadrant larger than 1x1 and takes more space to store as a quadtree than the image in Figure 1(a). Both images have four levels of nodes in their quadtrees; however, all quadrants of the quadtree of the image in Figure 2 will

be a single pixel. Contrast this with Figure 1(c), where some quadrants are of size 2x2 pixels. The quadtree of the image in Figure 2 will be full, with a total of sigma 4ⁱ=4⁰+4¹+4²+4³=85 nodes.

Quadtrees for Monochrome Images

Monochrome images encoded as quadtrees offer the best space savings. Since there are only two "colors," you need only store information for one color explicitly and can imply information for the second. Suppose the images you're processing have large quadrants of color 0 (say, white). To save the most space, store information for only color 1 (say, black). Figure 3, for instance, shows the quadtree for Figure 1(a), the same quadtree as in Figure 1(c), with the white circles (subquadrants) removed. Instead of allocating space in the quadtree for missing nodes, set their parent pointers to NULL. Notice there are 11 leaf nodes in this tree, compared to the 28 leaves in Figure 1(c), a savings of more than 60 percent.

Pointerless Quadtrees for
Monochrome Images

A "quadcode" is a mathematical notation (for monochrome images) that eliminates quadtree pointers. The savings can be enormous; at least 66 percent over that of regular quadtrees, according to Gargantini.

You can represent an entire quadtree with a sequence of numeric strings (quadcodes) by designating a subquadrant at any level by a quadcode from 0 to 3, preceded by the quadcode for its parent quadrant. (NW=0, NE=1, SW=2, and SE=3; thus, the SW child quadrant of NW has a quadcode of 02.) Figure 4 generates pointerless quadtrees using quadcodes. Each quadrant is assigned a numeric code from 0 to 3, preceded by its parent quadrant's code. If the image is 2ⁿx2ⁿ, the longest possible quadcode is n digits long, and it represents a quadrant of one pixel. (Parent codes are shorter than their child codes.)

Multicolor and Gray-scale Images

Color and gray-scale images can be represented by either quadtrees or pointerless quadtrees (quadcodes), but quadtrees for color images require more space than monochrome images of the same size. Still, their quadtrees give favorable space savings, provided there are large quadrants of color. As with monochrome images, multicolor or gray-scale quadtrees imply information for one color--say, white. In Figure 5, you can eliminate all the white circle nodes to save even more space.

To create pointerless quadtrees for multicolor and gray-scale images, store a pair of values for each region of the image. The first value is the quadcode, the second, the color of the quadrant. For example, the image in Figure 5 is quadcoded as listed in Table 1. Note that you don't code color 0 (white) regions. For images with 256 colors, represent each color by one of the ASCII characters from 0-255.

Quadtrees for Rectangular Images

Up to now, I've discussed only square images, although most computer screens have a rectangular bitmap (768x1024, 480x640, and so on). The easiest way to produce a quadtree for rectangular images is to use the smallest square grid that fully contains the image. For example, assume you have an image that's 480x640 pixels. The smallest square grid that fully contains this image is 1024x1024. Why? If you use n=9, you have a grid of size 512x512. That's enough to accommodate the 480-pixel dimension, but not the 640-pixel dimension. The only choice, then, is n=10, or a grid of 1024x1024. Treat the excess pixels as "don't-care" colors, chosen to minimize the number of subquadrants needed to partition the image. Figure 6 shows a quadtree for a 7x6 pixel image. The 7x6 image in Figure 6(a) needs to be contained in an 8x8 grid before we can create its quadtree. Notice in the augmented image in Figure 6(b) that the new row has pixels of both colors, whereas the two new columns have white pixels. This particular ordering ensures a minimal quadtree.

General Quadtree Operations

One advantage of quadtrees is that image manipulation becomes faster since operations apply to whole regions of pixels simultaneously. This is a necessity if you can't read an entire image into memory. Another advantage is that all operations performed on a quadtree transfer back to the image during conversion.

It's no problem if you have an augmented rectangular image and alter some of the excess pixels. Why? Because you ignore excess pixels when converting the quadtree back into a raster image, so it does not matter what operations you perform on "don't-care" pixels.

One quadtree operation is to contrast or change pixel colors. Suppose you have a gray-scale image that has large blocks of very light-gray pixels that you want to change to provide more contrast. By changing the color of the subquadrants containing the target pixels, you also change the component pixels. (This becomes obvious after the quadtree is converted back to its associated image.) See Figure 7.

Masking is an operation that "cuts" shapes in an image. Say you have a square monochrome image and you want to stamp it with the word "hi." Create the "mask" image first, then apply the mask by XORing it with the test image; refer to Figure 8.

Spatial Operations

A number of quadtree operations deal with the spatial attributes of an image, including those that determine the color of a particular pixel and calculate the area covered by a given color.

Attributes of a Given Pixel. Given either the quadcode or the row/column position of a pixel, you can easily determine its color. (Note that row/column values range from 0 to 2ⁿ-1.) You first convert the row/column pair to the equivalent quadcode by converting both the row and column values into equivalent binary (base 2) strings. You then pad the strings on the left with 0s so that each string is n digits long. Then, for each pair of bits from left to right, use Table 2 to determine the equivalent quadcode digit.

Now search the quadtree for either the calculated quadcode or an ancestor's code. If you can't find either, the pixel must be white (since this is the color left out of the quadtree). For example, suppose you use the pixel at row=2, column=2 (both of origin=0), as in Figure 5(a). Both the row and column values convert to the binary string 010. Since the first pair of bits consists of 0 and 0, the corresponding qcode digit is 0. The next qcode digit is 3, followed by 0: qcode=030. You now search the list of quadcodes for 030 or an ancestor code, such as 03 or 0. Since the parent quadrant (qcode=03, color=1) is present in the quadtree, the pixel's color is 2.

Area of a Given Color. The area covered by a particular color, c, is the sum of the areas of its component quadrants: A(color c)= sigma _iA(q_i) for all leaf quadrants q_i of color c.

A single quadrant that has a quadcode of length m has an area equal to 2^n-mx2^n-m, nm0. For example, the quadcode 03 in Figure 5(a) has color 1. The area is 2^3-2x2^3-2=2x2=4. (To determine the total area of color 1, search the quadtree for all leaf nodes having color 1, calculate each area as above, and then sum the individual areas.)

Manipulation of Two or More Quadtrees

Quadtrees can be used to manipulate several images simultaneously. In particular, you can perform image overlays and intersections on quadtrees when the associated images do not fit into memory. For example, take two images of size 1024x1024 pixels that have 512 nodes apiece in their respective quadtree structures. An image overlay then takes 512 operations instead of 1,048,576 (1024x1024).

Image Overlays. Monochrome-image overlay operations include AND, OR, and XOR; see Figure 9.

Image Intersection. For monochrome images, you perform image intersections with the AND operator. For color and gray-scale images, the method is somewhat different, although the principle is the same. In this case, you test two corresponding pixels for equality of color, instead of True (color white) and False (color black) values. (Choose the color of the first image's pixel if the two pixels are not the same.)

Figure 1: (a) Sample image; (b) same image but with level of corresponding quadrant indicated; (c) the quadtree for (a).

Figure 2: Sample image which has no homogeneous subquadrant larger than 1x1.

Figure 3: Same quadtree as for Figure 1(c) but with the white circles (subquadrants) removed, resulting in savings greater than 60 percent.

Figure 4: Generating pointerless quadtrees using quadcodes.

Figure 5: (a) Multicolor image; (b) multicolor quadtree.

Table 1: The image in Figure 5 is quadcoded like this.

NW:     (003,1), (012,1), (013,1), (021,1), (023,1), (03,1)
NE:     (103,2), (112,2), (113,2), (121,1), (123,2), (13,2)
SW:     (202,2), (203,2), (22,2), (23,1)
SE:     (3,3)

Figure 6: (a) Sample 7x6 image that needs to be contained in an 8x8 grid before we can create its quadtree; (b) augmented image.

Figure 7: Contrasting: Change all colors < 4 to color 1 and the colors > 3 to color 7. The result is a high-contrast image.

Figure 8: Filtering: (a) image; (b) mask; (c) masked (XORed result).

Table 2: Determining equivalent quadcode digits.

     Row      Column      qcode digit
     bit     bit     (base 4)
digit     0     0     0
     0     1     1
     1     0     2
     1     1     3