Hough Transform for absolute beginners
Ever wondered about the algorithm behind capturing straight lines while scanning a document?
Introduction
The Hough Transform is an algorithm patented by Paul V. C. Hough and was originally invented to recognize complex lines in photographs (Hough, 1962). Since its inception, the algorithm has been modified and enhanced to be able to recognize other shapes such as circles and quadrilaterals of specific types. In order to understand how the Hough Transform algorithm works, it is important to understand four concepts: edge image, the Hough Space and the mapping of edge points onto the Hough Space, an alternate way to represent a line, and how lines are detected.
HOW HOUGH TRANSFORM WORKS ?
Hough transform is a way of finding edge points in an image that lie along a straight line or a curve. It is basically used to isolate shapes of a particular parametric form in image. Before we discuss hough transform let’s understand about edge detection that is a prerequisite for hough transform. An edge image is the output of an edge detection algorithm. An edge detection algorithm detects edges in an image by determining where the brightness/intensity of an image changes drastically. Below edge detection is demonstrated with ‘Canny’ edge detection in Figure 2 implemented on Figure1. Canny edge detection is a technique to extract useful structural information from different vision objects and dramatically reduce the amount of data to be processed. It is common for an edge image to be binarized meaning all of its pixel values are either a 1 or a 0.
After we get the edge space, we use Hough transform. In figure 3, we have a simple demonstration.
The green and blue dots represent two points which lie on the same straight line in X-Y plane. We transform these two points into A-B plane (also called Hough Space). Now, these points are represented by lines. All the lines which intersect in Hough Space are said to be collinear. But there is a limitation with this form of straight line equation. If the points lie on a line that is parallel to either of the axes, those points will be transformed into parallel lines as shown in figure 4 and figure 5.
To overcome this, we use the parametric form of straight line expressed in terms of rho and theta.
Figure 6 shows implementation of the parametric form of straight line for creating Hough space. Rho is the distance from the origin to the along a vector perpendicular to the line. Theta is the angle between the x axis and this vector. Representation of the vertical and horizontal lines w.r.t rho and theta is shown below.
Horizontal line — 𝛳 is 0 degree , rho is positive x-axis intercept.
Vertical line — 𝛳 is 90 degree , rho is positive y-axis intercept.
After we get the Hough space, we see the positions with maximum intersections and separate those points from background noise. Hough transform works on a voting basis. Then we reconstruct these lines superimposing on the original image. Figure 7 shows the Hough space.
Figure 8 shows the detected lines superimposed on the original image.
MODIFICATION FOR DIFFERENT SHAPES
Figure 9 shows parametric form to find Hough space for different shapes.
PROS
- Hough transform is tolerant of gaps in images.
- It is unaffected by noise.
- Conceptually simple to implement.
- It can be adapted to various forms.
CONS
- Dependent on density.
- Large storage required.
- Difficult to implement for complex shapes as you have to know the parametric form of these shapes.
REAL LIFE APPLICATIONS
Sources:-
Hough Transform MATLAB Code can be found in the first embedded link for static image.
Thank you
