System and Method for Extracting Features from Data Having Spatial Coordinates

• US 20130096886A1
• Filed: 03/31/2011
• Published: 04/18/2013
• Est. Priority Date: 03/31/2010
• Status: Abandoned Application

• Current Assignee: Andrey Zaretskiy, Borys Vorobyov, Dmytro Gordon, Oleksandr Monastyrev, Yuriy Monastyrev
• Original Assignee: Andrey Zaretskiy, Borys Vorobyov, Dmytro Gordon, Oleksandr Monastyrev, Yuriy Monastyrev
• Inventors: Monastyrev, Oleksandr, Zaretskiy, Andrey, Vorobyov, Borys, Gordon, Dmytro, Monastyrev, Yuriy
• Application Number:
  US13/638,912
• Publication Number:
  US 20130096886A1
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G01C 11/00 Photogrammetry or videogrammetry, e.g. stereogrammetry; Photographic surveying
• CPC Class Codes: G06F 30/13 Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/11 Region-based segmentation

Abstract

Systems and methods are provided for extracting various features from data having spatial coordinates. The systems and methods may identify and extract data points from a point cloud, where the data points are considered to be part of the ground surface, a building, or a wire (e.g. power lines). Systems and methods are also provided for extracting wires from a noisy environment, for separating buildings from attached vegetation, for reconstructing a building, and for classifying data points according to their relief and terrain characteristics. The extraction of the features may be carried out automatically by a computing device.

Claims

1. A method for a computing device to extract a ground surface from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device establishing a grid of tiles over the set of data points, each of the tiles of a predetermined dimension;

the computing device identifying a data point with the lowest height in each of the tiles;

the computing device forming a triangulated surface using the lowest height data points, wherein the triangulated surface is the ground surface.

2. The method of claim 1 wherein the tile dimension is of a form T×

T, where the length T is greater than a length of a base of a building, the building also represented by a subset of the set of data points.

3. The method of claim 1 wherein a Delaunay triangulation algorithm is used to form the triangulated surface.

4. The method of claim 1 further comprising the computing device identifying additional data points as ground surface points, the method further comprising:

identifying data points that are within a horizontal distance R from any one of the lowest height data points, the identified data points grouped as a set of R-points;

removing from the set of R-points any data points that are located above the triangulated surface by a predetermined height MaxH and any data points that are located below a predetermined height MinH; and

wherein at least one of the remaining R-points in the set of R-points are classified as part of the ground surface.

5. The method of claim 4 further comprising, for the at least one of the remaining R-points in the set of R-points:

the computing device determining if a triangle in the triangulated surface, that is below the remaining R-point, is longer than the tile dimension T and if so;

the computing device determining an angle A2 subtended between a line and the horizontal plane, the line connecting the remaining R-point to a ground point closest to the remaining R-point; and

if the angle A2 is less than an elevation angle Maxα

, then the computing device classifying the remaining R-point as part of the ground surface.

6. The method of claim 4 further comprising, for the at least one of the remaining R-points in the set of R-points:

the computing device determining if a triangle in the triangulated surface, that is below the remaining R-point, is longer than the tile dimension T and if not;

determining an angle A1 subtended between a line and the triangulated surface, the line connecting the remaining R-point to a ground point closest to the remaining R-point;

determining an angle A2 subtended between the line and the horizontal plane; and

if the smaller of the angle A1 and the angle A2 is less than an elevation angle Maxα

, then the computing device classifying the remaining R-point as part of the ground surface.

7. The method of claim 4 further comprising the computing device re-forming a triangulated surface by combining the data points in the triangulated surface and the at least one of the remaining R-points classified as part of the ground surface, wherein the re-formed triangulated surface is the ground surface.

8. The method of claim 1 further comprising the computing device computing an average height of the data points of the ground surface to filter out irregularities.

9. The method of claim 5 wherein Maxα

is less than 2°

.

10. (canceled)

11. A method for a computing device to extract a building model from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device obtaining a set of ground surface points from the set of data points, the ground surface points classified as base points;

the computing device applying a triangulation algorithm to the data points that are not the base points to construct a triangulated surface;

the computing device removing edges from the triangulated surface that have at least one point classified as a base point;

