Enrichment of point cloud data for high-definition maps for autonomous vehicles

Patent metadata

Field	Value
Publication number	US-2018190016-A1
Application number	US-201715855547-A
Country	US
Kind code	A1
Filing date	Dec 27, 2017
Priority date	Dec 30, 2016
Publication date	Jul 5, 2018
Grant date	—

Abstract

A vehicle computing system performs enhances relatively sparse data collected by a LiDAR sensor by increasing the density of points in certain portions of the scan. For instance, the system generates 3D triangles based on a point cloud collected by the LiDAR sensor and filters the 3D triangles to identify a subset of 3D triangles that are proximate to the ground. The system interpolates points within the subset of 3D triangles to identify additional points on the ground. As another example, the system uses data collected by the LiDAR sensor to identify vertical structures and interpolate additional points on those vertical structures. The enhanced data can be used for a variety of applications related to autonomous vehicle navigation and HD map generation, such as detecting lane markings on the road in front of the vehicle or determining a change in the vehicle's position and orientation.

First claim

What is claimed is:

1 . A method comprising:
obtaining a point cloud comprising a plurality of three-dimensional (3D) points, the 3D points representing scanner data collected by a light detection and ranging (LiDAR) sensor; projecting the plurality of 3D points onto a two-dimensional (2D) plane to generate a plurality of 2D points, each of the 2D points corresponding to one of the 3D points; performing triangulation on the plurality of 2D points to generate a set of 2D triangles, each vertex of each of the 2D triangles defined by one of the 2D points; generating a set of 3D triangles, each of the 3D triangles corresponding to one of the 2D triangles, each vertex of each of the 3D triangles defined by the 3D point corresponding to the 2D point defining a corresponding vertex of the corresponding 2D triangle; filtering the set of 3D triangles to identify a subset of 3D triangles having vertices proximate to a ground surface surrounding the LiDAR sensor; generating a plurality of interpolated 3D points, each of the interpolated 3D points generated by randomly selecting one of the 3D triangles and randomly generating an interpolated 3D point within the selected 3D triangle; and providing the plurality of interpolated 3D points for inclusion in a high definition map, the high definition map for use in driving by one or more vehicles.

2 . The method of claim 1 , wherein obtaining the point cloud comprises:
receiving scanner data collected by the LiDAR sensor; and subsampling the scanner data to generate the point cloud.

3 . The method of claim 1 , further comprising obtaining an image captured by a camera having a field of view overlapping at least in part with a field of view of the LiDAR sensor.

4 . The method of claim 3 , wherein the 2D plane is parallel to an image sensor of the camera.

5 . The method of claim 4 , further comprising:
identifying a region of the 2D plane corresponding to a region depicted in the captured image; and after projecting the plurality of 3D points onto the 2D plane to generate the plurality of 2D points, discarding 2D points having a position outside of the identified portion of the 2D plane.

6 . The method of claim 3 , further comprising:
for at least one of the interpolated 3D points, selecting a color for the interpolated 3D point matching a color of one or more pixels in the captured image at a position corresponding to the interpolated 3D point.

7 . The method of claim 1 , wherein performing triangulation on the plurality of 2D points comprises performing a Delaunay triangulation process on the plurality of 2D points.

8 . The method of claim 1 , wherein filtering the set of 3D triangles comprises removing 3D triangles that fail to satisfy one or more predefined filtering criteria.

9 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle is at an elevation lower than a threshold elevation.

10 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle has a normal vector that differs by less than a threshold angle from a vertical direction.

11 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle has a longest side shorter than a threshold length.

12 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle has an area less than a threshold area.

13 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle has a corresponding 2D triangle having a longest side shorter than a threshold length.

14 . The method of claim 8 , wherein one of the filtering criteria is satisfied when a 3D triangle has a corresponding 2D triangle having an area less than a threshold area.

15 . The method of claim 8 , wherein filtering the set of 3D triangles further comprises:
after removing 3D triangles that fail to satisfy one or more predefined filtering criteria, fitting a plane to vertices of the set of 3D triangles; and removing 3D triangles having at least one vertex more than a threshold distance from the fitted plane.

16 . The method of claim 15 , wherein fitting the plane to vertices of the set of 3D triangles comprises performing a RANSAC regression on vertices of the set of 3D triangles.

17 . A non-transitory computer-readable storage medium comprising executable computer instructions that, when executed by a processor, cause the processor to perform steps comprising:
obtaining a point cloud comprising a plurality of three-dimensional (3D) points, the 3D points representing scanner data collected by a light detection and ranging (LiDAR) sensor; performing triangulation to generate a set of 3D triangles, each vertex of each of the 3D triangles defined by one of the 3D points; filtering the set of 3D triangles to identify a subset of 3D triangles having vertices proximate to a ground surface surrounding the LiDAR sensor; generating a plurality of interpolated 3D points, each of the interpolated 3D points generated by randomly selecting one of the 3D triangles and randomly generating an interpolated 3D point within the selected 3D triangle; and generating a high definition map based on the plurality of interpolated 3D points, the high definition map for use in driving by one or more vehicles.

18 . The non-transitory computer-readable storage medium of claim 17 , wherein filtering the set of 3D triangles comprises removing 3D triangles that fail to satisfy one or more predefined filtering criteria.

19 . The non-transitory computer-readable storage medium of claim 18 , wherein filtering the set of 3D triangles further comprises:
after removing 3D triangles that fail to satisfy one or more predefined filtering criteria, fitting a plane to vertices of the set of 3D triangles; and removing 3D triangles having at least one vertex more than a threshold distance from the fitted plane.

20 . A computing system comprising:
a processor; and a non-transitory computer-readable storage medium comprising executable computer instructions that, when executed by the processor, cause the processor to perform steps comprising:
obtaining a point cloud comprising a plurality of three-dimensional (3D) points, the 3D points representing scanner data collected by a light detection and ranging (LiDAR) sensor,
performing triangulation to generate a set of 3D triangles, each vertex of each of the 3D triangles defined by one of the 3D points,
filtering the set of 3D triangles to identify a subset of 3D triangles having vertices proximate to a ground surface surrounding the LiDAR sensor,
generating a plurality of interpolated 3D points, each of the interpolated 3D points generated by randomly selecting one of the 3D triangles and randomly generating an interpolated 3D point within the selected 3D triangle, and
generating a high definition map based on the plurality of interpolated 3D points, the high definition map for use in driving by one or more vehicles.

Assignees

• Deepmap Inc

Inventors

• Yang Lin

Classifications

• G01C11/12

  the pictures being supported in the same relative position as when they were taken · CPC title

• G06T17/05 Primary

  Geographic models · CPC title

• G01S19/46

  the supplementary measurement being of a radio-wave signal type · CPC title

• B60W2552/00

  Input parameters relating to infrastructure · CPC title

• G01S19/47

  the supplementary measurement being an inertial measurement, e.g. tightly coupled inertial · CPC title