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 slopeintercept 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 mcplane 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 mcplane as shown below[Gonzalez]:
Figure 1: representation of line in xy and mcplane
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:
 Find the edge of the given image using any edge detector.
 Design the accumulator by specifying the range of theta and rhos. Initialize the accumulator with zero values in each cell.
 Find the possible values of rho for each value of theta and increase the respective cell count.
 Apply a threshold value and then select the lines that have more then the specified number of votes.
 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:
Parameter 
Description 
image

The input image that must be a binary image (single channel) of 8bits.

lines

The HoughLines method will return the lines found in the input image. Each line is represented by a 2 or 3 element vector (ρ,θ) or (ρ,θ,votes).

rho

The number of divisions between –MaxRho and +maxRho. The division is usually incremented by 1 till reaching the maximum also we can refer as distance resolution of the accumulator in pixels.

theta

The increment of angle from 90 to +90. This angle is measured in radians. 1 degree = PI/180 radians.

threshold

Accumulator threshold parameter. Only those lines are returned that get enough votes ( >threshold ).

srn

For the multiscale Hough transform, it is a divisor for the distance resolution rho. The coarse accumulator distance resolution is rho and the accurate accumulator resolution is rho/srn. If both srn=0 and stn=0, the classical Hough transform is used. Otherwise, both these parameters should be positive.

stn

For the multiscale Hough transform, it is a divisor for the distance resolution theta.

min_theta

For standard and multiscale Hough transform, minimum angle to check for lines. Must fall between 0 and max_theta.

max_theta

For standard and multiscale Hough transform, an upper bound for the angle. Must fall between min_theta and CV_PI. The actual maximum angle in the accumulator may be slightly less than max_theta, depending on the parameters min_theta and theta.

Let us look at an example that finds the lines in a given image using HoughLines() as shown in Code 11.
Code 11 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')

Line 12: Imported required libraries.
Line 34: Specified image path and read image in BGR color space.
Line 5: Converted image into grayscale image.
Line 6: Apply Gaussian blur to reduce impact of noise.
Line 7: We calculated edges by applying Canny edge detector.
Line 89: Applied some morphological operations to for well formed lines by removing gaps or noises from the edge image.
Line 10: The value of threshold of votes above which we consider the lines. Lesser than this threshold we do not consider as line.
Line 11: We consider the length of the image to draw a line.
Line 12: HoughLines() method actually calculates the lines in the binary image. We provided edge image as input, for rho we set the resolution to 1 (increment by 1), 1 degree resolution (PI/180 Radians), threshold=300. Rest of the parameters are with default values. You can tweak these values according to your needs. The results are returned in the lines variable.
Line 13: Just make sure there is at least a line detected by HoughLines()
Line 14 24: For each rho and theta we draw lines on the original image. Since we only know rho and theta, we actually need to find two points to draw a line. So, using the rho and theta we draw the line.
Line 16  19: From the right angle triangle formula, we can calculate the x0 cordinate right angle triangle by rho* cos(theta), similalry y0 coordinate by rho*sin(theta).
Line 2021: Since using given theta and rho we can draw an infinite line. But a line on the image has finite length. Therefore, we tried to find two end points of the line. These lines find the begining point of the line by multiplying with length with negative of b.
Line 2223: Similarly, we calculated the far end point of the line also.
Line 24: Once we calculated the two points, using cv2.line() method we draw a line.
Line 2527: We just display the image containing lines.
Line 2829: In case no lines are detected, this message will be displayed.
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).