Parameter-Free Half-Spaces Based 3D Building Reconstruction Using Ground and Segmented Building Points from Airborne LiDAR Data with 2D Outlines

Abstract

This paper aims to automatically reconstruct 3D building models on a large scale using a new approach on the basis of half-spaces, while making no assumptions about the building layout and keeping the number of input parameters to a minimum. The proposed algorithm is performed in two stages. First, the airborne LiDAR data and buildings’ outlines are preprocessed to generate buildings’ base models and the corresponding half-spaces. In the second stage, the half-spaces are analysed and used for shaping the final 3D building model using 3D Boolean operations. In experiments, the proposed algorithm was applied on a large scale, and its’ performance was inspected on a city level and on a single building level. Accurate reconstruction of buildings with various layouts were demonstrated and limitations were identified for large-scale applications. Finally, the proposed algorithm was validated on an ISPRS benchmark dataset, where a RMSE of 1.31 m and completeness of 98.9% were obtained.

1. Introduction

As a part of the digitalisation of cities, 3D building models are essential and provide more accurate spatial and environmental analysis for various applications [1,2,3]. The availability of building models on a large scale is usually very limited, as for most buildings the corresponding 3D models do not exist due to their age, or are not in the public domain. Manual modelling of existing buildings is not practical on a large scale as it is very time consuming and costly. Hence, research is oriented towards solutions that reconstruct buildings automatically [4]. The common approach to automatic building reconstruction is by using point clouds [5], which can be obtained by various remote sensing technologies (e.g., stereo imaging, laser scanning). One of the more widely used technologies for this purpose is LiDAR (Light Detection and Ranging), which is the technology of active remote sensing, where laser light is used to acquire the geometry of the observed surface. It is usually mounted on an aircraft to scan large geographic areas. The quality of the point cloud obtained during such acquisition affects the accuracy of the reconstructed building models and other spatial analyses directly [6]. With the fast development of remote sensing technologies and, consequently, larger availability of the resulting data, the reconstruction of 3D building models from point clouds gained popularity in recent years [5,7,8]. In general, the building reconstruction algorithms from point clouds can be data-driven, model-driven, or hybrid-driven [5]. An additional type of algorithms that employ the machine learning approach to building reconstruction [9,10,11] is becoming popular, which is accelerated by the availability of training datasets for this purpose, such as the dataset presented by Wichmann et al. [12].

Data-driven algorithms are bottom-up based, where basic geometric shapes (i.e., planes, cylinders, cones …) are detected in point clouds first. The final building’s shape is then obtained with establishing a topological structure by analysing the dependence of adjacent basic geometric shapes. Data-driven algorithms can be further divided by the type of faces that are considered. Most algorithms consider flat faces only [13,14,15,16,17,18], while some maintain curved faces as well [19,20]. There are various approaches to the analysis of basic geometric shapes, such as by the adjacency matrix [16], region growing [17], adjacency graph [21], or by direct processing of planar faces and their neighbours for estimating the common edges [14]. Data-driven algorithms are sensitive to under- or over-segmentation, which can cause problems for the analysis of basic geometric shapes. When the extracted basic geometric shapes are incomplete or noisy, which is a common occurrence for low-quality input data in complex scenes, the reconstructed building model can be of bad quality. Vosselman and Dijkman [22] used building outlines and LiDAR data for building reconstruction, where building outlines are partitioned into segments, while considering intersection and height jump lines. Segments are later merged back together until each face corresponds to one segment to obtain the 3D model. Li et al. [23] presented a new framework based on TIN (Triangulated Irregular Network) and label maps to automatically create building models from LiDAR data. TIN-based roof primitives detection supports varying point density and label maps are processed by a graph-cut to provide a good representation of roof faces. Wang et al. [24] developed a new methodology for building reconstruction based on structural and closed constraints. A surface optimisation scheme is adopted to enforce consistency between polygonal surfaces of the building and geometric structures. Zhang et al. [25] perform reconstruction of building models using unclassified LiDAR data, where the points are classified in the first two steps. In the final third step the building models are generated on the basis of the 2D topology of roof facets and estimated dominant directions. Shan et al. [26] introduced a framework for building model reconstruction where point cloud segmentation and building reconstruction are described as a minimisation problem of the corresponding energy functions. The initial segmentation is optimised by a global energy function that takes distances of LiDAR points to planes, spatial smoothness and the number of planes into account. After segmentation the reconstruction is performed by partitioning the building into volumetric cells, which is followed by determination of building surfaces and their topology. Building models are obtained with a global energy function, which is minimised using the min-cut theorem. Tarsha Kurdi et al. [27] developed a methodology that is performed in two steps. In the first step 2D building outlines are generated automatically on the basis of a neighbourhood matrix, while detecting inner roof plane boundaries as well. In the second step the 3D building models are generated, where, after fitting and refining of roof planes, the roof plane boundaries are transformed to 3D by the analysis of relationships between neighbouring planes. Later, they [28] improved the building outline modelling by filtering the point cloud with the bias of a Z-coordinate histogram.

