Three-dimensional mapping of an environment

1. A method of constructing a three-dimensional map of an environment, comprising:

by a laser scanner, moving about an environment and collecting scan line data from a plurality of scans of the environment, wherein each of the scans comprises one or more scan lines, each returning a data value indicating a distance between the laser scanner and a point on a surface of a structure in the environment;

by at least one other sensor, moving about the environment with the laser scanner and collecting additional sensor data corresponding to the environment; and

by a processor:

obtaining the scan line data from the laser scanner,

extracting one or more feature points from the scan line data,

developing a laser scanner-based odometry from the feature points by:

for each instance of the scans of the laser scanner, identifying a window that comprises scan lines from one or more scans occurring immediately before or after the instance of the scan,

identifying a plurality of matching points from the one or more feature points extracted from the scan line data corresponding to one or more scans occurring immediately before or after the instance of the scan;

adjusting the number of matching points based on a distance of the laser scanner to each of the plurality of matching points, and

estimating a change in position of the laser scanner based on the adjusted number of matching points,

obtaining the additional sensor data from the at least one other sensor, and developing an additional odometry of the environment from the additional sensor data,

performing sensor fusion to supplement the laser scanner-based odometry with the additional odometry to develop a three-dimensional map of the environment, and

saving the three-dimensional map to a memory device.

2. The method of claim 1 , wherein developing the laser scanner-based odometry from the scan line data comprises using an iterative closest point (ICP) algorithm to estimate the change in position of the laser scanner by:

using an Extended Kalman Filter (EKF) to estimate the change in position of the laser scanner based on the adjusted number of matching points.

3. The method of claim 1 , wherein developing the three-dimensional map of the environment further comprises performing map registration through a global registration framework.

4. The method of claim 1 , wherein identifying the plurality of matching points from the one or more feature points comprises, for each feature point:

extracting a feature descriptor for the feature point; and

determining whether the feature point corresponds to a landmark by matching the feature point to a point of a collection of feature points based on an Euclidian distance therebetween and the feature descriptor of the point.

5. The method of claim 4 , wherein the feature descriptor comprises one or more LiDAR based features.

6. The method of claim 1 , wherein identifying the plurality of matching points comprises:

evaluating a curvature of each of the one or more feature points to determine whether the feature point is beyond a corner point; and

excluding the point from being a matching point if the feature point is determined to be beyond a corner point.

7. The method of claim 1 , wherein the at least one other sensor comprises a camera, and the method further comprises obtaining a sequence of images from the camera;

wherein:

the additional odometry is a camera odometry; and

developing the additional odometry comprises identifying a plurality of matching points by finding one or more additional feature points in the sequence of images within the identified window.

8. The method of claim 7 , further comprises determining a scale for scaling the camera odometry by:

using a depth registration between the scan line data from the laser scanner and the sequence of images from the camera; or

using data obtained from an inertial measurement unit (IMU).

9. The method of claim 7 , wherein identifying the plurality of matching points in the camera odometry comprises, for each of the one or more additional feature points:

extracting a feature descriptor for the additional feature point; and

determining whether the additional feature point corresponds to a landmark by matching the additional feature point to a point of a collection of feature points based on an Euclidian distance therebetween and the feature descriptor of the point.

10. The method of claim 9 , wherein the feature descriptor comprises one or more image based features.

11. The method of claim 1 , wherein developing the laser scanner-based odometry from the scan line data using the iterative closest point (ICP) algorithm comprises, for each instance of the scans from the laser scanner:

obtaining a first set of points from the instance of the scan and a second set of points from one or more previous scans of the laser scanner;

using the first and second set of points to estimate a first change in position of the laser scanner;

obtaining a third set of points comprising a number of most recent points from the laser scanner;

determining the laser scanner-based odometry based on the estimated first change in position and the third set of points; and

optimizing the odometry using a graph optimization process.

12. The method of claim 11 , where the graph optimization process comprises a general graph optimization (G2O) or Gauss-Schneider-based graph.

13. A system for constructing a three-dimensional map of an environment, comprising:

a laser scanner movable about an environment and configured to collect scan line data from a plurality of scans of the environment, wherein each of the scans comprises one or more scan lines, each returning a data value indicating a distance between the laser scanner and a point on a surface of a structure in the environment;

at least one other sensor movable about the environment with the laser scanner and configured collect additional sensor data corresponding to the environment;

a processor; and

a non-transitory computer-readable storage medium containing programming instructions configured to cause the processor to:

obtain the scan line data from the laser scanner,

extract one or more feature points from the scan line data,

develop a laser scanner-based odometry from the feature points by:

for each instance of the scans of the laser scanner, identifying a window that comprises scan lines from one or more scans occurring immediately before or after the instance of the scan,

identifying a plurality of matching points from the one or more feature points extracted from the scan line data corresponding to one or more scans occurring immediately before or after the instance of the scan,

adjusting the number of matching points based on a distance of the laser scanner to each of the plurality of matching points, and

