## Hough Lines Transform Explained

Hough Lines Transform is the key method used in the previous project where lane lines are detected. It is very helpful in many Computer Vision applications. The original form of Hough Transform aimed to identify straight lines. And that’s what I’m going to explain today. Furthermore, this technique was later generalized to detect also other shapes like circles, ellipses etc. .

### The goal of the method, image preparation

To use Hough Lines Transform, processed image should be binary. But we would like to search for the straight lines on an original, color image. Therefore, probably the most common solution is to firstly grayscale the image and then to detect edges. Such mask of edges can be then fetched to the Hough Lines method which should output a set of straight lines found on an image.

### Straight lines representations

As we learned from quite early school classes, the straight line can be represented by two parameters. The simplest and most widely used pair of parameters is which correspond to slope and intercept. The line is then described as: Let’s forget for a while about these parameters. We can also unambiguously describe the line using the pair in polar system. The first parameter, , is the shortest distance from the origin to the line (approaching the line perpendicularly). The second, , is the angle between x-axis and the distance line. One of the benefits of such representation is that we can describe vertical lines by and which is impossible by using only parameters in cartesian system.

For a given line, we can determine specific and . Then, the following equation is satisfied for each , point belonging to this line: ### Mapping from Image space to Hough space

Let’s draw a line on an image space again. As we already know, it is represented by some and . So, we can draw such point in coordinates which will be later called a Hough space.

Now, in the image space, we are drawing other lines which are intersecting at one common point. Let’s see what points will be produced in Hough space which are corresponding to these lines.

It turns out that these points in space are forming a sinusoid. Drawing infinite number of additional lines intersecting at this one point would result in a continuous sinusoid in Hough space. So, maybe, we can say that a point in image space results in a sinusoid in Hough space? Let’s recall the equation . Indeed, for fixed parameters representing point in image space and sliding through all possible values of in some range, we obtain values which form a sinusoid.

To sum up, we observed following relations:

### Finding Hough Lines

Finally, maybe the most interesting effect. 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. Below, you can see 2 lines and corresponding image in Hough space. Sure enough, there are 2 main intersections highlighted here for convenience. They are representatives (by and parameters) of the straight lines.

#### Hough Lines parameters

In real application, for example using OpenCV library, the Hough space of an image is divided into uniform clusters. The grid is defined by parameters which can be called rho resolution and theta resolution. They often equals 1 pixel and 1 degree respectively. We sweep through all cells in the grid and count how many votes there are for a certain line. 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.

### Implementation in Python

OK, now we are ready to find Hough Lines in real image using OpenCV and Python. After image loading I perform grayscaling, blurring and edge detection. Then, OpenCV cv2.HoughLines function is called to obtain set of detected lines. Next, the results are presented. Note that function cv2.HoughLines requires 3 parameters which were discussed before. They were chosen experimentally for the given image example. It’s good to play with these parameters. E.g. if threshold is lower, more lines will be found and vice versa.

import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import numpy as np
import cv2

gray_image = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
blurred_image = cv2.GaussianBlur(gray_image, (9, 9), 0)
edges_image = cv2.Canny(blurred_image, 50, 120)

rho_resolution = 1
theta_resolution = np.pi/180
threshold = 155

hough_lines = cv2.HoughLines(edges_image, rho_resolution , theta_resolution , threshold)

hough_lines_image = np.zeros_like(image)
draw_lines(hough_lines_image, hough_lines)
original_image_with_hough_lines = weighted_img(hough_lines_image,image)

plt.figure(figsize = (30,20))
plt.subplot(131)
plt.imshow(image)
plt.subplot(132)
plt.imshow(edges_image, cmap='gray')
plt.subplot(133)
plt.imshow(original_image_with_hough_lines, cmap='gray')
plt.show()


Below, there are some helper functions. I attach them for a better understanding of the entire code.

def draw_lines(img, houghLines, color=[0, 255, 0], thickness=2):
for line in houghLines:
for rho,theta in line:
a = np.cos(theta)
b = np.sin(theta)
x0 = a*rho
y0 = b*rho
x1 = int(x0 + 1000*(-b))
y1 = int(y0 + 1000*(a))
x2 = int(x0 - 1000*(-b))
y2 = int(y0 - 1000*(a))

cv2.line(img,(x1,y1),(x2,y2),color,thickness)

def weighted_img(img, initial_img, α=0.8, β=1., λ=0.):
return cv2.addWeighted(initial_img, α, img, β, λ)


### Example results

Results can be seen below. If there are too much lines in our opinion, or too few of them, we should adjust rho resolution, theta resolution and threshold parameters. But remember also about tuning parameters which are used in blurring and edge detection. Whole pipeline should be revised to fit your needs.

It’s worth noting that in OpenCV there exists another version of the function to find Hough Lines. It’s named HoughLinesP. P suffix stands for probabilistic here. It has more efficient implementation and the function outputs extremes of detected lines which can be very useful. Below, there is an example of the same image with the straight lines found using HoughLinesP.

### References

1. Generalized Hough Transform on Wikipedia
2. Hough Transform on Wikipedia
3. OpenCV 2.4 documentation – Hough Lines Transform
4. OpenCV 3.1 documentation – Hough Lines Transform

Also published on Medium.

1. Miroslav Karpíšek

Hi,

I’m trying to find out the vanishing point using the lines from hough transform (implemented in python). After i read your article I assume there must be some way of making the second hough transform on points i already found in rho-theta space and this line as it is a line in rho theta space can be represented as point in image space -> the vanishing point. I can’t tho find any material which will guide me (I’m pretty new to CV)
thanks

• tomasz.kacmajor

Hi,
I’ve never played with finding vanishing points. After some quick research, I think you’re right – second Hough transform should represent vanishing points on the original image. I found nice work about this topic, maybe it can help: https://pdfs.semanticscholar.org/f5a2/eb9c8d15f919c897fac80a392bdd34913ce7.pdf The authors claim that some processing of the first transform image is necessary before the 2nd transform – like local maxima suppression. Good luck with your project 🙂

This site uses Akismet to reduce spam. Learn how your comment data is processed.