Automatic occlusion detection in road network data

• US 10,552,689 B2
• Filed: 11/09/2017
• Issued: 02/04/2020
• Est. Priority Date: 11/09/2017
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Doria, David, Chen, Xin, Parker, Coby Spolin, Li, Zichen
• Primary Examiner(s): Chang, Jon
• Application Number:
  US15/808,277
• Publication Number:
  US 20190138823A1
• Time in Patent Office: 817 Days
• CPC Class Codes: G01S 17/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S17/46
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G01S 7/4808 Evaluating distance, position or velocity data
• CPC Class Codes: G05D 1/0231 using optical position detecting means position-fixing by using electromagnetic waves other than radio waves, e.g. optical position detecting means G01S5/16
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/521 from laser ranging, e.g. using interferometry; from the projection of structured light
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

The present embodiments provide for automatically detecting the location and severity of occluded regions within input data. A grid representation of a scene is generated from a data set, characterizing spaces of the grid representation as free, occupied, and hidden/occluded. The grid is bounded, and a connected component analysis is performed on the hidden space to identify the occluded regions.

Claims

1. A method of detecting an occlusion from point cloud data, the method comprising:

receiving, by a server from a data collection vehicle, point cloud data for a scene;

generating, by the server from the point cloud data, a grid representation of a region of interest in the scene, wherein the grid representation comprises free space, occupied space and hidden space;

identifying, by the server, an occlusion in the region of interest based on the hidden space of the grid representation, and

characterizing the occlusion based on a shape of the hidden space, the shape determined by connected component analysis of the hidden space.

2. The method of claim 1, wherein the region of interest is defined based on a traffic lane model.

3. The method of claim 1, wherein the free space corresponds to a location between a sensor location and a corresponding object location identified from the point cloud data, the occupied space corresponds to the object location identified from the point cloud data, and the hidden space corresponds to a location without point cloud data.

4. The method of claim 1, wherein the occlusion is characterized as a temporary occlusion or a permanent occlusion.

5. The method of claim 4, further comprising:

generating, by the server based on characterizing the occlusion as the temporary occlusion, a request for supplemental point cloud data for a location of the occlusion.

6. The method of claim 5, further comprising:

updating, by the server, map database data based on the occlusion.

7. The method of claim 6, further comprising:

providing, to an autonomous vehicle, the updated map database data for localizing the autonomous vehicle in the scene.

8. The method of claim 1, further comprising:

storing, by the server, the point cloud data in a spatial data structure.

9. An apparatus for detecting an occlusion from light detection and ranging (LIDAR) data, the apparatus comprising:

at least one LIDAR sensor;

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform;

receive, from the LIDAR sensor, LIDAR data for a region of interest;

assemble the LIDAR data as point cloud data in a spatial data structure;

generate a grid representation of the region of interest by evaluating the spatial data structure to characterize squares of the grid representation as a free square, an occupied square, or a hidden square;

detect an occlusion in the LIDAR data based on hidden squares of the grid representation based on a shape of the hidden squares, the shape determined by connected component analysis of the hidden squares; and

generate a localization model from the LIDAR data and the detected occlusion.

10. The apparatus of claim 9, wherein the spatial data structure is a probabilistic octree.

11. The apparatus of claim 10, wherein squares of the grid are characterized by tracing LIDAR rays from a sensor origin point to a corresponding end point.

12. The apparatus of claim 11, wherein the free square corresponds to a location between the sensor origin point and the corresponding end point, the occupied square corresponds to a location associated with the end point, and the hidden square corresponds to an untraced location.

13. A non-transitory computer readable medium including instructions that when executed by a processor, the processor is operable to perform:

receiving sensor data for a scene, the sensor data comprising an origin point and an end point;

generating, from the sensor data, a grid for the scene, wherein generating the grid comprises tracing a path from the origin point to the end point to identify free space, occupied space and hidden space;

detecting objects in the scene from the occupied space; and

identifying, from the hidden space, an occlusion comprising a false negative in the detected objects, wherein identifying the occlusion comprises determining a location of the occlusion and a severity of the occlusion.

14. The non-transitory computer readable medium of claim 13, wherein the false negative comprises missing sensor data a portion of the scene.

15. The non-transitory computer readable medium of claim 14, wherein the missing sensor data represents a temporary object obstructing the scene from the sensor.

16. The non-transitory computer readable medium of claim 13, wherein the severity comprises a characterization of the occlusion as a full occlusion or partial occlusion.

17. The non-transitory computer readable medium of claim 13, further comprising:

analyzing a shape of the occlusion to identify a source of the occlusion; and

updating, based on the shape of the occlusion, a localization model with;

additional sensor data for occlusion;

or

the identified false negative for the occlusion.

18. The non-transitory computer readable medium of claim 17, further comprising:

providing, to an autonomous vehicle, the localization model for localizing the autonomous vehicle in the scene.