Fast Hough transform: A hierarchical approach

Abstract

We have developed a fast algorithm for the Hough transform that can be incorporated into the solutions to many problems in computer vision such as line detection, plane detection, segmentation, and motion estimation. The fast Hough transform (FHT) algorithm assumes that image space features "vote" for sets of points lying on hyperplanes in the parameter space. It recursively divides the parameter space into hypercubes from low to high resolution and performs the Hough transform only on the hypercubes with votes exceeding a selected threshold. The decision on whether a hypercube receives a vote from a hyperplane depends on whether the hyperplane intersects the hypercube. This hierarchical approach leads to a significant reduction of both computation and storage. Due to the hyperplane formulation of the problem and the hierarchical representation of the hypercube, the computation in the FHT is incremental and does not require multiplication, which further contributes to efficiency. © 1986.