Hough Transform

This week, we shall study the Hough Transform and compare it with a few other techniques

Activity 1: Hough Transform

Hough transform takes a black and white binary image (say the output of an edge detector) and tries to find line segments in it.

A line can be expressed parametrically in terms of (pho, theta) as shown below on the left. If we take each point on the line (x,y) and keep it constant and vary rho and theta, we get the Hough space (below right). Thus a point on the x-y space becomes a curve on the Hough space. If the points lie on a line, then they intersect at a particular point in the Hough space, and that point's pho and theta characterizes the line on which the points lie

To detect lines using Hough transform. First we perform edge detection. Then we use the hough, houghpeaks and houghlines functions in MATLAB. The images below show an image, its Canny detected edges, the Hogh space and the straight lines detected by Hough transform. The cyan line is the longest detected line.

Activity 2: Comparing Hough transform to other line fitting algorithms

Hough transform can be interpreted as a robust method of fitting linear models to data. We know that linear regression (and its pseudo inverse solution) is another method, which is also optimal in the least squares sense. RANSAC is also another general model fitting method, that provides robustness to outliers. In this section we try to compare the effectiveness of these algorithms as a line fitting method for noisy data.

First we generate a noisy straight line using the following code:

Then the best Hough line (cyan), the pseudo inverse least squares fit (red), and the RANSAC pseudo inverse least squares fit (green) are shown below. The line segments are drawn to visualize the slope and intercept we get for each method. Clearly the naive pseudo inverse fit performs the worst, as it is very sensitive to outliers. Hough does a good job of ignoring the outliers. The best fit is obtained by RANSAC.

The code is available here.