Method for generating a three-dimensional model of a roof structure

• US 7,728,833 B2
• Filed: 08/18/2005
• Issued: 06/01/2010
• Est. Priority Date: 08/18/2004
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Hsu, Stephen Charles, Verma, Vivek, Kumar, Rakesh, Sawhney, Harpreet
• Primary Examiner(s): REPKO, JASON MICHAEL
• Application Number:
  US11/206,665
• Publication Number:
  US 20060061566A1
• Time in Patent Office: 1,748 Days
• Field of Search: 345/419, 345/420, 345/582, 382/154, 702150-155
• US Class Current: 345/420
• 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 for generating a three-dimensional model of a roof structure within a target scene, comprising the steps of:

identifying a point cloud data set corresponding to the target scene;

removing from the point cloud data set data points corresponding to a ground portion thereby generating a refined point cloud data set;

identifying, by a computer, one or more planar regions from within the refined point cloud data set;

grouping the one or more planar regions into one or more local planes;

grouping the one or more local planes into one or more roof structure planes, thereby creating one or more polygons, wherein the one or more polygons correspond to a face of the one or more roof structure planes;

creating a topology graph of the roof portion, comprising one or more nodes,

wherein each node represents one of the one or more polygons;

identifying one or more parametric shapes corresponding to the topology graph; and

generating a three-dimensional model of the roof structure within the target scene based on the one or more parametric shapes.

2. The method of claim 1, wherein the step of removing data points corresponding to the ground portion further comprises:

identifying non-planar points from the point cloud data set,

removing non-planar points from the point cloud data set thereby creating a planar point cloud data set,

identifying a plane including the largest number of data points from the planar point cloud data set, wherein said plane comprises the ground portion, and

removing data points corresponding to the plane with the largest number of data points from the planar point cloud data set, thereby creating the refined point cloud data set.

3. The method of claim 1, wherein the step of grouping the one or more planar regions into one or more local planes further comprises:

calculating a covariance matrix of two or more data points from within the one or more planar regions, and

grouping the two or more data points from within the one or more planar regions into local planes based on eigenvalues of the covariance matrix, thereby creating one or more local planes.

4. The method of claim 1, wherein the step of grouping the one or more local planes to define one or more roof structure planes further comprises:

calculating a normal for each of the one or more local planes, and

grouping together the one or more local planes having substantially parallel normals, thereby defining one or more roof structure planes.

5. The method of claim 1, wherein the step of grouping the one or more local planes into one or more roof structure planes, thereby creating one or more polygons utilizes a ball pivoting algorithm in order to define the boundaries of the one or more local planes.

6. The method of claim 1, wherein the topology graph is represented by two or more topological graphs.

7. The method of claim 1, wherein the step of identifying one or more parametric shapes corresponding to the topology graph further comprises searching a parametric shapes database for parametric shapes which correspond to the topology graph.