THREE-DIMENSIONAL POINT PROCESSING AND MODEL GENERATION

• US 20140098094A1
• Filed: 03/15/2013
• Published: 04/10/2014
• Est. Priority Date: 10/05/2012
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: Jing Huang, Suya You, Ulrich Neumann
• Inventors: NEUMANN, Ulrich, NOCERA, Luciano, YOU, Suya, QIU, Rongqi, PANG, Guan, HUANG, Jing
• Granted Patent: US 9,472,022 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering
• CPC Class Codes: G06V 20/653 by matching three-dimensional models, e.g. conformal mapping of Riemann surfaces

Abstract

A scene point cloud is processed and a solution to an inverse-function is determined to determine its source objects. A primitive extraction process and a part matching process are used to compute the inverse function solution. The extraction process estimates models and parameters based on evidence of cylinder and planar geometry in the scene. The matching process matches clusters of 3D points to models of parts from a library. A selected part and its associated polygon model is used to represent the point cluster. Iterations of the extraction and matching processes complete a 3D model for a complex scene made up of planes, cylinders, and complex parts from the parts library. Connecting regions between primitives and/or parts are processed to determine their existence and type. Constraints may be used to ensure a connected model and alignment of its components.

Claims

1. A method for three-dimensional point processing and model generation, comprising:

(a) providing data comprising a scan of a scene comprising a point cloud, the point cloud comprising a plurality of points;

(b) applying a primitive extraction to the data to associate primitive shapes with points within the point cloud;

(c) applying a part matching to the data to associate points within the point cloud with one or more part models; and

(d) assembling the primitive shapes and the part models into a 3D surface model of the scene.

2. The method of claim 1, further comprising creating joints between the primitive shapes and part models prior to assembling the 3D surface model of the scanned scene.

3. The method of claim 2, wherein the 3D surface model of the scanned scene comprises connectivity information for at least one joint.

4. The method of claim 1, further comprising pre-processing the point cloud scan into a 3D image.

5. The method of claim 4, wherein the pre-processing comprises:

converting the point cloud to a 3D image of voxels, each voxel corresponding to a subset volume of the point cloud; and

assigning an intensity value to each voxel based on a number of points within the voxel.

6. The method of claim 5, wherein each subset volume is equal to a selected proportion of a volume of the point cloud.

7. The method of claim 1, further comprising point cloud clustering prior to applying the part matching to the data.

8. The method of claim 1, wherein assembling the primitive shapes and part models into the 3D surface model of the scanned scene further comprises model adjustment to meet desired geometric constraints.

9. The method of claim 1, wherein metadata for one or more of the part models is provided in the 3D surface model of the scanned scene.

10. The method of claim 1, wherein the 3D surface model of the scanned scene comprises connectivity information for at least one primitive shape.

11. The method of claim 1, wherein the 3D surface model of the scanned scene comprises connectivity information for at least one part model.

12. The method of claim 1, wherein the part models are stored in a parts library.

13. The method of claim 1, further comprising importing part models from 3D surface models into the parts library using a virtual scanner.

14. The method of claim 13, further comprising selecting points on a surface of a scanned part and creating a corresponding surface model that is stored in the parts library.

15. The method of claim 1, wherein the applying a part matching comprises using a training module trained using a machine learning algorithm.

16. The method of claim 15, wherein the machine learning algorithm is an adaboost training procedure.

17. The method of claim 15, wherein the machine learning algorithm comprises using negative training samples known to lack a target object to reduce false detections.

18. A system for three-dimensional point processing and model generation, the system comprising:

a database configured to store data comprising a scan of a scene comprising a point cloud, the point cloud comprising a plurality of points;

a computer processer configured to receive the stored data from the database, and to execute software responsive to the stored data; and

a software program executable on the computer processer, the software program containing computer readable software instructions comprising;

(c) a primitive extraction module that applies primitive extraction to the data to associate primitive shapes with points within the point cloud;

(d) a part matching module that applies a part matching to the data to associate points within the point cloud with one or more part models; and

(e) a model integration module that assembles the primitive shapes and the part models into a 3D surface model of the scene.

19. A non-transitory processor readable medium containing computer readable software instructions used for three-dimensional point processing and model generation, the software instructions comprising:

(a) a primitive extraction module that applies primitive extraction to the data to associate primitive shapes with points within a scan of a scene comprising a point cloud;

(b) a part matching module that applies a part matching to the data to associate points within the point cloud with one or more part models; and

(c) a model integration module that assembles the primitive shapes and the part models into a 3D surface model of the scene.