System, method, and computer program product for detecting road marking points from LiDAR data

1. A computer implemented method comprising:

obtaining a LiDAR dataset generated by a LiDAR system, the LiDAR dataset defining a plurality of point clouds associated with a plurality of laser emitters of the LiDAR system;

separately processing, for each laser emitter of the plurality of laser emitters, a point cloud of the plurality of point clouds associated with that laser emitter by:

sorting, into a presorted array of points, points of the point cloud in an order according to azimuth angles associated with the points, times associated with the points, or any combination thereof, wherein neighboring points in the array correspond to neighboring measurements in a geographic area in which an autonomous vehicle is located;

determining, for each point in the point cloud, based on a gradient of intensity at that point for a pair of neighboring points in the point cloud including that point and another point, whether that point corresponds to a gradient edge point; and

determining, based on intensities of points in an interior segment of points between at least one candidate pair of gradient edge points and intensities of points in exterior segments of points outside the at least one candidate pair of gradient edge points, whether the at least one candidate pair of gradient edge points corresponds to a road marking edge, wherein candidate pairs of edge points are selected by moving from a beginning of the presorted array of points and selecting a first positive gradient edge point identified in the array as a first candidate point of the pair of candidate points and moving from an end of the presorted array of points and selecting a first negative gradient edge point identified in the presorted array of points as a second candidate point of the pair of candidate points;

aggregating, from the processing of the plurality of point clouds, candidate pairs of gradient edge points determined to correspond to road marking edges; and

using the candidate pairs of gradient edge points determined to correspond to the road marking edges to at least one of generate a map including the road marking edges, facilitate at least one autonomous driving operation of the autonomous vehicle, or any combination thereof.

2. The computer implemented method of claim 1 , wherein determining, for each point in the point cloud, based on the gradient of intensity at that point, whether that point corresponds to a gradient edge point further includes:

determining, based on the gradient of intensity at that point for the pair of neighboring points in the point cloud including that point and the another point and a relative difference in intensity between the pair of neighboring points, whether that point corresponds to a gradient edge point.

3. The computer implemented method of claim 1 , wherein determining whether the at least one candidate pair of gradient edge points corresponds to a road marking edge is based on at least one of the following parameters: an angular arc of the interior segment of points, a Euclidean distance of the interior segment of points, a maximum distance between consecutive points in the interior segment of points, a minimum intensity of the points in the interior segment of points, a ratio of the minimum intensity of the points in the interior segment of points to a maximum intensity of the points in the interior segment of points, a difference between a mean interior intensity of the interior segment of points and a mean exterior intensity of the exterior segments of points, a standard deviation of the interior segment of points, or any combination thereof.

4. The computer implemented method of claim 1 , wherein point clouds of the plurality of point clouds associated with the plurality of laser emitters are processed in parallel using multithreading.

5. The computer implemented method of claim 1 , wherein each LiDAR point cloud of the plurality of point clouds corresponds to a single 360 degree sweep of the LiDAR system.

6. The computer implemented method of claim 1 , further comprising:

localizing, based on the candidate pairs of gradient edge points determined to correspond to the road marking edges, the autonomous vehicle in a 3D LiDAR map of the geographic area in which the autonomous vehicle is located.

7. A system comprising:

one or more processors programmed and/or configured to:

obtain a LiDAR dataset generated by a LiDAR system, the LiDAR dataset defining a plurality of point clouds associated with a plurality of laser emitters of the LiDAR system;

separately process, for each laser emitter of the plurality of laser emitters, a point cloud of the plurality of point clouds associated with that laser emitter by:

sorting, into a presorted array of points, points of the point cloud in an order according to azimuth angles associated with the points, times associated with the points, or any combination thereof, wherein neighboring points in the array correspond to neighboring measurements in a geographic area in which an autonomous vehicle is located;

determining, for each point in the point cloud, based on a gradient of intensity at that point for a pair of neighboring points in the point cloud including that point and another point, whether that point corresponds to a gradient edge point; and

determining, based on intensities of points in an interior segment of points between at least one candidate pair of gradient edge points and intensities of points in exterior segments of points outside the at least one candidate pair of gradient edge points, whether the at least one candidate pair of gradient edge points corresponds to a road marking edge, wherein candidate pairs of edge points are selected by moving from a beginning of the presorted array of points and selecting a first positive gradient edge point identified in the array as a first candidate point of the pair of candidate points and moving from an end of the presorted array of points and selecting a first negative gradient edge point identified in the presorted array of points as a second candidate point of the pair of candidate points;

aggregate, from the processing of the plurality of point clouds, candidate pairs of gradient edge points determined to correspond to road marking edges; and

use the candidate pairs of gradient edge points determined to correspond to the road marking edges to at least one of generate a map including the road marking edges, facilitate at least one autonomous driving operation of the autonomous vehicle, or any combination thereof.

