Hough Transform

The Hough Transform is a global method for finding straight lines (functions) hidden in larger amounts of other data. It is an important technique in image processing. For detecting lines in images, the image is first binarised using some form of thresholding and then the positive instances catalogued in an examples dataset.

To understand the Hough Transform, it is important to know what the Hough space is. Each point (d,T) in Hough space corresponds to a line at angle T and distance d from the origin in the original data space. This is a parametrization. The value of a function in Hough space gives the point density along a line in the data space. The Hough Transform utilises this by the following method.

For each point in the original space consider all the lines which go through that point at a particular discrete set of angles, chosen a priori. For each angle T, calculate the distance to the line through the point at that angle and discretise that distance using an a priori chosen discretisation, giving value d.

Make a corresponding discretisation of the Hough space - this will result in a set of boxes in Hough space. These boxes are called the Hough accumulators. For each line we consider above, we increment a count (initialised at zero) in the Hough accumulator at point (d,T). After considering all the lines through all the points, a Hough accumulator with a high value will probably correspond to a line of points.


The code is documented here.