Robust Extrapolation of Lines in Video Using Probabilistic Hough Transform

A lane mark detection system is a driver assistance tool that automatically recognizes the lane mark painted on the road and the lane that he is travelling in. Such a system can warn the driver when has the tendency to move out from the lane, without being aware of it. This kind of system is a part of lane detection in self-driving cars, systems that has the goal to improve road safety.

Linear Hough transform is the crucial part in detecting lane lines in an image. Most of computer vision frameworks have a ready function for Hough transform like OpenCV. One of your most important tasks is to find a creative technique to extrapolate the line segments you have detected using Hough transform.

In this post, we propose a simple algorithm capable to extrapolate lane marks after it is detected using Hough transform and to determine the tendency of the traveling direction of the vehicle. We will illustrate code snippets within Python OpenCV framework.

Phase 1: Tuning Hough Transform Parameters:

The Standard Hough Transform returns parameters of detected lines in Polar Coordinate system, which is a vector of couples (rho, theta) as shown below.

Hesse Normal Form for representing a line

The probabilistic Hough line transform more efficient implementation of Hough transform. It gives as output the extremes of the detected lines (x0, y0, x1, y1). It is difficult to detect straight lines which are part of a curve because they are very very small. For detecting such lines it is important to properly set all the parameters of Hough transform. Two of most important parameters are: Hough votes and maximum distance between points which are to be joined to make a line. Both parameters are set at their minimum value.

import cv2
lines = cv2.HoughLinesP(image, rho, theta, min_number_of_votes, np.array([]), min_line_length, max_line_gap)

Phase 2: Threshold for Detected Line Slopes:

Now, the extrapolation part. Extrapolation means creating a tangent line at the end of the known data and extending it beyond that limit. Linear extrapolation will only provide good results when used to extend the graph of an approximately linear function or not too far beyond the known data.

If the two data points nearest the point x to be extrapolated are (x1, y1) and (x2, y2) linear extrapolation gives the function above.

Now, the question is which line should we extrapolate using its extreme points?

First approach is to take average of all slopes and intercepts of all Hough lines and extrapolate using results. The cons of such approach that a lot of noisy and very small lines of the curve are taken into account which is resulting our average line to diverge than actual lines.

Second approach, is to construct a feedback methodology in calculating your target slope of every frame taking into account two main points:

• How far is the current slope than average slope? In other words, tolerance for current slope than our average.
• “Average” is a feedback loop system where every frame Hough lines are averaged using history of preceding frames. The following flow diagram illustrates the idea.

Extrapolation Flow diagram

The most important rule for system stability is that you should never lose your history. When you iterate over Hough lines, add slope that are close to your current average. When you iterate over frames, add your slope and intercept into overall frame averages.

At the end of each frame, you should have a vector of intercepts and slopes of all lines in this form (avg_slope 1, avg_intercept 1, avg_slope 2, avg_intercept 2, …, avg_slope n, avg_intercept n). Now the final part is fitting all points using fitline function from OpenCV.

[line_1_vx,line_1_vy,line_1_x,line_1_y] = cv2.fitLine(np.array(line_1_points, dtype=np.int32), cv2.DIST_L2,0,0.01,0.01)

After we fitted our line, are we ready to plot it over our image frame? Well, not yet. Until this moment we didn’t use previous frame slopes and intercepts. Append your new fitted line into an array of previous frames fitted lines and do the normal arithmetic average.

avg = np.mean(previous_lines)
        line_1_b = avg[0]
        line_1_slope = avg[1]

Now you have for every line the slope and intercept and you are ready to extrapolate over the maximum points.

cv2.line(image, (bottom_x, bottom_y), (top_x, top_y), color, thickness)

Video below represents view of all steps involved in producing lane detection on highways for self-driving car.

We can realize in video shown at the beginning, the left line lane is too far than the actual left line lane. However, with next frames in time the left lane line are keeping to converge into the actual line lane due to implemented feedback systems.

Reflections

This was a part of a very interesting and joyful project to do with Udacity. The most interesting part in the project that I learned new algorithms techniques in Computer vision that I used and coded it simply. Also, the project pushed my mind into its limit to use my previous mathematical background to understand well the algorithms we use and get the best out of it.

Acknowledgement

Thanks to Udacity staff who selected me for Jan cohort to begin a new journey in my life with top-talented professionals and students all over the world learning and researching for top notch technologies.