10.2.1 Pose Estimation for Wide-Baseline Pairs and Triplets

As detailed below in Sect. 10.2.2, the basic building block for the determination of the poses for an image block by merging are triplets. While one could derive the poses for triplets directly from matches in three images, we start pose estimation with the smallest possible image sets, namely pairs. By this means, the complexity for matching in three images can be reduced by constraining it to the areas around the epipolar lines estimated for the pairs.

Because we want to deal with rather large baselines, we decided to employ affine least-squares matching [15,16] as the basic means for matching. “Affine” means that a patch is rotated by two angles (rotation and sheer), different scales are employed for the two basic axes and two translations (in x- and y-direction) are used. This enables a much better adaptation of two patches than the usually employed translations in combination with one rotation and one scale. What is more, least-squares matching does not only produce very accurate results, but additionally also provides estimates for the precision in the form of covariance matrices.

While the mathematically correct model for matching a planar patch would be the eight parameter projective transformation, we found empirically that it cannot be reliably estimated from the typical patch size of $13\times 13$ pixels. The latter has also been determined empirically and gives a good balance between sufficient information content and not being too large so that disturbances, e.g., due to occlusions or non-planarity, do not affect the matching too adversely.

Unfortunately, least-squares matching is computationally very demanding and, thus, has to be limited to regions where it is likely to be successful. To this end, first points are detected by means of the scale invariant feature transform—SIFT [17]—in images reduced to a resolution of about $200\times 150$ pixels. The points are then matched via (normalized) cross-correlation, because we found that the results of matching by cross-correlation do not degrade as abruptly as for matching by means of SIFT. Pairs with a correlation coefficient higher than an empirically determined low threshold of 0.5 are then input to least-squares matching, the results of which are only accepted if a high threshold of 0.95 is exceeded.

The resulting point pairs are input to the estimation of the relative pose of the pairs based on RANSAC and the five-point algorithm. We have extended this by a variant of the expectation maximization (EM) algorithm where we vary between expectation in the form of the determination of the inliers and maximization realized by means of robust bundle adjustment [18].

Once the relative pose has been determined for the pairs, the matching is repeated on double the resolution for triplets, reducing the search space considerably by means of the epipolar lines derived from the essential matrices estimated for the pairs. Pose estimation employs one “master” image for which the relative pose is determined to the other two “slave” images as above with RANSAC and the five-point algorithm for the same five points in the “master image”. To link the pairs, relative scale is computed by means of triangulating the five points and computing the relative distances in both pairs. The median of the ratio of the distances is taken as the relative scale, i.e., relative length of the baselines. This basic result for triplets is refined on again the double resolution, projecting points in three images via the trifocal tensors derived from the relative poses of the triplets.

Additionally to the above approach for pairs, we have developed means to estimate also the poses for pairs with extreme baselines [19]. It is based on distorting the images by means of a large set of different projective transformations, detecting and matching points in the transformed images. While the results demonstrate that it is possible to estimate the pose for these extreme configurations, the computational complexity is extremely high, making the approach only useful if not more than a couple of image pairs need to be matched. In [20] an approach has been presented addressing the problem that often the pose is precisely determined only for parts of an image, as not enough points can be matched on difficult areas with strong perspective distortions such as roads seen from ground level. While [20] demonstrates the feasibility, it is limited to specific setups (roads seen from ground level in the lower part of the image).

10.2.2 Hierarchical Merging of Triplets

The derived triplets are the basis for the determination of the poses for the whole image set. The approach is described in detail in [21]. At the core is the hierarchical merging of image sets starting with triplets as the minimum sets.

While in principle 3D points alone or also combinations of 3D points and camera poses can be used to align the coordinate system of an image set to another image set, here the poses for two images included in both image sets (e.g., images 2 and 3 in the two triplets consisting of images 1, 2, 3 and 2, 3, 4, respectively) are used to compute a 3D Euclidean transformation. Even though the poses for one image are enough to compute the relative translation and rotation, the relative scale of both coordinate systems can only be computed using additional information such as 3D points seen in two or more images in both sets. As individual 3D points can be wrong due to matching errors particularly for wide baselines, we opted to use the poses of an additional image included in both sets (i.e., image 3 additionally to image 2 in the above example) as accumulator for the relative distances of the 3D points and the relative scale of both sets is computed as the ratio between the lengths of the baselines (of images 2 and 3 in the above example) in both sets.

