Hough Transform

  The Hough transform [Hough59] is a standard tool in image analysis that allows recognition of global patterns in an image space by recognition of local patterns (ideally a point) in a transformed parameter space. It is particularly useful when the patterns one is looking for are sparsely digitized, have ``holes'' and/or the pictures are noisy.

The basic idea of this technique is to find curves that can be parameterized like straight lines, polynomials, circles, etc., in a suitable parameter space. Although the transform can be used in higher dimensions the main use is in two dimensions to find, e.g. straight lines, centres of circles with a fixed radius, parabolas y = ax² + bx + c with constant c, etc.

As an example consider the detection of straight lines in an image. We assume them parameterized in the form: , where is the perpendicular distance from the origin and  the angle with the normal. Collinear points (x_i,y_i), with , are transformed into N sinusoidal curves in the ( ) plane, which intersect in the point ( ).

Care has to be taken when one quantizes the parameter space ( ). When the bins of the ( ) space (it is easy to visualize the transform as a two-dimensional histogram) are chosen too fine, each intersection of two sinusoidal curves can be in a different bin. When the quantization is not fine enough, on the other hand, nearly parallel lines which are close together will lie in the same bin.

For a certain range of quantized values of parameters and , each (x_i, y_i) is mapped into the ( ) space and the points that map into the locations ( are accumulated in the two-dimensional histogram IHIST ( ), i.e. IHIST ( ) = IHIST ( .

If a greylevel image g(x,y) is given, and g_i is the greyvalue at the point (x_i, y_i) the greyvalues are accumulated: IHIST ( ) = IHIST ( .

In this form, the Hough transform is not basically different from the discrete Radon transform, typically used for reconstruction of three-dimensional images from two-dimensional projections.

Local maxima of the pixel intensity IHIST ( ) identify straight line segments in the original image space. Ideally, the Hough domain has to be searched for a maximum only once. In situations where a picture contains many patterns of different size, it may, however, be necessary to take out first those patterns in the original image space that correspond to clearly identifiable peaks in the Hough domain and to repeat the process.