Structure preserved point cloud simplification

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;

calculate a first pairwise distance set and a second pairwise distance set for the plurality of points to at least one other point in the plurality of points;

generate a first distance matrix, wherein the first distance matrix includes entries that correspond to the first pairwise distance set;

generate a second distance matrix, wherein the second distance matrix includes entries that correspond to the second pairwise distance set;

remove 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;

perform 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; and

construct a second point cloud distribution using the comparison and the second distance matrix.

19. The non-transitory computer readable medium of claim 18 , wherein the comparison further comprises:

perform a calculation, wherein the calculation includes a summation of all entries in the first distance matrix and the second distance 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 pairwise distance set; and

adjust the calculation by a ratio of the first neighbor set and the second neighbor set.

20. The non-transitory computer readable medium of claim 18 , wherein if the global spatial density and the local point density are not within a first and second predefined threshold, wherein the comparison further comprises:

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.