# US 10,482,196 B2 · Modeling point cloud data using hierarchies of Gaussian mixture models

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,482,196 B2
- Document ID: US10482196B2
- Status: Granted
- Kind: B2
- Application number: 15/055,440
- Filed: 2016-02-26
- Published: 2017-08-31
- Granted: 2019-11-19
- Earliest claimed: 2016-02-26
- Assignees: NVIDIA Corporation
- Applicants: NVIDIA Corporation
- Inventors: Benjamin David Eckart; Kihwan Kim; Alejandro Jose Troccoli; Jan Kautz
- Web page: https://patentgrep.com/patent/US10482196B2

## CPC

- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 18/231: Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
- G06F 18/2415: based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
- G06F 18/24323: {Tree-organised classifiers}
- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06V 10/7625: {Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms}
- G06V 10/764: using classification, e.g. of video objects
- G06V 10/955: {using specific electronic processors}
- G06F 2111/10: Numerical modelling
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A method, computer readable medium, and system are disclosed for generating a Gaussian mixture model hierarchy. The method includes the steps of receiving point cloud data defining a plurality of points; defining a Gaussian Mixture Model (GMM) hierarchy that includes a number of mixels, each mixel encoding parameters for a probabilistic occupancy map; and adjusting the parameters for one or more probabilistic occupancy maps based on the point cloud data utilizing a number of iterations of an Expectation-Maximum (EM) algorithm.

## Claims

### Claim 1

A method, comprising:
receiving, by a parallel processing unit, point cloud data defining a plurality of points;
defining a Gaussian Mixture Model (GMM) hierarchy that represents the point cloud data, wherein the GMM hierarchy is stored in a tree data structure in a memory and each node in the GMM hierarchy comprises a mixel encoding parameters for a probabilistic occupancy map corresponding to a sub-population of the points in the point cloud data; and
adjusting the parameters for one or more probabilistic occupancy maps in the GMM hierarchy by executing, via the parallel processing unit, a number of iterations of an Expectation-Maximum (EM) algorithm to fit the one or more probabilistic occupancy maps to the point cloud data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the EM algorithm comprises calculating a set of expectation values, at least in part, utilizing a uniform noise distribution function.

### Claim 3 (depends on 2)

The method of claim 2, wherein the uniform noise distribution function is associated with a probability density function of the form:
p(x)=ϵ,
where ϵ is constant across a bounding volume that encloses the plurality of points defined by the point cloud data.

### Claim 4 (depends on 1)

The method of claim 1, wherein the parameters comprise a set of weighted moments.

### Claim 5 (depends on 1)

The method of claim 1, wherein each probabilistic occupancy map encoded by the mixels is associated with a probability density function for a multi-variate Gaussian distribution of the form:
p
⁡
(
x
|
μ
,
Σ
)
=
1
(
2
⁢
π
)
n
/
2
⁢

Σ

1
/
2
⁢
e
(
-
1
2
⁢
(
x
-
μ
)
T
⁢
Σ
-
1
⁡
(
x
-
μ
)
)
,
where μ is a mean of the multi-variate Gaussian distribution and X is the covariance matrix of the multi-variate Gaussian distribution.

### Claim 6 (depends on 1)

The method of claim 1, wherein each iteration of the EM algorithm comprises:
an E-step to calculate a set of expectation values, the set of expectation values corresponding to a particular point in the point cloud data and a particular probabilistic occupancy map of the GMM hierarchy; and
an M-step to adjust the parameters for the probabilistic occupancy maps based on the set of expectation values.

### Claim 7 (depends on 6)

The method of claim 6, wherein the E-step is performed by the parallel processing unit to calculate the set of expectation values, and wherein at least two expectation values are calculated by the parallel processing unit in parallel.

### Claim 8 (depends on 7)

The method of claim 7, wherein a number of threads are allocated in the parallel processing unit, each thread corresponding to a particular probabilistic occupancy map, and wherein a number of expectation values for a particular point are calculated substantially simultaneously by the number of threads.