Because two images included in both sets are used, a merge of two image sets with $n_1$ and $n_2$ images leads to a combined set of images consisting of $n_1+n_2-2$ images.

While in earlier work [11] we had employed a serial extension by one triplet at a time, this was replaced by a hierarchical approach in [21]. Here, sets of approximately the same size are merged. This has two advantages: First, because we have found that after merging bundle adjustment is a must to obtain a reliable result by staying close to an optimal solution, the hierarchical approach avoids numerous bundle adjustments for large sets only slightly smaller than the complete set (in the serial case one has to adjust the complete set, the set minus one image, the set minus two images, etc.). Second, when the sets are of significantly different size, the employed robust bundle adjustment (cf. Sect. 10.2.1) tends to throw out the points from the smaller set, which due to a lower redundancy are less precise and thus more likely regarded as outliers.

In [21] it is also shown how one should reduce the points for merging if one wants to obtain a higher efficiency. The only way found to reduce the number of points which avoids a bias in the result is by randomly deleting 3D points. Intuitive means such as keeping points seen in as many images as possible also in combination with a policy to keep points well spread over the images give a better precision, but it was found that it can lead to a severe bias.

Recently, in [14] it has been shown that a search for maximum matching in the graph describing the connections between the images leads to a higher degree of parallelization and, therefore, a higher efficiency.

10.2.3 Automatic Determination of Overlap

The approach introduced in Sects. 10.2.1 and 10.2.2 assumes that the relation, i.e., overlap, between the images is known. Determining the overlap for larger image sets is a difficult problem, because basically all images have to be compared to all other. The least-squares matching approach of Sect. 10.2.1 can deal with large baselines, but its complexity is way too high to be used for all possible pairs.

Thus, a multistage approach has been devised [13,14], which first matches SIFT points in image pairs highly efficiently. The number of matches in each pair is the basis to restrict the approach introduced in Sect. 10.2.1 to a small subset of promising pairs and triplets. This allows one to estimate the pose for image sets containing essential wide-baseline connections which are the only means to connect certain subsets, but at the same time limits the computational complexity.

The relationships between images are modeled by an undirected weighted graph $G_I=(V_I,E_I)$, where a node $v\in V_I$ represents an image and an edge $(v_i,v_j)\in E_I$ connects two overlapping images corresponding to the nodes $v_i$ and $v_j$. The edges are weighted using the Jaccard distance [22] with correspondences determined by matching binary SIFT descriptors. The latter are obtained by embedding SIFT descriptors [17] from continuous space ${\mathbb{R}}^{128}$ into Hamming space ${\mathbb{H}}^{128}={\{0,1\}}^{128}$ based on orthants. By this means, a compact representation of the descriptors as bit vectors is achieved resulting in a very fast comparison using the Hamming distance followed by the distance ratio test [17].

The graph $G_I$ allows for a straightforward modeling if pairs are used for linking. However, it lacks descriptiveness in the case of triplet-based linking requiring higher-order relationships. In addition, the employed hierarchical merging of triplets (cf. Sect. 10.2.2) uses pairs to propagate the geometry (i.e., linkable triplets must have two images in common) and this constraint cannot be modeled by $G_I$.

Therefore, we employ the line graph $L(G_I)=(V_L,E_L)$ of the graph $G_I$ to describe the linking of images. It has as set of nodes $V_L$ the edges of $G_I$. An edge $(v_i,v_j)\in E_L$ exists iff the incident nodes $v_i$ and $v_j$, corresponding to edges in $E_I$, have exactly one node $v\in V_I$ in common. Hence, $V_L$ contains nodes corresponding to pairs of overlapping images, where two nodes are adjacent if the pairs have an image in common. Because of this, the linking of triplets using pairs for geometry propagation corresponds to a traversal through $L(G_I)$. An edge in $L(G_I)$ corresponds to a triplet and its weighting is based on the lowest quality of the three pairs of the triplet, where the quality of a pair is defined as the number of correspondences weighted by the roundness [23] of the corresponding reconstructed 3D points.

For a direct modeling of images, we extend $L(G_I)$ to explicitly represent the images using a second node type leading to the so-called linking graph $G=(V_I\cup V_L,E)$. It comprises pair nodes $n_p\in V_L$ corresponding to image pairs and image nodes $n_i\in V_I$ corresponding to images. An image and a pair node are adjacent if the pair node contains the image corresponding to the image node. Because the image nodes are only required for a complete modeling, no edges exist between them.

