Hough Transform

The Hough transform is a feature extraction technique used in image analysis and computer vision to detect imperfect instances of shapes, such as lines, circles, or ellipses, through a voting procedure in parameter space. It was invented by Paul Hough in 1962 and generalized by Richard Duda and Peter Hart in 1972.

The Hough transform is a feature extraction technique used in image analysis, computer vision, pattern recognition, and digital image processing. Its purpose is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in an accumulator space explicitly constructed by the algorithm. Mathematically, it is the Radon transform in the plane, known since at least 1917, but the Hough transform refers specifically to its use in image analysis.

The classical Hough transform was concerned with identifying lines in an image, but it has since been extended to identifying positions of arbitrary shapes, most commonly circles or ellipses. The transform as universally used today was invented by Richard Duda and Peter Hart in 1972, who called it a "generalized Hough transform" after the related 1962 patent of Paul Hough. It was popularized in the computer vision community by Dana H. Ballard through a 1981 journal article titled "Generalizing the Hough transform to detect arbitrary shapes."

History

The Hough transform was initially invented for machine analysis of bubble chamber photographs by Paul Hough in 1959. It was patented as U.S. patent 3,069,654 in 1962 and assigned to the U.S. Atomic Energy Commission under the name "Method and Means for Recognizing Complex Patterns." This patent used a slope-intercept parametrization for straight lines, which awkwardly led to an unbounded transform space, since the slope can go to infinity.

The rho-theta parametrization universally used today was first described in a 1972 paper by Richard Duda and Peter Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," published in Communications of the ACM. This parametrization was already standard for the Radon transform since at least the 1930s. Frank O'Gorman and M.B. Clowes published a variation in 1976 in IEEE Transactions on Computers, titled "Finding Picture Edges Through Collinearity of Feature Points." The story of how the modern form was invented is detailed in Peter Hart's 2009 article "How the Hough Transform was Invented" in IEEE Signal Processing Magazine.

Theory

In automated analysis of digital images, a subproblem often arises of detecting simple shapes, such as straight lines, circles, or ellipses. An edge detector can be used as a pre-processing stage to obtain image points on the desired curve. However, due to imperfections in image data or the edge detector, there may be missing points or spatial deviations between the ideal shape and noisy edge points. The Hough transform addresses this by performing an explicit voting procedure over a set of parameterized image objects, making it possible to group edge points into object candidates.

Detecting Lines

The simplest case is detecting straight lines. In general, a line y = mx + b can be represented as a point (b, m) in parameter space, but vertical lines pose a problem due to unbounded slope values. Duda and Hart proposed using the Hesse normal form: r = x cos(theta) + y sin(theta), where r is the distance from the origin to the closest point on the line, and theta is the angle between the x-axis and the line connecting the origin to that closest point. Every vector on the line is perpendicular to the line segment of length r from the origin. The intersection point is at P0 = (r cos(theta), r sin(theta)). For any point P on the line, the vector P - P0 must be orthogonal to P0, enforcing (P - P0) dot P0 = 0, which simplifies to r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta)).

Algorithm and Voting Procedure

In practice, the Hough transform discretizes the parameter space into an accumulator array. For each edge point in the image, the algorithm computes all possible parameter values (e.g., r and theta for lines) that could correspond to a shape passing through that point, and increments the corresponding accumulator cells. After processing all points, local maxima in the accumulator indicate likely shape candidates. This voting procedure is robust to noise and missing data, as it does not require all points on a shape to be perfectly aligned.

Extensions and Applications

The generalized Hough transform, introduced by Dana Ballard in 1981, extends the technique to arbitrary shapes by using a reference point and a table of edge orientations. This allows detection of complex shapes beyond lines, circles, and ellipses. The transform has been widely applied in fields such as autonomous driving, medical imaging, and industrial inspection. In Computer vision systems, it is often combined with edge-detection algorithms to identify objects in digital-image-processing pipelines. Its mathematical foundation in the radon-transform connects it to broader image-analysis techniques used in Machine learning and Artificial intelligence applications.

Limitations and Variants

One limitation of the classical Hough transform is its computational cost, especially for high-dimensional parameter spaces. Variants such as the probabilistic Hough transform and the Hough circle transform have been developed to improve efficiency. The probabilistic version samples a subset of edge points to reduce computation, while the circle transform uses a three-dimensional parameter space (center x, center y, radius). These variants are commonly implemented in libraries like opencv and are used in real-time systems, including those in autonomous-vehicles and Robotics.