Computing the Hough transform on reconfigurable meshes

摘要

Until now, buses have been used exclusively to support fast communication and data transfer needs within a parallel machine. Recently, the authors have demonstrated novel uses of buses in a multiprocessor reconfigurable architecture. Specifically, we have argued that buses can be successfully used both as topological descriptors and as powerful computational devices. The purpose of this note is to show that this new paradigm can be used for computing the Hough transform—the most widely used technique for detecting lines and curves in binary or grey level images. Specifically, for an N × N digitized image stored in a reconfigurable mesh of size N × N, one pixel per processor, we present an O (n × log(N/n)) time algorithm to compute the Hough transform with n standing for the number of angles in the quantization of the θ-space.