Building elevation maps from laser data

• US 9,709,679 B1
• Filed: 08/06/2014
• Issued: 07/18/2017
• Est. Priority Date: 08/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Waymo LLC (Alphabet Inc.)
• Inventors: Dahlkamp, Hendrik, Urmson, Christopher Paul, Chatham, Andrew Hughes, Montemerlo, Michael Steven, Zhu, Jiajun
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US14/452,894
• Time in Patent Office: 1,077 Days
• CPC Class Codes: G01C 21/3822 Road feature data, e.g. slope data
• CPC Class Codes: G01C 21/3826 Terrain data
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G09B 29/12 Relief maps relief models G09B25/06

Abstract

Aspects of the present disclosure relate generally to generating elevation maps. More specifically, data points may be collected by a laser moving along a roadway and used to generate an elevation map of the roadway. The collected data points may be projected onto a two dimensional or “2D” grid. The grid may include a plurality of cells, each cell of the grid representing a geolocated second of the roadway. The data points of each cell may be evaluated to identify an elevation for the particular cell. For example, the data points in a particular cell may be filtered in various ways including occlusion, interpolation from neighboring cells, etc. The minimum value of the remaining data points within each cell may then be used as the elevation for the particular cell, and the elevation of a plurality of cells may be used to generate an elevation map of the roadway.

Claims

1. A method comprising:

receiving, using one or more computing devices, a plurality of data points via one or more sensors, each data point representing a position and elevation of a surface;

determining, using the one or more computing devices, a first set of data points based on one or more positions of the plurality of data points;

determining, using the one or more computing devices, a plurality of portions of the surface wherein the positions of a plurality of the data points of the first set are located in each portion;

identifying, for each portion of the surface and using the one or more computing devices, a data point associated with a lowest relative elevation of the set of first data points located in the portion; and

generating, using the one or more computing devices, an elevation map wherein the elevation of each portion is based on at least the identified data point associated with the lowest relative elevation of the portion.

2. The method of claim 1, wherein the portions correspond to cells of a 2D grid.

3. The method of claim 1, further comprising transferring, using the one or more computing devices, the elevation to a vehicle in order to navigate the vehicle along a roadway.

4. The method of claim 1, further comprising, prior to identifying the first data points associated with the lowest relative elevations, filtering the first set of data points to remove outlier points by interpolating data.

5. The method of claim 4, wherein filtering the first set of data points includes removing outlier points based on a threshold deviation from an average elevation of the first set of data points.

6. The method of claim 2, further comprising, prior to identifying the data points associated with the lowest relative elevations, filtering the first set of data points for a particular cell of the plurality of cells by generating an approximate data point for the particular cell based on data from a neighboring cell of the particular cell.

7. The method of claim 4, wherein filtering the first set of data points includes filtering using an occlusion method.

8. The method of claim 4, wherein filtering the first set of data points includes identifying two clusters of data points.

9. The method of claim 8, further comprising:

identifying a second data point of the first set of data points associated with a lowest relative elevation for a higher relative cluster of the two clusters;

wherein generating the elevation map is further based on the second data point of the second set of data points.

10. A system for generating an elevation map of a roadway, the system comprising:

memory storing sensor data, the sensor data including a plurality of data points, each data point representing a position and elevation of a surface; and

one or more computing devices, each computing device having one or more processors, the one or more processors of each computing device coupled to the memory, and the one or more computing devices configured to;

access the stored sensor data;

determine a set of first data points based on one or more positions of the plurality of data points;

filter the set of first data points in order to generate a set of second data points;

determine a plurality of portions of the surface wherein the positions of a plurality of the second data points are located in each portion;

identify, for each portion of the surface, the second data point having the lowest relative elevation of the second data points in the portion; and

generate an elevation map of the surface wherein the elevation of each portion of the surface is based on at least the relative elevation of the portion'"'"'s identified second data point.

11. The system of claim 10, wherein the plurality of portions correspond to cells of a 2D grid.

12. The system of claim 10, wherein the one or more computing devices are further configured to transfer the elevation to a vehicle in order to navigate the vehicle along a roadway.

13. The system of claim 10, wherein the one or more computing devices are further configured to filter the set of first data points in order to generate the set of second data points by removing outlier points by interpolating data.

14. The system of claim 10, wherein the one or more computing devices are further configured to filter the set of first data points in order to generate the set of second data points by removing outlier points based on a threshold deviation from an average elevation of the set of first data points.

15. The system of claim 11, wherein the one or more computing devices are further configured to filter the set of first data points for a particular portion of the plurality of portions in order to generate the set of second data points for the particular portion by generating an approximate data point for the particular portion based on data from a neighboring portion of the particular portion, where the set of first data points for the particular portion does not include any data points.

16. The system of claim 10, wherein the one or more computing devices are further configured to filter the set of first data points to generate the set of second data points by identifying two clusters of data points.

17. The system of claim 16, wherein the one or more computing devices are further configured to:

identify a second data point of the set of second data points associated with a lowest relative elevation for a higher relative cluster of the two clusters;

wherein the processor generates the elevation map based on the second data point of the set of second data points.

18. The system of claim 10, further comprising a vehicle.

19. A non-transitory, tangible computer-readable storage medium on which computer readable instructions of a program are stored, the instructions, when executed by one or more processors, cause the one or more processors to perform a method of generating an elevation map of a roadway, the method comprising:

receiving a plurality of data points via one or more sensors, each data point representing a position and elevation of a surface;

determining a set of first data points based on one or more positions of the plurality of data points;

filtering the set of first data points in order to generate a set of second data points;

determining a plurality of portions of the surface wherein the positions of a plurality of the second data points are located in each portion;

identifying, for each portion of the surface, a data point of the set of second data points associated with a lowest relative elevation of the set of second data points located in the portion; and

generating an elevation map of the roadway wherein the elevation of each portion is based on at least the identified data point of the set of second data points associated with the lowest relative elevation.

20. The non-transitory, tangible computer-readable storage medium of claim 19, wherein the set of first data points correspond to cells of a 2D grid.