estimating a change in position of the laser scanner based on the adjusted number of matching points,

obtain the additional sensor data from the at least one other sensor, and develop an additional odometry of the environment from the additional sensor data,

perform sensor fusion to supplement the laser scanner-based odometry with the additional odometry to develop a three-dimensional map of the environment, and

save the three-dimensional map to a memory device.

14. The system of claim 13 , wherein the programming instructions for developing the laser scanner-based odometry comprise programming instructions configured to cause the processor to use an iterative closest point (ICP) algorithm to estimate the change in position of the laser scanner based on the scan line data and the plurality of landmarks by:

using an Extended Kalman Filter (EKF) to estimate the change in position of the laser scanner based on the adjusted number of matching points.

15. The system of claim 13 , wherein the programming instructions for developing the three-dimensional map of the environment comprise programming instructions configured to cause the processor to perform map registration through a global registration framework.

16. The system of claim 13 , wherein the laser scanner and the at least one other sensor are installed on a robotic device.

17. The system of claim 13 , wherein the programming instructions for identifying the plurality of matching points from the one or more feature points comprise programming instructions configured to cause the processor to:

for each feature point:

extract a feature descriptor for the feature point; and

determine whether the feature point corresponds to a landmark by matching the feature point to a point of a collection of feature points based on an Euclidian distance therebetween and the feature descriptor of the point.

18. The system of claim 13 , wherein the programming instructions for identifying the plurality of matching points from the one or more feature points comprise programming instructions configured to cause the processor to:

evaluate a curvature of each of the one or more feature points to determine whether the feature point is beyond a corner point; and

exclude the point from being a matching point if the feature point is determined to be beyond a corner point.

19. The system of claim 13 , wherein the at least one other sensor comprises a camera, and the programming instructions comprise additional programming instructions configured to cause the processor to obtain a sequence of images from the camera;

wherein:

the additional odometry is a camera odometry; and

developing the additional odometry comprises identifying a plurality of matching points by finding one or more additional feature points in the sequence of images within the identified window.

20. The system of claim 19 , wherein the programming instructions comprise additional programming instructions configured to cause the processor to determine a scale for scaling the camera odometry by:

using a depth registration between the scan line data from the laser scanner and the sequence of images from the camera; or

using data obtained from an inertial measurement unit (IMU).

21. The system of claim 19 , wherein the programming instructions for identifying the plurality of matching points in the camera odometry comprise programming instructions configured to cause the processor to:

for each of the one or more additional feature points:

extract a feature descriptor for the additional feature point; and

determine whether the additional feature point corresponds to a landmark by matching the additional feature point to a point of a collection of feature points based on an Euclidian distance therebetween and the feature descriptor of the point.

22. The system of claim 13 , wherein the programming instructions for developing the laser scanner-based odometry using the iterative closest point (ICP) algorithm from the scan line data comprise programming instructions configured to cause the processor to, for each instance of the scans from the laser scanner:

obtain a first set of points from the instance of the scan and a second set of points from one or more previous scans of the laser scanner;

use the first and second set of points to estimate a first change in position of the laser scanner;

obtain a third set of points comprising a number of most recent points from the laser scanner;

determine the laser scanner-based odometry based on the estimated first change in position and the third set of points; and

optimize the odometry using a graph optimization process.

23. The system of claim 13 , wherein:

the at least one other sensor comprises an inertial measurement unit (IMU); and

the programming instructions for using the ICP to estimate the changes in position comprise programming instructions configured to cause the processor to use measurements from the IMU to determine an initial estimate of a position of a device holding the laser scanner and the IMU.

24. A system for constructing a three-dimensional map of an environment, comprising:

a robotic device movable about an environment, wherein the robotic device comprises:

a laser scanner installed thereon and configured to collect scan line data from a plurality of scans of the environment, wherein each of the scans comprises one or more scan lines, each returning a data value indicating a distance between the laser scanner and a point on a surface of a structure in the environment, and

a camera installed thereon with the laser scanner and configured to collect a sequence of images corresponding to the environment;

a processor; and

a non-transitory computer-readable storage medium containing programming instructions configured to cause the processor to:

obtain the scan line data from the laser scanner,

extract one or more feature points from the scan line data,

develop a laser scanner-based odometry from the feature points by:

for each instance of the scans of the laser scanner, identifying a window that comprises scan lines from one or more scans occurring immediately before or after the instance of the scan,

identifying a plurality of matching points from the one or more feature points extracted from the scan line data corresponding to one or more scans occurring immediately before or after the instance of the scan,

adjusting the number of matching points based on a distance of the laser scanner to each of the plurality of matching points, and

estimating a change in position of the laser scanner based on the adjusted number of matching points,

obtain at least a portion of the sequence of images from the camera, and develop a camera odometry of the environment from the portion of the sequence of images,

perform sensor fusion to supplement the laser scanner-based odometry with the camera odometry to develop a three-dimensional map of the environment, and

save the three-dimensional map to a memory device.