Overview

Here we discuss an algorithm that helps a car use a camera to drive in between two lines. To be more concrete, this guide will explain the code and logic of a Python class with functions that:

  1. Detects lines on the sides of a lane.
  2. Uses the detected line to generate a goal point.

The full code is provided at the bottom of the page.

At First Glance

From a high level, our code has four main functions

import numpy as np
import cv2 as cv

class SimpleLaneDetector:
    def __init__(self, image=None, crop_factor=3/5, threshold=200): ...

    def set_img(self, image): ...

    def get_lines(self): ...

    def get_point(self): ...

In the __init__()function, every input has a default value. This allows the class to be initialized with no inputs. There are also some parameters to configure the algorithm.

  • crop_factor determines the fraction of the top of the image to crop out when determining where the lane is. A default of 3/5 means the algorithm only looks for lanes in the bottom 2/5 of the image.
  • threshold is used to differentiate the road from the lines and should be adjusted according to lighting.

The rest of the functions are also pretty straightforward.

  • set_img() sets or overrides the current image and resets all variables to default values.
  • get_lines() detects the lane and returns the endpoints of the lines that form the lane sorted left to right.
  • get_point() first calls get_lines() if get_lines() was not called, then calculates a goal point and returns.

Default Values When Setting Image

In set_img(), the dimensions of the image is extrapolated and saved along with the source image.

