Neighbor Finding Techniques for Images Represented by Quadtrees
Hanan Samet · 1980
Image representation plays an important role in image processing applications. Recently there has been a considerable interest in the use of quadtrees. This has led to the development of algorithms for performing image processing tasks as well as for performing converting between the quadtree and other representations. Common to these algorithms is a traversal of the tree and the performance of a given computation at each node. These computations typically require the ability to examine adjacencies between neighboring nodes. Algorithms are given for determining such adjacencies in the horizontal, vertical, and diagonal directions. The execution times of the algorithms are analyzed using a suitably defined model. I. JNTRODUCTJON Region representation is an important aspect of image processing with numerous representations finding use. Recently, there has emerged a considerable amount of interest in the quadtree [3-8, 111. This stems primarily from its hierarchical nature, which lends itself to a compact representation. It is also quite efficient for a number of traditional image processing operations such as computing perimeters [14], labeling connected components [ 131, finding the genus of an image [I], and comput-