The linking graph completely describes the image linking, but can contain links of varying quality, e.g., due to critical camera configurations [24], as well as redundant links which are either less suitable or not required for pose estimation. Thus, we determine a linking subgraph (LSG) containing only essential links by searching for a terminal minimum Steiner tree [25] in the linking graph.

However, due to the tree-like structure, potential image loops in the LSG are not closed. At this stage, we can obtain additional information in the form of approximate poses very fast by hierarchically merging the triplets contained in the LSG without bundle adjustment. By this means we are able to efficiently search for image pairs which can be used to close loops by restricting the search space using a Euclidean neighborhood as well as the view direction difference between images. In addition, we determine the length of a potential image loop in the form of the graph distance between its outermost image nodes and restrict it as well.

For an efficient pose estimation the linking graph is iteratively constructed using minimum spanning trees of $G_I$ as well as its subgraph LSG determined until all images are suitably linked or the further search is not meaningful anymore. As the terminal Steiner problem has been shown to be NP-complete [25], an approximation [26] is used for the determination of the LSG. After closing the image loops, hierarchical merging of triplets (cf. Sect. 10.2.2) is employed to determine the actual poses.

Fig. 10.1 shows the poses (left) as well as the links between them (right) for our running example scene Building 1.

10.3.1 Dense Depth Map Generation and Uncertainty Estimation

We use semi-global matching (SGM) [32] for MVS matching as it allows for an efficient but still effective processing even for high-resolution images. In our pipeline, stereo pairs that have a sufficient overlap determined from the sparse 3D point cloud generated by pose estimation are selected from the entire image set. Subsequently, the pairwise estimated stereo depth maps are fused for each image to compensate for noise and to filter outliers. In addition, SGM makes use of peak filtering by means of depth map clustering.

In general, the optimization scheme employed in SGM allows for a dense reconstruction of disparities even of weakly textured areas. Because of the reasonably lower quality for weakly textured areas, we additionally employ a pixelwise uncertainty estimation of disparities as post-processing [33,20]. It has been shown that besides the lack of texturedness especially the orientation of the surface relative to the cameras' line-of-sight influences the disparity uncertainty. This can be traced back to fronto-parallel prior assumptions embedded in the SGM optimization framework. Therefore, we classify the disparity uncertainties to consider their quality subsequently in the 3D surface reconstruction (cf. Fig. 10.2).

While the estimation of surface orientation (e.g. the normal vector) cannot be done in a stable way on disparity maps, we found a feature based on the local Total Variation (TV) of disparities to work well for uncertainty estimation. More precisely, we determine the TV in an iteratively growing pixel neighborhood (window) until it exceeds a given threshold. We define the resulting window size as a TV class and use its uncertainty for the estimation of the spatial error. To assign a disparity uncertainty to the TV class, we make use of stereo ground truth data [34] and learn a Gaussian uniform mixture function representing noise and outliers with an EM approach for each TV class. The finally employed disparity uncertainty range from a quarter of a pixel to a couple of pixels demonstrates the span of uncertainty of individual disparities which strongly influences the uncertainty of the 3D point.

10.3.2 3D Uncertainty Propagation and 3D Reconstruction

From dense disparity maps with pixelwise disparity uncertainty we estimate the 3D coordinates and the corresponding 3D error functions [35,20]. To this end, we use well-known analytic error propagation [36]. Beside the disparity uncertainty, the 3D error depends on focal length, baseline length, image resolution and distance of the 3D point to the camera.

For an unrestricted 3D reconstruction from 3D point clouds with varying quality, especially volumetric approaches have shown their potential for 3D reconstruction on a large scale [20]. For a volumetric representation, the 3D space is discretized into voxels in the surrounding of a 3D point. Depending on the spatial distance to the 3D point, individual voxels are assigned values that describe their likeliness to be behind or in front of a surface (cf. Fig. 10.3). We use probabilistic Gaussian cumulative distribution functions (CDFs) for the estimation of the voxel values [35,20]. For measurements from multiple cameras, the individual values are fused using a sound theoretical model employing binary Bayes theory. The final volumetric space can be transformed to 3D point clouds or triangle meshes by a Gaussian regression considering neighboring voxel values.

