Connected Component Labeling Using Quadtrees

Abstract

An algorithm is presented for labeling the connected components of an image represented by a quadtree. The algorithm proceeds by exploring all possible adjacencies for each node once and only once. Once this is done, any equivalences generated by the adjacency labeling phase are propagated. Analysis of the algorithm reveals that its worst case average execution time is bounded by a quantity proportional to the product of the log of the region's diameter and the number of blocks comprising the area connected by the components.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1979
Accession Number
ADA076130

Entities

People

  • Hanan Samet

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computations
  • Computer Graphics
  • Computer Science
  • Computers
  • Contracts
  • Diameters
  • Image Processing
  • Maryland
  • New York
  • Night Vision
  • Pattern Recognition
  • Quadrants
  • Terminals
  • Trees (Data Structures)
  • Universities

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.