The FHT Algorithm

A coarse Hough Transform is applied to the initial ``root'' hypercube in parameter space by dividing it into $2^k$ ``child'' hypercubes formed by halving the root along each of the $k$ 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 $T$ 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:

$${\rm maximum\;subdivision\;level}=\log_2 {\rm\frac{initial\;range}{required\;accuracy}}.$$

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 $T$ 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.