A reverse, top-down based approach is typical for model-driven algorithms, where the building shapes are estimated by parametric fitting of shape candidates to the input point cloud. The result of fitting is a building model with a roof that is defined by parameters for the roof shape of the candidate that is best-fitted to the point cloud. This type of algorithms are usually faster than data-based, are easier to implement and can be used for datasets with a low point cloud density (1.2 pts/m² [29]). However, the main restriction of such approach is the limited collection of possible candidates that do not cover all possible roof shapes. In case a building’s roof shape is in part or entirely different from every existing candidate in the library, the reconstruction will either fail, or generate a model with large errors. Model-driven algorithms differ mainly regarding the manner in which candidates are fitted to the point cloud. Poullis et al. [30] fitted geometric shapes while considering constraints found in architecture, Huang et al. [31] used statistical analysis, and Henn et al. [29] employed a modified RANSAC algorithm for this purpose.

The components of both approaches are combined in hybrid-driven algorithms in order to reduce the weaknesses of both. There are two main types of such reconstruction [5]. The first is by dividing buildings into smaller parts, based on the edges of the buildings’ outlines, jump edges and roof ridges. Smaller parts can be fitted to the candidates of roof shapes with a higher success rate [5]. Building parts are then combined to obtain a whole building by 3D Boolean operations as a part of CSG (Constructive Solid Geometry) [32,33,34]. Kada and Wichmann [34] estimate building shapes with half-spaces, where the model is divided into smaller convex parts, which are then combined. The concave shape can be obtained through a correct division, which is only considered for a limited number of building layouts. The second type of reconstruction is by the RTG (Roof Topology Graph), which is established over basic geometric shapes and can contain additional information about edges. Verma et al. [35] establish RTG over segmented planar roof faces. They determine building’s geometry by searching for subgraphs within RTG, that exist in the roof candidate database. More advanced RTG approaches were introduced by Xiaong et al. [36,37], where it was demonstrated, that it is possible to present the topology of any roof using a graph with minimal cycles in addition to nodes and edges [36]. Later, they improved the algorithm with a graph edit dictionary, which was used to reduce typical errors in RTG [37].

A new half-spaces based algorithm for building reconstruction from point clouds is introduced in this paper. In contrast to the related algorithms, which divide buildings’ 2D outlines into smaller parts and then process them while taking only convex shapes into account, the proposed algorithm performs reconstruction without division, while also considering concave parts of the building’s roof. Additionally, no assumptions about the building layout are made, which allows processing of buildings on a large-scale. This is achieved in two stages, where the input data is processed first to obtain the definition of each building’s base model and the corresponding half-spaces. The second stage generates a building shape by performing 3D Boolean operations over the analysed half-spaces.

The remainder of the paper is divided into three Sections. The next Section describes both stages of the proposed algorithm in detail. The third Section presents the results over a large geographic area with the complementary discussion, and the final Section concludes this work.

2. Methodology

