Quad trees and Octrees:Image Processing Applications
Image Processing Applications
Quad trees are ubiquitously used in image processing applications. Consider a two dimensional square array of pixels representing a binary image with black foreground and white background (Figure 19.8). As with region quad trees used to represent point data, a hierarchical cell decomposition is used to represent the image. The pixels are the smallest cells used in the decomposition and the entire image is the root cell. The root cell is decomposed into its four immediate subcells and represented by the four children of the root node. If a subcell is completely composed of black pixels or white pixels, it becomes a leaf in the quad tree. Otherwise, it is recursively decomposed. If the resolution of the image is 2k × 2k, the height of the resulting region quad tree is at most k. A two dimensional image and its corresponding region quadtree are shown in Figure 19.8. In drawing the quad tree, the same ordering of the immediate subcells of a cell into SW, NW, SE and NE quadrants is followed.
Each node in the tree is colored black, white, or gray, depending on if the cell consists of all black pixels, all white pixels, or a mixture of both black and white pixels, respectively.
Thus, internal nodes are colored gray and leaf nodes are colored either black or white.
Each internal node in the image quad tree has four children. For an image with n leaf nodes, the number of internal nodes is (n−1) . For large images, the space required for storing the internal nodes and the associated pointers may be expensive and several space-efficient storage schemes have been investigated. These include storing the quad tree as a collection of leaf cells using the Morton numbering of cells [21], or as a collection of black leaf cells only [8, 9], and storing the quad tree as its preorder traversal [19]. Iyengar et al. introduced a number of space-efficient representations of image quad trees including forests of quad trees [10, 26], translation invariant data structures [17, 32, 33] and virtual quad trees [18].
The use of quad trees can be easily extended to grayscale images and color images. Sig- nificant space savings can be realized by choosing an appropriate scheme. For example, 2r gray levels can be encoded using r bits. The image can be represented using r binary valued quad trees. Because adjacent pixels are likely to have gray levels that are closer, a gray encoding of the 2r levels is advantageous over a binary encoding [19]. The gray encoding has the property that adjacent levels differ by one bit in the gray code representation. This should lead to larger blocks having the same value for a given bit position, leading to shallow trees.
Construction of Image Quad trees
Region quad trees for image data can be constructed using an algorithm similar to the bottom-up construction algorithm for point region quad trees described in Subsection 19.2.5. In fact, constructing quad trees for image data is easier because the smallest cells in the hierarchical decomposition are given by the pixels and all the pixels can be read by the algorithm as the image size is proportional to the number of pixels. Thus, quad tree for region data can be built in time linear in the size of the image, which is optimal. The pixels of the image are scanned in Morton order which eliminates the need for the sorting step in the bottom-up construction algorithm. It is wasteful to build the complete quad tree with all pixels as leaf nodes and then compact the tree by replacing maximal sub trees having all black or all white pixels with single leaf nodes, though such a method would still run in linear time and space. By reading the pixels in Morton order, a maximal black or white cell can be readily identified and the tree can be constructed using only such maximal cells as leaf nodes [27]. This will limit the space used by the algorithm to the final size of the quad tree.
Union and Intersection of Images
The union of two images is the overlay of one image over another. In terms of the array of pixels, a pixel in the union is black if the pixel is black in at least one of the images. In the region quad tree representation of images, the quad tree corresponding to the union of two images should be computed from the quad trees of the constituent images. Let I1 and I2 denote the two images and T1 and T2 denote the corresponding region quadtrees. Let T denote the region quad tree of the union of I1 and I2. It is computed by a preorder traversal of T1 and T2 and examining the corresponding nodes/cells. Let v1 in T1 and v2 in T2 be nodes corresponding to the same region. There are three possible cases:
• CaseI: If v1 or v2 is black, the corresponding node is created in T and is colored black. If only one of them is black and the other is gray, the gray node will contain a sub tree underneath. This sub tree need not be traversed.
• CaseII: If v1 (respectively, v2) is white, v2 (respectively, v1) and the subtree underneath it (if any) is copied to T .
• CaseIII: If both v1 and v2 are gray, then the corresponding children of v1 and v2 are considered.
The tree resulting from the above merging algorithm may consist of unnecessary subdivisions of a cell consisting of completely black pixels. For example, if a region is marked gray in both T1 and T2 but each of the four quadrants of the region is black in at least one of T1 and T2, then the node corresponding to the region in T will have four children colored black. This is unnecessary as the node itself can be colored black and should be considered a leaf node. Such adjustments need not be local and may percolate up the tree. For instance, consider a checker board image of 2k × 2k pixels with half black and half white pixels such that the north, south, east and west neighbors of a black pixel are white pixels and vice versa. Consider another checker board image with black and white interchanged. The quad tree for each of these images is a full 4-ary tree of level k. But overlaying one image over another produces one black square of size 2k × 2k. The corresponding quad tree should be a single black node. However, merging initially creates a full 4-ary tree of depth k. To compact the tree resulting from merging to create the correct region quad tree, a bottom-up traversal is performed. If all children of a node are black, then the children are removed and the node is colored black.
The intersection of two images can be computed similarly. A pixel in the intersection of two images is black only if the corresponding pixels in both the images are black. For instance, the intersection of the two complementary checkerboard images described above is a single white cell of size 2k × 2k. The algorithm for intersection can be obtained by interchanging the roles of black and white in the union algorithm. Similarly, a bottom- up traversal is used to detect nodes all of whose children are white, remove the children, and color the node white. Union and intersection algorithms can be easily generalized to multiple images.
Rotation and Scaling
Quad tree representation of images facilitates certain types of rotation and scaling operations. Rotations on images are often performed in multiples of 90 degrees. Such a rotation has the effect of changing the quadrants of a region. For example, a 90 degree clockwise rotation changes the SW, NW, SE, NE quadrants to NW, NE, SW, SE quadrants, respectively. This change should be recursively carried out for each region. Hence, a rotation that is a multiple of 90 degrees can be effected by simply reordering the child pointers of each
node. Similarly, scaling by a power of two is trivial using quad trees since it is simply a loss of resolution. For other linear transformations, see the work of Hunter [14, 15].
Two black pixels of a binary image are considered adjacent if they share a horizontal or vertical boundary. A pair of black pixels is said to be connected if there is a sequence of adjacent pixels leading from one to the other. A connected component is a maximal set of black pixels where every pair of pixels is connected. The connected component labeling problem is to find the connected components of a given image and give each connected component a unique label. Identifying the connected components of an image is useful in object counting and image understanding. Samet developed algorithms for connected component labeling using quad trees [28].
Let B and W denote the number of black nodes and white nodes, respectively, in the quad tree. Samet’s connected component labeling algorithm works in three stages:
1. Establish the adjacency relationships between pairs of black pixels.
2. Identify a unique label for each connected component. This can be thought of as computing the transitive closure of the adjacency relationships.
3. Label each black cell with the corresponding connected component.
The first stage is carried out using a postorder traversal of the quad tree during which adjacent black pixels are discovered and identified by giving them the same label. To begin with, all the black nodes are unlabeled. When a black region is considered, black pixels adjacent to it in two of the four directions, say north and east, are searched. The post order traversal of the tree traverses the regions in Morton order. Thus when a region is encountered, its south and west adjacent black regions (if any) would have already been processed. At that time, the region would have been identified as a neighbor. Thus, it is not necessary to detect adjacency relationships between a region and its south or west adjacent neighbors.
Suppose the postorder traversal is currently at a black node or black region R. Adjacent black regions in a particular direction, say north, are identified as follows. First, identify the adjacent region of the same size as R that lies to the north of R. Traverse the quad tree upwards to the root to identify the first node on the path that contains both the regions, or equivalently, find the lowest common ancestor of both the regions in the quad tree. If such a node does not exist, R has no north neighbor and it is at the boundary of the image. Otherwise, a child of this lowest common ancestor will be a region adjacent to the north boundary of R and of the same size as or larger than R. If this region is black, it is part of the same connected component as R. If neither the region nor R is currently labeled, create a new label and use it for both. If only one of them is labeled, use the same label for the other. If they are both already labeled with the same label, do nothing. If they are both already labeled with different labels, the label pair is recorded as corresponding to an adjacency relationship. If the region is gray, it is recursively subdivided and adjacent neighbors examined to find all black regions that are adjacent to R. For each black neighbor, the labeling procedure described above is carried out.
The run time of this stage of the algorithm depends on the time required to find the north and east neighbors. This process can be improved using the smallest-cell primitive described earlier. However, Samet proved that the average of the maximum number of nodes visited by the above algorithm for a given black region and a given direction is smaller than or equal to 5, under the assumption that a black region is equally likely to occur at any
position and level in the quad tree [28]. Thus, the algorithm should take time proportional to the size of the quad tree, i.e., O(W + B) time.
Stage two of the algorithm is best performed using the union-find data structure [34]. Consider all the labels that are used in stage one and treat them as singleton sets. For every pair of labels recorded in stage one, perform a find operation to find the two sets that contain the labels currently, and do a union operation on the sets. At the end of stage two, all labels used for the same connected component will be grouped together in one set. This can be used to provide a unique label for each set (called the set label), and subsequently identify the set label for each label. The number of labels used is bounded by
B. The amortized run time per operation using the union-find data structure is given by the inverse Ackermann’s function [34], a constant (≤ 4) for all practical purposes. Therefore,
the run time of stage two can be considered to be O(B). Stage three of the algorithm can be carried out by another postorder traversal of the quadtree to replace the label of each black node with the corresponding set label in O(B + W ) time. Thus, the entire algorithm runs in O(B + W ) time.
Comments
Post a Comment