Understanding the Hough transform

The Hough transform is a feature extraction technique. It is used mostly for detecting lines, but can be extended to find circles and ellipses. In this post the basics of this procedure are explained with an online demonstration to help better understanding.

The general formula of a line is the well-known equation, where m denotes the slope, while b is the point where the line crosses the y-axis:

$$ y = m\cdot x+b \\ $$

Although this is a simple and easy-to-use formula, vertical lines cannot be described with it. Now have a look at the following image:

 

Here a polar coordinate describes the line: r is the distance of the origin and the line, while θ is the angle of the vector pointing from the pole to the closest P point of the line. Using these notations, the equation of the line becomes the following:

$$ y = -\frac{cos(\theta)}{sin(\theta)}x+\frac{r}{sin(\theta)} $$

Which can be rearranged to:

$$ r = x\cdot cos(\theta)+y\cdot sin(\theta) $$

Suppose, that we have an arbitrary P point on an image. To get all possible lines going through it, simply rotate a line crossing P from 0 to 180 degrees: as θ changes r will change too.

To feel this and the equation above, please load the following application, and simply click on an arbitrary point on the white section of the left panel. You will see a line rotating around, while on the right panel the corresponding θ and r coordinates will be visualized.

The result is sinusoidal. Now click another point: the trajectory of the first point is kept, while the second is continuously redrawn. There is a very important thing to note: the two trajectory cross each other, when the two points are on the same line. The θ and r coordinates of the crossing point exactly describe the line on which both points are found.

This is the basic idea of the Hough transform: we draw the sinusoid for each edge point, and then find the crossings, which describe the lines. Of course the more point is located on a line, the more sinusoid will cross at the given θ and r pair. In the demo above you can try it by clicking for more points. Use the Reset button to remove all points, and begin the game again.

The explanation of calculating and finding the crossings with some example MATLAB code will be in another post. Till that to read more about Hough transform, please read this Wikipedia article.