Removing extraneous objects from maps

• US 8,565,958 B1
• Filed: 06/02/2011
• Issued: 10/22/2013
• Est. Priority Date: 06/02/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Montemerlo, Michael Steven, Burnette, Donald Jason, Chatham, Andrew, Egnor, Daniel Trawick
• Primary Examiner(s): Trammell, James
• Assistant Examiner(s): TESTARDI, DAVID A
• Application Number:
  US13/151,461
• Time in Patent Office: 873 Days
• Field of Search: 701/25, 701/28, 701/23
• US Class Current: 701/25
• 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/106 using electronic means

Abstract

Aspects of the present disclosure relate generally to safe and effective use of autonomous vehicles. More specifically, laser data including locations, intensities, and elevation data may be collected along a roadway in order to generate a 3D map of the roadway. In order to remove extraneous objects such as moving vehicles from the 3D map, a 2D grid of the roadway may be generated. The grid may include a plurality of cells, each representing an area of the roadway. The collected data may be sorted into the grid based on location and then evaluated to identify the lowest elevation of the cell. All data points above some threshold distance above this lowest elevation may be removed. The resulting data points may be used to generate a 3D map of the roadway which excludes the extraneous objects.

Claims

1. A method for generating a 3D map of a roadway, the method comprising:

receiving sensor data collected by a sensor of a vehicle, the sensor data including a plurality of data points, each data point representing a location 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 and having particular dimensions, wherein the processor generates the particular dimensions for each cell of the plurality of cells based on an absolute geographic location of the vehicle defined at least by the geographic latitude of the vehicle when the sensor data was collected;

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

for each particular cell of the plurality of cells, identifying a data point of the first set associated with a lowest relative elevation;

generating a second set of data points for each cell of the plurality of cells based on the lowest relative elevation; and

generating the 3D map of the roadway based on the second set.

2. The method of claim 1, further comprising transferring the 3D map to an autonomous vehicle in order to navigate the vehicle along the roadway.

3. The method of claim 1, wherein generating the second set includes removing any data points exceeding a threshold distance above the lowest elevation from the first set for the particular cell.

4. The method of claim 3, wherein the threshold distance is a fixed value for each cell of the plurality of cells.

5. The method of claim 3, wherein the threshold distance is based on the elevations of the data points of the first set.

6. The method of claim 3, further comprising determining the threshold distance based on an accuracy of the sensor.

7. The method of claim 1, wherein generating the second set is further based on a threshold distance above the lowest relative elevation for each particular cell of the plurality of cells.

8. The method of claim 1, wherein the sensor data includes data collected from moving objects along the roadway, and the generated 3D map of the roadway does not include the data collected from the moving objects.

9. The method of claim 1, wherein the particular dimensions for the area of each cell of the plurality of cells are generated by the processor further based on a map projection over the 2D grid.

10. The method of claim 1, further comprising determining, for each particular cell the plurality of cells, a threshold distance for the particular cell, and wherein generating the second set includes removing any data points exceeding the threshold distance for the particular cell above the lowest elevation from the first set for the particular cell.

11. The method of claim 10, wherein the threshold distances are further determined based on a mean elevation difference between the lowest relative elevation and the elevations of the first set of data points for that given cell.

12. A device for generating a 3D map of a roadway, the device comprising:

memory for storing received sensor data collected by a sensor of a vehicle, the sensor data including a plurality of data points, each data point representing a location and elevation of a particular location along the roadway;

a processor coupled to the memory, the processor being operable to;

generate a 2D grid of the roadway, the 2D grid including a plurality of cells, each cell representing an area of the roadway and having particular dimensions, wherein generating the particular dimensions for the area of each cell of the plurality of cells is based on an absolute geographic location of the vehicle defined at least by the geographic latitude of the vehicle when the sensor data was collected;

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

for each particular cell of the plurality of cells, identify a data point of the first set associated with a lowest relative elevation;

generate a second set of data points for each cell of the plurality of cells based on the lowest relative elevation; and

generate the 3D map of the roadway based on the second set.

13. The device of claim 12, wherein the processor is further operable to transfer the 3D map to an autonomous vehicle in order to navigate the vehicle along the roadway.

14. The device of claim 12, wherein the processor generates the second set by removing any data points exceeding a threshold distance above the lowest elevation from the first set for the particular cell.

15. The device of claim 14, wherein the threshold distance is a fixed value for each cell of the plurality of cells.

16. The device of claim 14, wherein the threshold distance is based on the elevations of the data points of the first set.

17. The device of claim 12, wherein the processor is further operable to generate the second set based on a threshold distance above the lowest relative elevation for each particular cell of the plurality of cells.

18. The device of claim 12, wherein the sensor data includes data collected from moving objects along the roadway, and the generated 3D map of the roadway does not include the data collected from the moving objects.

19. A non-transitory 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 a 3D map of a roadway, the method comprising:

receiving sensor data collected by a sensor of a vehicle, the sensor data including a plurality of data points, each data point representing a location 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 and having particular dimensions, wherein generating the particular dimensions for the area of each cell of the plurality of cells is based on an absolute geographic location of the vehicle defined at least by the geographic latitude of the vehicle when the sensor data was collected;

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

for each particular cell of the plurality of cells, identifying a data point of the first set associated with a lowest relative elevation;

generating a second set of data points for each cell of the plurality of cells based on the lowest relative elevation; and

generating the 3D map of the roadway based on the second set.

20. The non-transitory computer-readable storage medium of claim 19, wherein the method further comprises generating the second set by removing any data points exceeding a threshold distance above the lowest elevation from the first set for the particular cell.

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 the direction of motion of the vehicle;

a processor coupled to the braking, acceleration, and steering systems;

and

memory coupled to the processor, the memory storing a 3D map of a roadway, the 3D map being generated by;

receiving sensor data, the sensor data including a plurality of data points, each data point representing a location 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 and having particular dimensions, wherein generating the particular dimensions for the area of each cell of the plurality of cells is based on an absolute geographic location of the vehicle defined at least by the geographic latitude of the vehicle when the sensor data was collected;

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

for each particular cell of the plurality of cells, identifying a data point of the first set associated with a lowest relative elevation;

generating a second set of data points for each cell of the plurality of cells based on the lowest relative elevation; and

generating the 3D map of the roadway based on the second set; and

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