DocumentCode :
1520608
Title :
An improved constant-time algorithm for computing the Radon and Hough transforms on a reconfigurable mesh
Author :
Pan, Yi ; Li, Keqin ; Hamdi, Mounir
Author_Institution :
Dept. of Comput. Sci., Dayton Univ., OH, USA
Volume :
29
Issue :
4
fYear :
1999
fDate :
7/1/1999 12:00:00 AM
Firstpage :
417
Lastpage :
421
Abstract :
The Hough transform is an important problem in image processing and computer vision. An efficient algorithm for computing the Hough transform has been proposed on a reconfigurable array by Kao et al. (1995). For a problem with an √N×√N image and an n×n parameter space, the algorithm runs in a constant time on a three-dimensional (3-D) n×n×N reconfigurable mesh where the data bus is N1c/-bit wide. To our best knowledge, this is the most efficient constant-time 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 n*n×n×√n√n reconfigurable mesh, where the data bus is only log N-bit wide. In most practical situations, n=O(√N). 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 O(1) time on the same model, whereas the algorithm in the above paper cannot be adapted to computing Radon transform easily
Keywords :
Hough transforms; Radon transforms; computational complexity; image processing; O(1) time; constant-time algorithm; data bus; reconfigurable mesh; time complexity; Aerospace electronics; Computer science; Computer vision; Councils; Equations; Image processing; International collaboration; NASA; Transforms; Very large scale integration;
fLanguage :
English
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4427
Type :
jour
DOI :
10.1109/3468.769762
Filename :
769762
Link To Document :
بازگشت