EFFICIENT AND SCALABLE THREE-DIMENSIONAL POINT CLOUD SEGMENTATION FOR NAVIGATION IN AUTONOMOUS VEHICLES

• US 20190310378A1
• Filed: 04/04/2019
• Published: 10/10/2019
• Est. Priority Date: 04/05/2018
• Status: Active Grant

• Current Assignee: Apex.AI, Inc.
• Original Assignee: Apex.AI, Inc.
• Inventors: HO, Christopher
• Granted Patent: US 10,921,455 B2
• Time in Patent Office: Days
• CPC Class Codes: G01S 13/89 for mapping or imaging
• CPC Class Codes: G01S 13/931 of land vehicles
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G01S 2013/9318 Controlling the steering
• CPC Class Codes: G01S 2013/93185 Controlling the brakes
• CPC Class Codes: G01S 2013/9319 Controlling the accelerator
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• 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/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling

Abstract

Efficient and scalable three-dimensional point cloud segmentation. In an embodiment, a three-dimensional point cloud is segmented by adding points to a spatial hash. For each unseen point, a cluster is generated, the unseen point is added to the cluster and marked as seen, and, for each point that is added to the cluster, the point is set as a reference, a reference threshold metric is computed, all unseen neighbors are identified based on the reference threshold metric, and, for each identified unseen neighbor, the unseen neighbor is marked as seen, a neighbor threshold metric is computed, and the neighbor is added or not added to the cluster based on the neighbor threshold metric. When the cluster reaches a threshold size, it may be added to a cluster list. Objects may be identified based on the cluster list and used to control autonomous system(s).

Claims

1. A method comprising using at least one hardware processor to:

receive data from one or more sensors;

generate a three-dimensional point cloud from the data received from the one or more sensors;

segment the three-dimensional point cloud using a clustering algorithm by

adding points from the three-dimensional point cloud to a spatial hash,

for each unseen point in the three-dimensional point cloud,

generating a new cluster,

adding the unseen point to the cluster,

marking the unseen point as seen, and,

for each point that is added to the cluster,

setting the point as a reference point,

computing a reference threshold metric for the reference point,

identifying all unseen neighbor points to the reference point in the spatial hash, based on the reference threshold metric, and,

for each identified unseen neighbor point to the reference point,

 

marking the unseen neighbor point as seen,

 

computing a neighbor threshold metric for the neighbor point,

 

determining whether or not the neighbor point should be added to the cluster based on the neighbor threshold metric, and,

 

when the neighbor point is determined to be added to the cluster, adding the neighbor point to the cluster, and,

when a size of the cluster reaches a threshold, adding the cluster to a cluster list,

identify one or more objects based on the cluster list; and

control one or more autonomous systems based on the identified one or more objects.

2. The method of claim 1, wherein the method further comprises using the at least one hardware processor to, prior to segmenting the three-dimensional point, remove points outside a predefined range from the three-dimensional point cloud.

3. The method of claim 2, wherein each point comprises an x, y, and z coordinate, wherein the x and y coordinates represent a horizontal plane, wherein the z coordinate represents a vertical axis, and wherein removing points outside a predefined range comprises removing all points that have a z coordinate that has a value outside a predefined range of values.

4. The method of claim 1, wherein the method further comprises using the at least one hardware processor to, prior to segmenting the three-dimensional point, remove ground points from the three-dimensional point cloud.

5. The method of claim 1, wherein adding points from the three-dimensional point cloud to the spatial hash comprises, for each point in the three-dimensional point cloud:

quantizing coordinates of the point;

computing a bin identifier for the point;

generating a node that represents the point;

determining whether or not a list of nodes is associated with the computed bin identifier in an associative mapping;

when a list of nodes is determined to be associated with the computed bin identifier in the associative mapping, adding the generated node to the list of nodes associated with the computed bin identifier; and

,

when a list of nodes is not determined to be associated with the computed bin identifier in the associative mapping, adding a new list to the associative mapping in association with the computed bin identifier, and adding the generated node to the new list.