The volumetric reconstruction is implemented runtime and memory efficient by using octree data structures. For the generation of 3D models from images captured at varying distances it is inevitable to propagate the depths into multiple octree levels. To this end, the voxel size (cf. Fig. 10.3) corresponding to the octree depth is estimated for each measurement. More precisely, individual 3D points are included in the octree on varying levels which are selected considering the scale implied by the 3D error derived from the disparity uncertainty and the camera configuration. At this point, our TV prior functions act as a local regularization term and points on lower octree depths are filtered by points with relatively lower uncertainty.

We have also demonstrated that the employed local optimization allows for the reconstruction of very large scenes by means of space division of the entire 3D reconstruction space into smaller subsets [37] (cf. Fig. 10.4). To this end, the space is incrementally split until the number of 3D points is below a given number in each subset. While a globally optimized surface would lack in consistent scalability, our local optimization paradigm avoids complex divide and conquer strategies for fusing neighboring subspaces.

10.4.1 Relative Features

Replacing absolute by relative features to obtain more stable classifications is not a novel idea. E.g., relative heights of buildings and trees in relation to the ground derived based on an estimated DTM (digital terrain model) have become standard and are even considered the most significant features [40] for urban scene classification. Previous work, however, suffers from (1) the heterogeneous appearance of objects of the same class, e.g., diverse sizes and types of buildings as well as different materials/colors of streets, and (2) the similarity of features of objects from different classes, e.g., heights of buildings and trees. Shadows and variable lighting conditions during data acquisition make the situation even more difficult. The challenge is to devise more intra-class stable and, at the same time, more inter-class discriminative features concerning both color and geometry information, which is one of the goals of this work.

10.4.1.1 Color coherence

In urban scene classification changing lighting conditions usually cannot be avoided and may considerably influence the results. For instance, shadows of buildings and trees are cast on the streets, lawns and roofs. These regions are often miss-classified because of their substantially different color values. Color coherence allows for intra-class stability by dealing with objects under various lighting conditions. It measures the difference between two colors with a single value and has been proposed for image segmentation in [41]. We employ the $L^{⁎}{a}^{⁎}{b}^{⁎}$ color space, which has an independent channel ($L^{⁎}$) for lightness/luminance, i.e., it can deal with various illumination conditions. The other two channels $a^{⁎}$ and $b^{⁎}$ represent red/green and yellow/blue, respectively. We assume that (1) the $a^{⁎}$ channel is sensitive to vegetation objects, i.e., trees and lawn, and (2) the $b^{⁎}$ channel can help to analyze objects lying in the shadow. This is because Rayleigh scattering, i.e., diffuse sky radiation (scattered solar radiation), makes the sky blue and the sun itself is more yellowish. Thus, as the bright side of a roof takes more direct sun light, it has a more yellow tone, while the dark side of a roof reflects more sky radiation and, therefore, has a more blue tone.

Color coherence is a relative feature concerning a predefined color. In contrast to [41], we do not measure the direct color distance between two arbitrary objects, but the distance from the current data point to a given object class. As the “reference” class we choose vegetation because of its relatively invariant appearance concerning color for both RGB and multispectral images. Fig. 10.5 (right) shows a map of color coherence concerning vegetation for $a^{⁎}-b^{⁎}$, where the vegetation areas are dark while all other objects are lighter, i.e., have a significant difference to vegetation. Fig. 10.5 also shows that in comparison with only the $a^{⁎}$ channel (center right), subtracting the $b^{⁎}$ channel gives a much better result concerning the influence of shadows (right).

10.4.1.2 Definition of neighborhood

The spatial neighborhood relationship is employed in many approaches to integrate contextual information for more plausible results. The definition of neighborhood shared by most related work consists of the data points around the current point. For a square image grid, the range of neighbors is a simple $(2m+1)⁎(2m+1)$ matrix with m the order of neighbors (Fig. 10.6, left). While this is a general setup widely used, it only works well under the assumption that the meaningful neighbors are isotropically distributed or there is no direction-related information to consider. Another tricky problem is the order/size of the neighborhood: A larger window is desirable to include more contextual information, but it also implies a more time-consuming processing. The latter becomes particularly critical when graphical models are used as higher-order neighbors mean an exponentially increased computational effort.

Inspired by [32], radial neighborhood patterns (Fig. 10.6, center and right) are proposed. The lengths of the “beams” can be set to “infinity” [32] to reach the boundary of the data and cross as many different objects as possible, while the size of the whole population of neighbors is still acceptable. The length as well as the thickness of the “beams” (Fig. 10.6, right) can be adapted to the object characteristics, e.g., height information in undulating terrain (cf. Sect. 10.4.1.3), where a finite setup is appropriate.

