Apparatus and method for efficient point cloud feature extraction and segmentation framework

Patent metadata

Field	Value
Publication number	US-11567207-B2
Application number	US-202016943991-A
Country	US
Kind code	B2
Filing date	Jul 30, 2020
Priority date	Aug 16, 2019
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

A computer implemented scheme for a light detection and ranging (LIDAR) system where point cloud feature extraction and segmentation by efficiently is achieved by: (1) data structuring; (2) edge detection; and (3) region growing.

First claim

What is claimed is:

1. A non-transitory machine-readable storage media having instructions stored thereon, that when executed, cause one or more processors to perform an operation for a LIDAR system where point cloud feature extraction and segmentation is performed, the operation comprising:
receiving scan pattern information and point cloud data from the LIDAR system, wherein the scan pattern information and point cloud data are associated with a physical object;
generating a scan pattern grid from the scan pattern information and point cloud data;
detecting one or more silhouette edges using the scan pattern grid and the point cloud data;
detecting one or more intersection edges using the scan pattern grid and the point cloud data; and
growing a region based on the detected one or more silhouette edges and the one or more intersection edge,

wherein detecting the one or more intersection edges comprises:
generating a mesh around a point, which is not a silhouette edge point, of the scan pattern grid with neighbor points forming shared edges between regions of the mesh; and
computing normal gradient across an individual shared edge to determine whether the point is lying on an intersection edge of a smooth surface.

2. The non-transitory machine-readable storage media of claim 1 , wherein the scan pattern grid is a 2-D grid structure having cells organized in rows and columns, wherein an individual row corresponds to a vertical angle of a scan from a scanner of the LIDAR system, and wherein an individual column corresponds to a horizontal angle from the scanner of the LIDAR system.

3. The non-transitory machine-readable storage media of claim 1 , wherein the LIDAR system is a mobile LIDAR system, wherein the scan pattern grid is a 2-D grid structure having cells organized in rows and columns, wherein an individual row corresponds to a time of a scan from a scanner of the LIDAR system, and wherein an individual column corresponds to a scan angle from the scanner of the LIDAR system.

4. The non-transitory machine-readable storage media of claim 2 , wherein an individual cell of the scan pattern grid represents a laser pulse from the scanner, wherein the individual cell includes information of a return point, and wherein the information of the return point includes scan coordinates, color, and intensity.

5. The non-transitory machine-readable storage media of claim 1 , wherein the one or more silhouette edges comprises points lying on an edge between an object scanned by the LIDAR system and a shadow of the object.

6. The non-transitory machine-readable storage media of claim 1 , wherein detecting the one or more silhouette edges comprises:
determining, from the scan pattern grid, points with no return; and
identifying points in the scan pattern grid that neighbor the points with no return as silhouette edge points, wherein the silhouette edge points form the one or more silhouette edges.

7. The non-transitory machine-readable storage media of claim 1 , wherein detecting the one or more silhouette edges comprises:
determining mixed points, between two objects, from the scan pattern grid;
distinguishing silhouette edge points of the two objects from the mixed points by determining whether an incidence angle associated with a point in the scan pattern grid is on one of the two objects;
comparing the incidence angle, associated with a point, against a threshold;
identifying the point as a silhouette edge point if the incidence angle exceeds the threshold, wherein the silhouette edge point forms the one or more silhouette edges; and
identifying the point as a mixed point if the incidence angle is below the threshold.

8. The non-transitory machine-readable storage media of claim 1 , wherein the one or more intersection edges intersect two or more smooth surfaces.

9. The non-transitory machine-readable storage media of claim 1 , wherein detecting the one or more intersection edges is independent of a normal vector at each point of the scan pattern grid.

10. The non-transitory machine-readable storage media of claim 1 , wherein the mesh is a triangular mesh around the point, and wherein the regions of the mesh are triangles of the triangular mesh.

11. The non-transitory machine-readable storage media of claim 10 , wherein detecting one or more intersection edges comprises comparing a maximum normal gradient, from among the computed normal gradient across each shared edge, with a threshold of maximum normal gradient.

12. The non-transitory machine-readable storage media of claim 1 , wherein the scan pattern grid is a first scan pattern grid, wherein growing the region comprises:
analyzing points in the first scan pattern grid and a second scan pattern grid; and
generating clusters of homogeneous points continuous in space.

13. A system comprising:
a memory;
a processor coupled to the memory; and
a communication interface coupled to the processor, wherein the processor is to:
receive scan pattern information and point cloud data from a LIDAR system, wherein the scan pattern information and point cloud data are associated with a physical object;
generate a scan pattern grid from the scan pattern information and point cloud data;
detect one or more silhouette edges using the scan pattern grid and the point cloud data;
detect one or more intersection edges using the scan pattern grid and the point cloud data; and
grow a region based on the detected one or more silhouette edges and the one or more intersection edges,

wherein to detect the one or more intersection edges, the processor is to:
generate a mesh around a point, which is not a silhouette edge point, of the scan pattern grid with neighbor points forming shared edges between regions of the mesh; and
compute normal gradient across an individual shared edge to determine whether the point is lying on an intersection edge of a smooth surface.

14. The system of claim 13 , wherein the scan pattern grid is a 2-D grid structure having cells organized in rows and columns, wherein an individual row corresponds to a vertical angle of a scan from a scanner of the LIDAR system, and wherein an individual column corresponds to a horizontal angle from of the scan from the scanner of the LIDAR system.

15. The system of claim 13 , wherein the LIDAR system is a mobile LIDAR system, wherein the scan pattern grid is a 2-D grid structure having cells organized in rows and columns, wherein an individual row corresponds to a time of a scan from a scanner of the LIDAR system, and wherein an individual column corresponds to a scan angle from the scanner of the LIDAR system.

16. The system of claim 15 , wherein an individual cell of the scan pattern grid represents a laser pulse from the scanner, wherein the individual cell includes information of a return point, and wherein the information of the return point includes scan coordinates, color, and intensity.

17. The system of claim 13 , wherein the one or more silhouette edges comprises points lying on an edge between an object scanned by the LIDAR system and a shadow of the object, wherein to detect the one or more silhouette edges the processor is to:
determine, from the scan pattern grid, points with no return; and
identify points in the scan pattern grid points that neighbor the points with no return as a silhouette edge points, wherein the silhouette edge points form the one or more silhouette edges.

18. The system of claim 13 , wherein to detect the one or more silhouette edges the processor is to:
determine mixed points, between two object

Assignees

• Univ Oregon State

Inventors

• Che Erzhuo
• Olsen Michael

Classifications

• G01S7/4804

  Auxiliary means for detecting or identifying lidar signals or the like, e.g. laser illuminators · CPC title

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title

• G06T7/187

  involving region growing; involving region merging; involving connected component labelling · CPC title

• G06T7/13

  Edge detection · CPC title

• G06T7/11

  Region-based segmentation · CPC title