Hough transformation

An approach to detect straight lines (or curves) in an image (a picture), by applying a coordinate transformation to the image such that all the points belonging to a line (or a curve) are mapped into a single point in the transformed space.

The method to detect lines may be explained as follows [a2]. The set of all straight lines in the $ ( x,y ) $- image plane gives rise to a two-parameter family. When using the normal parametrization (cf. also Normal equation), the equation of a line is given by

$$ \tag{a1 } x \cos \theta + y \sin \theta = \rho, $$

where $ \theta $ is the oriented angle of the normal onto the line, and where $ \rho $ is the algebraic distance of the line from the origin. Restricting $ \theta $ to the interval $ [ 0, \pi ] $, the normal parameters for a line are unique. Taking the $ ( \theta, \rho ) $- space as the transformed space, every line in the $ ( x,y ) $- plane corresponds to a unique point in the transformed space (in the original Hough-transform method the slope-intercept representation of a line, namely $ y = mx + b $, was used, and the $ ( m,b ) $- space was the transformed space; as both the slope and the intercept may become infinite, the technique is more involved, [a3]).

Taking now a fixed point $ ( x _ {i} ,y _ {i} ) $ in the $ ( x,y ) $- plane, this point gives rise in the $ ( \theta, \rho ) $- space to a curve defined by

$$ \tag{a2 } \rho = x _ {i} \cos \theta + y _ {i} \sin \theta. $$

Clearly, when one has a set $ \{ ( x _ {1} ,y _ {1} ) \dots ( x _ {n} ,y _ {n} ) \} $ of picture points that are collinear in the $ ( x,y ) $- plane, the $ n $ curves in the $ ( \theta, \rho ) $- space corresponding to these points according to (a2) have a common point of intersection, say $ ( \theta _ {s} , \rho _ {s} ) $. Writing (a1) with $ \theta \equiv \theta _ {s} $ and $ \rho \equiv \rho _ {s} $, one obtains the equation of a line in the $ ( x,y ) $- plane passing through the $ n $ points.

Having now a digital picture in the $ ( x,y ) $- plane, and mapping all these points to their corresponding curves in the parameter space, collinear subsets of picture points can be found by searching coincident points of intersection in the parameter space. In practice this is done by quantizing both parameters $ \theta $ and $ \rho $, and treating the quantized region as a two-dimensional array of accumulators. For each point $ ( x _ {i} ,y _ {i} ) $ in the $ ( x,y ) $- picture plane, the curve corresponding to it by (a2) gives rise to incrementing the count in some cells of the array. After all picture points have been treated, the array is inspected to find cells having high counts. When in some cell $ ( \theta _ {a} , \rho _ {b} ) $ there are $ m $ counts, then the line with normal parameters $ ( \theta _ {a} , \rho _ {b} ) $ passes (approximately) through $ m $ picture points.

The Hough-transform method as explained above to detect straight lines in a picture can, in principle, be generalized to detect analytic curves involving more than two parameters. For instance, as the equation of a circle in the $ ( x,y ) $- plane is given by

$$ \tag{a3 } ( x - a ) ^ {2} + ( y - b ) ^ {2} = r ^ {2} , $$

a point $ ( x _ {i} ,y _ {i} ) $ on that circle determines a subset of the three-dimensional $ ( a,b,r ) $- parameter space. When a number of picture points are arranged on a circle with parameters $ ( a _ {0} ,b _ {0} ,r _ {0} ) $, the corresponding subsets in the $ ( a,b,r ) $- parameter space will intersect at the point $ ( a _ {0} ,b _ {0} ,r _ {0} ) $, and this point may be detected by using a three-dimensional array. As methods to detect curves in a picture are usually applied to find out if edge points are situated on a particular curve, it is often possible to reduce the number of points to be checked, while also the use of directional information may reduce the computational burden [a1].

References

[a1]	D.H. Ballard, "Generalizing the Hough transform to detect arbitrary shapes" Pattern Recognition , 13 (1981) pp. 111–122
[a2]	H. Bässmann, PH.W. Besslich, "Konturorientierte Verfahren in der digitalen Bildverarbeitung" , Springer (1989)
[a3]	A. Rosenfeld, A.C Kak, "Digital picture processing" , 2 , Acad. Press (1982)