Region Representation: Quadtree-to-Raster Conversion

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1979
Accession Number
ADA084288

Entities

People

  • Hanan Samet

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computer Graphics
  • Conversion
  • Graphics
  • Image Processing
  • Mathematics
  • Night Vision
  • Pattern Recognition
  • Quadrants
  • Recognition
  • Security
  • Terminals
  • Universities

Fields of Study

  • Computer science

Readers

  • Image Processing and Computer Vision.
  • Linear Algebra
  • Mathematical Modeling and Probability Theory.