Structure preserved point cloud simplification

Patent metadata

Field	Value
Publication number	US-9582939-B2
Application number	US-201514736476-A
Country	US
Kind code	B2
Filing date	Jun 11, 2015
Priority date	Jun 11, 2015
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

Systems, methods, and apparatuses are disclosed for simplifying a point cloud. A point cloud is received where the point cloud has a plurality of points, a global spatial structure, and a local point density. The processor calculates a set of pairwise distances for the plurality of points to at least one other point in the plurality of points. A first distance matrix is generated using the set of pairwise distances. The processor calculates a second pairwise distance set where the plurality of points have a weight and generates a second distance matrix based off the second pairwise distance set. A portion of the points in the second pairwise distance set are removed based on the weight. The processor performs a comparison of the two matrices using the comparison and the global spatial structure and the local point density, and generates a second point cloud based on the second distance matrix.

First claim

We claim:

1. A method comprising:
receiving, using a processor, a first point cloud distribution from a sensor configured to detect the surroundings of a vehicle, wherein the point cloud distribution includes a plurality of points, a global spatial structure and a local point density;
calculating, using the processor, a first pairwise distance set for the plurality of points to at least one other point in the plurality of points;
generating, using the processor, a first distance matrix, wherein the first distance matrix includes entries that correspond to the first pairwise distance set;
calculating, using the processor, a second pairwise distance set for the plurality of points to at least one other point in the plurality of points, wherein the plurality of points have a weight;
generating, using the processor, a second distance matrix, wherein the second distance matrix includes entries that correspond to the second pairwise distance set;
removing, using the processor, a portion of the points in the second pairwise distance set based on the weight of the at least one point in the plurality of points;
performing, using the processor, a comparison of the first distance matrix and the second distance matrix, wherein the comparison uses the global spatial structure and the local point density;
constructing, using the processor, a second point cloud distribution using the comparison and the second distance matrix; and
providing, using the processor, the second point cloud distribution to a navigation device.

2. The method of claim 1 , wherein the weight is one or zero.

3. The method of claim 1 , wherein the second point cloud distribution is provided when a result of the comparison is within a threshold.

4. The method of claim 1 , further comprising:
removing, using the processor, a second portion of the points in the second pairwise distance set based on one or more new weights for the plurality of points;
updating, using the processor, the second distance matrix; and
performing, using the processor, a second comparison of the first distance matrix and the second distance matrix with the second portion removed.

5. The method of claim 1 , wherein performing the comparison further comprises:
calculating a summation of the entries in the first distance matrix and second distance matrix.

6. The method of claim 1 , wherein performing the comparison further comprises:
performing, using the processor, a calculation including a summation of the entries in the first distance matrix and the second distance matrix;
identifying a first neighbor set for each point in the plurality of points, and a second neighbor set for the at least one point in the second pairwise distance set; and
adjusting the calculation by a ratio of the first neighbor set and the second neighbor set.

7. The method of claim 1 , further comprising:
normalizing the first distance matrix and the second distance matrix.

8. The method of claim 1 , wherein the portion removed includes at least half of the points in the second pairwise set.

9. The method of claim 1 , wherein the global spatial structure is an outline of the first point cloud distribution, and the local point density is a measure of the density of the plurality of points.

10. The method of claim 9 , wherein the comparison includes the global spatial structure being within a first predefined threshold and local point density being within a second predefined threshold.

11. The method of claim 10 , wherein if the global spatial structure and local point density are not within the first and second predefined threshold, further comprising:
removing, using the processor, a second portion of the points in the second pairwise distance set based on one or more new weights for the plurality of points;
updating, using the processor, the second distance matrix; and
performing, using the processor, a second comparison of the first distance matrix and the second distance matrix with the second portion removed.

12. An apparatus comprising:
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 a first point cloud from a sensor configured to detect the surroundings of a vehicle, wherein the first point cloud includes a plurality of points, a global structure and a local density;
calculate a first distance set for the plurality of points to at least one other point in the plurality of points;
generate, a first matrix, wherein the first matrix includes entries that correspond to the first distance set;
assign a weight to the at least one point in the plurality of points;
calculate a second distance set for the at least one point in the plurality of points to at least one other point in the plurality of points;
generate a second matrix, wherein the second matrix includes entries that correspond to the second distance set;
remove, a portion of the points in the second distance set based on the weight of the at least one point in the plurality of points;
perform a comparison of the first matrix and the second matrix, wherein the comparison uses the global structure and the local density;
construct a second point cloud using the comparison and the second matrix; and
output the second point cloud to a navigation device.

13. The apparatus of claim 12 , wherein the second matrix is provided if a result of the comparison is within a threshold, and if the result of the comparison is not within the threshold repeating the method until the comparison is within a threshold, further cause the apparatus to at least perform:
remove a second portion of the points in the second distance set based on one or more new weights for the plurality of points;
update the second matrix; and
perform a second comparison of the first matrix and the second matrix with the second portion removed.

14. The apparatus of claim 12 , wherein perform further comprises:
perform a calculation including a summation of all entries in the first matrix and the second matrix;
identify a first neighbor set for each point in the plurality of points, and a second neighbor set for the at least one point in the second distance set; and
adjust the calculation by a ratio of the first neighbor set and the second neighbor set.

15. The apparatus of claim 12 , wherein the comparison includes normalize the first matrix and second matrix.

16. The apparatus of claim 12 , wherein the portion removed includes at least half of the points in the second distance set, and wherein the comparison includes the global structure being within a first predefined threshold and local density being within a second predefined threshold.

17. The apparatus of claim 16 , wherein if the global structure and local density are not with the first and second predefined threshold causing the apparatus to:
remove a second portion of the points in the second distance set based on one or more new weights for the plurality of points;
update the second matrix; and
perform a second comparison of the first matrix and the second matrix with the second portion removed.

18. A non-transitory computer readable medium comprising instructions that when executed are operable to:
receive a first point cloud distribution from a sensor configured to detect the surroundings of a vehicle, wherein the first point cloud distribution includes a global spatial structure and a local point density;
calcula

Assignees

• Nokia Technologies Oy

Inventors

• Zhang Xi
• Chen Xin

Classifications

• G06V20/64 Primary

  Three-dimensional [3D] objects · CPC title

• G06T2207/10028

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

• G06K9/4604

  Physics · mapped topic

• G06T7/0051

  Physics · mapped topic

• G06K9/64

  Physics · mapped topic