ALIGNING 3D POINT CLOUDS USING LOOP CLOSURES

• US 20160379366A1
• Filed: 06/25/2015
• Published: 12/29/2016
• Est. Priority Date: 06/25/2015
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: SHAH, CHINTAN ANIL, BERCLAZ, JEROME FRANCOIS, HARVILLE, MICHAEL L., MATSUSHITA, YASUYUKI, SHIRATORI, TAKAAKI, LI, TAOYU, YOON, TAEHUN, SHILLER, STEPHEN EDWARD, PYLVAENAEINEN, TIMO P.
• Application Number:
  US14/749,876
• Publication Number:
  US 20160379366A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• 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: G06T 7/38 Registration of image sequences
• CPC Class Codes: G06T 7/50 Depth or shape recovery

Abstract

Systems, methods, and computer-readable storage media are provided for aligning three-dimensional point clouds that each includes data representing at least a portion of an area-of-interest. The area-of-interest is divided into multiple regions, each region having a closed-loop structure defined by a plurality of border segments, each border segment including a plurality of fragments. Point clouds representing the fragments that make up each closed-loop region are aligned with one another in a parallelized manner, for instance, utilizing a Simultaneous Generalized Iterative Closest Point (SGICP) technique, to create aligned point cloud regions. Aligned point cloud regions sharing a common border segment portion are aligned with one another to create a single, consistent, aligned point cloud having data that accurately represents the area-of-interest.

Claims

1. A method being performed by one or more computing devices including at least one processor, the method for aligning point clouds, the method comprising:

receiving a plurality of point clouds, each point cloud including data representative of at least a portion of an area-of-interest;

dividing the area-of-interest into multiple closed-loop regions each defined by a plurality of border segments, each border segment defining a distance between two nodes, wherein at least a first of the multiple closed-loop regions shares a common border segment portion with at least a second of the multiple closed-loop regions, wherein each border segment is comprised of a plurality of fragments, and wherein multiple point clouds of the plurality of point clouds represent each fragment;

for each of the plurality of fragments that comprises each of the plurality of border segments defining a first of the multiple closed-loop regions, aligning the representative multiple point clouds with one another to create a first aligned closed-loop region;

for each of the plurality of fragments that comprises each of the plurality of border segments defining a second of the multiple closed-loop regions, aligning the representative multiple point clouds with one another to create a second aligned closed-loop region; and

aligning the first aligned closed-loop region and the second aligned closed-loop region along the common border segment portion.

2. The method of claim 1, wherein the plurality of point clouds is received from at least one of a plurality of sensors and a plurality of point-capture-paths from individual sensors of the plurality of sensors.

3. The method of claim 2, wherein at least a portion of the plurality of sensors are LiDAR sensors.

4. The method of claim 2, wherein dividing the area-of-interest into a multiple closed-loop regions comprises utilizing an initial estimate of at least a portion of the point-capture-paths associated with each sensor.

5. The method of claim 4, wherein the initial estimate of at least a portion of the point-capture-paths associated with each sensor is derived from one or both of GPS and IMU data.

6. The method of claim 4, wherein aligning the first aligned closed-loop region with the second aligned closed-loop region along the common border segment portion includes constraining the alignment of the first and second aligned closed-loop regions with one or more high-confidence locations within the initial point-capture-path estimates.

7. The method of claim 1, wherein aligning the representative multiple point clouds for each of the plurality of fragments that comprises each of the plurality of border segments defining a first of the multiple closed-loop regions to create a first aligned closed-loop region and aligning the representative multiple point clouds for each of the plurality of fragments that comprises each of the plurality of border segments defining a second of the multiple closed-loop regions to create a second aligned closed-loop region comprises aligning the representative multiple point clouds for each of plurality of fragments that comprises the plurality of border segments defining the first and the second closed-loop regions utilizing a Simultaneous Generalized Iterative Closest Point technique.

8. A system for aligning three-dimensional point clouds that each include data representative of at least a portion of an area-of-interest, the system comprising:

