Fast multi-scale point cloud registration with a hierarchical gaussian mixture

Patent metadata

Field	Value
Publication number	US-10826786-B2
Application number	US-201916351312-A
Country	US
Kind code	B2
Filing date	Mar 12, 2019
Priority date	Apr 11, 2018
Publication date	Nov 3, 2020
Grant date	Nov 3, 2020

Abstract

Point cloud registration sits at the core of many important and challenging 3D perception problems including autonomous navigation, object/scene recognition, and augmented reality (AR). A new registration algorithm is presented that achieves speed and accuracy by registering a point cloud to a representation of a reference point cloud. A target point cloud is registered to the reference point cloud by iterating through a number of cycles of an EM algorithm where, during an Expectation step, each point in the target point cloud is associated with a node of a hierarchical tree data structure and, during a Maximization step, an estimated transformation is determined based on the association of the points with corresponding nodes of the hierarchical tree data structure. The estimated transformation is determined by solving a minimization problem associated with a sum, over a number of mixture components, over terms related to a Mahalanobis distance.

First claim

What is claimed is:

1. A computer-implemented method for registration of point cloud data, comprising:
obtaining a hierarchical tree data structure that represents first point cloud data as a hierarchy of mixture distributions;
receiving second point cloud data; and
registering the second point cloud data to the first point cloud data utilizing the hierarchical tree data structure to identify an estimated transformation,
wherein the registering comprises executing, on a parallel processing unit, an expectation maximization algorithm that includes:
an expectation (E) step configured to implement a recursive search of the hierarchical tree data structure to associate each point in the second point cloud data with a node of the hierarchical tree data structure, and
a maximization (M) step configured to determine the estimated transformation based on the association of the points in the second point cloud data with corresponding nodes of the hierarchical tree data structure.

2. The computer-implemented method of claim 1 , further comprising iteratively alternating between the E step and the M step for a number of cycles to converge on an optimal transformation.

3. The computer-implemented method of claim 1 , wherein the E step includes, at each node during the recursive search of the hierarchical tree data structure:
comparing a heuristic value for each mixture component included in the mixture distribution for the node to an adaptive threshold value to determine whether to terminate the recursive search for a particular child node of the node associated with the mixture component.

4. The computer-implemented method of claim 3 , wherein the heuristic value is based on eigenvalues associated with a covariance matrix identified for a particular mixture component included in the mixture distribution of the node.

5. The computer-implemented method of claim 1 , wherein the M step includes solving for a maximum likelihood estimation (MLE) criteria using a weighted least squares technique.

6. The computer-implemented method of claim 1 , further comprising:
receiving the first point cloud data; and
generating the hierarchical tree data structure.

7. The computer-implemented method of claim 6 , wherein generating the hierarchical tree data structure comprises iterating through a second EM algorithm to generate the hierarchical tree data structure.

8. The computer-implemented method of claim 6 , wherein each node of the hierarchical tree data structure represents at least a portion of the first point cloud data using a mixture distribution that includes a number of Gaussian distributions and a uniform distribution.

9. The computer-implemented method of claim 1 , wherein the E step comprises, for each point object in the second point cloud data:
for each mixture component associated with the node associated with the point object, calculating a correspondence value for the mixture component in accordance with the following equation:

E
⁡

[

c
ij

]

=

π
j

⁢

N
(

Z
i

⁢



Θ
j

)

∑

k
=
1

J

⁢

π
k

⁢

N
(

Z
i

⁢



Θ
k

)

.

10. The computer-implemented method of claim 1 , wherein the M step comprises, for each mixture component included in the hierarchical tree data structure:
calculating a first parameter for the mixture component in accordance with the following equation:

π
j
*

=

∑
i

⁢

γ
ij

N

;

calculating a second parameter for the mixture component in accordance with the following equation:

μ
j
*

=

∑
i

⁢

γ
ij

⁢

z
i

∑
i

⁢

γ
ij

.

11. The computer-implemented method of claim 10 , wherein the M step further comprises:
identifying a transformation by minimizing a maximum likelihood estimation (MLE) criteria using a weighted least squares technique, wherein the MLE criteria comprises a sum over J mixture components included in the hierarchical tree data structure in accordance with the following equation:

T
^

=

arg
⁢

Assignees

• Nvidia Corp

Inventors

• Eckart Benjamin David
• Kim Kihwan
• Kautz Jan

Classifications

• G06T7/33 Primary

  using feature-based methods · CPC title

• G06T2207/10028

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

• H04L41/142 Primary

  using statistical or mathematical methods · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title