The proposed algorithm for building reconstruction is performed in two stages as shown in Figure 1. In the first stage, the input data is preprocessed, where the buildings’ 2D outlines and the classified airborne LiDAR point cloud are used to obtain base building models and the corresponding definitions of half-spaces through segmentation. These serve as the input to the second stage, where the half-spaces are classified and processed by 3D Boolean operations to obtain the final building shape, where convex and concave parts of the final shape are considered. The model of each building is bounded by floor, exterior wall and roof faces. Only roofs without height jumps are considered. A height jump can be described as an edge of a roof’s face, which height is different from a neighbouring roof’s face. The following subsections describe both stages in detail.

2.1. Data Preprocessing

The input data to the proposed algorithm represent 2D building outlines and the airborne LiDAR point cloud. Both types of data are considered to be georeferenced using the same coordinate system and, therefore, aligned. The points of the LiDAR data that are classified as ground or building are considered in this work. In case the input LiDAR point cloud classification is missing or is of bad quality, there are various methods for classification available (for an overview, see [38]). As there are many possible classes of LiDAR points, a method that focuses on ground and building points [39] should be used for this purpose. Only building points that are located within the 2D building outline are considered for reconstructing the roof of the corresponding building model.

2.1.1. Generating Base Models

The base model of each building is used in the second stage for estimating its final roof shape. It is bounded by the floor face, top bounding face and exterior wall faces that are obtained from the 2D building outline. Floor face g is determined by placing the polygon of the corresponding 2D building outline to the height of the lowest LiDAR ground point in the direct proximity of the building. The top bounding face $g^{\prime }$ is determined in the same way as g, only it is placed above the highest LiDAR building point, so it does not limit the final building model. Each exterior wall face $s_i$ is defined by the points that lie on sides g and $g^{\prime }$ as shown in Figure 2. The base model M is given as a watertight model, bounded by a set of faces: $\{g,g^{\prime },s_1,s_2,\dots s_n\}$, where n is the number of sides of the building outline. An example of a generated base model from a 2D building outline is illustrated in Figure 2.

2.1.2. Half-Spaces’ Definition

A half-space is a core element for shaping the roof in this work. It is obtained from the LiDAR point cloud, which is first segmented into sets of LiDAR points that describe each individual planar roof face. For the segmentation of planar faces various segmentation methods are applicable. Considering the type of input LiDAR point cloud, segmentation methods that take the LiDAR point cloud density into account [40,41,42,43] are more suitable for this purpose. The reason for this is variable density of the input point cloud, which occurs due to different laser scanner technology and height of the aerial vehicle that performs point cloud acquisition. Segmentation that takes variable point cloud density into account should, therefore, be used for the best results. The overview of segmentation methods is out of the scope of this paper, for more information see [44]. An example segmentation of a LiDAR point cloud that belongs to the same building as the base model from Figure 2 is shown in Figure 3.

The roof of each building will be shaped by a set of half-spaces $H=\left\{H_i\right\}$. Half-space $H_i$ is defined by the corresponding set of LiDAR points $S_i$ and a plane $P_i$ that is calculated from $S_i$. $H_i$ is given as $x{P}_i.a+y{P}_i.b+z{P}_i.c+d>0$. The definition of each half-space is obtained from the segmented LiDAR point cloud, where sets of segmented LiDAR points $S_i$ that describe individual roof faces are taken. The plane $P_i$ that is best-fitted to the corresponding set of LiDAR points is determined as $P_i=[a,b,c,d]=\mathrm{LSqFit}\left(S_i\right)$, where $P_i.c>0$ and LSqFit is a function that fits a plane to a set of LiDAR points by least-square fitting [45].

2.2. Shaping 3D Building Models by 3D Boolean Operations

During this stage, base models are shaped by 3D Boolean operations based on half-spaces to obtain the final 3D building models. The half-spaces of the previous stage are classified as obstructed or unobstructed for further analysis and shaping by slicing the base models.

Classification of Half-Spaces

Each half-space $H_i$, of which the corresponding set of LiDAR points $S_i$ is partly contained within the base model M, is classified as unobstructed or obstructed in this step. A half-space is unobstructed, if it does not contain any LiDAR points of other half-spaces:

