#### 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
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:
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
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:
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()
detect.set_img(frame)
goal = detect.get_point()
print("OUTPUT: ", goal)