8. The system of claim 7 , wherein determining, for each point in the point cloud, based on the gradient of intensity at that point, whether that point corresponds to a gradient edge point further includes:

determining, based on the gradient of intensity at that point for the pair of neighboring points in the point cloud including that point and the another point and a relative difference in intensity between the pair of neighboring points, whether that point corresponds to a gradient edge point.

9. The system of claim 7 , wherein determining whether the at least one candidate pair of gradient edge points corresponds to a road marking edge is based on at least one of the following parameters: an angular arc of the interior segment of points, a Euclidean distance of the interior segment of points, a maximum distance between consecutive points in the interior segment of points, a minimum intensity of the points in the interior segment of points, a ratio of the minimum intensity of the points in the interior segment of points to a maximum intensity of the points in the interior segment of points, a difference between a mean interior intensity of the interior segment of points and a mean exterior intensity of the exterior segments of points, a standard deviation of the interior segment of points, or any combination thereof.

10. The system of claim 7 , wherein the one or more processors are further programmed and/or configured to process point clouds of the plurality of point clouds associated with the plurality of laser emitters in parallel using multithreading.

11. The system of claim 7 , wherein each LiDAR point cloud of the plurality of point clouds corresponds to a single 360 degree sweep of the LiDAR system.

12. The system of claim 7 , wherein the one or more processors are further programmed and/or configured to:

localize, based on the candidate pairs of gradient edge points determined to correspond to the road marking edges, the autonomous vehicle in a 3D LiDAR map of the geographic area in which the autonomous vehicle is located.

13. An autonomous vehicle comprising:

a LiDAR system configured to generate a LiDAR dataset, the LiDAR dataset defining a plurality of point clouds associated with a plurality of laser emitters of the LiDAR system; and

a computing device programmed and/or configured to:

obtain a LiDAR dataset generated by a LiDAR system, the LiDAR dataset defining a plurality of point clouds associated with a plurality of laser emitters of the LiDAR system;

separately process, for each laser emitter of the plurality of laser emitters, a point cloud of the plurality of point clouds associated with that laser emitter by:

sorting, into a presorted array of points, points of the point cloud in an order according to azimuth angles associated with the points, times associated with the points, or any combination thereof, wherein neighboring points in the array correspond to neighboring measurements in a geographic area in which the autonomous vehicle is located;

determining, for each point in the point cloud, based on a gradient of intensity at that point for a pair of neighboring points in the point cloud including that point and another point, whether that point corresponds to a gradient edge point; and

determining, based on intensities of points in an interior segment of points between at least one candidate pair of gradient edge points and intensities of points in exterior segments of points outside the at least one candidate pair of gradient edge points, whether the at least one candidate pair of gradient edge points corresponds to a road marking edge, wherein candidate pairs of edge points are selected by moving from a beginning of the presorted array of points and selecting a first positive gradient edge point identified in the array as a first candidate point of the pair of candidate points and moving from an end of the presorted array of points and selecting a first negative gradient edge point identified in the presorted array of points as a second candidate point of the pair of candidate points;

aggregate, from the processing of the plurality of point clouds, candidate pairs of gradient edge points determined to correspond to road marking edges; and

localize, based on the candidate pairs of gradient edge points determined to correspond to the road marking edges, the autonomous vehicle in a 3D LiDAR map of the geographic area in which the autonomous vehicle is located.

14. The autonomous vehicle of claim 13 , wherein determining, for each point in the point cloud, based on the gradient of intensity at that point, whether that point corresponds to a gradient edge point further includes:

determining, based on the gradient of intensity at that point for the pair of neighboring points in the point cloud including that point and the another point and a relative difference in intensity between the pair of neighboring points, whether that point corresponds to a gradient edge point.

15. The autonomous vehicle of claim 13 , wherein determining whether the at least one candidate pair of gradient edge points corresponds to a road marking edge is based on at least one of the following parameters: an angular arc of the interior segment of points, a Euclidean distance of the interior segment of points, a maximum distance between consecutive points in the interior segment of points, a minimum intensity of the points in the interior segment of points, a ratio of the minimum intensity of the points in the interior segment of points to a maximum intensity of the points in the interior segment of points, a difference between a mean interior intensity of the interior segment of points and a mean exterior intensity of the exterior segments of points, a standard deviation of the interior segment of points, or any combination thereof.

16. The autonomous vehicle of claim 13 , wherein the computing device is further programmed and/or configured to process point clouds of the plurality of point clouds associated with the plurality of laser emitters in parallel using multithreading.

17. The autonomous vehicle of claim 13 , wherein each LiDAR point cloud of the plurality of point clouds corresponds to a single 360 degree sweep of the LiDAR system.