Lane detection and tracking techniques for imaging systems
A method for detecting boundaries of lanes on a road is presented. The method comprises receiving, by one or more processors from an imaging system, a set of pixels associated with lane markings. The method further includes partitioning, by the one or more processors, the set of pixels into a plurality of groups. Each of the plurality of groups is associated with one or more control points. The method further includes generating, by the one or more processors, a spline that traverses the control points of the plurality of groups. The spline traversing the control points describes a boundary of a lane.
1. A method for detecting boundaries of lanes on a road, the method comprising:
receiving, by one or more processors from an imaging system, a set of pixels associated with lane markings;
partitioning, by the one or more processors, the set of pixels into a plurality of groups, each of the plurality of groups associated with one or more control points; and
generating, by the one or more processors, a spline that traverses the control points of the plurality of groups, the spline describing a boundary of a lane.
2. The method of claim 1 , wherein partitioning the set of pixels into a plurality of groups further comprises:
iteratively linking, by the one or more processors, the pixels from the set of pixels into one or more linked sections of pixels; and
partitioning, by the one or more processors, the one or more linked sections of pixels into the plurality of groups.
3. The method of claim 2 , wherein partitioning the linked section of pixels into the plurality of groups further comprises:
determining, by the one or more processors, a principal component for each group of the plurality of groups, wherein each principal component includes at least one control point of the one or more control points; and
associating, by the one or more processors, groups of the plurality of groups based on the respective principal components.
4. The method of claim 3 , wherein determining the principal component for each group further comprises fitting, by the one or more processors, a principal component line to the pixels included in each group, wherein the principal component line is bounded by two control points.
5. The method of claim 4 , wherein the respective two control points corresponding to each principal component define a set of control points, and wherein partitioning the set of pixels into a plurality of groups further comprises executing, by the one or more processors, an association algorithm, the association algorithm comprising:
determining an endpoint distance between respective pairs of control points from two different groups;
comparing the endpoint distance for each respective pair of control points with a minimum threshold endpoint distance; and
responsive to determining that the endpoint distance for a respective pair of control points is less than or equal to the minimum threshold endpoint distance, associating the two groups including the respective pairs of control points.
6. The method of claim 5 , the association algorithm further comprising:
determining an endpoint angle between the respective pairs of control points;
comparing (i) the endpoint angle for each respective pair of control points with a threshold endpoint angle and (ii) the endpoint distance for each respective pair of control points with the minimum threshold endpoint distance and a maximum threshold endpoint distance; and
responsive to determining that (i) the endpoint angle for a respective pair of control points is less than or equal to the threshold endpoint angle and (ii) the endpoint distance for the respective pair of control points is above the minimum threshold endpoint distance and below the maximum threshold endpoint distance, associating the two groups including the respective pairs of control points.
7. The method of claim 4 , wherein the respective two control points corresponding to each principal component define a set of control points, and wherein partitioning the set of pixels into a plurality of groups further comprises executing, by the one or more processors, a graph-based association algorithm, the association algorithm comprising:
assigning each control point of the set of control points to a node in a graph;
forming an edge between each pair of nodes in the graph;
determining a cost for each edge in the graph;
adding a source node and a target node to the graph; and
determining one or more low-cost paths that traverse the graph from the source node to the target node, wherein the control points along each of the low-cost paths correspond to a lane.
8. The method of claim 7 , wherein forming the edge between each pair of nodes in the graph corresponds to fitting a spline between the pair of nodes.
9. The method of claim 7 , wherein determining the cost for each edge includes on one or more of:
assigning a higher cost to an edge that crosses a road barrier;
assigning a lower cost to an edge that follows one or more lane markings; or
assigning a higher cost to an edge that corresponds to a high sharpness in view of a driving environment.
10. The method of claim 1 , wherein partitioning the set of pixels into a plurality of groups further comprises executing, by the one or more processors, a linking algorithm, the linking algorithm comprising:
generating, by the one or more processors, a bounding box around a first pixel of the set of pixels;
scanning, by the one or more processors, an area encompassed by the bounding box to locate a second pixel; and
linking, by the one or more processors, the first pixel and the second pixel.
11. The method of claim 10 , wherein the bounding box is rectangular, and the bounding box includes a forward bias with respect to the first pixel.
12. The method of claim 10 , further comprising iteratively performing, by the one or more processors, the linking algorithm until each pixel in the set of pixels is linked to another pixel in the set of pixels, wherein each pixel in the set of pixels is linked to at most two other pixels in the set of pixels and each pixel in the set of pixels is part of one of one or more linked sections of pixels.
13. The method of claim 1 , wherein partitioning the set of pixels into a plurality of groups further comprises executing, by the one or more processors, a partitioning algorithm, the partitioning algorithm comprising:
constructing, by the one or more processors, a line between a start pixel of a linked section of pixels and an end pixel of the linked section of pixels;
determining, by the one or more processors, a distance of each pixel between the start pixel and end pixel from the line;
determining, by the one or more processors, that greater than a threshold number of pixels are located beyond a threshold distance from the line; and
separating, by the one or more processors and in response to determining that greater than the threshold number of pixels are located beyond the threshold distance, the linked section of pixels into two or more separate linked sections of pixels.
14. The method of claim 13 , further comprising iteratively performing, by the one or more processors, the partitioning algorithm until each pixel of the set of pixels is included in one group of the plurality of groups.
15. The method of claim 1 , wherein generating the spline further comprises executing, by the one or more processors, a spline technique, and wherein the spline technique utilizes only the one or more control points.
16. The method of claim 15 , wherein the spline technique is a Catmull-Rom spline technique.
17. The method of claim 1 , further comprising identifying the set of pixels associated with lane markings, comprising:
receiving, by one or more processors from an imaging system, an image of a road surface, the image made up of a set of pixels; and
determining, by the one or more processors, within the set of pixels, a first group of pixels associated with lane markings separating a first pair of lanes and a second group of pixels associated with lane markings separating a second pair of lanes, including, for each of the first and second groups:
identifying lane marking pixels that correspond to lane markings,
estimating a left boundary and a right boundary relative to the lane marking pixels, such that the left and the right boundaries are substantially aligned with a direction of a lane indicated by the lane marking pixels, and
associating pixels within the left boundary and the right boundary with the corresponding group.
18. The method of claim 17 , wherein associating within the left boundary and the right boundary includes applying a region growth algorithm to grow clusters initially containing only the lane marking pixels.
19. The method of claim 18 , wherein applying the region growth algorithm includes preventing pixels in the first group from crossing either boundary of the second group.
20. The method of claim 17 , wherein:
determining the first and second groups of pixels includes applying a machine learning model to the image, the machine learning model configured to predict which pixels in the image will be associated with the first group of pixels or the second group of pixels; and
estimating the left and the right boundaries for each group includes generating respective predictions using the machine learning model.
21. The method of claim 20 , further comprising configuring the machine learning model to generate the predictions related to the left and the right boundaries simultaneously with predictions related to road segmentation.
22. The method of claim 20 , wherein applying the machine learning model includes applying, as feature labels, indications from an operator regarding the pixels in the image corresponding to the lane markings.
23. The method of claim 17 , wherein the image includes a plurality of rows substantially perpendicular to the orientation of the lanes; the method further comprising:
for a lane marking pixel in a certain row, estimating to which next-row pixel in an adjacent row the pixel is connected, wherein the next-row pixel is (i) immediately below the lane marking pixel, (ii) immediately below and one pixel to the left of the marking pixel, or (iii) immediately below and one pixel to the right of the marking pixel.
24. The method of claim 23 , further comprising growing clusters of pixels associated with the first group or the second group along connected pixels.
25. The method of claim 23 , wherein estimating to which next-row pixel in an adjacent row the pixel is connected includes applying a machine-learning model trained using (i) a prior plurality of pixels and (ii) one or more indications that a first adjacent-row pixel and a second adjacent-row pixel in the prior plurality of pixels are connected when the first adjacent-row pixel is (a) immediately below the second adjacent-row pixel, (b) immediately below and one pixel to the left of the second adjacent-row pixel, or (c) immediately below and one pixel to the right of the second adjacent-row pixel.