Algorithms for the Conversion of Quadtrees to Rasters

Abstract

A number of algorithms are presented for obtaining a raster representation for an image given its quadtree. The algorithms are given in an evolutionary manner starting with the straight-forward top-down approach that visits each run in a row in succession starting at the root of the tree. The remaining algorithms proceed in a manner akin to an inorder tree traversal. All of the algorithms are analyzed and an indication is given as to when each is preferable. The execution time of all of the algorithms is shown to be proportional to the sum of the heights of the blocks comprising the image.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1980
Accession Number
ADA109563

Entities

People

  • Hanan Samet

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Coding
  • Contrast
  • Diameters
  • Efficiency
  • Lists (Data Structures)
  • Notation
  • Quadrants
  • Separators
  • Sequences
  • Symbols
  • Terminals
  • Transitions
  • Trees (Data Structures)
  • Two Dimensional

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Vision.
  • Operations Research