10.4.1.3 Relative height

Relative height is defined as the elevation difference between the current data point and the estimated local ground level. By this means, the differences between classes become more discriminative and stable. A radial neighborhood pattern (cf. above) is employed for relative height computation. For scenes with flat terrain, for instance Fig. 10.7 (left), an “infinite” length of the “beams” is used to gather as much information as possible by including all available ground data.

In contrast, a limited length is mandatory for scenarios with larger height differences like for undulating terrain (Fig. 10.7, right). On hillsides or in valleys, the ground level of one building can be similar or even higher than the roof of another building in the neighborhood. This implies that the absolute height from the training data is not a valid prior for buildings any more. In this case, the range of neighbors is set slightly larger than the average building length.

As shown in Fig. 10.8, the height maps for valley and hillside areas are enhanced using the relative height. What is more important, the height values of different objects, e.g., roofs and ground, are directly comparable in the relative height maps. That is, a classifier trained on one dataset can be applied to both areas.

10.4.1.4 Coplanarity of 3D points

Coplanarity measures how well the current point and its neighbors form a plane. A common plane for the given point and its neighbors is estimated using RANSAC [3] and their coplanarity is quantified by calculating the percentage of inliers to the estimated plane. Coplanarity is employed as a feature to infer the probability of the current point being a part of a planar object. In this work, it was found to be very effective to distinguish trees from other objects, especially roofs, which might have very similar heights in most European urban areas. Fig. 10.9 presents a coplanarity map calculated from the direct neighbors of each pixel.

In summary, relative features integrate both local and contextual information. The definition of “context” is extended from a geometric neighborhood to a more semantic description of environment (ground height) and class (vegetation). In comparison to conventional features with absolute values, the proposed relative features are more discriminative between different classes, and at the same time more stable for objects of the same class.

10.4.2 Classification and Results

A standard RF classifier is employed for the classification. The calculation of the features and the classification with the trained classifier are both implemented for parallel processing splitting the dataset into independent partitions. Because the proposed features are robust for various scenarios, we empirically found that a generally trained classifier can be directly applied to all partitions from the same dataset and provide reasonable results without additional local or incremental training. The computation time can be reduced considerably because the partitions can be distributed. As long as the partitions have a reasonable size, i.e., are large enough to contain whole major objects like buildings and road segments with full width, the division will only marginally deteriorate the results.

10.4.2.2 Results for Bonnland

The Bonnland dataset (cf. also Sect. 10.2 and Fig. 10.10) includes buildings in the valley and on the hillside. The height of the hillside ground level can be greater than that of some building roofs in the valley. Accordingly, a classifier trained with absolute height values for ground and buildings will not work in this area. The proposed relative feature for height, by contrast, is stable in the undulating terrain without need to train the classifier locally. Fig. 10.11 presents the classification result for the whole dataset.

We use a reduced version of the reconstructed 3D point cloud (cf. Sect. 10.2.2; about 8.8 million out of over 1 billion points), which is rasterized into a 2.5D point cloud with a resolution of 0.2 meters. Fig. 10.11 presents the whole Bonnland dataset and the classification result. We have defined four object classes, i.e., ground (gray), building (red), high vegetation/tree (green) and low vegetation/lawn (blue).

10.5.1 Scene Decomposition

The goal of scene decomposition is to extract individual buildings from the building mask derived by scene classification (cf. Sect. 10.4). As the separation of buildings in the building mask may be adversely affected by data as well as labeling errors (cf. Fig. 10.13, red dashed contour), a mathematical morphological “opening” operation is conducted, as shown in Fig. 10.13, to remove trivial connections for a better isolation of the buildings and to eliminate small outliers. A disk-shaped structuring element is employed with a radius of 1 meter.

We start to detect individual buildings via connected components (CCs). The input building mask, as presented in Fig. 10.13, is segmented into rectangular tiles accordingly. Overlap between tiles is allowed to make sure that the buildings are completely included in the tiles. Please note that global coordinates and the height (for undulating areas) are tagged to each tile for the final model assembly.

