MODELING POINT CLOUD DATA USING HIERARCHIES OF GAUSSIAN MIXTURE MODELS

• US 20170249401A1
• Filed: 02/26/2016
• Published: 08/31/2017
• Est. Priority Date: 02/26/2016
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Eckart, Benjamin David, Kim, Kihwan, Troccoli, Alejandro Jose, Kautz, Jan
• Granted Patent: US 10,482,196 B2
• Time in Patent Office: Days
• CPC Class Codes: 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
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 2111/10 Numerical modelling
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/955 using specific electronic processors

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

1. A method, comprising:

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.

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

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

4. The method of claim 1, wherein the GMM hierarchy comprises a tree, each node in the tree representing a mixel.

5. The method of claim 4, 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:

6. The method of claim 1, wherein each iteration of the EM algorithm comprises:

an E-step to calculate a set of expectation values, each 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.

7. The method of claim 6, wherein the set of expectation values is calculated in parallel utilizing a parallel processing unit.

8. The method of claim 7, wherein a number of threads are allocated in a 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.

9. The method of claim 1, further comprising generating a mesh based on the GMM hierarchy.

10. The method of claim 9, wherein generating a mesh comprises:

defining a set of voxels corresponding to a volume associated with the GMM hierarchy;

generate a set of active voxels based on an importance sampling algorithm, wherein the set of active voxels includes a subset of voxels in the set of voxels associated with the volume; and

test each voxel in the set of active voxels based on a modified marching cubes algorithm to generate the mesh.

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

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

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

14. The non-transitory computer-readable storage medium of claim 12, wherein the GMM hierarchy comprises a tree, each node in the tree representing a mixel.

15. The non-transitory computer-readable storage medium of claim 14, 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:

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

17. A system comprising:

a memory storing point cloud data defining a plurality of points; and

a processor configured to;

define a Gaussian Mixture Model (GMM) hierarchy that includes a number of mixels, each mixel encoding parameters for a probabilistic occupancy map, and

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

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

19. The system of claim 17, wherein the GMM hierarchy comprises a tree, each node in the tree representing a mixel, and 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:

20. The system of claim 17, wherein the processor is a parallel processing unit.