The Hough Transform has O(N) Complexity on SIMD N x N Mesh Array Architectures.

Abstract

This paper reports on new algorithms for computing the Hough transform on mesh array architectures. The mesh is fine-grained, consisting of an N x N array of processors, each holding a single pixel of the image. The mesh array operates in an SIMD mode. Several algorithms, differing in the techniques they use, their asymptotic complexity, or the architectural resources required, are presented for computing the Hough transform. The main algorithm computes any P angles of the Hough transform in O(N + P) time and used only a constant amount of memory per processor. All the algorithms apply to the more general problem of computing the Radon transform of gray-level images. Keywords: Parallel algorithms; Image processing; Mesh; Hough transform. (jhd)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA195925

Entities

People

  • J. L. Sanz
  • L. Snyder
  • R. E. Cypher

Organizations

  • University of Washington

Tags

Communities of Interest

  • Advanced Electronics
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Addressing
  • Algorithms
  • Artificial Intelligence
  • Computer Architecture
  • Computer Science
  • Computer Vision
  • Computers
  • Computing System Architectures
  • Digital Images
  • Image Processing
  • Images
  • Machines
  • Parallel Computing
  • Parallel Processors
  • Pattern Recognition
  • Pipelines
  • Recognition

Fields of Study

  • Engineering

Readers

  • Image Processing and Computer Vision.
  • Parallel and Distributed Computing.