The Labeled Discrete Voroni Diagram

Abstract

Generalized voronoi diagrams of sets of digital curves are a helpful tool in picture anlaysis. In this paper, an algorithm for computing laberled Voronoi diagrams for digital straight line segments is given. Special emphasis was given to the use of a labeled Euclidean distance transform. This transform is the key feature of the proposed lable propagation process. The proposed parallel algorithm for computing labeled Voronoi diagrams has time complexity 0(max(M,N)) for input pictures of size NxM using a mesh connected array processor. The proposed serial algorithm for computing labeled Voronoi diagrams has time complexity 0(MN). Additional Keywords: Image analysis; and Pixels.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1983
Accession Number
ADA157167

Entities

People

  • Takashi Matsuyama
  • Tsaiyun Phillips

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Classification
  • Computations
  • Data Analysis
  • Digital Image Processing
  • Digital Images
  • Extraction
  • Geometry
  • Image Processing
  • Images
  • Information Processing
  • Pattern Recognition
  • Rotation
  • Shape
  • Two Dimensional

Fields of Study

  • Engineering

Readers

  • Computer Vision.
  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design