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

摘要

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)