Lane detection

You can find my code here. It might be more up to date than the article ;).

Intro

This is the first article in the self driving cars series. If you want to know why I’m sharing this and more about my journey, please read this.

Goal

For each image of the given video, we are going to detect the driving lane lines on each side of the car and visually highlight them.

Input conditions

The first iteration of the lane detection algorithm will work well on non-curved roads with a single camera on the dashboard. In these images, the weather conditions are good, and it is daytime. We will handle shadows, different line colors and continuous/discontinuous lanes. Much more work will need to be done later to make this work on curved roads, in different lighting and weather conditions.

Algorithm: Step by step

This algorithm is executed step by step on each frame:

1: Convert the picture to HSV. If you’re unfamiliar with HSV, it is basically a different way to describe color than the classic RGB we are used to, you can learn more about it on Wikipedia. We will explain later why this conversion is necessary.

2: We apply a small gaussian blur on the picture. It helps us reduce noise, keeping us from detecting tiny, irrelevant details on the picture such as foliage or very distant objects.

3: We now want to filter out (turn black) any pixel that is not the color of the lanes, in this case white or yellow.

This is where the HSV conversion comes in handy: it allows us to filter these colors much more easily by focusing on the hue and saturation of the pixel (which color it is and how intense the color is), and not so much on its value (how dark it is), thus handling shadows and overall worse lighting conditions much more easily.

The image has way fewer elements now, there only remain ones with white or yellowish tint, with some false positives but our two lines are very clearly defined.

4: We use Canny edge detection. The Canny algorithm detects edges on a picture by looking for quick changes in color between a pixel and its neighbors, in our case between the white or yellow lane line and black pixels.

5: We define our region of interest now. Given the position and orientation of the camera, we know that the lanes will be located in the lower half of the image, usually in a trapezoid covering the bottom corners and the center. We don’t want our region to be too narrow and have the lines out of our region of interest.

6: We run Hough transform to detect lines on our image. What does Hough transform do? To summarize quickly, it allows us to easily extract all the lines passing through each of our edge points and group by similarity, thus grouping together the points that are roughly located on a same line. This algorithm is overall fascinating and I encourage you to take a look at it here: Intro to Computer Vision @ Udacity. You need to create an account on Udacity but it’s worth it, believe me.

The Hough transformation gives us back multiple lines, but we only want 2 distinct lanes for our car to drive in between. There is still some work to do.

7: We filter the lines with horizontal slopes first, to make sure the data left is clean.

8: We distinguish between the left and right lane thanks to the line slopes.

9. Now that we grouped our points by lane line, we compute the linear regression of both groups and draw the results in our region of interest. Simply put, a linear regression is an attempt at finding the relationship between a group of points, so basically finding the line that passes at the closest possible distance from each point. This operation allows us to fill the blanks in a dashed lane line.

Beautiful.

10: All we have to do now is add these lanes to our original image.

As you can see, since the lanes are curved, and our extrapolation being linear, we do not match the curbs perfectly. But this is just an introduction and we’ll consider it good enough for now ;).

11: The final tweak we add since we will be using our algorithm on videos is some smoothing. We always take into consideration the previous lanes by giving them a weight before drawing the new lanes to have a smoother movement and reducing the effect of errors.

Here are 3 videos to show the final output.

Next time we’ll talk about deep learning and how we can detect traffic signs! Stay tuned.

Thanks to Eric Sauvegrain for his feedback on this post.