Building elevation maps from laser data

• US 8,825,391 B1
• Filed: 08/04/2011
• Issued: 09/02/2014
• Est. Priority Date: 08/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Urmson, Christopher Paul, Chatham, Andrew, Dahlkamp, Hendrik, Montemerlo, Michael Steven, Zhu, Jiajun
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US13/198,199
• Time in Patent Office: 1,125 Days
• Field of Search: 701/1, 701/22, 701/23, 701/24, 701/25, 701/26, 701/27, 701/28, 701300-302, 701/400, 701/448, 701/450, 701/514, 701/523
• US Class Current: 701/448
• 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 for generating an elevation map of a roadway, the method comprising:

receiving sensor data, the sensor data including a plurality of data points, each of the plurality of data points representing a position and elevation of a particular location along the roadway;

generating, by a processor, a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;

generating a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;

filtering the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;

for each cell of the plurality of cells, identifying a data point of the second set of data points associated with a lowest relative elevation; and

generating an elevation map of the roadway based on the identified data points of the second sets of data points associated with the lowest relative elevations.

2. The method of claim 1, wherein each of the plurality of cells has the same dimensions.

3. The method of claim 1, wherein at least two cells of the plurality of cells include different dimensions.

4. The method of claim 1, further comprising transferring the elevation to a vehicle in order to navigate the vehicle along the roadway.

5. The method of claim 1, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes removing outlier points by interpolating data from a neighboring cell of the particular cell.

6. The method of claim 1, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes generating an approximate data point for the particular cell based on data from a neighboring cell of the particular cell, where the first set of data points for the particular cell does not include any data points.

7. The method of claim 1, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes filtering using an occlusion method.

8. The method of claim 1, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes identifying two clusters of data points for the particular cell.

9. The method of claim 8, further comprising:

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

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

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

memory storing sensor data, the sensor data including a plurality of data points, each data point of the plurality of data points representing a position and elevation of a particular location along the roadway; and

a processor, coupled to the memory and operable to;

access the stored sensor data;

generate a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;

generate a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;

filter the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;

for each cell of the plurality of cells, identify a data point of the second set of data points associated with a lowest relative elevation; and

generate the elevation map of the roadway based on the identified data points of the second sets of data points associated with the lowest relative elevations.

11. The device of claim 10, wherein the processor is further operable to transfer the elevation to a vehicle in order to navigate the vehicle along the roadway.

12. The device of claim 10, wherein the processor is further operable to filter the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell by removing outlier points by interpolating data from a neighboring cell of the particular cell.

13. The device of claim 10, wherein the processor is further operable to filter the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell by generating an approximate data point for the particular cell based on data from a neighboring cell of the particular cell, where the first set of data points for the particular cell does not include any data points.

14. The device of claim 10, wherein the processor is further operable to filter the first set of data points for a particular cell of the plurality of cells to generate the second set of data points for the particular cell by identifying two clusters of data points for the particular cell.

15. The device of claim 10, wherein the processor is further operable to:

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

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

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

receiving sensor data, the sensor data including a plurality of data points, each of the plurality of data points representing a position and elevation of a particular location along the roadway;

generating a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;

generating a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;

filtering the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;

for each cell of the plurality of cells, identifying a data point of the second set of data points associated with a lowest relative elevation; and

generating the elevation map of the roadway based on the identified data points of the second sets of data points associated with the lowest relative elevations.

17. The non-transitory, tangible computer-readable storage medium of claim 16, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes removing outlier points by interpolating data from a neighboring cell of the particular cell.

18. The non-transitory, tangible computer-readable storage medium of claim 16, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes generating an approximate data point for the particular cell based on data from a neighboring cell of the particular cell, where the first set of data points for the particular cell does not include any data points.

19. The non-transitory, tangible computer-readable storage medium of claim 16, wherein filtering the first set of data points for a particular cell of the plurality of cells in order to generate the second set of data points for the particular cell includes identifying two clusters of data points for the particular cell.

20. The non-transitory, tangible computer-readable storage medium of claim 16, wherein the method further comprises:

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

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

21. A vehicle comprising:

a braking system configured to decelerate the vehicle;

an acceleration system configured to accelerate the vehicle;

a steering system configured to change a direction of motion of the vehicle;

a processor configured to control the breaking, acceleration, and steering systems; and

memory coupled to the processor, the memory storing an elevation map, the elevation map being generated by;

receiving sensor data, the sensor data including a plurality of data points, each of the plurality of data points representing a position and elevation of a particular location along a roadway;

generating a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway;

generating a first set of data points for each cell of the plurality of cells based on the positions of the plurality of data points;

filtering the first set of data points for each cell of the plurality of cells in order to generate a second set of data points for each cell of the plurality of cells;

for each cell of the plurality of cells, identifying a data point of the second set of data points associated with a lowest relative elevation; and

generating the elevation map based on the identified data points of the second sets of data points associated with the lowest relative elevations; and

wherein the processor is operable to access the elevation map from the memory and use the elevation map to navigate the vehicle along a route by controlling one or more of the braking, acceleration, and steering systems.