#include <gandalf/vision/fast_hough_transform.h>
A Hough transform is a mapping from an observation space into a
parameter space. In computer vision, observation space could be a
digital image, an edge map etc. Now assume that
a certain structure is thought to be present in image space. For an edge
map, this could be a straight line or a circle. The parameters of the
structure define parameter space (gradient and intercept for a line, radius
and centre coordinates for a circle). In a Hough transform, each point
in image space ``votes'' for that part of parameter space which describes
structures which include the point. For instance, to find circles in an
edge map, edges vote for the region in parameter space (in fact a conical
surface) which describes circles that pass through them. A part of parameter
space receiving a large number of votes corresponds to a possible fit.
In the normal Hough transform approach, parameter space is bounded by setting lower and upper limits on the parameter values, and then divided into blocks in each direction, and an accumulator assigned to each block. The Hough transform proceeds with each point in image space being transformed to an region in parameter space as described in the previous paragraph. When the region intersects one of the blocks, the corresponding accumulator is incremented. The block whose accumulator has the most votes can then be taken as the best fit of the structure to the image points, the values of the parameters usually being calculated at the centre of the block.