Method and apparatus for performing three-dimensional computer modeling

• US 20060061566A1
• Filed: 08/18/2005
• Published: 03/23/2006
• Est. Priority Date: 08/18/2004
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Kumar, Rakesh, Sawhney, Harpreet, Hsu, Stephen Charles, Verma, Vivek
• Granted Patent: US 7,728,833 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method and apparatus for automatically generating a three-dimensional computer model from a “point cloud” of a scene produced by a laser radar (LIDAR) system. Given a point cloud of an indoor or outdoor scene, the method extracts certain structures from the imaged scene, i.e., ceiling, floor, furniture, rooftops, ground, and the like, and models these structures with planes and/or prismatic structures to achieve a three-dimensional computer model of the scene. The method may then add photographic and/or synthetic texturing to the model to achieve a realistic model.

Claims

1. A method of generating a three-dimensional model of a scene, comprising:

automatically deriving a three-dimensional geometry from a point cloud representing a scene; and

applying texture to the three-dimensional geometry to create a textured model of the scene.

2. The method of claim 1 wherein the deriving step further comprises:

classifying portions of the point cloud as particular objects within the scene; and

creating a model for each of the classified portions.

4. The method of claim 1 wherein the at least one object is a building.

5. The method of claim 4 wherein the at least one plane defines a rooftop.

3. A method of generating a three-dimensional model of a scene, comprising:

identifying a boundary of at least one object within a point cloud;

determining at least one planar polygon that substantially fits points of the point cloud within the boundary; and

extruding the at least one planar polygon to a reference plane to form a model of the at least one object.

6. The method of claim 3 wherein the at least one plane is a portion of a parametric shape.

7. The method of claim 3 wherein the point cloud represents a room and the at least one object is furniture.

8. The method of claim 3 wherein the identifying step further comprises:

identifying a ground plane within the point cloud; and

removing points in the point cloud that substantially lie in the ground plane.

9. The method of claim 3 wherein the determining step further comprises:

creating planar patches of neighboring points within the point cloud;

grouping the planar patches; and

defining a planar boundary of the at least one plane using the grouped planar patches.

10. The method of claim 9 wherein the determining step further comprises:

generating a topological graph for the at least one plane.

11. The method of claim 10 wherein the determining step further comprises:

selecting a parametric shape to represent the at least one plane based upon the topological graph.

12. The method of claim 11 wherein the parametric shape is a prismatic shape.

13. The method of claim 3 wherein the reference plane is at least one of a ground plane or a floor plane.

14. The method of claim 11 wherein the parametric shape represents a shape of a roof of a building.

15. The method of claim 3 further comprising:

applying texture to the model.

16. The method of claim 15 wherein the texture comprises at least one of photographic imagery, synthetic imagery, or image information from a LIDAR system that created the point cloud.

17. The method of claim 11 wherein the parametric shape comprises component parametric shapes that are represented by topology sub-graphs.

18. A method of generating a three-dimensional model of room, comprising:

identifying a boundary of the room represented by a point cloud;

determining a ceiling plane and a floor plane to estimate a height of the room;

removing points in the point cloud that substantially lie within the floor plane and the ceiling plane to create a set of remaining points;

identifying a boundary of at least one object within said remaining points;

determining at least one plane that substantially fits points of the remaining points within the boundary; and

extruding the at least one plane to a reference plane to form a model of the at least one object.

19. The method of claim 18 further comprising aligning a first point cloud with a second point cloud to create said point cloud.

20. The method of claim 18 wherein the at least one plane is a portion of a parametric shape.

21. The method of claim 18 wherein the point cloud represents a room and the at least one object is furniture.

22. The method of claim 18 wherein the reference plane is a floor plane.

23. The method of claim 18 further comprising:

applying texture to the model.

24. The method of claim 21 wherein the texture comprises at least one of photographic imagery, synthetic imagery, or image information from a LIDAR system that created the point cloud.

25. Apparatus for generating a three-dimensional model of a scene, comprising:

means for identifying a boundary of at least one object within a point cloud;

means for determining at least one plane that substantially fits points of the point cloud within the boundary; and

means for extruding the at least one plane to a reference plane to form a model of the at least one object.

26. The apparatus of claim 25 wherein the at least one object is a building.

27. The apparatus of claim 26 wherein the at least one plane defines a rooftop.

29. The apparatus of claim 25 wherein the point cloud represents a room and the at least one object is furniture.

28. The apparatus of daim 25 wherein the at least one plane is a portion of a parametric shape.