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. [1].

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 (a, b) which correspond to slope and intercept. The line is then described as: y = a x + b

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 (a, b) parameters in Cartesian system.

For a given line, we can determine specific ρ and θ. Then, the following equation is satisfied for each x, y point belonging to this line:

ρ = x cos(θ) + y sin(θ)

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 ρ = x cos(θ) + y sin(θ). Indeed, for fixed (x, y) 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 between Image space and Hough space:

Straight line → Point

Point → Sinusoid

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.

from en.wikipedia.org/wiki/Hough_transform

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.

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

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 (x0, y0, x1, y1) 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

Originally published at ProggBlogg.