Region Representation: Quadtrees from Binary Arrays

Abstract

An algorithm is presented for constructing a quadtree from the array representation of a binary image. The algorithm examines each pixel in the image once and only once. In addition, as the tree is constructed, only maximal sized nodes are ever created. Thus the algorithm never requires temporary nodes. The execution time of the algorithm is equal to the number of pixels in the image. The amount of space, in addition to that necessary for the final quadtree, is proportional to the log of the image diameter.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1979
Accession Number
ADA084287

Entities

People

  • Hannan Samet

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Cartography
  • Computer Graphics
  • Computers
  • Construction
  • Contrast
  • Decomposition
  • Diameters
  • Efficiency
  • Graphics
  • Image Processing
  • Information Processing
  • Quadrants
  • Terminals

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Human-Computer Interaction (HCI).

Technology Areas

  • Space
  • Space - Space Objects