Due to the complexity of the scene and the errors of the classification, however, it cannot be guaranteed that each CC contains exactly one individual building. That is, as Fig. 10.14 shows, after decomposition, a tile may contain a single detached building, a complex building (a building consisting of multiple building components), or even multiple buildings which are closely adjacent to each other. The last case is often found in densely inhabited areas.

In this work we name both, complex buildings and adjacent building groups, “building complexes”. Further parsing of building complexes is described in the following.

10.5.2 Building Decomposition

Building decomposition works on the results of scene decomposition. It further divides building complexes into standard building components—primitives, which are employed in the following building model reconstruction. Although our approach presented in [43] allows one to model multiple building components by means of the “birth” and “death” jumps in a reversible jump Markov chain Monte Carlo (RJMCMC) framework, a preceding decomposition makes the statistical search more efficient and robust.

We employ a combined bottom-up and top-down scheme for building decomposition, which uses 3D geometry parsing based on a predefined primitive library. Conventional building decomposition is conducted bottom-up based on 2D footprints that are either already available [44,45] or derived from the data [46]. The performance of footprint-based decomposition is limited where 3D geometric information, e.g., different heights or roof types of buildings, has to be considered [47]. 3D geometric parsing, however, cannot be conducted on 3D building models, because the latter do not yet exist. The best decomposition is found by means of statistical model selection and optimization.

Please note that the decomposition and the following building modeling have to share a common construction principle to guarantee a consistent work pipeline. Two basic strategies for building (footprint) decomposition can be differentiated based on one key difference: if the components of a building are allowed to overlap [48,42] or not [44,45]. Different definitions are correspondingly employed for the primitives. In [43], we have demonstrated that the first concept allowing for overlap fits better to generative modeling because of its flexibility and most importantly, the potential to generate complete and plausible models.

10.5.2.1 Ridge extraction

From the 3D point cloud, we employ bottom-up methods to extract ridge lines, which can be considered as key geometric features of buildings. As shown in Fig. 10.15, we define the edges on the roof as: (1) Horizontal ridge line (red), which connects two apexes of the roof, (2) diagonal ridge line (green) connecting one apex and one eave corner, and (3) eave line (blue), which links two eave corners. The roof contour consisting of eave lines can be used as approximation of the building footprint when the roof overhang is ignored.

For non-flat roofs, ridge lines can be determined as the intersection lines of the individual roof planes as also demonstrated in current work [49,50]. Planes of a building complex are detected from the 3D point cloud by a RANSAC-based approach. All intersection lines are filtered by means of the “Relation Matrix” [51] to separate ridge lines from other intersection lines as well as to determine the type of ridge lines, i.e., horizontal or diagonal ridges. “Central lines” are used for flat roofs, which do not have any ridge. In comparison with building skeletons, central lines of roofs are 3D. That is, as shown in Fig. 10.15 (right), they have a height value and in the case of adjacent flat roofs they can differentiate multiple building components by means of their heights.

Ridge lines have the following advantages for the decomposition of complicated buildings:

• •  Full 3D information: different heights can be used to distinguish different building components even though they have an identical width (cf. Fig. 10.15, bottom).
• •  High accuracy and reliability: The ridge lines are calculated by the intersection of robustly determined planes, i.e., they are actually derived from all inliers of the involved planes.
• •  The horizontal ridges consist of straight line segments, which can be regarded as ridge lines of individual primitives and, thus, can guide the decomposition.

10.5.2.2 Primitive-based building decomposition

A statistical primitive-based decomposition guided by the ridges is illustrated by Fig. 10.16. The detected horizontal ridge lines (Fig. 10.16, center, red) consist of straight line segments (Fig. 10.16, right, bold). The primitives selected from a predefined library [52] have a rectangular contour as well as a single straight horizontal ridge line (except for flat roof and shed roof). The end points of the segments are determined by intersection with diagonal ridges or the boundary of the building mask.

The horizontal ridges guide the decomposition: The most appropriate primitives (cf. Fig. 10.16, right) are statistically selected with the goals to fit (1) to the already extracted diagonal ridges and (2) to the rest of the edges, without conflicts with the known planes and the boundary of the building mask.

The building decomposition does not deal with actual building models, because they do not yet exist. The goal of the decomposition is to find an optimal combination of primitives to approximate the underlying model (Fig. 10.16, left). That is, the decomposition determines the number and types of primitives as well as the way of their combination (Fig. 10.16, right). Additionally, building decomposition also results in initial values of parameters for the primitives (cf. Sect. 10.6.1).

