HOUGH TRANSFORM ON RECONFIGURABLE MESHES

The Hough transform is an important image processing operation. Given an N x N digital image, we first present a parallel algorithm for computing the Hough transform in O((p/k) log N) time on a reconfigurable mesh of O(kN(2)) processors, 1 less than or equal to k less than or equal to p, where p is the number of angles to be considered. Then, on a 3-dimensional reconfigurable mesh using O(kN(3)) processors, the Hough transform can be computed in O(p/k) time. When setting k = O(p), a constant time algorithm is derived. Furthermore, a more general result is presented; the Hough transform can be computed in O((p log N)/(k log M)) time on a reconfigurable mesh of O(kN(2)M) processors, where 2 less than or equal to M less than or equal to N. (C) 1995 Academic Press, Inc.