Building datum extraction from laser scanning data

Patent metadata

Field	Value
Publication number	US-9811714-B2
Application number	US-201414465569-A
Country	US
Kind code	B2
Filing date	Aug 21, 2014
Priority date	Aug 28, 2013
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

A method, apparatus, system, and computer program product provide the ability to extract level information and reference grid information from point cloud data. Point cloud data is obtained and organized into a three-dimensional structure of voxels. Potential boundary points are filtered from the boundary cells. Level information is extracted from a Z-axis histogram of the voxels positioned along the Z-axis of the three-dimensional voxel structure and further refined. Reference grid information is extracted from an X-axis histogram of the voxels positioned along the X-axis of the three-dimensional voxel structure and a Y-axis histogram of the voxels positioned along the Y-axis of the three-dimensional voxel structure and further refined.

First claim

What is claimed is:

1. A computer-implemented method for extracting level and reference grid information for a building interior from point cloud data, comprising:
obtaining point cloud data, of the building interior, comprising laser scanning points of a building;
organizing the point cloud data into a three-dimensional structure of voxels, the three-dimensional structure consisting of an X-axis, Y-axis, and Z-axis, wherein each voxel represents a value on a regular grid in three-dimensional space;
generating an X-axis histogram by accumulating the voxels positioned along the X-axis of the three-dimensional voxel structure;
generating a Y-axis histogram by accumulating the voxels positioned along the Y-axis of the three-dimensional voxel structure;
generating a Z-axis histogram by accumulating the voxels positioned along the Z-axis of the three-dimensional voxel structure;
extracting level information from the Z-axis histogram for an interior structure of the building interior; and
extracting reference grid information of the interior structure of a floor plan for the building interior from the X-axis histogram and the Y-axis histogram, wherein peaks of the X-axis histogram and Y-axis histogram are used to identify a wall location or location marker of a reference grid.

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

3. The computer-implemented method of claim 1 further comprising:
extracting a principal direction of the point cloud data by determining X-axis, Y-axis, and Z-axis directions of the point cloud data; and
transforming the point cloud data such that a front face of the building is parallel to a plane defined by the X-axis and Z-axis or a plane defined by the Y-axis and Z-axis;
wherein the transformed point cloud data is organized into the three-dimensional structure of voxels.

4. The computer-implemented method of claim 1 further comprising determining one or more planes of the point cloud data wherein the Z-axis of the point cloud is parallel to the plane containing the greatest total number of laser scanning points.

5. The computer-implemented method of claim 1 further comprising:
determining one or more planes of the point cloud data;
generating a Gaussian sphere map f[α,β] by counting a total number of laser scanning points for the one or more planes with a different normal angle [α,β], wherein α is a first normal angle and β is a second normal angle;
selecting the Z-axis to be parallel to a direction of one or more of the one or more planes with the greatest total number of laser scanning points, and the X-axis and Y-axis to each be parallel to a separate plane with a normal angle orthogonal with the normal angle of the one or more planes parallel to the Z-axis.

6. The computer-implemented method of claim 1 wherein:
the voxels along the Z-axis contain at least one laser scanning point; and
a peak in the Z-axis histogram identifies a rough location of the level.

7. The computer-implemented method of claim 6 wherein a point x i in the Z-axis histogram is identified as a peak if:
i) x i is greater than or equal to the mean m of neighboring points around x i ;
ii) an absolute value of x i minus m is greater than or equal to the standard deviation s of the neighboring points around the peak x i multiplied by a value h predefined by the user;
iii) s is greater than or equal to a standard deviation threshold τ s ; and
iv) x i is greater than or equal to an area threshold a.

8. The computer-implemented method of claim 1 further comprising refining the extracted level information by plane sweeping.

9. The computer-implemented method of claim 8 further comprising:
moving two parallel sweep planes defined by the X-axis and Y-axis in successive positions along the Z-axis of the point cloud data in a peak voxel, the two parallel sweep planes separated by an interval value in the Z-axis direction;
calculating the total number of laser scanning points within the interval value of the two parallel sweep planes for each position along the Z-axis;
wherein the position along the Z-axis with the greatest total number of laser scanning points is selected as a refined level location.

10. The computer-implemented method of claim 1 wherein the building is segmented by level and the reference grid is generated for each level.

11. The computer-implemented method of claim 10 wherein:
the X-axis histogram comprises voxels along the X-axis that contain at least one laser scanning point and the Y-axis histogram comprises voxels along the Y-axis that contain at least one laser scanning point; and
a peak in the X-axis histogram or Y-axis histogram identifies a rough wall location on the reference grid.

12. The computer-implemented method of claim 1 further comprising refining the extracted reference grid information by line sweeping.

13. The computer-implemented method of claim 12 further comprising:
moving two parallel sweep lines in successive positions along the X-axis of the point cloud data in a peak voxel, the two parallel sweep lines separated by an interval value in the X-axis direction;
calculating the total number of laser scanning points within the interval value of the two parallel sweep lines for each position along the X-axis, wherein the position along the X-axis with the greatest total number of laser scanning points is selected as a refined wall location on the reference grid;
moving two parallel sweep lines in successive positions along the Y-axis of the point cloud data in the peak voxel, the two parallel sweep lines separated by an interval value in the Y-axis direction; and
calculating the total number of laser scanning points within the interval value of the two parallel sweep lines for each position along the Y-axis, wherein the position along the Y-axis with the greatest total number of laser scanning points is also selected as a refined wall location on the reference grid.

14. The computer-implemented method of claim 1 further comprising:
removing floor and ceiling points from the point cloud data;
generating a height histogram of the point cloud data and removing laser scanning points above a maximum value on the height histogram;
retaining voxels with neighboring voxels that consist of laser scanning points that form a plane parallel to the Z-axis;
generating a two-dimensional X-Y histogram of the retained voxels that contain at least one laser scanning point and removing voxels with a total number of laser scanning points below a minimum value; and
extracting wall locations from the two-dimensional X-Y histogram.

15. An apparatus for extracting level and reference grid information for a building interior 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 point cloud data, of the building interior, comprising laser scanning points of a building;
(2) organize the point cloud data into a three-dimensional voxel structure consisting of an X-axis, Y-axis, and Z-axis, wherein each voxel represents a value on a regular grid in three-dimensional space;
(3) generate an X-axis histogram by accumulating the voxels positioned along the X-axis of the three-dimensional voxel structure;
(4) generate a Y-axis histogram by accumulating the voxels positioned along the Y-axis of the three-dimensional voxel structure;
(5) generate a Z-axis histogram by accumulating the voxels positioned along the Z-axis of the three-dimensional voxel structure;
(

Assignees

• Autodesk Inc

Inventors

• Fu Yan

Classifications

• G06K9/00201 Primary

  Physics · mapped topic

• G06V20/64 Primary

  Three-dimensional [3D] objects · CPC title