Real-time ground surface segmentation algorithm for sparse point clouds

Patent metadata

Field	Value
Publication number	US-11668798-B2
Application number	US-202016781708-A
Country	US
Kind code	B2
Filing date	Feb 4, 2020
Priority date	Nov 14, 2019
Publication date	Jun 6, 2023
Grant date	Jun 6, 2023

Abstract

Embodiments include a method for ground surface segmentation on sparse Light Detection And Ranging (LiDAR) point clouds comprising: reading a LiDAR point cloud from a LiDAR sensor, the LiDAR point cloud comprising data representing one or more objects in physical surroundings detected by the LiDAR sensor; voxelizing the LiDAR point cloud to produce a three-dimensional representation of each of the one or more objects; constructing a maximum height map from the three-dimensional representation of each of the one or more objects, the maximum height map comprising a two-dimensional mapping of spatial points representing each of the one or more objects; performing minimum filtering on the spatial points of the maximum height map; and classifying each spatial point as a ground point or a non-ground point based on the minimum filtering of each spatial point.

First claim

What is claimed is:

1. A method for ground surface segmentation on sparse Light Detection And Ranging (LiDAR) point clouds, the method comprising:
reading, by a navigation system, a LiDAR point cloud from a LiDAR sensor, the LiDAR point cloud comprising data representing one or more objects in physical surroundings detected by the LiDAR sensor;
voxelizing, by the navigation system, the LiDAR point cloud, wherein voxelizing the LiDAR point cloud produces a three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor;
constructing, by the navigation system, a maximum height map from the three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor, the maximum height map comprising a two-dimensional mapping of spatial points representing a maximum height value for each of the one or more objects in the physical surroundings detected by the LiDAR sensor, wherein the maximum height map is constructed based on a segmented estimate of a local ground height value without use of a planar ground representation;
performing, by the navigation system, minimum filtering on the spatial points of the maximum height map, wherein performing minimum filtering on the spatial points of the maximum height map comprises estimating the local ground height value at each spatial point, and wherein estimating the local ground height value at each spatial point comprises searching the two-dimensional mapping of spatial points for local neighbor spatial points within a rectangular region of the two-dimensional mapping of spatial points for a lowest maximum height value; and
classifying, by the navigation system, each spatial point as a ground point or a non-ground point based on the minimum filtering of each of the spatial points.

2. The method of claim 1 , wherein constructing the maximum height map comprises:
constructing a grid of coordinates comprising two-dimensional coordinates for each spatial point, the two-dimensional coordinates obtained from the three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor; and
storing the maximum height value for each spatial point based on the two-dimensional coordinates of the grid of coordinates.

3. The method of claim 1 , wherein the rectangular region comprises a bounding box for an assigned anchor point related to the spatial point.

4. The method of claim 1 , wherein classifying each spatial point as a ground point or a non-ground point based on the minimum filtering of each of the spatial points is based on the maximum height value for each spatial point and the estimated local ground height value for each spatial point.

5. The method of claim 1 , wherein the ground surface segmentation is performed without a planar ground representation.

6. The method of claim 1 , further comprising:
performing, by the navigation system, maximum filtering on the spatial points of the maximum height map; and
classifying, by the navigation system, at least one spatial point as a top of an object based on the maximum filtering of each of the spatial points.

7. The method of claim 6 , wherein performing maximum filtering on the spatial points of the maximum height map comprises searching the two-dimensional mapping of spatial points for local neighbor spatial points within a rectangular region of the two-dimensional mapping of spatial points for a highest maximum height value.

8. A navigation system comprising:
a processor; and
a memory coupled with and readable by the memory and storing therein a set of instructions which, when executed by the processor, causes the processor to perform ground surface segmentation on sparse Light Detection And Ranging (LiDAR) point clouds by:
reading a LiDAR point cloud from a LiDAR sensor, the LiDAR point cloud comprising data representing one or more objects in physical surroundings detected by the LiDAR sensor;
voxelizing the LiDAR point cloud, wherein voxelizing the LiDAR point cloud produces a three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor;
constructing a maximum height map from the three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor, the maximum height map comprising a two-dimensional mapping of spatial points representing a maximum height value for each of the one or more objects in the physical surroundings detected by the LiDAR sensor, wherein the maximum height map is constructed based on a segmented estimate of a local ground height value without use of a planar ground representation;
performing minimum filtering on the spatial points of the maximum height map, wherein performing minimum filtering on the spatial points of the maximum height map comprises estimating the local ground height value at each spatial point, and wherein estimating the local ground height value at each spatial point comprises searching the two-dimensional mapping of spatial points for local neighbor spatial points within a rectangular region of the two-dimensional mapping of spatial points for a lowest maximum height value; and
classifying each spatial point as a ground point or a non-ground point based on the minimum filtering of each of the spatial points.

9. The navigation system of claim 8 , wherein constructing the maximum height map comprises:
constructing a grid of coordinates comprising two-dimensional coordinates for each spatial point, the two-dimensional coordinates obtained from the three-dimensional representation of each of the one or more objects in the physical surroundings detected by the LiDAR sensor; and
storing the maximum height value for each spatial point based on the two-dimensional coordinates of the grid of coordinates.

10. The navigation system of claim 8 , wherein the rectangular region comprises a bounding box for an assigned anchor point related to the spatial point.

11. The navigation system of claim 8 , wherein classifying each spatial point as a ground point or a non-ground point based on the minimum filtering of each of the spatial points is based on the maximum height value for each spatial point and the estimated local ground height value for each spatial point.

12. The navigation system of claim 8 , wherein the ground surface segmentation is performed without a planar ground representation.

13. The navigation system of claim 8 , wherein the set of instructions further cause the processor to:
perform maximum filtering on the spatial points of the maximum height map; and
classify at least one spatial point as a top of an object based on the maximum filtering of each of the spatial points.

14. The navigation system of claim 13 , wherein performing maximum filtering on the spatial points of the maximum height map comprises searching the two-dimensional mapping of spatial points for local neighbor spatial points within a rectangular region of the two-dimensional mapping of spatial points for a highest maximum height value.

15. A vehicle comprising:
a Light Detection And Ranging (LiDAR) sensor;
a navigation system coupled with the LiDAR sensor and comprising a processor and a memory coupled with and readable by the processor and storing therein a set of instructions which, when executed by the processor, causes the processor to perform ground surface segmentation on sparse Light Detection And Ranging (LiDAR) point clouds by:
reading a LiDAR point cloud from a LiDAR sensor, the LiDAR point cloud comprising

Assignees

• Nio Technology Anhui Co Ltd

Inventors

• Kumar Arun C S
• Ahuja Disha
• Aithal Ashwath

Classifications

• G06V10/25

  Determination of region of interest [ROI] or a volume of interest [VOI] · CPC title

• G06V10/82

  using neural networks · CPC title

• G06F18/24

  Classification techniques · CPC title

• G01S17/89

  for mapping or imaging · CPC title

• G01S17/931

  of land vehicles · CPC title