High-definition city mapping

Patent metadata

Field	Value
Publication number	US-11238643-B1
Application number	US-202017124444-A
Country	US
Kind code	B1
Filing date	Dec 16, 2020
Priority date	Dec 16, 2020
Publication date	Feb 1, 2022
Grant date	Feb 1, 2022

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.

First claim

The invention claimed is:

1. A computing system on a vehicle, 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 computing system to perform:
obtaining point clouds at different positions, orientations, and times from one or more Lidar sensors;
registering, in pairs, a subset of the point clouds based on respective surface normals of each of the point clouds, the registering comprising:
aligning a target point cloud with a source 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 between the target point cloud and the source point cloud, the forming of the alignment comprising:
selecting, using a graphics processing unit (GPU), for a point from the source point cloud, a corresponding closest point in the target point cloud;
determining whether the point and the corresponding closest point have a same category;
in response to determining that the point and the corresponding closest point have a same category, determining a mahalanobis distance between the point and the corresponding closest point; and
determining a position parameter or an orientation parameter of the source point cloud and the target point cloud based on the determined mahalanobis distance, the alignment being based on the position parameter or the orientation parameter;

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 a 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.

2. The computing system of claim 1 , wherein the aligning the target point cloud with a source point cloud further comprises:
iteratively selecting additional points from the source point cloud and respective closest points in the target point cloud until an updated position parameter and an updated orientation parameter converge;
determining whether each pair comprising an additional point of the additional points and a respective closest point of the respective closest points have a same category;
for each pair having a same category:
determining a mahalanobis distance between additional point and the respective closest point; and
determine the updated position parameter and the updated orientation parameter of the source point cloud and the target point cloud based on the determined mahalanobis distances between the additional point and the respective closest point, and between the point and the corresponding closest point;

determining whether a difference between the updated position parameter and an immediate previous position parameter is less than a threshold, and whether a second difference between the updated orientation parameter and an immediate previous orientation parameter is less than a threshold; and
in response to determining that the difference is less than a threshold and the second difference is less than the second threshold, determining that the updated position parameter and the updated orientation parameter converge.

3. The computing system vehicle of claim 1 , further comprising an inertial measurement unit (IMU) and a global navigation satellite system (GNSS) sensor, and wherein the instructions further cause the computing system to perform:
fusing global navigation satellite system (GNSS) data and inertial measurement unit (IMU) data using GNSS/INS post processing to estimate odometry data of the vehicle, the odometry data including a position, an orientation, and a velocity of the vehicle; and
determining a position and an orientation of each of the subset of the point clouds based on a constraint associated with the fused GNSS/IMU data and based on the constraint associated with the determined loop closures.

4. The computing system of claim 3 , 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.

5. The computing system of claim 3 , wherein the constraint associated with the fused GNSS/IMU data requires that the vehicle be within a range of distances at two distinct times.

6. The computing system of claim 3 , 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/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/IMU data.

7. The computing system of claim 6 , 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/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/IMU data is unsatisfiable, removing the constraint determined to be unsatisfiable based on a self-adaption threshold of an actual cost, iterations of repetition, and differences in Euclidean distance.

8. The computing system of claim 7 , wherein the instructions further cause the system to perform:
adding an additional constraint associated with a loop closure corresponding to a region where a frequency or concentration of repeating features exceeds a threshold frequency or density.

9. A computer implemented method performed by one or more processors on a vehicle, comprising:
obtaining, from one or more Lidar sensors, point clouds at different positions, orientations, and times;
registering, in pairs, a subset of the point clouds based on respective surface normals of each of the point clouds, the registering comprising:
aligning a target point cloud with a source 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 between the target point cloud and the source point cloud, the forming of the alignment comprising:
selecting, using a graphics processing unit (GPU), for a point from the source point cloud, a corresponding closest point in the target point cloud;
determining whether the point and the corresponding closest point have a same category;
in response to determining that the point and the corresponding closest point have a same category, determine a mahalanobis distance between the point and the corresponding closest point; and
determine a position parameter or an orientation parameter of the source point cloud and the target point cloud based on the determined mahalanobis distance, the alignment being based on the position parameter or the orientation parameter;

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 a constraint 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.

10. The computer implemented method of claim 9 , wherein the aligning t

Assignees

• Pony Ai Inc

Inventors

• Yang Mengda
• Jiang Weixin
• Liu Chuanchuan

Classifications

• G06F18/25

  Fusion techniques · CPC title

• G01C21/3841 Primary

  Data obtained from two or more sources, e.g. probe vehicles · CPC title

• G06V20/56

  exterior to a vehicle by using sensors mounted on the vehicle · CPC title

• G01S2013/93274

  on the side of the vehicles · CPC title

• G01S2013/93272

  in the back of the vehicles · CPC title