Building segmentation for densely built urban regions using aerial LIDAR data

• US 8,224,097 B2
• Filed: 06/12/2008
• Issued: 07/17/2012
• Est. Priority Date: 06/12/2008
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Matei, Bogdan Calin Mihai, Samarasekera, Supun, Kim, Janet Yonga, Karney, Charles Fielding Finch, Sawhney, Harpreet Singh, Kumar, Rakesh
• Primary Examiner(s): Repko, Jason M
• Assistant Examiner(s): Dunphy, David F
• Application Number:
  US12/138,027
• Publication Number:
  US 20090310867A1
• Time in Patent Office: 1,496 Days
• Field of Search: None
• US Class Current: 382/204
• CPC Class Codes: G06T 2207/10032 Satellite or aerial image; Remote sensing
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 7/11 Region-based segmentation

Abstract

A method for extracting a 3D terrain model for identifying at least buildings and terrain from LIDAR data is disclosed, comprising the steps of generating a point cloud representing terrain and buildings mapped by LIDAR; classifying points in the point cloud, the point cloud having ground and non-ground points, the non-ground points representing buildings and clutter; segmenting the non-ground points into buildings and clutter; and calculating a fit between at least one building segment and at least one rectilinear structure, wherein the fit yields the rectilinear structure with the fewest number of vertices. The step of calculating further comprises the steps of (a) calculating a fit of a rectilinear structure to the at least one building segment, wherein each of the vertices has an angle that is a multiple of 90 degrees; (b) counting the number of vertices; (c) rotating the at least one building segment about an axis by a predetermined increment; and (d) repeating steps (a)-(c) until a rectilinear structure with the least number of vertices is found.

Claims

1. A method for automatically extracting a 3D terrain model for identifying at least buildings and terrain from light detection and ranging (LIDAR) data, comprising the steps of:

generating a point cloud representing terrain and buildings mapped by LIDAR;

classifying points in the point cloud, the point cloud having ground and non-ground points, the non-ground points representing buildings and clutter;

segmenting the non-ground points into buildings and clutter;

calculating a fit between at least one building segment and at least one rectilinear structure by rotating the at least one building segment incrementally, wherein the calculating is performed repeatedly until the fit yields the rectilinear structure with the fewest number of vertices.

2. The method of claim 1, wherein said step of calculating further comprises the steps of:

(a) calculating a fit of a rectilinear structure to the at least one building segment, wherein each of the vertices has an angle that is a multiple of 90 degrees; and

(b) counting the number of vertices.

3. The method of claim 1, further comprising the step of rendering the orientations of building segments to be consistent with neighboring buildings.

4. The method of claim 3, further comprising the steps of, before the step of calculating:

extracting contours for each of the building segments.

5. The method of claim 4, wherein a contour is extracted using a ball pivoting algorithm.

6. The method of claim 1, wherein said step of segmenting the non-ground points into buildings and clutter further comprises the steps of:

estimating local surfels of the non-ground points at an adaptive scale and forming the volumetric regions into voxels at the local surfels;

grouping non-ground surfels into coarse regions using a bottom up region growing technique;

estimating planes for each course region;

refining the location of the planes by fitting points to the planes by employing an expectation maximization technique; and

segmenting building regions from the planes so as to enforce neighborhood constraints between planes and ensure sharp boundaries between regions by employing a loopy belief propagation (BP) framework.

7. The method of claim 6, wherein the voxels that are not grouped into any of the planes are removed as clutter.

8. The methods of claim 6, wherein said step of estimating local surfels further comprises the step of computing the local covariance at multiple scales at each of the voxel which contains 3D data.

9. The method of claim 6, wherein said step of grouping non-ground surfels into coarse regions further comprises the steps of:

determining a histogram of local normal orientation and computing a measurement of local planarity by integrating normal direction cues over a large area; and

starting region growing from the voxels which have a higher degree of local planarity,

wherein a voxel from the voxels is joined into a proposed region if local planar regions are coherent.

10. The method of claim 6, wherein said step of estimating planes for each course region further comprises the step of enforcing a constraint that joined surfels are either planar or quadric surfaces, so that the planar surfaces are fit to the course regions.

11. The method of claim 6, wherein the expectation maximization technique includes iteratively fitting points to planes and declaring points not fitting on any planes as outliers until there is no more changes to the assigned points on planes or outliers.

12. The method of claim 1, wherein said step of classifying points in the point cloud further comprises the steps of:

performing an initial filtering out of points in the point cloud wherein high points are removed, the remaining points being putative ground points, the high points being those points that are higher than a maximum predetermined threshold;

estimating surfels for each of the putative ground points;

grouping ground surfels into planar regions using bottom-up region growing;

constructing a hole-free terrain; and

