Building Information Modeling is growing more relevant as digital models are not only used during the construction phase but also throughout the building's life cycle. The digital representation of geometric, physical and functional properties enables new methods for planning, execution and operation. Digital models of existing buildings are commonly derived from surveying data such as laser scanning which needs to be processed either manually or automatically throughout various steps. Aligning point clouds along a coordinate system's main axes is a common manual task benefitting subsequent manual and automated processing steps. With the intention of automating the alignment task, we hereby present an enhanced approach based on point density histograms. Our results show that this approach is computationally cheap, robust towards non-uniform point cloud resolutions and clutter as well as easy to integrate into existing BIM modelling software.
Scan to BIM process
Data capturing and preprocessing - Registration - Filtering - Downsampling - Axis-Alignment
Segmentation - Separation into Regions of Interest - Rooms/Sections - Elements
Classification
BIM model fitting - Feature Extraction - Object Classification - Object Registration - Component Identification - Component Creation
The process of automatic BIM model generation from point clouds (scan to BIM) can roughly be subdivided into the phases preprocessing, segmentation, classification and BIM model fitting as outlined in the adapted Figure 1 following Loges & Blankenbach (2017). Data preprocessing generally represents the point cloud processing step performed immediately after data capturing. The general goal of preprocessing is to denoise the point cloud by removing outliers, smoothing out noise and possibly downsampling and transforming it into a suitable format for later computations. Furthermore, this step can also be beneficial for manual modelling and visualization, as preprocessed data eases the modeling of structures, reduces the risk of potential errors and is generally more pleasant to deal with. In this work, we focus on point cloud alignment, as it is most often the first operation done in manual modeling and carries great importance in automated reconstruction. Aligning a point cloud or pose normalization refer to rotating the point cloud such that at least one of the dominant building axes captured with it, is oriented along one of the global coordinate system axes. In the field of automation, the benefits of the alignment process lie in the fact that most data structures which ease point neighborhood lookups during point cloud processing such as voxel grids and octrees use boundary volumes oriented along the global coordinate system axes. Therefore, axis-aligned point clouds ensure optimal compactness and therefore usage of these structures. An example on how proper alignment reduces aliasing artifacts which might otherwise occur for voxel-based feature extraction is illustrated in Figure 2. Whereas in the aligned point cloud edges derived from the voxel-wise scatter values are clearly visible, edges in the unaligned point cloud are harder to identify and suffer from visible noise. This problem is commonly caused by planar surfaces which are not properly aligned with the axis-aligned voxels of the used grid.
Aside from benefits for data structures and some feature extraction techniques, many successful methods for segmentation and analysis make use of the Manhattan World assumption, which assumes structures contained in the point cloud to be oriented along a rectangular grid. Determining the global orientation of the grid and rotating the point cloud to match this grid thus represents an important precondition for such algorithms to work properly.
The problem of pose normalization for 3D shapes and meshes has been extensively discussed
in other works. However, publications in this field for point clouds are either sparse or
concerned with solving different, related problems. Many works in the field of pose
normalization commonly deal with alignment as a preprocessing step for shape matching or
discuss it in context of feature extraction.
Many of aforementioned works compared the pose normalization problem together with the
principal component analysis (PCA). Most often the PCA is being used for feature extraction,
but also represents a common way for calculating an object’s principal axis. This is achieved
by constructing the covariance matrix of a point set, followed by an eigenvalue decomposition
of this matrix resulting in an orthogonal basis of principal axes. These principal axes,
however, are often sensitive to noise and local sampling such that only the most dominant
principal axis ends up being useful for shape alignment. In their publications,
For all rotation angles = 0 … Rotate cloud by
along up-axis Calculate point histogram and the related standard deviation
false
If > ∗ Remove upper quantile from histogram and recalculate standard deviation as ′ .
Calculate = | − ′ |.
true
Set ∗ = and ∗ =
Combining the ideas of both, symmetrical properties and dominant planes,
Our approach to point cloud alignment makes use of point density histogram to identify dominant wall segments, but contains multiple analysis steps shown in Figure 3. We initially start by defining a vector pointing “upwards” as our rotation axis and selecting an axis for alignment (which is oriented orthogonally to the upwards vector). This vector is typically chosen to be the global z-axis which is usually fixed in case of point cloud data captured with a terrestrial laser scanner in static mode. Afterwards, we incrementally rotate the point cloud and construct the density histograms. These histograms are created by counting the number of points falling into a specific range along the alignment axis. The shape of these histograms strongly depends on the chosen rotation, a behaviour explored further in Figure 3. As point densities are larger along planar surfaces such as walls, clearly identifiable peaks will emerge if a viable rotation angle for alignment has been chosen. Contrary, an unsuitable rotation angle results in a rather flat distribution in the density histogram. Based on this observation, the alignment problem is reduced to finding dominant peaks in the density histogram as their presence indicates that walls are aligned with the main axes. As a fast and robust metric for detecting histograms related to the desired rotation angle, the per-bin standard deviation of the point distribution histogram is being calculated. Afterwards, the histogram bins falling into an upper quantile are being removed. In case of histograms related to suitable angles, this operation removes peaks and in consequence greatly reduces the standard deviation of the point density distributions. The difference between the original standard deviation and the new standard ′ deviation is used as an indicator for the desired histogram and therefore the desired rotation angle. The desired rotation angle in the search space thus maximizes the calculated difference of the standard deviations: = max(| − ′ |)
Even though searching for the largest peak in the density histograms seems like a simpler option, we decided to use aforementioned method as it has proven to be more robust towards local point density variations and clutter. If desired, this alignment step may be repeated for the remaining axes. To ensure that the point cloud is still roughly located at the same position, all rotations are performed around the point cloud’s centre of gravity.
The described algorithm depends on three parameters which are the resolution of the rotation angle, the number of histogram bins and upper quantile size. In case of the number of histogram bins, it is advisable to choose their amount such that the resulting bin sizes roughly correspond to a wall’s thickness. The size of the rotation angle increments on the other hand has an impact on the size of the search space and therefore on the algorithm’s running time. In case of the point cloud with 1,629,143 points in Figure 4, we observed an overall execution time of around 8.408s for an angular resolution of 1 degree, but a significantly reduced execution time of 1.762s for an angular resolution of 5 degrees. The accuracy also depends on the upper histogram bin quantile, for which we found a value of 90% to be adequate for our experiments. In our example, removing this upper quantile from the histogram results reduces the overall standard deviation of the remaining histogram bins by 6,313.613 points.
We evaluated our method on various data sets (further examples shown in figure 6) and found that it performs desirably for evenly sampled point clouds. In direct comparison, it performs considerably better than an alignment based on the principal component analysis (PCA). For evaluation purposes, we implemented our algorithm and a PCA-based alignment algorithm as command line tools and subsequently embedded them both into Autodesk Revit as plugins, making them available inside a BIM-enabled modeling environment. It is important to point out that our experiments in Autodesk Revit were limited to 1,000,000 points due to API restrictions, while the command line tool has no such point count limits. Figure 5 displays the result of our algorithm in Autodesk Revit and compares it to the results of PCA-based alignment. As displayed in the figure, our method is capable of identifying the desired rotation angle even for point clouds where the PCA-based method struggles. Not only are point clouds being rotated as intended, but the algorithm is also capable of dealing with the uneven sampling mentioned earlier. Aligning subsampled point clouds also gives satisfactory results, meaning that accelerating the alignment by using subsampled data sets of the original point cloud is a viable option. Moreover, we found the algorithm capable of dealing with scans spanning along multiple floors. We also evaluated our method on point clouds acquired from different sensors with results being listed in Table 1. All show an uneven resolution with locally high point densities.
The PCA-based alignment method on the other hand merely calculates a local frame for a point cloud and aligns it with the global frame. This method is significantly faster in comparison, often finishing in less than a second, but delivers poor results as regions with high point densities will have a higher impact on the rotation. Another problem arises from laser scans where only one section of the building has been captured. In these cases, the scanned rooms have a bigger influence on the calculation of the principal axis than sparsely scanned corridors.
We presented an enhanced method for the automated alignment of point clouds to a global coordinate system. Our method has proven to be fast and robust towards uneven sampling and delivers more precise results than the PCA-based method. Although we have already carried out extensive test runs with various point clouds of building, we intend to evaluate our method also with point clouds of engineering structures (e.g. bridges). With the algorithm being based on point density histograms, our brute-force algorithm could be optimized further by means of using more sophisticated optimization methods such as gradient descent, Monte Carlo methods or genetic algorithms. Large point clouds in particular would benefit from this extension. Modifying the algorithm to use histograms based on voxels rather than points might be an option to make it more robust towards densely sampled regions. Interestingly, first trials of our command-line tool indicated that pose normalization with respect to multiple axes seems possible as well, with the alignment being performed successively for each axis. However, further evaluations need to be performed to verify this assumption. Aside from these technical aspects, an option for automated parameter selection would be useful to simplify user input and manual parameter selection.
Loges, S., Blankenbach, J. (2017), As-built Dokumentation für BIM – Ableitung von bauteilorientierten Modellen aus Punktwolken, Photogrammetrie – Laserscanning – optische 3D-Messtechnik: Beiträge der Oldenburger 3D-Tage 2017.
Okorn, B. E., Xiong, X., Akinci, B., Huber, D. (2010), Toward Automated Modeling of Flor Plans, Proceedings of the Symposium on 3D Data Processing, Visualization and Transmission.