The Fast Hough Transform (FHT)

The above method has two main drawbacks: large memory requirement and slowness. In order to find the plane parameters accurately, parameter space must be divided finely in all three directions, and an accumulator assigned to each block. Also it takes a long time to fill the accumulators when there are so many. The Fast Hough Transform described in [#!Li_etc_86!#] gives considerable speed up and reduces memory requirement. Instead of dividing parameter space uniformly into blocks, the FHT ``homes in'' on the solution, ignoring areas in parameter space relatively devoid of votes. The relative speed advantage of the FHT increases for higher dimensional parameter spaces.

The FHT applies to those Hough transform problems in which a feature $F_j$ votes for a hyperplane in parameter space (a hyperplane is a $k-1$ dimensional generalisation of a plane, where $k$ is the dimension of parameter space). This means that the relationship between feature space and parameter space must be linear in the parameters. In addition, it must be known in advance how many votes the solution will receive in the Hough transform. The FHT is also restricted in that it only supplies one ``best fit'' solution, whereas for the more conventional Hough transform method above it is plausible to consider local maxima as alternatives to the global maximum, i.e. the block in parameter space receiving the most votes.

A major advantage of the FHT is that it only uses addition and multiplication by two, which in integer arithmetic can be done efficiently using bitwise shifts. This is very convenient for computers on which integer arithmetic is much faster than floating point arithmetic.