Aligning 3d point clouds using loop closures

Patent metadata

Field	Value
Publication number	US-2016379366-A1
Application number	US-201514749876-A
Country	US
Kind code	A1
Filing date	Jun 25, 2015
Priority date	Jun 25, 2015
Publication date	Dec 29, 2016
Grant date	—

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.

First claim

What is claimed is:

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 clos

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Shah Chintan Anil
• Berclaz Jerome Francois
• Harville Michael L
• Matsushita Yasuyuki
• Shiratori Takaaki
• Li Taoyu
• Yoon Taehun
• Shiller Stephen Edward
• Pylvaenaeinen Timo P

Classifications

• G06T7/0051

  Physics · mapped topic

• G06T7/0028 Primary

  Physics · mapped topic

• G06T2207/10028

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

• G06T7/33 Primary

  using feature-based methods · CPC title

• G06T11/60

  Creating or editing images; Combining images with text · CPC title