### Claim 9 (depends on 1)

The method of claim 1, further comprising generating a mesh by extracting iso-surfaces from the GMM hierarchy.

### Claim 10 (depends on 9)

The method of claim 9, wherein generating the mesh comprises:
defining a set of voxels corresponding to a volume associated with the GMM hierarchy;
generating a set of active voxels by sampling the probabilistic occupancy maps, wherein the set of active voxels includes a subset of voxels in the set of voxels associated with the volume; and
comparing probability values computed for each voxel in the set of active voxels against an iso-value to generate the mesh.

### Claim 11 (depends on 10)

The method of claim 10, further comprising rendering the mesh.

### Claim 12

A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:
receiving point cloud data defining a plurality of points;
defining a Gaussian Mixture Model (GMM) hierarchy that represents the point cloud data, wherein the GMM hierarchy is stored in a tree data structure in a memory and each node in the GMM hierarchy comprises a mixel encoding parameters for a probabilistic occupancy map corresponding to a sub-population of the points in the point cloud; and
adjusting the parameters for one or more probabilistic occupancy maps in the GMM hierarchy by executing a number of iterations of an Expectation-Maximum (EM) algorithm to fit the one or more probabilistic occupancy maps to the point cloud data.

### Claim 13 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, wherein the EM algorithm comprises calculating a set of expectation values, at least in part, utilizing a uniform noise distribution function.

### Claim 14 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, wherein the parameters comprise a set of weighted moments.

### Claim 15 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, wherein each probabilistic occupancy map encoded by the mixels is associated with a probability density function for a multi-variate Gaussian distribution of the form:
p
⁡
(
x
|
μ
,
Σ
)
=
1
(
2
⁢
π
)
n
/
2
⁢

Σ

1
/
2
⁢
e
(
-
1
2
⁢
(
x
-
μ
)
T
⁢
Σ
-
1
⁡
(
x
-
μ
)
)
,
where μ is a mean of the multi-variate Gaussian distribution and X is the covariance matrix of the multi-variate Gaussian distribution.

### Claim 16 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, wherein the processor is a parallel processing unit.

### Claim 17

A system comprising:
a memory storing point cloud data defining a plurality of points; and
a parallel processing unit-configured to:
define a Gaussian Mixture Model (GMM) hierarchy that represents the point cloud data, wherein the GMM hierarchy is stored in a tree data structure in the memory and each node in the GMM hierarchy comprises a mixel encoding parameters for a probabilistic occupancy map corresponding to a sub-population of the points in the point cloud, and
adjust the parameters for one or more probabilistic occupancy maps by executing a number of iterations of an Expectation-Maximum (EM) algorithm to fit the one or more probabilistic occupancy maps to the point cloud data.

### Claim 18 (depends on 17)

The system of claim 17, wherein the EM algorithm comprises calculating a set of expectation values, at least in part, utilizing a uniform noise distribution function.

### Claim 19 (depends on 17)

The system of claim 17, wherein each probabilistic occupancy map encoded by the mixels is associated with a probability density function for a multi-variate Gaussian distribution of the form:
p
⁡
(
x
|
μ
,
Σ
)
=
1
(
2
⁢
π
)
n
/
2
⁢

Σ

1
/
2
⁢
e
(
-
1
2
⁢
(
x
-
μ
)
T
⁢
Σ
-
1
⁡
(
x
-
μ
)
)
,
where μ is a mean of the multi-variate Gaussian distribution and X is the covariance matrix of the multi-variate Gaussian distribution.

### Claim 20 (depends on 17)

The system of claim 17, wherein each iteration of the EM algorithm comprises:
an E-step to calculate a set of expectation values, the set of expectation values corresponding to a particular point in the point cloud data and a particular probabilistic occupancy map of the GMM hierarchy; and
an M-step to adjust the parameters for the probabilistic occupancy maps based on the set of expectation values.