10.6.1 Primitive Selection and Optimization

We propose a statistical building modeling based on generative primitive models [43]. The primitives are defined with parameters (cf. Fig. 10.17):

$\theta \in \mathrm{\Theta };\mathrm{\Theta }=\{\mathcal{P},\mathcal{C},\mathcal{S}\},$

where the parameter space Θ consists of position parameters $\mathcal{P}=\{x,y,\mathit{azimuth}\}$, contour parameters $\mathcal{C}=\{\mathit{length},\mathit{width}\}$ (rectangular footprint), and $\mathcal{S}$ containing shape parameters: Ridge/eave height and the depth parameters of hips.

The maximum a posteriori (MAP) estimate of Θ is employed to find the optimal model fitting the data:

${\hat{\mathrm{\Theta }}}_{MAP}=\underset{\mathrm{\Theta }}{\mathit{\text{argmax}}}\left\{\frac{L(\mathcal{D}|\mathrm{\Theta })p(\mathrm{\Theta })}{P(\mathcal{D})}\right\}=\underset{\mathrm{\Theta }}{\mathit{\text{argmax}}}\{L(\mathcal{D}|\mathrm{\Theta })p(\mathrm{\Theta })\},$

where $L(\mathcal{D}|\mathrm{\Theta })$ is the likelihood function presenting the goodness of fit of the model to the data $\mathcal{D}$ and $p(\mathrm{\Theta })$ presents the prior for Θ, which is derived from empirical knowledge and incrementally improved during the reconstruction. That is, the parameter values of the already found building components or of adjacent buildings are used to update the priors. $P(\mathcal{D})$ is the marginal probability, which is regarded as constant in the optimization as it does not depend on Θ.

Reversible rump Markov chain Monte Carlo (RJMCMC) is used for the statistical search of the parameters, allowing for an efficient exploration of the high-dimensional (determined by the number of parameters) search space. The reversible jumps allow one to switch between different search spaces, i.e., different types of primitives. Model selection is integrated in the transition kernel of reversible jumps to guide the search of the optimal primitive type. Multiple hypothetical models are generated via statistical sampling of the primitive type as well as the corresponding parameters. The final model is the verified candidate with the best goodness of fit to the data.

As mentioned above in Sect. 10.5.2.2, certain initial values of the parameters can be derived from the primitive-based building decomposition. The following parameters can be determined directly from nothing but the horizontal ridges (cf. Sect. 10.5.2.1):

Additional parameters can be determined by taking the building footprints into account, which either stem from given building masks or can be derived from the diagonal ridges (cf. Sect. 10.5.2.1):

Known initial values can significantly improve the performance of the statistical search. They are, to a certain extent, reliable and specific, as the ridge lines can be precisely determined (cf. Sect. 10.5.2.1).

Fig. 10.18 presents the reconstruction result of the running example Building 1 (top) and demonstrates the robustness of the proposed modeling approach against data flaws (bottom). 3D point clouds from image matching may contain flaws because of the quality and coverage of the images, homogeneous texture of the objects (i.e., points cannot be matched), occlusion, etc. They lead not only to false colors or incorrect positions of points, but also to gaps (missing points) in the objects. While conventional bottom-up methods may encounter insurmountable difficulties in this case, resulting in irregular and/or incomplete building components, the proposed method guarantees plausible results despite such flaws.

10.6.2 Primitive Assembly

If a building consists of multiple primitives, the reconstructed primitives are assembled into a single model in two consecutive steps: (1) Joint parametric adjustment and (2) geometrical model merging.

The “joint parametric adjustment” helps to remove trivial conflicts between primitives and compensates for small deviations (cf. Fig. 10.19, top left), which can occur during the reconstruction driven by a stochastic process. In the adjustment, the change of each side of a primitive is proportional to its size, i.e., footprint area. The parameters of all building components are jointly adjusted using two rules [43]:

where the thresholds are determined according to data resolution and quality.

