Lane detection with NumPy #2 : Hough Transform
In the previous post about lane detection we’ve figured out how to extract edges from an image. In this article I will extract lines.
Matrices and lines
The images are stored as 2-d matrices, so we can look on them as a cartesian coordinate system. In this system we can define any line as the following function:
In order to find out about a pixel if it belongs to a given line, we just need to check, if at the given x coordinate the function results the correct y value.
The problem with this is that a point can belong to infinitely many possible lines (as the equation of the line has 2 variables).
So instead, we’ll create so-called 2d Hough-space and plot there all the possible m and b values for the given pixel. For every point in the normal space we’ll have a line in the Hough-space.
However, in practice we’ll doing a slightly different thing. We are using the polar representation for the pixel points, so we can define our lines as a distance and the angle of rotation from a reference point (usually the 0,0 point of the image). In this representation the line equation is the following:
d = x * cos(θ) +y * sin(θ)
So for a point in normal space we’ll get a sinusoid curve. Any d, θ from the curve in the Hough-space represents a line in the image space, which goes through the (x, y) point. Note that this means that we can have infinitely many possible lines for one point.
In order to define a line exactly, we need at least 2 points. Let’s see:
And here comes the magic: the 2 curves has a point of intersection — and this point describes the equation of our line in the image space. This is the logic behind it: The 2 points independently can belong to a lot of possible lines (as they d and θ can vary). However, there is only one possible (d, θ) line, which goes through both of the points.
And this works with any number of points, too:
What happens if we have more then one line?
We will have more than one point of intersection. Actually, we’ll have many of them. This makes sense, as we may know that we have only 2 lines on the image, but the computer doesn’t. It just tells us which are the most promising. When working with real images, we usually have a lot of noise, as well as lines which are not ‘real’ lines; so we can look on the points in the Hough-space as a probability value of the given (d, theta) line .
As you can see, doing the Hough-transform algorithm can yield some meaningful results, but we still need to filter it, as this strategy is very prone to noise.
In the next article I’m going to discover how to get rid of false positive line results and how to plot them. For more information about Hough-transform I really recommend these lectures.
The algorithm
build_hough_space_fom_image(img)
returns the Hough-space for the image. The algorithm loops over every pixel, and builds the curve for the given image in the Hough-space. The new curve is added to the existing Hough-space, so this way the pixel which belongs to intersections will end up with higher values. The most important lines are highlighted.
def build_hough_space_fom_image(img, shape = (100, 300), val = 1):
hough_space = np.zeros(shape)
for i, row in enumerate(img):
for j, pixel in enumerate(row):
if pixel != val : continue
hough_space = add_to_hough_space_polar((i,j), hough_space)
return hough_spacedef add_to_hough_space_polar(p, feature_space):
space = np.linspace(0, pi, len(feature_space))
d_max = len(feature_space[0]) / 2
for i in range(len(space)):
theta = space[i]
d = int(p[0] * sin(theta) + p[1] * cos(theta)) + d_max if (d >= d_max * 2) : continue feature_space[i, d] += 1
return feature_space