6. The method of claim 1, wherein identifying all unseen neighbor points to the reference point in the spatial hash, based on the reference threshold metric, comprises:

quantizing coordinates of the reference point;

quantizing the reference threshold metric into a distance metric;

generating an overestimated bin set of bins that are within the distance metric from the quantized coordinates of the reference point; and

,

for each bin in the overestimated bin set,

determining whether or not a best distance of the bin from a reference bin, comprising the reference point, is less than the distance metric, and,

when the best distance of the bin from the reference bin is determined to be less than the distance metric, for each point in the bin,

determining whether or not a distance between the point in the bin and the reference point is less than the reference threshold metric, and,

when the distance between the point in the bin and the reference point is determined to be less than the reference threshold metric, identifying the point in the bin as a neighbor point to the reference point.

7. The method of claim 1, wherein the one or more sensors comprise a plurality of sensors.

8. The method of claim 1, wherein the one or more sensors comprise a light detection and ranging (Lidar) sensor.

9. The method of claim 1, wherein the one or more autonomous systems are comprised in a vehicle.

10. The method of claim 9, wherein the one or more autonomous systems comprise a braking system for applying brakes to one or more wheels of the vehicle.

11. The method of claim 9, wherein the one or more autonomous systems comprise a steering system for steering one or more wheels of the vehicle.

12. The method of claim 9, wherein the one or more autonomous systems comprise an acceleration system for throttling an engine of the vehicle.

13. The method of claim 1, wherein the one or more autonomous systems are comprised in a robot.

14. A system comprising:

at least one hardware processor; and

one or more software modules that are configured to, when executed by the at least one hardware processor,

receive data from one or more sensors,

generate a three-dimensional point cloud from the data received from the one or more sensors,

segment the three-dimensional point cloud using a clustering algorithm by

adding points from the three-dimensional point cloud to a spatial hash,

for each unseen point in the three-dimensional point cloud,

generating a new cluster,

adding the unseen point to the cluster,

marking the unseen point as seen, and,

for each point that is added to the cluster,

 

setting the point as a reference point,

 

computing a reference threshold metric for the reference point,

 

identifying all unseen neighbor points to the reference point in the spatial hash, based on the reference threshold metric, and,

 

for each identified unseen neighbor point to the reference point,

 

 

marking the unseen neighbor point as seen,

 

 

computing a neighbor threshold metric for the neighbor point,

 

 

determining whether or not the neighbor point should be added to the cluster based on the neighbor threshold metric, and,

 

 

when the neighbor point is determined to be added to the cluster, adding the neighbor point to the cluster, and,

when a size of the cluster reaches a threshold, adding the cluster to a cluster list,

identify one or more objects based on the cluster list, and

control one or more autonomous systems based on the identified one or more objects.

15. A non-transitory computer-readable medium having instructions stored therein, wherein the instructions, when executed by a processor, cause the processor to:

receive data from one or more sensors;

generate a three-dimensional point cloud from the data received from the one or more sensors;

segment the three-dimensional point cloud using a clustering algorithm by

adding points from the three-dimensional point cloud to a spatial hash,

for each unseen point in the three-dimensional point cloud,

generating a new cluster,

adding the unseen point to the cluster,

marking the unseen point as seen, and,

for each point that is added to the cluster,

setting the point as a reference point,

computing a reference threshold metric for the reference point,

identifying all unseen neighbor points to the reference point in the spatial hash, based on the reference threshold metric, and,

for each identified unseen neighbor point to the reference point,

 

marking the unseen neighbor point as seen,

 

computing a neighbor threshold metric for the neighbor point,

 

determining whether or not the neighbor point should be added to the cluster based on the neighbor threshold metric, and,

 

when the neighbor point is determined to be added to the cluster, adding the neighbor point to the cluster, and,

when a size of the cluster reaches a threshold, adding the cluster to a cluster list,

identify one or more objects based on the cluster list; and

control one or more autonomous systems based on the identified one or more objects.