Hough Transform

Direct fitting of lines to edge pixels is problematic when edges are noisy or fragmented. The Hough Transform avoids this by converting the problem: instead of finding a line y=mx+b that fits many points in image space, it finds a point (θ, ρ) in parameter space that receives many votes. Peaks in parameter space directly reveal dominant lines, making the voting mechanism robust to noise and gaps.

The Hough Transform typically uses polar coordinates: θ is the angle of a line perpendicular to the line of interest (ranging from 0 to π), and ρ is the perpendicular distance from the image origin to the line (ranging from −∞ to ∞). This parameterization avoids the singularity problem of slope-intercept form (which is undefined for vertical lines) and is more numerically stable.

The Generalized Hough Transform uses a look-up table (R-table) that encodes the relationship between edge orientations and offsets to a reference point on the shape. For each edge pixel with a given orientation, the R-table provides possible reference point locations. Accumulating votes at these locations creates peaks where the shape is likely located. This approach works for any shape, not just lines and circles.

In scenes with many intersecting lines or complex geometry, the accumulator array becomes crowded with peaks, making it difficult to distinguish true shapes from noise-induced artifacts. Additionally, parameter space quantization can cause nearby shapes to interfere. For such scenes, RANSAC (Random Sample Consensus) or deep learning methods may be more effective.