classifying points as ground and non-ground, wherein non-ground points are those which are higher than a predetermined threshold above the terrain.

13. The method of claim 12, wherein bottom-up region growing comprises the step of finding those neighboring surfels whose normals are the same and whose origins are consistent such that it can be concluded that the neighboring surfels belong to the same plane, and repeating said step of finding wherein until sharp edges are reached.

14. A system for automatically extracting a 3D terrain model for identifying at least buildings and terrain from light detection and ranging (LIDAR) data, comprising:

a processor being configured for;

generating a point cloud representing terrain and buildings mapped by LIDAR;

classifying points in the point cloud, the point cloud having ground and non-ground points, the non-ground points representing buildings and clutter;

segmenting the non-ground points into buildings and clutter; and

calculating a fit between at least one building segment and at least one rectilinear structure by rotating the at least one building segment incrementally, wherein the calculating is performed repeatedly until the fit yields the rectilinear structure with the fewest number of vertices.

15. The system of claim 14, wherein said step of fitting further comprises the steps of:

(a) calculating a fit of a rectilinear structure to the at least one building segment, wherein each of the vertices has an angle that is a multiple of 90 degrees; and

(b) counting the number of vertices.

16. The system of claim 14, further comprising the step of rendering the orientations of building segments to be consistent with neighboring buildings.

17. The system of claim 16, further comprising the steps of, before the step of calculating:

extracting contours for each of the building segments.

18. The system of claim 14, wherein said step of segmenting the non-ground points into buildings and clutter further comprises the step of:

estimating local surfels of the non-ground points at an adaptive scale and forming the volumetric regions into voxels at the local surfels;

grouping non-ground surfels into coarse regions using a bottom up region growing technique;

estimating planes for each course region;

refining the location of the planes by fitting points to the planes by employing an expectation maximization technique; and

segmenting building regions from the planes so as to enforce neighborhood constraints between planes and ensure sharp boundaries between regions by employing a loopy belief propagation (BP) framework.

19. The system of claim 14, wherein said step of classifying points in the point cloud further comprises the steps of:

performing an initial filtering out of points in the point cloud wherein high points are removed, the remaining points being putative ground points, the high points being those points that are higher than a maximum predetermined threshold;

estimating surfels for each of the putative ground points and forming the volumetric regions into voxels at the local surfels;

grouping ground surfels into planar regions using bottom-up region growing;

constructing a hole-free terrain; and

classifying points as ground and non-ground, wherein non-ground points are those which are higher than a predetermined threshold above the terrain.

20. A non-transitory computer-readable medium carrying one or more sequences for automatically extracting a 3D terrain model for identifying at least buildings and terrain from light detection and ranging (LIDAR) data, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the step of:

generating a point cloud representing terrain and buildings mapped by LIDAR;

classifying points in the point cloud, the point cloud having ground and non-ground points, the non-ground points representing buildings and clutter;

segmenting the non-ground points into buildings and clutter; and

calculating a fit between at least one building segment and at least one rectilinear structure by rotating the at least one building segment incrementally, wherein the calculating is performed repeatedly until the fit yields the rectilinear structure with the fewest number of vertices.

21. The computer readable medium of claim 20, wherein said step of fitting further comprises the steps of:

(a) calculating a fit of a rectilinear structure to the at least one building segment, wherein each of the vertices has an angle that is a multiple of 90 degrees; and

(b) counting the number of vertices.

22. The computer readable medium of claim 20, further comprising the step of rendering the orientations of building segments to be consistent with neighboring buildings.

23. The computer readable medium of claim 20, further comprising the steps of, before the step of calculating:

extracting contours for each of the building segments.

24. The computer readable medium of claim 20, wherein said step of segmenting the non-ground points into buildings and clutter further comprises the step of:

estimating local surfels of the non-ground points at an adaptive scale and forming the volumetric regions into voxels at the local surfels;

grouping non-ground surfels into coarse regions using a bottom up region growing technique;

estimating planes for each course region;

refining the location of the planes by fitting points to the planes by employing an expectation maximization technique; and

segmenting building regions from the planes so as to enforce neighborhood constraints between planes and ensure sharp boundaries between regions by employing a loopy belief propagation (BP) framework.

25. The computer readable medium of claim 20, wherein said step of classifying points in the point cloud further comprises the steps of:

performing an initial filtering out of points in the point cloud wherein high points are removed, the remaining points being putative ground points, the high points being those points that are higher than a maximum predetermined threshold;

estimating surfels for each of the putative ground points;

grouping ground surfels into planar regions using bottom-up region growing;

constructing a hole-free terrain; and

classifying points as ground and non-ground, wherein non-ground points are those which are higher than a predetermined threshold above the terrain.