** Next:** Notation
** Up:** Fast Hough Transform
** Previous:** Fast Hough Transform
** Contents**

##

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
votes for a *hyperplane* in parameter space (a hyperplane is
a dimensional generalisation of a plane, where 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.

**Subsections**

** Next:** Notation
** Up:** Fast Hough Transform
** Previous:** Fast Hough Transform
** Contents**
2006-03-17