$$H_i\in \left\{\begin{array}{cc}{H}^O,\hfill & \exists p\in S_j:p\in H_i,j\ne i\hfill \\ H^U,\hfill & \mathrm{else}\hfill \end{array}\right.,$$

(1)

where $H^O\subset H$ is a set of obstructed half-spaces and $H^U\subset H$ a set of unobstructed half-spaces. As only planar roof faces are considered, small variations in faces’ shapes can be neglected, and in Equation (1) the number of LiDAR points are reduced from $S_j$ to $C_j\subset S_j$. The set $C_j$ only contains points that are located on the convex hull of perpendicularly projected LiDAR points from $S_j$ to the plane $P_j$. In case $H_i$ contains a point from another half-space, it is classified as obstructed, which means that $H_i$ is obstructed by a different half-space on a concave part of the roof. As a result, it cannot be used directly for shaping the building roof and needs to be analysed further.

2.3. Performing 3D Boolean Operations with Half-Spaces

Unobstructed half-spaces describe the convex shape of the building’s roof as they are not obstructed by any other half-spaces. Therefore, they can be used directly for shaping the building model. This is performed by subtracting all corresponding open half-spaces from the building’s base model M:

$$\forall H_i\in H^U:M=M\backslash H_i$$

(2)

Figure 4 shows an example of shaping the model with unobstructed half-spaces.

Each obstructed half-space may not be directly useful for shaping the model. As an example, a pair of half-spaces’ corresponding planes might be parallel at different heights or oriented in such a way that they intersect outside of the building model. Therefore, obstructed half-spaces are processed by determining the smallest slice $s_k$, if it exists, for each half-space $H_k\in H^O$. A slice $s_k$ is determined by the intersection between $H_k$ and all half-spaces $H_l\in H^O$, $k\ne l$, that are visible from $H_k$. Half-spaces $H_k$ and $H_l$ are visible, if a line between a point from $C_k$ and a point from $C_l$ exists that does not intersect with any other roof face, and if $\exists p\in C_k\wedge \exists p^{\prime }\in C_l$, such that:

$$(\overrightarrow{{\mathit{p}}^{\prime }}-\overrightarrow{\mathit{p}})·\widehat{{\mathit{P}}_{\mathit{k}}.\mathit{n}}>0\mathrm{and}(\overrightarrow{\mathit{p}}-\overrightarrow{{\mathit{p}}^{\prime }})·\widehat{{\mathit{P}}_{\mathit{l}}.\mathit{n}}>0,$$

(3)

where $\widehat{{\mathit{P}}_{\mathit{k}}.\mathit{n}}$ and $\widehat{{\mathit{P}}_{\mathit{l}}.\mathit{n}}$ are normalised normal vectors of the corresponding planes. A slice is valid if half-spaces that determine the slice intersect within the model. In case a slice is not valid, it is processed as empty. The final model M is obtained by subtracting all slices:

$$\forall H_k\in H^O:M=M\backslash s_k$$

(4)

Figure 5 illustrates shaping the building with obstructed half-spaces for the model from Figure 4b. The final building model is shown in Figure 5e.

3. Results

To analyse the proposed algorithm’s large-scale performance, it was applied on the basis of airborne LiDAR data and 2D buildings’ outlines. The input data cover a 6.153 km² large geographic area of the city of Maribor, Slovenia (bounding box: 46°33′8.54301″N 15°37′29.23113″E, 46°34′13.15573″N 15°39′52.97941″E). The provided LiDAR data’s average density is 11.3 pts/m² and the considered 14,227,123 building points and 31,420,386 ground points are shown in Figure 6. Buildings’ outlines were obtained from a public spatial database maintained by The Surveying and Mapping Authority of the Republic of Slovenia. There were 5254 buildings’ outlines contained entirely within the bounding box of the area.

First, the building points for each corresponding building’s outline were segmented. For this, a graph-based segmentation [41] that takes point cloud density and local curvature of faces into account was selected, as roofs of buildings are not always completely flat. The segmentation establishes the initial topology over the point cloud as an undirected graph by the k-nearest neighbour approach, and is controlled by the local curvature $t_{\theta }$ and distance $t_d$ thresholds. The building points from the input LiDAR point cloud for each corresponding building’s outline were segmented using the settings given in

Table 1. Parameters used for segmentation of the point cloud.

Parameter	Value
k	20
$t_{\theta }$	2.0
$t_{CC}$	50
$t_d$ [m]	2

. A minimum of 50 points were required for each segment ($t_{CC}=50$), which was set to avoid too small roof faces. The resulting segmentation of building points from Figure 6 is shown in Figure 7.

The building models were generated next. A building model is deemed geometrically valid, if the building’s floor face remains intact which, as such, does not necessarily imply an accurately reconstructed model. In some cases, especially with height jumps, the obtained building models were invalid. To achieve a higher validity rate the number of obstructed half-spaces was limited to 10 for cases with height jumps. In such cases, only unobstructed half-spaces were considered for shaping the model. An example of handling these cases is shown in Figure 8.

The reconstruction produced a geometrically valid model for 4817 building outlines in 92% of cases. The resulting buildings’ reconstruction is shown in Figure 9.

In practice, many buildings’ roofs contain height jumps and, as they are not considered by the proposed method, several geometrically invalid models are to be expected.

Next, we examined various cases of buildings from the reconstructed city model with roofs of different types without height jumps, which are shown in Figure 10.

Figure 10a shows a relatively simple case that is described by eight half-spaces of a single building, of which five are obstructed. The next case from Figure 10b shows an example of two terraced buildings, where the same roof faces are shared between buildings. In such cases, where there are no geometrical features available to determine the border between two buildings, it is crucial to have buildings’ outlines already available. The building shown in Figure 10c has a roof with four ridges at different heights or orientations, and a horizontal part of the roof, which were incorporated into the model correctly from 17 half-spaces. The following case, shown in Figure 10d, has a flat face at the highest point of the building model. The building is described by 17 segments of points, where gaps can be observed in the shape of some of them. The gaps occur due to small objects located at the roof that are either too small or curved. The final case, Figure 10e, illustrates the reconstruction of a building with a complex roof that is described by 30 half-spaces, of which only one (top horizontal half-space) is unobstructed. There were at least 14 slices performed to obtain the correct shape, including slices determined by four half-spaces. The presented cases from Figure 10 demonstrate the ability of the proposed algorithm for the reconstruction of buildings of various layouts.

Validation

The proposed methodology was validated with the International Society for Photogrammetry and Remote Sensing (ISPRS) benchmark dataset, specifically the third area of the data captured over Vaihingen, Germany [46,47]. Building outlines and LiDAR data, where building points were classified manually and the density is 4 pts/m², were used from the benchmark as input data. The output building models of the proposed algorithm were compared by height difference with the ground truth data from the benchmark, as shown in Figure 11. Ground truth data is presented as building roof faces, given as 3D polylines. The height difference was estimated over a regular grid with 10 cm resolution. Statistics for the comparison is given in

Table 2. Validation of the obtained results from the comparison with ISPRS benchmark data.

Metric	Value
RMSE [m]	1.31
Completeness [%]	98.9
e0.5 [%]	79.4

, where RMSE (Root Mean Square Error) was estimated over height differences, completeness specifies the proportion of the building area covered by geometrically valid building models, and $e_{0.5}$ designates the proportion of the building area, where the height difference is lower than 0.5 m.

The majority of the difference manifested over areas, where height jumps are present. Some difference can be observed over parts of roofs with small elements (e.g., chimneys or small dormers) or parts of the dataset, where the point cloud is too sparse.

4. Discussion

The main challenges of applying the proposed algorithm to large-scale datasets include the presence of building roofs with height jumps and the availability and quality of the input data. Building roofs with height jumps are a common occurrence on a large scale and, as the proposed method does not consider them, had to be taken into account to obtain as complete city model as possible. For cases with height jumps, shaping the building model with obstructed half-spaces caused many building models to become invalid, as the subtraction of some slices affected the floor face of the building model. This was particularly apparent for buildings with many small obstructed half-spaces, where half-spaces may be oriented towards a part of a roof, where only unobstructed half-spaces are present. In such case a slice can cut through a part of a building model that would otherwise remain intact. For this reason the number of obstructed half-spaces was limited to keep a validity rate over 90%.

The availability of the input data represents an important drawback that should be taken into account. Building outlines could be, to an extent, generated from the LiDAR data [28], however some drop in accuracy can not be avoided. On the other hand, LiDAR data is essential and may not be available at a selected location. In such cases, the point cloud data could be obtained using an aerial or UAV (Unmanned Aerial Vehicle) photogrammetric survey. Even though the proposed algorithm was developed with aerial LiDAR data in mind, it could be applied to any 3D point cloud. Another aspect of the input data to consider is quality. It includes density and accuracy of the point cloud data, which largely depend on the laser scanner quality. The publicly available LiDAR data is often of low density, which means that smaller roof faces are much harder to detect. The required density for the correct reconstruction depends on the minimum size of roof faces that are desired to be included in the generated building models. In theory, there need to be at least 3 segmented points on a roof face to determine the corresponding plane. However, due to variations in measurement accuracy that affect plane orientation and the fact that as the shape of the roof face is important for further analysis as well, a higher point count is beneficial. In our experience, the minimal point cloud density, using the selected segmentation algorithm for faces larger than 10 m², was 1.5 pts/m². Building outline datasets are often acquired manually, which means that human error can be present as well. Another option is to use cartographic outline datasets from public databases, as was done in this work. However, it should be noted that existing outline datasets can be misaligned, inconsistent, or out of date. Some buildings might have been demolished, changed or replaced, and outlines of new buildings could be missing. Any discrepancies in the input data are presented directly in building models.

The comparison with the Vaihingen dataset has shown that, apart from the acknowledged lack of height jump processing, the proposed algorithm demonstrated satisfactory performance. This is confirmed by a large proportion of the building area, where the height error was under 0.5 m. When comparing the results with related work [47] in terms of RMSE, the proposed method yields higher value, which is largely attributed to height jumps, where every error accumulates substantially over a large surface. In addition, as completeness was reported higher than in related work at nearly 100%, which comes as a result of a reliable building reconstruction and using building outlines as input, the RMSE for the proposed algorithm accumulates extensively over a sparse part of the dataset. Building outlines provided additional completeness over sparse part of the dataset. In such cases, related work, in contrast to the presented algorithm, did not generate the building model over the entire building outline due to lack of data.

Moreover, as shown in Figure 10, it can be observed how a LiDAR point cloud can contain relatively large empty spaces between scan lines in practice. It is important to keep this in mind when choosing the segmentation method and the appropriate parameters. Apart from the segmentation of point clouds, no additional parameters are required for controlling the reconstruction. This simplifies the use of the proposed algorithm significantly, especially as the segmented point cloud could also be provided as an input to the algorithm.

5. Conclusions

This work presents a novel algorithm, based on half-spaces, for 3D building reconstruction that processes airborne LiDAR data and buildings’ outlines to generate building models. It performs in two stages, where the input data is preprocessed first to obtain buildings’ base models and the corresponding half-spaces. In the final stage, 3D building models are finalised by shaping their roof using 3D Boolean operations over the analysed half-spaces.

In experiments, the presented method has shown promising reconstruction performance for the considered type of buildings. As in practice, on a large scale, there are many building roofs with height jumps, some constraints were required to obtain a more complete 3D city model. For a more accurate reconstruction, the height jumps should be considered and incorporated in future work, which could be explored by splitting the buildings’ outlines. Another possible improvement could be the integration of curved faces support, where special attention should be given to classification and limiting the reach of a curved face when using 3D Boolean operations to shape the building model. Moreover, as the segmentation performance greatly affects the algorithm’s output, the impact of various segmentation algorithms with different parameter settings could be investigated as well.

The proposed algorithm’s large-scale applicability is highly beneficial for urban simulations, or as a component of various urban analytical processes, especially those that consider environmental impact, which is a growing global concern. Apart from the segmentation part, for which any appropriate segmentation algorithm can be used, the proposed algorithm is parameter-free, which simplifies its use strongly and enhances adoption potential.