the computing device re-applying the triangulation algorithm to the triangulated surface to generate one or more subsets of triangulated and interconnected paints;

the computing device identifying a large subset defined by a plan-view area of the large subset being above a predetermined threshold; and

the computing device classifying the large subset as the building model.

12-19. -19. (canceled)

20. A method for a computing device to remove data points representing vegetation from a set of data points, the set of data points with three-dimensional spatial coordinates of at least the vegetation and a ground surface, the method comprising:

the computing device obtaining a set of ground surface points and non-ground surface points from the set of data points;

the computing device applying a triangulation algorithm to the non-ground surface points to construct a triangulated surface;

the computing device removing edges from the triangulated surface that are longer than a predetermined length and are at an angle greater then 45°

above the horizontal plane; and

the computing device removing small subsets having a plan-view area smaller than a predetermined threshold.

21-22. -22. (canceled)

23. A method for a computing device to construct a polygonal building model from a set of data points with three-dimensional spatial coordinates of a building, the method comprising:

the computing device computing a histogram of the number of data points along a vertical axis;

the computing device classifying a height of each local maximum of the histogram as a height of a separate building layer;

the computing device applying a triangulation algorithm to the data points lying within each of the separate building layers to construct a triangulated layer correspond to each separate building layer;

the computing device removing long edges, that are longer than a threshold, from each of the triangulated layers;

the computing device forming a boundary line for each triangulated layer, the boundary line formed from the outer edges of each triangulated layer; and

for each triangulation layer, the computing device projecting the boundary line downwards to a triangulated layer below to generate walls of the polygonal building model.

24-34. -34. (canceled)

35. A method for a computing device to extract a wire from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device obtaining ground surface points, representative of the ground surface, and non-ground surface points from the set of data points;

the computing device applying a triangulation algorithm to the non-ground surface points to construct a triangulated surface;

the computing device removing points from the triangulated surface that are lower than a predetermined height from the ground surface;

the computing device removing points from the triangulated surface that are sparsely located;

the computing device removing edges from the triangulated surface that have a length greater than a predetermined length Dmin;

the computing device identifying a largest subset of interconnected data points in the triangulated surface;

the computing device computing a line through the largest subset; and

wherein the line is the wire.

36-45. -45. (canceled)

46. A method for a computing device to extract a wire from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device constructing an XYZ frame of reference comprising an origin O at an end of a known wire segment represented by line L_R, a Y axis collinear with the line L_R, and a plane XOY that is parallel to a ground surface;

computing a first polygon and a second polygon both coplanar with a plane XOZ and both having the origin O at their centre, the second polygon larger than the first polygon;

computing a line S of finite length extending from the origin O and collinear with the line L_R;

computing a number of data points n1 that project on to the line S and project on to the plane XOZ within a perimeter of the first polygon;

computing a number of data points n2 that project on to the line S and project on to plane XOZ within a perimeter of the second polygon;

determining if the line S represents a segment of the wire by using the number of points n1 and n2; and

if so, forming the wire by combing the lines S and L_R

47-52. -52. (canceled)

53. A method for a computing device to classify a relief of a ground surface from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device separating the set of data points into horizontal tiles;

the computing device forming a triangulated surface comprised of the lowest point from each of the horizontal tiles, the triangulated surface identified as the ground surface; and

the computing device classifying the relief of the ground surface based on computed inclination angles of each triangle within the ground surface relative to a horizontal plane.

54-62. -62. (canceled)

63. A method for a computing device to classify a ground surface by vegetation from a set of data points with three-dimensional spatial coordinates, the method comprising:

the computing device separating the set of data points into horizontal tiles;

the computing device forming a triangulated surface comprised of the lowest point from each of the horizontal tiles, the triangulated surface identified as the ground surface;

computing for each tile a standard deviation of the data points'"'"' heights relative to the ground surface; and

the computing device classifying the ground surface by vegetation based on a percentage of tiles having the standard deviation above a predetermined height Hdev.

64-70. -70. (canceled)

71. A method for extracting features from a data set representing spatial coordinates, the method comprising:

extracting an approximate ground surface from the data;

characterising the relief and terrain of the approximate ground surface;

extracting an accurate ground surface based on the characterised relief and terrain;

extracting building points from data located above the accurate ground surface; and

,

reconstructing a building model from the building points.