High-definition city mapping

Abstract

A vehicle generates a city-scale map. The vehicle includes one or more Lidar sensors configured to obtain point clouds at different positions, orientations, and times,one or more processors, and a memory storing instructions that, when executed by the one or more processors, cause the system to perform registering, in pairs, a subset of the point clouds based on respective surface normals of each of the point clouds; determining loop closures based on the registered subset of point clouds; determining a position and an orientation of each of the subset of the point clouds based on constraints associated with the determined loop closures; and generating a map based on the determined position and the orientation of each of the subset of the point clouds.

The invention claimed is: 
     
       1. A computing system on a vehicle configured to generate a city-scale map, the computing system configured to generate a city-scale map and comprising:
 one or more processors; and 
 a memory storing instructions that, when executed by the one or more processors, cause the system to perform:
 obtaining point clouds at different positions, orientations, or times; 
 registering, in pairs, a subset of the point clouds based on respective surface normals of each of the point clouds; 
 obtaining inertial measurement unit (IMU) data from an IMU and global navigation satellite system (GNSS) data from a GNSS sensor; 
 fusing the GNSS data and the IMU data; 
 determining a position or an orientation of each of the subset of the point clouds based on a constraint associated with the fused GNSS and IMU data; and 
 generating a map based on the determined position or the orientation of each of the subset of the point clouds. 
 
 
     
     
       2. The computing system of  claim 1 , wherein the instructions further cause the computing system to perform:
 constructing a cost function corresponding to the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data; and 
 the determining a position and an orientation of each of the subset of the point clouds is based on an optimization of the cost function corresponding to the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data. 
 
     
     
       3. The computing system of  claim 1 , wherein the determining a position and an orientation of each of the subset of the point clouds is based on a distance between the vehicle and each of the subset of the point clouds. 
     
     
       4. The computing system of  claim 1 , the registering comprising:
 aligning a target point cloud with a source point cloud based on a position parameter or an orientation parameter of the source point cloud and the target point cloud, wherein the target point cloud was obtained at a later time compared to the source point cloud; and 
 determining a rigid transformation including a rotation and a translation to form an alignment, based on the position parameter or the orientation parameter, between the target point cloud and the source point cloud. 
 
     
     
       5. The computing system of  claim 4 , wherein the registering further comprises:
 determining the position parameter or the orientation parameter based on a point from the source point cloud and a corresponding closest point in the target point cloud. 
 
     
     
       6. The computing system of  claim 5 , wherein the point and the corresponding closest point have a common category indicative of respective degrees to which the source point cloud and the target point cloud are self-repetitive. 
     
     
       7. The computing system of  claim 5 , wherein the registering further comprises:
 determining that the point and the corresponding closest point have a common category based on an eigen decomposition of the point and the corresponding closest point. 
 
     
     
       8. The computing system of  claim 1 , wherein the determining a position or an orientation of each of the subset of the point clouds is based on a distance between the vehicle and each of the subset of the point clouds. 
     
     
       9. The computing system of  claim 1 , wherein the instructions further cause the computing system to perform:
 determining loop closures based on the registered subset of point clouds; and the determination of the position or an orientation of each of the subset of the point clouds is additionally based on a constraint associated with the determined loop closures. 
 
     
     
       10. The computing system of  claim 9 , wherein the instructions further cause the computing system to perform:
 determining whether the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data is satisfiable; and 
 in response to determining that the constraint associated with the determined loop closures or the constraint associated with the fused GNSS and IMU data is unsatisfiable, removing the constraint determined to be unsatisfiable based on a self-adaption threshold of an actual cost, iterations of repetition, or differences in Euclidean distance. 
 
     
     
       11. A computer-implemented method performed by one or more processors on a vehicle, comprising:
 obtaining point clouds at different positions, orientations, or times; 
 registering, in pairs, a subset of the point clouds based on respective surface normals of each of the point clouds; 
 obtaining inertial measurement unit (IMU) data from an IMU and global navigation satellite system (GNSS) data from a GNSS sensor; 
 fusing the GNSS data and the IMU data; 
 determining a position or an orientation of each of the subset of the point clouds based on a constraint associated with the fused GNSS and IMU data; and 
 generating a map based on the determined position or the orientation of each of the subset of the point clouds. 
 
     
     
       12. The computer-implemented method of  claim 11 , further comprising:
 constructing a cost function corresponding to the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data; and 
 the determining a position and an orientation of each of the subset of the point clouds is based on an optimization of the cost function corresponding to the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data. 
 
     
     
       13. The computer-implemented method of  claim 11 , wherein the determining a position and an orientation of each of the subset of the point clouds is based on a distance between the vehicle and each of the subset of the point clouds. 
     
     
       14. The computer-implemented method of  claim 11 , wherein the registering comprises:
 aligning a target point cloud with a source point cloud based on a position parameter or an orientation parameter of the source point cloud and the target point cloud, wherein the target point cloud was obtained at a later time compared to the source point cloud; and 
 determining a rigid transformation including a rotation and a translation to form an alignment, based on the position parameter or the orientation parameter, between the target point cloud and the source point cloud. 
 
     
     
       15. The computer-implemented method of  claim 14 , wherein the registering further comprises:
 determining the position parameter or the orientation parameter based on a point from the source point cloud and a corresponding closest point in the target point cloud. 
 
     
     
       16. The computer-implemented method of  claim 15 , wherein the point and the corresponding closest point have a common category indicative of respective degrees to which the source point cloud and the target point cloud are self-repetitive. 
     
     
       17. The computer-implemented method of  claim 15 , wherein the registering further comprises: determining that the point and the corresponding closest point have a common category based on an eigen decomposition of the point and the corresponding closest point. 
     
     
       18. The computer-implemented method of  claim 11 , wherein the determining a position or an orientation of each of the subset of the point clouds is based on a distance between the vehicle and each of the subset of the point clouds. 
     
     
       19. The computer-implemented method of  claim 11 , further comprising:
 determining loop closures based on the registered subset of point clouds; and the determination of the position or an orientation of each of the subset of the point clouds is additionally based on a constraint associated with the determined loop closures. 
 
     
     
       20. The computer-implemented method of  claim 19 , further comprising:
 determining whether the constraint associated with the determined loop closures and the constraint associated with the fused GNSS and IMU data is satisfiable; and 
 in response to determining that the constraint associated with the determined loop closures or the constraint associated with the fused GNSS and IMU data is unsatisfiable, removing the constraint determined to be unsatisfiable based on a self-adaption threshold of an actual cost, iterations of repetition, or differences in Euclidean distance.