Hough Transform

Created January 1, 2021 ยท Updated March 4, 2026

It is an algorithm to fit multiple lines. Given a binary edge image, find the lines (or curves) that explain the data points best in the parameter space. This parameter space is called a Hough space.

A point $\left(x_{1}, y_{1}\right)$ is mapped to a line in the Hough space.
Houghspace

Accumulator:

  • For each pixel, draw a line in the discretised Hough space, assigning a value of one.
  • Process all image pixels and find local maximum, convert it back to point space.
houghdiscreet

Properties

  • Can detect multiple lines in an image (from multiple local maxima)
  • Can be easily extended for circles and ellipses
  • Computationally efficient.

Using Polar Form

Problem: $(m, b)$ are unbounded. For example, the slope parameter $m$ can have an infinite value. How do we solve it?

polarformHoughspace dataHoughspace

Pipeline

Use Edge Detection > Canny Edge Detector to detect edge, apply Hough transform:
edgeToHough

Find the peaks and post-process:
finalHough

Advantages

  • All points are processed independently, so can cope with occlusion
  • Some robustness to noise: noise points unlikely to contribute consistently to any single bin
  • Can detect multiple instances of a model in a single pass

Disadvantages

  • Complexity of search time increases exponentially with the number of model parameters
  • Non-target shapes can produce spurious peaks in parameter space
  • Quantization: hard to pick a good grid size