The Hough transform is the choice technique for identifying straight lines through digital images, with applications to high energy physics and computer vision. Classical methods for implementing the Hough transform of a N/spl times/N binary image require to compute N/sup 3/ additions over n=log/sub 2/(N) bits integers, hence nN/sup 3/ bit operations per transform. We introduce a new algorithm for computing the fast Hough transform FHT which only requires log/sub 2/(N)/spl times/N/sup 2/ additions, for a total of n/sup 2/N/sup 2/ bit operations per transform. The method is based on a recursive algorithm for raster-scan line drawing, which is different from Bresenham's iterative one The FHT has a divide and conquer recursive structure similar to that of the classical fast Fourier transform FFT algorithm, with simpler atomic operations-additions over n bits numbers-and a more complex interconnect. The FHT algorithm can readily be implemented in software. It maps into hardware as well, and we detail the structure of a bit-serial circuit for computing the FHT. >
['Jean Vuillemin']
Fast linear Hough transform