Segmentation of ground-based laser scanning points from urban environment

• US 9,396,545 B2
• Filed: 02/17/2012
• Issued: 07/19/2016
• Est. Priority Date: 06/10/2010
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Fu, Yan, Yang, Jin
• Primary Examiner(s): Huynh, Phuong
• Application Number:
  US13/399,158
• Publication Number:
  US 20130218472A1
• Time in Patent Office: 1,614 Days
• Field of Search: 702/5
• US Class Current: 1/1
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 7/4802 using analysis of echo signal for target characterisation; Target signature; Target cross-section
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 20/176 Urban or other man-made structures

Abstract

A method, apparatus, system, and article of manufacture provide object descriptors for objects in point cloud data for an urban environment by segmenting the point cloud data. Point cloud data for an urban environment is obtained using a ground-based laser scanner. Terrain points are filtered out from the point cloud data using ground filtering. The point cloud data is then segmented into two or more blocks. Objects that lie on neighboring adjacent blocks are combined. Object descriptors for the combined objects are then provided (e.g., to the user or a program used by the user).

Claims

1. A computer-implemented method for providing object descriptors for objects in point cloud data for an urban environment by segmenting the point cloud data in a computer that is programmed to perform:

obtaining, using a ground-based laser scanner, the point cloud data, wherein the point cloud data is for the urban environment;

in a pre-process phase, filtering out, in the computer, terrain points from the point cloud data using ground filtering;

after the pre-process phase, segmenting, in the computer, the point cloud data into two or more blocks;

combining, in the computer, objects that lie on neighboring adjacent blocks of the two or more blocks based on cell continuity;

providing, in the computer, object descriptors for the combined objects;

utilizing, in the computer, the object descriptors to process the point cloud data, and facilitate and output a scene interpretation of the urban environment.

2. The computer-implemented method of claim 1, wherein the ground filtering comprises:

subdividing the point cloud data into two or more patches; and

filtering out the terrain points in each patch one patch at a time.

3. The computer-implemented method of claim 2, wherein:

a size of each of the two or more patches is defined wherein each patch contains at least one of the terrain points; and

a length and width of each patch is adaptively set based on a mean distance of the point cloud data.

4. The computer-implemented method of claim 2, wherein the filtering out the terrain points in each patch one patch at a time comprises performing the following for each patch:

removing outlier points;

classifying ground points and non-ground points; and

filtering out the ground points.

5. The computer-implemented method of claim 4, wherein the removing outlier points comprises:

constructing nearest neighborhood information for all of the points in patch P;

defining a mean distance of the nearest neighborhood information for each point in patch P;

examining each point in patch P; and

removing the point as an outlier point if a height of the point is above or below a threshold amount from the mean distance.

6. The computer-implemented method of claim 4, wherein the classifying ground points and non-ground points comprises:

building a hierarchical structure of two or more cells for the patch being filtered, wherein the hierarchical structure ranges from coarse to fine;

for each level from coarse to fine;

obtaining lowest cell points of a current level as representative points of a coarse terrain surface;

using the lowest cell points to calculate an approximate planar surface;

calculating a weighted residual from the approximate planar surface to each point in each cell;

iteratively filtering out points that have a weighted residual above a threshold as non-ground points;

updating the approximate planar surface using the weighted residuals for points that have not been filtered out; and

interpolating a z-measurement of each cell based on the updated approximate planar surface; and

classifying all of the remaining points by comparing the z-measurement of each remaining point with an interpolated z-measurement of a cell center of the finest level, wherein if the z-measurement of each remaining point is a threshold higher than the interpolated z-measurement of the cell center, then the point is classified as a non-ground point, and if not, the point is classified as a ground point.

7. The computer-implemented method of claim 1, wherein the segmenting comprises removing additional ground points by:

subdividing the point cloud data into the two or more blocks;

distributing points from the point cloud data to each of the two or more blocks;

organizing each block into a three-dimensional (3D) cubic grid structure having two or more cells;

for each cell of the two or more cells;

determining if the cell is a ground cell based on a grounded plane;

if the cell is a ground cell, propagating the cell to adjacent cells of the two or more cells in order to create a ground cell cluster;

saving the ground cell cluster and the grounded plane; and

filtering out the ground cell cluster.

8. The computer-implemented method of claim 1, wherein:

the point cloud data is subdivided into the two or more blocks;

points from the point cloud data are distributed to each of the two or more blocks;

each block is organized into a three-dimensional (3D) cubic grid structure having two or more cells;

subsequent to filtering out the terrain points, remaining points of the point cloud data represent the objects;

the segmenting the point cloud data comprises;

selecting a random non-empty cell from the two or more cells;

propagating the non-empty cell to continuous neighboring cells; and

