Region Representation: Quadtree-to-Raster Conversion

摘要

An algorithm is presented for obtaining a raster representation for an image given its quadtree. For each raster row the algorithm visits the appropriate nodes in the quadtree and, for each such node, outputs a run of length equal to the width of the corresponding block. Each block's node is visited as many times as it is high. Analysis of the algorithm reveals that its execution time is proportional to the sum of the heights of the blocks comprising the image. The total number of terminal and non-terminal nodes visited by the algorithm is also computed and shown to be a function of the number of maximal black and white blocks in the image. This means that the algorithm's execution time is directly proportional to the complexity of the image. (Author)