The
Hough Transform is an
image transform often used to detect
patterns, such as
lines,
circles or other
shapes in images.
The easiest demonstration is to use the straight line form. Consider the equation of a line:
y=mx+c
This defines a line in the space with axes x, y, defined by the parameters m, c.
This can be rearranged to the form:
c=-xm+y
But this itself is the original form, describing a line in a space with the axes m, c, and defined by the parameters -x, y.
From this we can define an accumulator space (sometimes called Hough Space) with the axes m,c. This has some interesting properties:
- A point in accumulator space corresponds to a line in normal space.
- A point in normal space corresponds to a line in accumulator space. The points on this line correspond back to lines in normal space, all of which pass through the original point.
- If a line exists in normal space, each point on the line will correspond to a line in accumulator space. Each of these lines will pass through a single point, corresponding to the original line in normal space.
Algorithm
The last of these properties can be used to detect lines with a fairly simple
algorithm. Consider the problem of detecting white lines on a black background.
Define an accumulator array
For each white pixel in the source image:
"Draw" the corresponding line into the accumulator array:
For each point drawn in this line, increment the previous value.
Search the accumulator array, find the entry with the highest value. This entry corresponds to the line detected.
Discussion
Essentially the accumulator array stores '
votes' for particular lines. Each point on the source line will give another 'vote' for it. This system gives good
performance in detecting lines, even with large amounts of noise. It also has the advantage of being mathematically quite
beautiful.
The system described here is flawed in that it needs an infinite sized accumulator array and cannot deal with vertical lines (infinite gradient). This can be solved using the polar form of a line. The Hough Transform can be trivially extended to detect other shapes, such as circles or other generic shapes (see Generalised Hough Transform)
node your homework!