if the non-empty cell is a boundary cell of one of the two or more blocks, storing an object index for the object containing the boundary cell.

9. The computer-implemented method of claim 1, wherein the combining comprises:

searching for objects that lie on neighboring adjacent blocks by determining if one cell of a first object is in one of 3*3 neighboring cells of a second object; and

merging the first object and the second object when both the first object and the second object lie on neighboring adjacent blocks.

10. The computer-implemented method of claim 9, wherein the merging comprises:

utilizing an array to mark that the first object will be merged to the second object thereby creating an object link; and

merging the first object into the second object based on the object link.

11. An apparatus for providing object descriptors for objects in point cloud data for an urban environment by segmenting the point cloud data in a computer system comprising:

(a) a computer having a memory; and

(b) an application executing on the computer, wherein the application is configured to;

(1) obtain, using a ground-based laser scanner, the point cloud data, wherein the point cloud data is for the urban environment;

(2) in a pre-process phase, filter out terrain points from the point cloud data using ground filtering;

(3) after the pre-process phase, segment the point cloud data into two or more blocks;

(4) combine objects that lie on neighboring adjacent blocks of the two or more blocks based on cell continuity;

(5) provide object descriptors for the combined objects;

(6) utilize the object descriptors to process the point cloud data, and facilitate an output a scene interpretation of the urban environment.

12. The apparatus of claim 11, wherein the ground filtering comprises:

subdividing the point cloud data into two or more patches; and

filtering out the terrain points in each patch one patch at a time.

13. The apparatus of claim 12, wherein:

a size of each of the two or more patches is defined wherein each patch contains at least one of the terrain points; and

a length and width of each patch is adaptively set based on a mean distance of the point cloud data.

14. The apparatus of claim 12, wherein the application is configured to filter out the terrain points in each patch one patch at a time by performing the following for each patch:

removing outlier points;

classifying ground points and non-ground points; and

filtering out the ground points.

15. The apparatus of claim 14, wherein the removing outlier points comprises:

constructing nearest neighborhood information for all of the points in patch P;

defining a mean distance of the nearest neighborhood information for each point in patch P;

examining each point in patch P; and

removing the point as an outlier point if a height of the point is above or below a threshold amount from the mean distance.

16. The apparatus of claim 14, wherein the classifying ground points and non-ground points comprises:

building a hierarchical structure of two or more cells for the patch being filtered, wherein the hierarchical structure ranges from coarse to fine;

for each level from coarse to fine;

obtaining lowest cell points of a current level as representative points of a coarse terrain surface;

using the lowest cell points to calculate an approximate planar surface;

calculating a weighted residual from the approximate planar surface to each point in each cell;

iteratively filtering out points that have a weighted residual above a threshold as non-ground points;

updating the approximate planar surface using the weighted residuals for points that have not been filtered out; and

interpolating a z-measurement of each cell based on the updated approximate planar surface; and

classifying all of the remaining points by comparing the z-measurement of each remaining point with an interpolated z-measurement of a cell center of the finest level, wherein if the z-measurement of each remaining point is a threshold higher than the interpolated z-measurement of the cell center, then the point is classified as a non-ground point, and if not, the point is classified as a ground point.

17. The apparatus of claim 11, wherein the application is configured to segment by removing additional ground points by:

subdividing the point cloud data into the two or more blocks;

distributing points from the point cloud data to each of the two or more blocks;

organizing each block into a three-dimensional (3D) cubic grid structure having two or more cells;

for each cell of the two or more cells;

determining if the cell is a ground cell based on a grounded plane;

if the cell is a ground cell, propagating the cell to adjacent cells of the two or more cells in order to create a ground cell cluster;

saving the ground cell cluster and the grounded plane; and

filtering out the ground cell cluster.

18. The apparatus of claim 11, wherein:

the point cloud data is subdivided into the two or more blocks;

points from the point cloud data are distributed to each of the two or more blocks;

each block is organized into a three-dimensional (3D) cubic grid structure having two or more cells;

subsequent to filtering out the terrain points, remaining points of the point cloud data represent the objects;

the segmenting the point cloud data comprises;

selecting a random non-empty cell from the two or more cells;

propagating the non-empty cell to continuous neighboring cells; and

if the non-empty cell is a boundary cell of one of the two or more blocks, storing an object index for the object containing the boundary cell.

19. The apparatus of claim 11, wherein the application is configured to combine by:

searching for objects that lie on neighboring adjacent blocks by determining if one cell of a first object is in one of 3*3 neighboring cells of a second object; and

merging the first object and the second object when both the first object and the second object lie on neighboring adjacent blocks.

20. The apparatus of claim 19, wherein the application is configured to merge by:

utilizing an array to mark that the first object will be merged to the second object thereby creating an object link; and

merging the first object into the second object based on the object link.