def set_img(self, image):
    # Set image and parameters
    self.input_img = image
    self.height, self.width, _ = self.input_img.shape

    # Reset variables
    self.left_line = [[0,0],[1,self.height]]
    self.right_line = [[self.width-1,self.height],[self.width,0]]
    self.point = (self.width//2,self.height//2)
    self.lines_called = False

The default values for some variables are also set.

  • self.left_line and self.right_line default to nearly vertical lines on their respective sides of the photo. They are there so that when no line is found, the line is assumed to be out of frame and therefore the goal point will be weighted to the corresponding side. They are not completely vertical to avoid division by zero issues when calculating the slope. You can change this to None and handle these cases in your controller.
  • self.point defaults to the very center of the screen so that when no point is found the car just keeps going forward. You can also change to None and handle with your controller.
  • The self.lines_called variable is a flag that is used to store whether or not get_lines() has been called. This is checked when get_point() is called.

Finding the Lane

On a high level, lanes can be found by:

  1. Looking for lines using OpenCV’s built in functions.
  2. For each line found, determine if it’s on the left or right of the lane.
  3. Find the left and right lanes by taking the average of the left and right lines found.

In the get_lines() function, self.lines_called is set to true to keep track whether get_lines() has been called.

def get_lines(self):
    self.lines_called = True

To detect lines from the image, the image must first be processed. The first step is to crop to the relevant portion of the image. OpenCV’s image container uses y-values that increase going down the image, where (0,0) is the top left and (w,h) is the bottom right.

    y_offset = int(self.height*self.CROP_FACTOR)
    # Crop to region of interest, grayscale and increase contrast
    crop_img = self.input_img[y_offset:, :]
    gray_img = cv.cvtColor(crop_img,cv.COLOR_BGR2GRAY)
    thresh_img = cv.threshold(gray_img, self.THRESHOLD, 255, 0)[-1]

The cropped image is gray-scaled and thresholded here to prepare for the next function. Thresholding uses the parameter, self.THRESHOLD as the threshold for converting a gray-scale image to a binary image. That is, every pixel above the threshold is set to 255 (white) and below is set to 0 (black).

The binary image is fed into cv.HoughLinesP(), a function that is able to find lines within a binary image.

    # Detect the lines
    lines = cv.HoughLinesP(thresh_img, 1, np.pi/180, 100, maxLineGap=200)

Here, the parameters are:

  • rho: the distance resolution in pixels
  • theta: the angle resolution in radians
  • threshold: the number of votes a line needs to have to be returned. It’s correlated with the number of points it finds in a row.
  • minLineLength: the minimum length a line of lines returned. It defaults to 0.
  • maxLineGap maximum distance between two found lines to link together as one line.

It returns a list of lines represented as pairs of endpoints in a 1 by 4 matrix. If it finds no lines, it will return None.

    # If no lines are found, return default lines
    if lines is None:
        return (self.left_line, self.right_line)

Filtering out when no lines are found prevents errors further in the code.

To determine which lines define the left and right edges of the lane, the lines are sorted into two lists. For each line,

  1. The slope is calculated from the endpoints
  2. Left boundaries are assumed to be sloping up and vice versa. But the image has its y axis flipped, so a left boundary would have negative slope and vice versa.
    lefts = []
    rights = []
    # Split lines into left and right lines based on slope
    for line in lines:
        x1,y1,x2,y2 = line[0]
        slope = (y2-y1)/(x2-x1)
        # Shift lines back to pre-cropped image
        sorted_line = sorted([[x1,y1+y_offset],[x2,y2+y_offset]])
        
        # Image has y axis flipped, slope is also negated
        if slope < 0:
            lefts.append(sorted_line)
        else:
            rights.append(sorted_line)

The endpoints of each line are sorted by their x values and then represent as nested tuples. The left and right lines are then determined by taking the average of their respective lists.

 # Average the lines
    if lefts:
        self.left_line = np.mean(lefts,axis=0).astype(int)

    if rights:
        self.right_line = np.mean(rights,axis=0).astype(int)

    self.left_line = tuple(map(tuple,self.left_line))
    self.right_line = tuple(map(tuple,self.right_line))        
    return (self.left_line, self.right_line)

Calculating a Goal Point

To find the goal point, the function:

  1. Averages the left and right lines to find a center line
  2. Finds a point along the center line to return as the goal

When get_points() is first called, it will call get_lines() it has not been called.

def get_point(self):
    if not self.lines_called:
        self.get_lines()

The endpoints are extracted and their slopes and offsets are calculated. The center line is found by flipping to the y-x axis, averaging the slopes, then flipping back. If the center line is vertical then the car is completely parallel with the lanes and so the center point is returned.

    # Calculate the center line
    (l_x1, l_y1), (l_x2, l_y2) = self.left_line
    (r_x1, r_y1), (r_x2, r_y2) = self.right_line

    m_l = (l_y2-l_y1)/(l_x2-l_x1)
    b_l = l_y1 - m_l*l_x1
    m_r = (r_y2-r_y1)/(r_x2-r_x1)
    b_r = r_y1 - m_r*r_x1

    # If center line has undefined slope, return center point
    if m_l == -m_r:
        self.point = (self.width//2, self.height//2)
        return self.point 

    m = 2/(1/m_l + 1/m_r)
    b = (b_l/m_l + b_r/m_r) / (1/m_l + 1/m_r)

The goal point is found by sampling points along the center line that is on screen and taking a weighted average. Each point is weighted by its vertical distance from the top. This weights the points towards further distances. You can change how to points are weighted or just use a fixed horizontal intercept.

    # Calculate y values of points
    pts = m*np.arange(self.width) + b

    # Remove values that are off the screen
    pts = pts[pts > 0]
    pts = pts[pts < self.height]

    # Generate weights, weighing points towards top of img
    weights = self.height - pts

    # Make sure weights aren't empty
    if np.shape(pts)[0]==0:
        self.point = (self.width//2, self.height//2)
        return self.point 

    # Generate goal point based on weighted average
    mean_y = np.average(pts,weights=weights)
    mean_x = (mean_y-b)/m

    self.point = int(mean_x), int(mean_y)
    return self.point

Full Code

#!/usr/bin/env python3
import numpy as np
import cv2 as cv

class SimpleLaneDetector:
    def __init__(self, image=None, crop_factor=3/5, threshold=200):
        # Algorithm parameters
        self.CROP_FACTOR = crop_factor
        self.THRESHOLD = threshold
        self.lines_called = False

        if image is not None:
            self.set_img(image)

    def set_img(self, image):
        # Set image and parameters
        self.input_img = image
        self.height, self.width, _ = self.input_img.shape

        # Reset variables
        self.left_line = [[0,0],[1,self.height]]
        self.right_line = [[self.width-1,self.height],[self.width,0]]
        self.point = (self.width//2,self.height//2)
        self.lines_called = False

    def get_lines(self):
        self.lines_called = True

        y_offset = int(self.height*self.CROP_FACTOR)
        # Crop to region of interest, grayscale and increase contrast
        crop_img = self.input_img[y_offset:, :]
        gray_img = cv.cvtColor(crop_img,cv.COLOR_BGR2GRAY)
        thresh_img = cv.threshold(gray_img, self.THRESHOLD, 255, 0)[-1]

        # Detect the lines
        lines = cv.HoughLinesP(thresh_img,1, np.pi/180, 100, maxLineGap=200)

        # If no lines are found, return default lines
        if lines is None:
            return (self.left_line, self.right_line)

        lefts = []
        rights = []
        # Split lines into left and right lines based on slope
        for line in lines:
            x1,y1,x2,y2 = line[0]
            slope = (y2-y1)/(x2-x1)
            # Shift lines back to pre-cropped image
            sorted_line = sorted([[x1,y1+y_offset],[x2,y2+y_offset]])
            
            # Image has y axis flipped, slope is also negated
            if slope < 0:
                lefts.append(sorted_line)
            else:
                rights.append(sorted_line)

        # Average the lines
        if lefts:
            self.left_line = np.mean(lefts,axis=0).astype(int)

        if rights:
            self.right_line = np.mean(rights,axis=0).astype(int)

        self.left_line = tuple(map(tuple,self.left_line))
        self.right_line = tuple(map(tuple,self.right_line))        
        return (self.left_line, self.right_line)

    def get_point(self):
        if not self.lines_called:
            self.get_lines()

        # Calculate the center line
        (l_x1, l_y1), (l_x2, l_y2) = self.left_line
        (r_x1, r_y1), (r_x2, r_y2) = self.right_line

        m_l = (l_y2-l_y1)/(l_x2-l_x1)
        b_l = l_y1 - m_l*l_x1
        m_r = (r_y2-r_y1)/(r_x2-r_x1)
        b_r = r_y1 - m_r*r_x1

        # If center line has undefined slope, return center point
        if m_l == -m_r:
            self.point = (self.width//2, self.height//2)
            return self.point 

        m = 2/(1/m_l + 1/m_r)
        b = (b_l/m_l + b_r/m_r) / (1/m_l + 1/m_r)

        # Calculate y values of points
        pts = m*np.arange(self.width) + b

        # Remove values that are off the screen
        pts = pts[pts > 0]
        pts = pts[pts < self.height]

        # Generate weights, weighing points towards top of img
        weights = self.height - pts

        # Make sure weights aren't empty
        if np.shape(pts)[0]==0:
            self.point = (self.width//2, self.height//2)
            return self.point 

        # Generate goal point based on weighted average
        mean_y = np.average(pts,weights=weights)
        mean_x = (mean_y-b)/m

        self.point = int(mean_x), int(mean_y)
        return self.point

Example Usage

To use this, import the class into another file and construct the class.

import simple_lane_detector as ld

Set the image and get the line or goal point by calling the corresponding function

# Construct object
detect = ld.SimpleLaneDetector()

# Set image, takes OpenCV image as inpute
detect.set_img(image)

# Detect line and point
detect.get_line()
detect.get_point()

You can iterate through a list of images as well.

detect = ld.SimpleLaneDetector()
for frame in video:
    detect.set_img(frame)
    detect.get_point()

Here’s an example run on a test image. The code below the print statement visualizes the outputted goal point as a green circle.

#!/usr/bin/env python3
import cv2 as cv
import lane_detection_simple as ld

detect = ld.SimpleLaneDetector()
frame = cv.imread("/home/ray/test.jpg")
detect.set_img(frame)
goal = detect.get_point()
print("OUTPUT: ", goal)

cv.circle(frame, goal, radius=3, color=(0,255,0), thickness=5)
cv.imshow("test.jpg",frame)
cv.waitKey(0)
cv.destroyAllWindows()

The input image is this:

Running this in a linux terminal returns this:

The visualized point is this: