Hough Transformation
Hough transform is a feature extraction method used in image analysis. Hough transform in its simplest from can be used to detect straight lines in an image.
Intuition behind Hough Transformation
The equation of the line in the image space is of the form y = mx + c where m is the slope and c is the y-intercept of the line. However with this representation, we cannot represent a vertical line, as the slope is infinite. Programmatically, this means that a computer would need an infinite amount of memory to represent all possible values of m. So we need a better way parametrization, polar coordinates (ρ and θ) which is represented by a normal line that passes through the origin and perpendicular to that straight line. The form of the normal line is ρ = x cos(θ) + y sin(θ) where ρ and θ are given by:
- rho (ρ): describes the length of the perpendicular from the origin to the straight line
- theta (θ): describes the angle between the normal line and the x axis.
This line will be transformed to a point of the form (ρ,θ) in the hough space. This point describes the equation of our line in the image space.
Representation in Hough Space
A Line in image space results in a point in hough space.
A point in image space results in a sinusoid in hough space.
Finding Hough Lines
Finally, maybe the most interesting effect. If we take multiple points around a line, and we transform into Hough space. A single dot on image space translates to a curve on Hough space, if we draw points which form a line in the image space, we will obtain a bunch of sinusoids in the Hough space. But, magically, they are intersecting at exactly one point!
It means that, to identify candidates for being a straight line, we should seek for intersections in Hough space
Multiple lines in image space results in multiple sinusoids with multiple points of intersection in hough space.
To sum up, we observed following relations between Image space and Hough space:
Straight line → Point
Point → Sinusoid
Multiple points on Straight line → Multiple sinusoids intersecting at a point
Multiple lines → Multiple sinusoid with multiple points of intersection
Accumulator and Voting
The Hough transform constructs a M x N matrix, also known as an accumulator representing the parameter space (i.e., an M x N matrix, for M different values of the radius ρ and N different values of angle θ). If two edge points lay on the same line, their corresponding cosine curves will intersect each other on a specific (ρ, θ) pair. We sweep through all cells in the grid and count how many such sinusoid intersect in a cell for a certain line, this is referred to as voting. If there are more votes than a given threshold, we claim that the straight line has been found and it’s described by ρ and θ parameters from the considered cluster.
This article gave a conceptual introduction towards Hough space, intuition behind hough transformation, representation of lines, points and multiple intersecting lines in hough space and how hough transformation leads to detection of straight lines using voting in accumulator.
