Non-Rigid Registration for Large-Scale Space-Time 3D Point Cloud Alignment

• US 20170046840A1
• Filed: 08/11/2015
• Published: 02/16/2017
• Est. Priority Date: 08/11/2015
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Technologies Oy (Nokia Corporation)
• Inventors: Chen, Xin, Yang, Ruigang
• Granted Patent: US 9,760,996 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30248 Vehicle exterior or interior
• CPC Class Codes: G06T 3/14 Transformations for image registration, e.g. adjusting or mapping for alignment of images
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G06V 20/56 exterior to a vehicle by using sensors mounted on the vehicle
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

Point cloud data sets representing overlapping physical areas are received. Surface feature points are extracted from the point cloud data sets and coordinates are determined for each point of the point cloud data sets. The point cloud data sets are aligned based on matching surface feature points between the point cloud data sets. Matched surface feature points are moved toward the coordinates of corresponding matched surface feature points and the remaining points are moved based on the moved matched surface feature points and the determined coordinates for each point.

Claims

1. A method comprising:

receiving an anchor point cloud data set and at least one corresponding point cloud data set, wherein at least a portion of the anchor point cloud data set and at least a portion of the corresponding point cloud data set represent the same physical surface;

extracting a plurality of surface feature points from the anchor point cloud data set and from the at least one corresponding point cloud data set;

determining coordinates for each point of the anchor point cloud data set and the at least one corresponding point cloud data set;

matching surface feature points of the plurality of surface feature points between the anchor point cloud data set and the at least one corresponding point cloud data set;

aligning the at least one corresponding point cloud data set to the anchor point cloud data set based on the matched surface feature points between the anchor point cloud data set and the at least one corresponding point cloud data set;

moving matched surface feature points of the corresponding point cloud data set towards the determined coordinates of the matched surface feature points of the anchor point cloud data set; and

moving remaining points of the at least one corresponding point cloud data set based on the moved matched surface feature points and the determined coordinates for each remaining point.

2. The method of claim 1, the method further comprising:

dividing the aligned at least one corresponding point cloud data set and the anchor point cloud data set into a plurality of point cloud data set portions, wherein each point cloud data set portion overlaps with at least one other point cloud data set portion.

3. The method of claim 2, wherein each point cloud data set portion of the plurality of point cloud data set portions includes a portion of the anchor point cloud data set and a related portion of the at least one corresponding point cloud data set.

4. The method of claim 2, the method further comprising:

merging the plurality of point cloud data set portions into a single point cloud data set including each moved surface feature points and each moved remaining point.

5. The method of claim 4, further comprising:

determining navigational directions based on the merged single point cloud data set; and

providing the determined navigational directions to an autonomous vehicle.

6. The method of claim 2, wherein the divided plurality of overlapping point cloud data set portions contain substantially uniform divisions based on a number of points.

7. The method of claim 2, wherein the divided overlapping point cloud data set portions are based on a density of surface feature points.

8. The method of claim 1, wherein determining coordinates for each point further comprises is the difference between a mean value neighboring points and each point.

9. The method of claim 1, wherein the extracted surface feature points represent corners in the physical area.

10. The method of claim 1, wherein aligning the plurality of point cloud data scans based on matching surface feature points is based on quadratic energy functional minimization.

11. The method of claim 1, wherein the determined coordinates are based on a location of neighboring points.

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 an anchor point cloud data set and at least one corresponding point cloud data set, wherein at least a portion of the anchor point cloud data set and at least a portion of the corresponding point cloud data set represent the same physical surface;

extract a plurality of surface feature points from the anchor point cloud data set and from the at least one corresponding point cloud data set;

determine coordinates for each point of the anchor point cloud data set and the at least one corresponding point cloud data set;

match surface feature points of the plurality of surface feature points between the anchor point cloud data set and the at least one corresponding point cloud data set;

align the at least one corresponding point cloud data set to the anchor point cloud data set based on the matched surface feature points between the anchor point cloud data set and the at least one corresponding point cloud data set;

divide the aligned at least one corresponding point cloud data set and the anchor point cloud data set into a plurality of point cloud data set portions, wherein each point cloud data set portion overlaps with at least one other point cloud data set portion;

for each point cloud data set portion, move matched surface feature points of the corresponding point cloud data set toward the determined coordinates of the matched surface feature points of the anchor point cloud data set; and

for each point cloud data set portion, move the remaining points of the at least one corresponding point cloud data set based on the moved matched surface feature points and the determined coordinates for each remaining point.

13. The apparatus of claim 12, wherein each point cloud data set portion of the plurality of point cloud data set portions includes a portion of the anchor point cloud data set and a related portion of the at least one corresponding point cloud data set.

14. The apparatus of claim 12, 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:

merge the plurality of point cloud data set portions into a single point cloud data including each moved surface feature points and each moved remaining point.

15. The apparatus of claim 12, wherein the divided plurality of overlapping point cloud data set portions contain substantially uniform divisions based on a number of points.

16. The apparatus of claim 12, wherein the divided plurality of overlapping point cloud data set portions are based on a density of surface feature points.

17. The apparatus of claim 12, wherein aligning the plurality of point cloud data scans based on matching surface feature points is based on quadratic energy functional minimization.

18. The apparatus of claim 12, wherein the determined coordinates are based on a location of neighboring points.

19. A non-transitory computer readable medium including instructions that when executed are operable to:

receive a first point cloud and a second point cloud;

extract a plurality of surface feature points from the first point cloud and from the second point cloud;

match surface feature points of the plurality of surface feature points between the first point cloud and the second point cloud;

align the second point cloud to the first point cloud based on the matched surface feature points;

move matched surface feature points of the second point cloud towards the matched surface feature points of the first point cloud; and

move the remaining points of the second point cloud based on the moved matched surface feature points.

20. The non-transitory computer readable medium of claim 19, further comprising instructions that when executed are operable to:

determine coordinates for each point of the first point cloud and the second point cloud wherein the moved remaining points of the second point cloud are further based on the determined coordinates.