Hough transform

Example

The Hough transform detects straight lines in a finite set of points $p_1, \dots, p_N$ of the plane, such as the edge pixels of an image. Each line is written as $x \cos\theta + y \sin\theta = \rho$ with $\theta \in [0, \pi)$ and $\rho \in \R$. A point $p_i = (x_i, y_i)$ lies on this line exactly when $\rho = x_i \cos\theta + y_i \sin\theta$. So each point gives a sinusoidal curve in the $(\theta, \rho)$ plane, and the curves of collinear points meet at the parameters of their common line. The transform is the count $$H(\theta, \rho) = \#\set{i : x_i \cos\theta + y_i \sin\theta = \rho},$$ computed in practice on a grid of cells, and lines are found as peaks of $H$.

Check on three points: $(1, 0)$, $(0, 1)$ and $(2, -1)$ lie on the line $x + y = 1$. For $\theta = \pi/4$ and $\rho = 1/\sqrt{2}$, each point satisfies $x \cos\theta + y \sin\theta = (x + y)/\sqrt{2} = 1/\sqrt{2}$. So $H(\pi/4, 1/\sqrt{2}) = 3$.

The Radon transform integrates a function along each line, and $H$ counts the given points on each line. So the Hough transform is a discrete analogue of the Radon transform, applied to an edge image.