The parameter adjustment, however, cannot deal with all mismatching positions of the primitives. The mismatching is the result of deviations caused by stochastic processes and the uncertainty of the data, which in principle cannot be corrected in this step. Therefore, a further geometrical adjustment is required. “Geometrical model merging” generates the final single model of a building complex. Similar to [43], we conduct a simple vertex-shifting to correct the geometrical mismatching and all the primitives are matched to each other (Fig. 10.19, bottom left). The primitives are originally generated as Boundary Representation (B-Rep) models, as shown in Fig. 10.19 (center), and simply placed together as separate models which overlap. Although in the rendered model (left) the intersecting part is hidden and does not affect the appearance, the model is ontologically not a single “subject” and geometrically not watertight. To fix this, our model merging employs Constructive Solid Geometry (CSG) modeling. The B-Rep primitives are first converted into CSG models and merged with a “union” operation into a single solid body (cf. Fig. 10.19, right). The latter is then converted back to a single and watertight B-Rep model, i.e., the final model.

10.6.3 LoD2 Models

We have performed experiments on the Bonnland dataset (cf. Sect. 10.4), representing a complete and typical central European village with a mixture of detached buildings and building complexes, a church, as well as a small castle on a hill. The 3D point cloud has been reconstructed from UAV imagery [33] and covers about 0.12 square kilometers of undulating terrain. We use a reduced and rasterized version with a resolution of 0.2 meters.

The building mask provided by scene classification (cf. Sect. 10.4) is decomposed into 62 connected components and corresponding data tiles (cf. Fig. 10.14), which are processed in parallel. The reconstructed building models are assembled in the global coordinate system. Bird's-eye views of input point cloud (top) and the reconstructed model (bottom) are presented in Fig. 10.20. Along with the watertight building models a mesh model is generated from the non-building points to model the ground.

The runtime of building modeling for 33 detached buildings and 29 building complexes, which consist of 112 primitives, is about 14 minutes on a laptop with a four cores/eight threads CPU at 2.3 GHz. Except for buildings with large flaws in the data (cf. Fig. 10.18, bottom) or occlusions, where the average deviation does not reflect the reconstruction accuracy, the reconstruction error of the majority of the buildings is less than half of the resolution, i.e., 10 centimeters.

10.6.4 Detection of Facade Elements

As the original input to the described workflow are images and because semantic analysis by Convolutional Neural Networks (ConvNets) has made significant progress in recent years, it seems promising to use this technique for the detection of facade elements. To reduce the necessary computational complexity when using a ConvNet, we restrict the image regions to the facades.

The building primitives define planar elements for roofs and facades. Once the optimum primitives have been determined, the facade planes can be derived in the form of polygons defined by vertices. The corresponding regions of a facade can then be extracted from the images and projected via a planar homography onto the same virtual fronto-parallel plane. Assuming that the facade including all elements, such as windows and doors, is almost planar, the projections from all images should have a similar position on the virtual plane. This reduces the search space for our ConvNet to a limited two-dimensional space. Fig. 10.21 shows the projections of three different views of one facade onto its corresponding virtual plane.

An adapted ConvNet [53] is employed to detect the facade elements in the images (cf. Fig. 10.22). The network is based on AlexNet [54], which was pretrained on the ImageNet dataset [55] and is extended by a set of convolutional (Conv) and deconvolutional (DeConv) layers to achieve pixelwise classification.

Rectified facades from the eTRIMS dataset [56] were used for fine-tuning the network to classify facade images into the four classes building, door, wall, and other. The results of the ConvNet for individual images are combined by summation of the output of the last fully connected (FC) layer and application of the softmax function to the sum. A rectangle is fitted to each window and door and, finally, the facade elements are projected back into the original 3D model which allows one to generate the LOD3 model (cf. next section). In Fig. 10.23 the process is visualized using one of several images.

10.6.5 Shell Model

We propose the so-called “shell model”—a hybrid model combining elements of CSG and BRep—for the modeling of buildings in LoD3. The motivations for the “shell model” are:

A shell is, therefore, considered a more reasonable and practical geometrical assumption (model) compared to a simple surface or a solid body. The concept of the shell model is presented in Fig. 10.24. It consists of parallel inner- and outer-layers and the solid body defined by them.

The shell model is specifically designed for our application, in which the images from both airborne and terrestrial cameras are fused and the reconstructed point cloud (cf. Sect. 10.3) is available for both roofs and facades. In comparison with the modeling approaches for either roof or facade data (Fig. 10.25, top), the advantages of the shell model can be summarized as follows:

Fig. 10.26 presents the reconstruction of Building 1 using the shell model. The shell model (center) is initially used for building detection from the input point cloud (left) with inner (red) and outer (blue) layers. The model of best fit is then assumed to be the layer (green) between them. The final model (right) is generated with integrated windows as well as door and a given thickness of the walls.