Modeling point cloud data using hierarchies of Gaussian mixture models

• US 10,482,196 B2
• Filed: 02/26/2016
• Issued: 11/19/2019
• 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
• Primary Examiner(s): Alhija, Saif A
• Application Number:
  US15/055,440
• Publication Number:
  US 20170249401A1
• Time in Patent Office: 1,362 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, 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.

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 parameters comprise a set of weighted moments.

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

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

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

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

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

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

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

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 parameters comprise a set of weighted moments.

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

16. The non-transitory computer-readable storage medium of claim 12, 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 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.

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