Line Detection using Hough Line Transform

We can detect lines or circles using a powerful technique proposed by Hough in his paper in 1962. We know that a line can be represented by the equation in slope-intercept form as:

$$ y_i = - m x_i + c $$

where m and c are slope and intercept, respectively. However, we are interested in a set of line that pass though a fixed point. So, if x and y are known then above equation can be rewritten in mc-plane as:

$$ c = - m x_i + y_i $$

We can use above equation to find the lines that pass though a fixed point (x_i, y_i), however, when the line is vertical then slope (m) will be infinite. To overcome this issue, we can use the normal equation of the line as:

$$ \rho = x \cos(\theta) + \sin (\theta)$$

Graphically we can represent the points and the line in the xy- and mc-plane as shown below[Gonzalez]:

Figure 1: representation of line in xy- and mc-plane

So, for given set of (x_i,y_i) points we can then find a set of lines that pass though each point by setting different values of theta and obtaining different values of rho. For each theta we get a row. We need to count the votes for each rho value using an accumulator. This accumulator will be zero in the beginning and then keep incrementing the cells that match rho and theta. The count of the cell in accumulator indicates the number of lines that exists on the line x cos(theta)+ y sin(theta) = rho. An example of an accumulator is shown in figure 2 [Gonzalez].

Figure 2: An example of an accumulator in Hough Transform

The basic question is how can we search for theta and rho. A possible range of value for theta is usually between −≤90^o and ≤90^o

While the $\rho $ values will be between $-\sqrt{M \times N }$ and $+\sqrt{ M \times N }$ . Where M and N represent the image rows and columns.

Hough Line Transform Algorithm

The main step of Hough Transform for line detection are as follows:

1. Find the edge of the given image using any edge detector.
2. Design the accumulator by specifying the range of theta and rhos. Initialize the accumulator with zero values in each cell.
3. Find the possible values of rho for each value of theta and increase the respective cell count.
4. Apply a threshold value and then select the lines that have more then the specified number of votes.
5. For selected rho and theta draw the lines on the image.

In OpenCV, the lines can be detected via HoughLines() method. The signature of the HoughLines() method is as shown below:

Cv2.HoughLines( image, rho, theta, threshold[, lines[, srn[, stn[, min_theta[, max_theta]]]]] )

The parameters of the above function are described as below:

Let us look at an example that finds the lines in a given image using HoughLines() as shown in Code 1-1.

Code 1-1 Hough Line Transform

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import cv2
import numpy as np
path = r'F:\img\soduku.jpg'
imgOriginal = cv2.imread(path, cv2.IMREAD_COLOR)
gray = cv2.cvtColor(imgOriginal,cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray, (5,5),0) 
edges = cv2.Canny(blur, 50, 200,apertureSize=3)
edges =  cv2.dilate(edges, np.ones((5,5),dtype=np.uint8))
edges =  cv2.erode(edges, np.ones((5,5),dtype=np.uint8))
threshold = 300
length = edges.shape[0]
lines = cv2.HoughLines(edges, 1, np.pi/180, threshold)
if(lines is not None):
    for line in lines:
        for rho,theta in line:
            a = np.cos(theta)
            b = np.sin(theta)
            x0 = a*rho
            y0 = b*rho
            x1 = int(x0 + length*(-b))
            y1 = int(y0 + length*(a))
            x2 = int(x0 - length*(-b))
            y2 = int(y0 - length*(a))
        cv2.line(imgOriginal, (x1, y1), (x2, y2), (0, 0, 255), 2)
    cv2.imshow("Hough Lines", imgOriginal)
    cv2.waitKey(0)
    cv2.destroyAllWindows()
else:
    print('No Lines found')

The output obtained for the code shown above is shown in Figure 3.

Figure 3: The lines detected using Hough Transform in OpenCV. Original image (left) and output image (right).