The quadtree is a hierarchical data model based upon a regular recursive decomposition of space, which has been found useful in such areas as image processing, computer graphics, cartography and spatial information sy...
详细信息
The quadtree is a hierarchical data model based upon a regular recursive decomposition of space, which has been found useful in such areas as image processing, computer graphics, cartography and spatial information systems. The linearquadtree is a pointerless representation of the quadtree. In the paper, a number of linear quadtree algorithms are presented for a transputer array. These form a largely complementary set to those developed by Bhaskaret al.[1] for a similar multiprocessor architecture. Emphasis is placed on algorithms which require the neighbours of quadtree leaves to be accessed. These include perimeter computation, connected component labelling and image dilation. A quadtree generation algorithm is also described. Timing estimates have been carried out using a transputer development system. A price to be paid for the speed increases achieved is an increase in the complexity of the multiprocessor algorithms.
暂无评论