Houghtransform

The Hough transform is a feature extraction technique used in image analysis to detect shapes within images by transforming points from image space into a parameter space and identifying accumulations that indicate the presence of a shape. It is robust to noise and partial occlusion and can detect shapes without requiring a precise edge model.

For lines, the standard parameterization uses rho = x cos theta + y sin theta, where rho is the distance from the origin to the line and theta is the angle of the line’s normal. Each edge point (x, y) in the image votes for all (rho, theta) pairs that could pass through it, producing a sinuous curve in parameter space. Discretizing rho and theta into an accumulator array, local maxima correspond to detected lines after thresholding and non-maximum suppression.

For circles, a common parameterization is (a, b, r), where (a, b) is the center and r is the radius. An edge point votes for all centers (a, b) that lie on a circle of radius r around the point, or for a range of radii, resulting in a three-dimensional accumulator. This approach is more computationally intensive but effective for circular features.

Variants include the probabilistic Hough transform, which uses a random subset of edge points to reduce computation, and gradient-based or generalized Hough transforms that incorporate edge orientation or support arbitrary shapes. Extensions cover ellipses and other parametric families.

Applications span road and lane detection, object recognition, OCR, fingerprint analysis, and industrial inspection. Limitations include high computational cost, sensitivity to discretization and edge quality, and potential false positives in cluttered images without careful post-processing.