Identifying and parameterizing roof types in map data

Patent metadata

Field	Value
Publication number	US-9582932-B2
Application number	US-201213551394-A
Country	US
Kind code	B2
Filing date	Jul 17, 2012
Priority date	Jun 5, 2012
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

Methods and apparatus for a roof analysis tool for constructing a parameter set, where the parameter set is derived from mapping data for a map region, and where the parameter set describes the roofs for the buildings within the map region. In some cases, the parameter set includes a list of roof type identification values and the respective buildings in the map region for which a given roof type identification value corresponds. The roof analysis tool may operate on a server and work in conjunction with a mobile device, where the mobile device may display map views of a map region such that the map view is based on a three-dimensional model of the map region, and where a portion of the three-dimensional model is based on data generated on the mobile device and a portion of the three-dimensional model is based on data generated on the server.

First claim

What is claimed is:

1. A method, comprising:
performing, by one or more computing devices:
accessing footprint data for one or more structures within a map region;
identifying, from a three-dimensional data set corresponding to the map region and based on the footprint data for a structure of the one or more structures within the map region, a plurality of points on a roof of the structure;
calculating, based on the plurality of points on the roof of the structure, a plurality of normals;
generating a two-dimensional representation comprising a corresponding pair of geometric coordinates for each of the plurality of normals, each pair of geometric coordinates determined based at least in part on a transformation of corresponding three-dimensional coordinates of the corresponding normal for the plurality of normals;
identifying, based at least in part on the two-dimensional representation of the plurality of normals, a plurality of groups of normals from among the plurality of normals;
identifying, based on different respective groups of normals within the plurality of groups of normals, different respective planes of the roof; and
determining a parameter set for the roof of the structure based on parameter values describing the different respective planes of the roof that have been identified based on the different groups of normals.

2. The method of claim 1 , wherein said determining further comprises identifying, based on each respective plane of the roof identified based on the different respective groups of normals, a classification of a roof type, wherein the respective groups of normals have been identified based at least in part on the two-dimensional representation of the plurality of normals.

3. The method of claim 2 , wherein said determining further comprises basing the parameter set on an identification value for the classification of the roof type and an identification of the structure for which the roof corresponds.

4. The method of claim 1 , wherein said generating the two-dimensional representation comprises:
generating a two-dimensional histogram based on a Hough transformation of spherical coordinates for each of the plurality of normals; and
identifying clusters of normals in the two-dimensional histogram based on a mass threshold value; wherein the groups of normals are based at least in part on the clusters of normals.

5. The method of claim 4 , further comprising determining a classification of a roof type based on the respective orientation of each respective plane of the roof.

6. A system, comprising:
a computing device comprising at least one processor; and
a memory comprising program instructions, wherein the program instructions are executable by the at least one processor to:
access footprint data for one or more structures within a map region;
identify, from a three-dimensional data set corresponding to the map region and based on the footprint data for a structure of the one or more structures within the map region, a plurality of points on a roof of the structure;
calculate, based on the plurality of points on the roof of the structure, a plurality of normals;
generate a two-dimensional representation comprising a corresponding pair of geometric coordinates for each of the plurality of normals, each pair of geometric coordinates determined based at least in part on a transformation of corresponding three-dimensional coordinates of the corresponding normal for the plurality of normals;
identify, based at least in part on the two-dimensional representation of the plurality of normals, a plurality of groups of normals from among the plurality of normals; and
identify, based on the plurality of groups of normals, a roof type classification for the structure.

7. The system of claim 6 , wherein to identify the roof type classification for the structure, the program instructions are further executable by the at least one processor to determine, for each respective group of normals within the plurality of groups of normals, a respective plane of the roof, wherein each respective group of normals has been identified based at least in part on the two-dimensional representation of the plurality of normals.

8. The system of claim 7 , wherein to identify the roof type classification for the structure, the program instructions are further executable by the at least one processor to determine, for each respective plane of the roof, a respective orientation based on an average normal for a respective group of normals of the plurality of normals.

9. The system of claim 8 , wherein to identify the roof type classification for the structure, the program instructions are further executable by the at least one processor to determine, based on a respective orientation for each respective plane of the roof, a similarity between the respective orientation for the respective plane of the roof and an orientation of a plane of an archetypal roof for the roof type classification.

10. The system of claim 9 , wherein the roof type classification is determined to be similar when less than all planes of the archetypal roof are determined to be similar to the respective planes of the roof of the structure.

11. A non-transitory, computer-readable storage medium storing program instructions, wherein the program instructions are computer-executable to implement:
receiving, for a map region, three-dimensional mapping data comprising a plurality of triangles representing a respective plurality of surface regions for objects in the map region;
identifying a subset of triangles of the plurality of triangles, wherein the subset of triangles correspond to a roof for a building in the map region;
calculating a normal for a surface of a triangle within the subset of triangles, wherein the normal is represented in three-dimensional Cartesian coordinates;
transforming the three-dimensional Cartesian coordinates of the normal for the surface of the triangle into spherical coordinates for a unit sphere; and
reducing, based at least in part on using rho angle and psi angle parameters instead of theta angle and phi angle parameters in said transforming the three-dimensional Cartesian coordinates of the normal, a range of azimuth angles used in identifying a plane, wherein the range of azimuth angles is due to a range of z-axis values in the three-dimensional Cartesian coordinates for the normal for the surface of the triangle.

12. The non-transitory, computer-readable storage medium of claim 11 , wherein the range of azimuth angles in the theta-phi spherical coordinates is 360 degrees due to z-axis values for normals for the surfaces of the subset of triangles, and wherein a range of azimuth angles in the rho-psi spherical coordinates is 180 degrees.

13. The non-transitory, computer-readable storage medium of claim 12 , wherein the program instructions are computer-executable to further implement:
determining, for each plane in the roof and based on the rho angle and psi angle parameters, a respective plane orientation.

14. The non-transitory, computer-readable storage medium of claim 11 , wherein the program instructions are computer-executable to further implement generating a two-dimensional histogram based on a Hough transformation of spherical coordinates for each of a plurality of normals for the subset of triangles.

15. The non-transitory, computer-readable storage medium of claim 14 , wherein the program instructions are computer-executable to further implement identifying the plane, and wherein the plane is a plane of a roof for a building based on the two-dimensional histogram.

16.

Assignees

• Van Der Merwe Rudolph
• Solem Jan Erik
• Waldman Jaron I
• Kassebaum John W
• Noble Samuel G
• Wu Xiaqing
• Liu Yang
• Apple Inc

Inventors

• Van Der Merwe Rudolph
• Solem Jan Erik
• Waldman Jaron I
• Kassebaum John W
• Noble Samuel G
• Wu Xiaqing
• Liu Yang

Classifications

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G06K9/00637

  Physics · mapped topic

• G06T2210/04

  Architectural design, interior design · CPC title

• G06T17/05 Primary

  Geographic models · CPC title

• G06T17/10

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title