Outline approximation for point cloud of building

Patent metadata

Field	Value
Publication number	US-9189862-B2
Application number	US-201314012702-A
Country	US
Kind code	B2
Filing date	Aug 28, 2013
Priority date	Jun 10, 2010
Publication date	Nov 17, 2015
Grant date	Nov 17, 2015

Abstract

A method, apparatus, system, and computer program product provide the ability to model a polyline boundary from point cloud data. Point cloud data is obtained and boundary cells are extracted. Potential boundary points are filtered from the boundary cells. Line segments are extracted from the potential boundary points and refined. A regularized polygon is obtained by intersecting the refined line segments.

First claim

What is claimed is:

1. A computer-implemented method for modeling a polyline boundary from point cloud data, comprising:
obtaining, into a memory of a computer, the point cloud data;
extracting, using a processor in the computer, one or more boundary cells from the point cloud data;
filtering, using the processor in the computer, one or more potential boundary points from the one or more boundary cells;
extracting, using the processor in the computer, one or more line segments from the one or more potential boundary points;
refining, using the processor in the computer, the one or more line segments;
obtaining, using the processor in the computer, a regularized polygon by intersecting the one or more refined line segments; and
utilizing, using the processor in the computer, the regularized polygon to reconstruct a building in a building information model.

2. The computer-implemented method of claim 1 , wherein:
the point cloud data is obtained using a laser scanner; and
the point cloud data is for a building.

3. The computer-implemented method of claim 1 , wherein:
the one or more boundary cells are extracted by flood filling.

4. The computer-implemented method of claim 3 , wherein the flood filling comprises:
subdividing a two-dimensional bounding box of the point cloud data along an x-direction and a y-direction to form one or more rectangular grids having one or more grid cells;
distributing points of the point cloud to the one or more grid cells; and
ensuring that grid cells of the one or more grid cells that are in a most exterior loop of the one or more grid cells are empty cells.

5. The computer-implemented method of claim 4 , wherein:
the one or more boundary cells are extracted from the one or more grid cells using boundary filling.

6. The computer-implemented method of claim 1 , wherein the filtering comprises filtering through a modified convex hull by:
marking all points located in the one or more boundary cells as the one or more potential boundary points;
for each potential boundary point, fitting a circle to neighboring points and calculating one or more arc ranges between the neighboring points;
for each of the one or more arc ranges that is larger than a threshold and does not contain a point, marking the potential boundary point as a boundary point; and
resampling each of the boundary points in each boundary cell, wherein only boundary points nearest to a boundary grid line compared to that of other boundary points are kept.

7. The computer-implemented method of claim 1 , wherein:
the one or more line segments are extracted using RANdom Sample Consensus (RANSAC).

8. The computer-implemented method of claim 1 , wherein:
the refining is under one or more constraints of parallel and perpendicular segments.

9. The computer-implemented method of claim 8 , wherein the refining comprises:
selecting an initial principal orientation for a first line segment of the one or more line segments; and
adjusting a subsequent line segment of the one or more line segments to be either parallel or orthogonal to the initial principal orientation.

10. The computer-implemented method of claim 9 , wherein:
if the subsequent line segment is within a parallel threshold of being parallel to the first line segment, but a distance between the first line segment and the second line segment is above a distance threshold, then the subsequent line segment is adjusted to be parallel to the first line segment and an orthogonally oriented segment is inserted between the first line segment and the second line segment;
if the subsequent line segment is within the parallel threshold of being parallel to the first line segment, but the distance between the first line segment and the second line segment is below the distance threshold, then the subsequent line segment is adjusted to be parallel to the first line segment and the subsequent line segment is extended or trimmed to merge with the first line segment;
if the subsequent line segment is within a perpendicular threshold of being perpendicular to the first line segment, then the subsequent line segment is adjusted to be perpendicular to the first segment and linked at an intersection point of the first line segment and the subsequent line segment;
if none of the above conditions are satisfied, a third line segment is created and inserted to connect adjacent points of the first line segment and the subsequent line segment.

11. An apparatus for modeling a polyline boundary from 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 the point cloud data into the memory;
(2) extract one or more boundary cells from the point cloud data;
(3) filter one or more potential boundary points from the one or more boundary cells;
(4) extract one or more line segments from the one or more potential boundary points;
(5) refine the one or more line segments;
(6) obtain a regularized polygon by intersecting the one or more refined line segments; and
(7) utilize the regularized polygon to reconstruct a building in a building information model.

12. The apparatus of claim 11 , wherein:
the point cloud data is obtained using a laser scanner; and
the point cloud data is for a building.

13. The apparatus of claim 11 , wherein:
the one or more boundary cells are extracted by flood filling.

14. The apparatus of claim 13 , wherein the flood filling comprises:
subdividing a two-dimensional bounding box of the point cloud data along an x-direction and a y-direction to form one or more rectangular grids having one or more grid cells;
distributing points of the point cloud to the one or more grid cells; and
ensuring that grid cells of the one or more grid cells that are in a most exterior loop of the one or more grid cells are empty cells.

15. The apparatus of claim 14 , wherein:
the one or more boundary cells are extracted from the one or more grid cells using boundary filling.

16. The apparatus of claim 11 , wherein application is configured to filter by filtering through a modified convex hull by:
marking all points located in the one or more boundary cells as the one or more potential boundary points;
for each potential boundary point, fitting a circle to neighboring points and calculating one or more arc ranges between the neighboring points;
for each of the one or more arc ranges that is larger than a threshold and does not contain a point, marking the potential boundary point as a boundary point; and
resampling each of the boundary points in each boundary cell, wherein only boundary points nearest to a boundary grid line compared to that of other boundary points are kept.

17. The apparatus of claim 11 , wherein:
the one or more line segments are extracted using RANdom Sample Consensus (RANSAC).

18. The apparatus of claim 11 , wherein:
the application is configured to refine under one or more constraints of parallel and perpendicular segments.

19. The apparatus of claim 18 , wherein the application is configured to refine by:
selecting an initial principal orientation for a first line segment of the one or more line segments; and
adjusting a subsequent line segment of the one or more line segments to be either parallel or orthogonal to the initial principal orientation.

20. The apparatus of claim 19 , wherein:
if the subsequent line segment is within a parallel threshold of being parallel

Assignees

• Autodesk Inc

Inventors

• Fu Yan

Classifications

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title

• G06T7/0085 Primary

  Physics · mapped topic

• G06T7/13 Primary

  Edge detection · CPC title

• G06V20/64

  Three-dimensional [3D] objects · CPC title