a vehicle configured for moving through the area-of-interest;

a plurality of LiDAR sensors coupled with the vehicle; and

a point cloud alignment engine that;

receives a plurality of three-dimensional point clouds that each includes data representative of at least a portion of the area-of-interest;

divides the area-of-interest into a multiple closed-loop regions each defined by a plurality of border segments, each border segment defining a distance between two nodes, wherein each border segment is comprised of a plurality of fragments, and wherein multiple point clouds represent each fragment;

for each of the plurality of fragments that comprises each of the plurality of border segments defining a first of the multiple closed-loop regions, aligns the representative multiple point clouds with one another to create a first aligned closed-loop region;

for each of the plurality of fragments that comprises each of the plurality of border segments defining a second of the multiple closed-loop regions, aligns the representative multiple point clouds with one another to create a second aligned closed-loop region, wherein the first aligned closed-loop region and the second aligned closed-loop region share a common border segment portion; and

aligns the first aligned closed-loop region and the second aligned closed-loop region along the common border segment portion.

9. The system of claim 8, further comprising one or more GPS sensors coupled with the vehicle.

10. The system of claim 8, further comprising one or more IMU sensors coupled with the vehicle.

11. The system of claim 8, wherein the point cloud alignment engine divides the area-of-interest into multiple closed-loop regions, at least in part, by utilizing an initial estimate of point-capture-paths associated with one or more of the plurality of LiDAR sensors.

12. The system of claim 11, wherein the point cloud alignment engine further constrains the alignment of the first aligned closed-loop region and the second aligned closed-loop region with one or more high-confidence locations within the initial point-capture-path estimates.

13. The system of claim 8, wherein the point cloud alignment engine utilizes a Simultaneous Generalized Iterative Closest Point technique to create the first and second aligned closed-loop regions.

14. The system of claim 8, wherein the point cloud alignment engine aligns the first aligned closed-loop region and the second aligned closed-loop region according to a least squares optimization with closed form solution.

15. A method being performed by one or more computing devices including at least one processor, the method for aligning three-dimensional point clouds, the method comprising:

dividing an area-of-interest into multiple closed-loop regions each defined by a plurality of border segments, each border segment defining a distance between two nodes, wherein at least a first of the multiple closed-loop regions shares a common border segment portion with at least a second of the multiple closed-loop regions, wherein each border segment is comprised of a plurality of fragments, and wherein multiple point clouds of the plurality of point clouds represent each fragment;

aligning the representative multiple three-dimensional point clouds for each of the plurality of fragments that comprises each of the plurality of border segments defining each of the multiple closed-loop regions to create a plurality of aligned closed-loop regions within the area-of-interest; and

aligning the aligned closed-loop regions along the common border segment portion to form a single aligned three-dimensional point cloud representative of the area-of-interest according to a least squares optimization with closed form solution.

16. The method of claim 15, further comprising receiving each of the plurality of point clouds from at least one of a plurality of LiDAR sensors and a plurality of point-capture-paths from individual LiDAR sensors of the plurality of LiDAR sensors.

17. The method of claim 16, wherein dividing the area-of-interest into multiple closed-loop regions comprises utilizing an initial estimate of point-capture-paths associated with at least a portion of the plurality of LiDAR sensors.

18. The method of claim 17, wherein the initial estimate of the point-capture-paths associated with at least a portion of the LiDAR sensors are derived from one or both of GPS and IMU data.

19. The method of claim 17, wherein aligning the aligned closed-loop regions along the common boundary segment portion to form a single aligned three-dimensional point cloud includes constraining the alignment of the aligned closed-loop regions with one or more high-confidence locations within the initial point-capture-path estimates.

20. The method of claim 15, wherein aligning the representative multiple three-dimensional point clouds for each of the plurality of fragments that comprises each of the plurality of border segments defining each of the multiple closed-loop regions to create a plurality of aligned closed-loop regions within the area-of-interest comprises aligning the multiple three-dimensional point clouds within each closed-loop region utilizing a Simultaneous Generalized Iterative Closest Point technique.