---
tag: 3DK4V3A10K
kind: example
name: Hough transform
msc: [68U10, 44A12, 68T45]
illustrates: [VJNZJ352PC]
sources:
  - url: https://en.wikipedia.org/wiki/Hough_transform
same_as:
  wikidata: Q195076
  wikipedia: 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|VJNZJ352PC]] 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.

## Explanations

### L1 human

Every point votes for all the lines that pass through it.
A line that passes through many points collects many votes.
After the vote, the lines with the most votes are the lines in the picture.
The method still works when some points are missing or extra noise points are present, which makes it popular in computer vision.