An improved constant-time algorithm for computing the radon and hough transforms on a reconfigurable mesh

Abstract — The Hough transform is an important problem in image processing and computer vision. Recently, an efficient algorithm for computing the Hough transform has been proposed on a reconfigurable array [12]. For a problem with an � x 2 � x image and an � 2 � parameter space, the algorithm runs in a constant time on a threedimensional (3-D) � 2 � 2 x reconfigurable mesh where the data bus is x Ia™-bit wide. To our best knowledge, this is the most efficient constanttime algorithm for computing the Hough transform on a reconfigurable mesh. In this paper, an improved Hough transform algorithm on a reconfigurable mesh is proposed. For the same problem, our algorithm runs in constant time on a 3-D � 3 � 2 � x 2 � x reconfigurable mesh, where the �data bus is only �� � x-bit wide. In most practical situations, � a y @ x A. Hence, our algorithm requires much less VLSI area to accomplish the same task. In addition, our algorithm can compute the Radon transform (a generalized Hough transform) in y@IA time on the same model, whereas the algorithm in [12] cannot be adapted to computing Radon transform easily. Index Terms — Hough transform, image processing, reconfigurable mesh, time complexity