** Next:** Example: Line Fitting
** Up:** The Fast Hough Transform
** Previous:** Notation
** Contents**

###

The FHT Algorithm

A coarse Hough Transform is applied to the initial ``root'' hypercube in
parameter space by dividing it into ``child''
hypercubes formed by halving the root along each of the dimensions and
assigning an accumulator to each child. Each hyperplane passing through
a child hypercube increments its accumulator. Those children receiving
greater than a threshold votes are recursively subdivided, becoming
parents themselves, and so on.
A limit is set on the level of subdivision. Because the range of the
parameters in a hypercube is halved for each level of subdivision,
This is equivalent to having a precision threshold:

An extra speed up is made possible by keeping track of which features vote
for (i.e. which hyperplanes intersect) each hypercube.
Only those features need be tested for intersection
between hyperplane and child hypercubes, since children lie inside their
``parents''.

Li et al. consider two methods of calculating whether a hyperplane passes
through a hypercube. The ``brute force'' method is to test whether all
the vertices of the hypercube are on the same side of the hyperplane by
evaluating the left hand side of equation 5.15 for each
vertex. For increased speed, Li et al. recommend determining whether the
hyperplane intersects the hypercube's circumscribing hypersphere.
This is an approximation, since some planes will intersect the
hypersphere but not the hypercube. One effect of this is that the
total number of subdivisions will be increased, because a hypersphere
may get more than votes when the hypercube on its own
(being smaller) would not have. However the increased speed more
than compensates for this, especially for high-dimensional
parameter spaces. The method is fast because the perpendicular distance
from the centre of a child hypercube to a hyperplane can be
calculated simply in terms of the corresponding distance from the parent's
centre to the hyperplane, as is shown on page .
This distance is then compared with the radius of the hypersphere.

** Next:** Example: Line Fitting
** Up:** The Fast Hough Transform
** Previous:** Notation
** Contents**
2006-03-17