THE HOUGH TRANSFORM ON A RECONFIGURABLE MULTIRING NETWORK

A novel reconfigurable network referred to as the Reconfigurable Multi -Ring Network (RMRN) is described. The RMRN is shown to be a truly sca lable network, in that each node in the network has a fixed degree of connectivity and the reconfiguration mechanism ensures a network diame ter of O(log2 N) for an N-processor network. Algorithms for the 2-D me sh and the SIMD n-cube are shown to map very elegantly onto the RMRN. Basic message passing and reconfiguration primitives for the SIMD RMRN are designed which could be used as building blocks for more complex parallel algorithms. The RMRN is shown to be a viable architecture for image processing and computer vision problems via the parallel comput ation of the Hough transform. The parallel implementation of the Y-ang le Hough transform of an N x N image is showed to have a asymptotic co mplexity of O(Y log2 Y + log2 N) on the SIMD RMRN with O(N2) processor s. This compares favorably with the O(Y + log2 N) optimal algorithm fo r the same Hough transform on the MIMD n-cube with O(N2) processors. ( C) 1995 Academic Press, Inc.