Accession Number : ADA195925

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

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF COMPUTER SCIENCE

Personal Author(s) : Cypher, R E ; Sanz, J L ; Snyder, L

PDF Url : ADA195925

Report Date : Jul 1987

Pagination or Media Count : 8

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)

Descriptors :   *IMAGE PROCESSING, *PARALLEL PROCESSING, *COMPUTER ARCHITECTURE, ALGORITHMS, ARCHITECTURE, ARRAYS, MESH, RESOURCES

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE