Constructing compact three-dimensional building models

Patent metadata

Field	Value
Publication number	US-12148232-B2
Application number	US-202218088759-A
Country	US
Kind code	B2
Filing date	Dec 26, 2022
Priority date	Oct 22, 2019
Publication date	Nov 19, 2024
Grant date	Nov 19, 2024

Abstract

An example method performed by a processing system includes obtaining a light detecting and ranging point cloud of a building, where the point cloud includes a plurality of points, and where each point is associated with a set of (x,y,z) coordinates. A first point of the plurality of points is assigned to a subset of the plurality of points that is associated with the building, where the subset includes points whose (x,y) coordinates fall within a footprint of the building. The first point is grouped into a first cluster according to at least one of: a (z) coordinate of the first point and a gradient to which the first point belongs. A first prism formed by the first cluster is constructed. A model of the building is stored as a plurality of connected prisms, where the plurality of connected prisms includes the first prism.

First claim

What is claimed is:

1. A method comprising:
obtaining, by a processing system including at least one processor, a light detection and ranging point cloud of a building, wherein the light detection and ranging point cloud comprises a plurality of points, and wherein each point in the plurality of points is associated with a set of (x,y,z) coordinates;
assigning, by the processing system, a first point of the plurality of points to a subset of the plurality of points that is associated with the building, wherein the subset comprises points whose (x,y) coordinates fall within a footprint of the building;
grouping, by the processing system, the first point into a first cluster according to at least one of: a (z) coordinate of the first point or a gradient to which the first point belongs, wherein the first cluster comprises a first further subset of the subset, and wherein differences in (z) coordinates of points in the first further subset all fall below a predefined threshold difference;
constructing, by the processing system, a first prism formed by the first cluster; and
storing, by the processing system, a model of the building as a plurality of connected prisms, wherein the plurality of connected prisms includes the first prism.

2. The method of claim 1 , wherein the footprint of the building comprises a polygon extracted from a satellite image of the building.

3. The method of claim 2 , wherein the footprint of the building is obtained from an existing dataset of building footprints.

4. The method of claim 1 , wherein the (x,y) coordinates define a latitudinal and longitudinal position of the first point, and the (z) coordinates define elevations above sea level.

5. The method of claim 1 , wherein the grouping comprises:
creating, by the processing system, a temporary grid index of the subset of the plurality of points, to produce a plurality of indexed points;
inserting, by the processing system, the plurality of indexed points into a list, wherein the list sorts the plurality of indexed points according to the (z) coordinates; and
determining, by the processing system and based on the list, that the first point belongs to the first cluster.

6. The method of claim 5 , wherein the determining comprises:
calculating, by the processing system, that a difference between a minimum (z) coordinate of the (z) coordinates and a maximum (z) coordinate of the (z) coordinates is below a predefined threshold; and
grouping, by the processing system, all points in the plurality of indexed points into the first cluster in response to the calculating.

7. The method of claim 6 , wherein the predefined threshold is equal to a resolution of the light detection and ranging point cloud.

8. The method of claim 5 , wherein the determining comprises:
calculating, by the processing system, that a difference between a minimum (z) coordinate of the (z) coordinates and a maximum (z) coordinate of the (z) coordinates is above a predefined threshold;
adding, by the processing system, the first point to the first cluster;
adding, by the processing system, a first set of additional points of the plurality of indexed points to the first cluster, wherein each point in the first set of additional points is a neighbor of the first point, and wherein a difference between a (z) coordinate of each additional point of the first set of additional points and the z coordinate of the first point is below the predefined threshold;
iteratively adding, by the processing system, subsequent sets of additional points of the plurality of indexed points to the first cluster, wherein each point in the subsequent sets of additional points is a neighbor of a point that is already in the first cluster, and wherein a difference between a (z) coordinate of each additional point of the subsequent sets of additional points and the z coordinate of the point that is already in the first cluster is below the predefined threshold; and
returning, by the processing system, the first cluster as a final cluster when the iteratively adding is completed.

9. The method of claim 8 , wherein the iteratively adding is completed when there are no points remaining in the plurality of indexed points that are neighbors of any point that is already in the first cluster and for which the difference between the (z) coordinate and the (z) coordinate of the any point falls below the predefined threshold.

10. The method of claim 1 , further comprising:
grouping, by the processing system, a second point in the subset into a second cluster according to at least one of: a (z) coordinate of the second point or a gradient to which the second point belongs, wherein the second cluster comprises a second further subset of the subset, and wherein differences in gradients of unit vectors associated with points in the second further subset all fall below a predefined threshold difference;
constructing, by the processing system, a second prism formed by the second cluster, wherein the plurality of connected prisms includes the second prism.

11. The method of claim 10 , wherein the grouping the second point in the subset into the second cluster comprises:
creating, by the processing system, a temporary grid index of the subset of the plurality of points, to produce a plurality of indexed points;
computing, by the processing system and for each point of the plurality of indexed points, a unit vector perpendicular to a plane of each point, to produce a plurality of unit vectors; and
determining, by the processing system and based on a unit vector of the plurality of unit vectors corresponding to the second point, that the second point belongs to the second cluster.

12. The method of claim 11 , wherein the determining comprises:
calculating, by the processing system, that a difference between a smallest gradient among the plurality of unit vectors and a largest gradient among the plurality of unit vectors is below a predefined threshold; and
grouping, by the processing system, all points in the plurality of indexed points into the second cluster in response to the calculating.

13. The method of claim 12 , wherein the predefined threshold is equal to a resolution of the light detection and ranging point cloud.

14. The method of claim 11 , wherein the determining comprises:
calculating, by the processing system, that a difference between a smallest gradient among the plurality of unit vectors and a largest gradient among the plurality of unit vectors is above a predefined threshold;
adding, by the processing system, the second point to a preliminary cluster;
adding, by the processing system, a first set of additional points of the plurality of indexed points to the second cluster, wherein each point in the first set of additional points is a neighbor of the second point, and wherein a difference between a gradient of the unit vector associated with each additional point of the first set of additional points and a gradient of the unit vector associated with the second point is below the predefined threshold;
iteratively adding, by the processing system, subsequent sets of additional points of the plurality of indexed points to the second cluster, wherein each point in the subsequent sets of additional points is a neighbor of a point that is already in the second cluster, and wherein a difference between a gradient of a unit vector associated with each additional point of the subsequent sets of additional points and the gradient of the unit vector associated with the point that is already in the second cluster is below the predefined threshold; and
returning, by the processing system, the second cluster as

Assignees

• At & T Ip I Lp

Inventors

• Kanza Yaron
• Brown Philip
• Kounev Velin
• Jotshi Arun

Classifications

• G06V10/763

  Non-hierarchical techniques, e.g. based on statistics of modelling distributions · CPC title

• G06V20/176

  Urban or other man-made structures · CPC title

• G01S17/42

  Simultaneous measurement of distance and other co-ordinates (indirect measurement G01S17/46) · CPC title

• G01S17/89

  for mapping or imaging · CPC title

• G06F18/23211

  with adaptive number of clusters · CPC title