# Aggregation of 3D buildings using a hybrid data approach.

Introduction

The adequate presentation of 3D landscape models--particularly of urban regions--becomes increasingly important as the availability of such data sets increases. Although it has already been demonstrated that the real-time rendering of completely textured 3D city models is possible with current commodity 3D graphics hardware (Kada et al. 2003; Buchholz and Dollner 2005), different levels of detail are still essential for network transmission visibility, analysis and visualization, especially for mobile applications like pedestrian navigation systems. As photorealistic views pose huge information loads on humans, the 3D building models need to be generalized under cartographic considerations with the purpose to make spatial situations easier and faster to comprehend.

While there has been and continues to be much work done in the 2D domain (Haunert and Wolff 2010), the topic of 3D generalization is rather new. Only few approaches have so far been presented, and most focus on the geometric simplification of single buildings. Whereas surface simplification approaches known from the field of computer graphics are meant for general shapes, the simplification of 3D building models in a cartographic sense is commonly expected to preserve existing shape symmetries and regularities like co-planar, parallel, and rectangular alignment of facade walls. For this purpose, 3D generalization approaches have been proposed that add restrictions to surface simplification operators (Coors 2001; Kada 2002; Rau et al. 2006), use mathematical morphology and specially designed curvature-space operators (Forberg 2004), apply feature segmentation, recognition, and elimination (Thiemann and Sester 2004), match and replace complex shapes with coarse parameterized templates (Thiemann and Sester 2006), and detect shape symmetries by crystallographic analyses (Poupeau and Ruas 2007).

However, for 3D city models that are currently being produced for large areas, their geometric complexity does not come from the individual buildings, as the majority thereof are of rather low detail, but from the large number of entities that can easily reach into the hundreds of thousands. Only few landmarks are modeled by means of terrestrial data, or by hand feature high detail. Therefore, the simplification process on its own has a natural limit up to which the complexity of such models can be reduced without violating the above-mentioned restrictions. For example, a single-family house with a saddleback roof can be simplified to a rectangular ground plan with four facade sides and two roof faces; maybe one if the roof is generalized to a flat roof. But a further simplification is not possible without losing the characteristics of a building or deleting it entirely from the data set.

The classic motivation of cartographic generalization states that if a feature cannot be properly presented in a map due to its scale, then it should be eliminated, accentuated, or replaced by something that allows for better readability Regarding closely located buildings that are often found in urban areas that cannot be distinguished as single objects, their aggregation to a larger building block can help to further reduce the complexity without changing the appearance of the spatial situation. Small gaps or even wider openings between the buildings are eliminated in the process with regard to some distance criteria. One of the few approaches for the geometric aggregation of 3D buildings is presented in Anders (2005): building groups are projected into three orthogonal directions, their silhouettes simplified in 2D with the ground plan generalization software CHANGE, the results extruded and then intersected to form the generalized 3D building group. For the purpose of interactive visualizations of 3D city models, Glander and Dollner (2009) show abstraction techniques that also include the aggregation of city blocks. Depending on the context, important landmarks are maintained in their original state to better help the viewer to focus on the current task. However, both aggregation approaches have only shown to produce flat roof shapes.

In this paper, we introduce an extension of a simplification algorithm that aggregates buildings with their specific roof shapes. The algorithm relies on an overlap test, which is altered with the use of morphological operations to allow for an aggregation of buildings. As these operations are not well-defined for vector models, the polygonal models need first to be transformed into raster representations, thus motivating the hybrid data approach. Although the purpose is to aggregate buildings, the modification also helps to close holes and concavities by the generalization with large simplification thresholds. Such cases are, however, rather uncommon and the focus is therefore on the aggregation. Because the generation of the roof structure for aggregated buildings is quite difficult in certain cases, a discussion and some possible solutions are also provided.

[FIGURE 1 OMITTED]

3D Building Simplification

In previous research (Kada 2007), a generalization approach was proposed that generates low detailed versions of any given vectorial 3D building model. In contrast to general surface simplification approaches or many 2D generalization algorithms for ground plans, the simplification is not performed in an iterative process, where the most "insignificant" detail of the model is step by step identified and removed. Rather, a new model with a simplified shape is constructed from scratch in the solid modeling representation called cell decomposition (Foley et al. 1990). In short, cell decomposition can be considered as a restricted form of constructive solid geometry (CSG). The predominantly simple cells must not intersect one another, but can be "glued" together to construct more complex shapes. However, models in cell decomposition are usually not constructed, but rather generated in a decomposition process in order to gain cells of simple shape for which geometric computations become much easier.

Here, the simplification of a 3D building model in cell decomposition works as follows (see Figure 1). In the first phase, a ground-plan decomposition is generated from the building facade. For this purpose, a minimum set of vertical planes is determined by averaging the plane equations of similarly oriented facade polygons that are located within some user-defined simplification distance. Facade faces with a non-zero z-value in their normal direction are at this point ignored. Then, a solid block with a size that is much larger than the original building is taken and divided approximately along these facade planes, thereby producing the initial cell decomposition. The resulting cells are now tested against the original ground plan and only the ones with an overlap value that is higher than a given threshold are kept for further processing; the other cells are discarded. The intermediate result is a cell decomposition that approximates the original ground plan and therefore is a good 2D generalization. Now in order to gain a real 3D building model with a simplified roof structure, the former three steps of finding approximating planes, further decomposing the extruded ground plan cells, and testing the overlap are repeated in the second phase, but now with planes generated from the roof polygons.

In an alternative approach for the second phase of the algorithm, the original roof structure can be analyzed in order to determine the general building roof type. Each cell is then given a parameterized roof shape that best fits the original shape. Special care has to be taken for cells that form corners and junctions, so that different roof types fit well to one another. Whereas the first approach for roof generalization works on general shapes, the second one is restricted to standard shapes like flat, pent, saddleback, hipped roof, etc. However, due to its restrictions, the second approach always produces valid roof shapes, which is not guaranteed for the first.

If the simplification algorithm receives more than one building as input, it considers them as one object with many parts and processes them as described, aggregating the buildings if they are closer to one another than the above mentioned simplification threshold (see e.g. Figure 2). The approximating planes are in this case determined from all buildings facades, which results in a common facade and roof structure. Although additional planes are generated in between buildings, they do not affect the result as long as they do not come in pairs, because adjacent cells are "glued" together.

[FIGURE 2 OMITTED]

However, as illustrated in Figure 3, the algorithm produces less reliable results if there es empty space between buildings. On the left side in Figure 3, the two rectangular building footprints are depicted with increasing distances from top to bottom, which leads to differences in the cell decomposition (dotted lines in the middle column). If the distance remains shorter than the simplification threshold, then the space in between the buildings is decomposed once (top and middle row). As the responsible decomposition plane approximates the facades of both buildings, the plane lies exactly in the middle of the two buildings, with results in two elongated cells that adjoin at this position. The elongated area of the cells has no overlap with the original building footprint (highlighted in red) and will lower the overlap value of these cells. Whereas the overlap values of the top row cells are still over 90%, the values in the middle row drop to around 75%. If the overlap threshold is for example 80%, the cells in the middle row are considered non-building cells and are consequently discarded and no resulting model is constructed at all (dashed rectangles). The problem could be counteracted by lowering the overlap threshold, however, this is not a sound solution as it will inevitably lead to additional problems and not improve the reliability- of the algorithm. Now as the distance becomes greater than the simplification threshold (bottom row), two decomposition planes are generated because one plane can no longer approximate both facades. The decomposition produces additional cells in between the planes, but they have no overlap with the original ground plan, so no aggregation occurs for this case. To make an aggregation of the two buildings possible, the area in between them must also be considered as being part of the original ground plan. Only then can it positively contribute to the overlap value of the cells located in between the building that are needed to fill the respective space.

[FIGURE 3 OMITTED]

The desired level of detail is controlled by the simplification distance. The greater the simplification distance, the fewer planes that are needed to approximate the original shape. This subsequently results in fewer cells and therefore a model with fewer details (Figure 4). Also, the overlap values of the cells decrease, which is a general problem of the algorithm and becomes especially apparent for the purpose of aggregation. In summary, the simplification approach is able to aggregate adjoining buildings, but produces less reliably valid models if more than one object is processed at a time and if the simplification distance threshold increases. The solution must somehow increase the overlap values of the cells that are to be retained so that the overlap threshold must not be lowered, which makes the whole process less likely to produce valid results.

[FIGURE 4 OMITTED]

As a side note, to allow for more flexibility in the simplification process, two distance thresholds can be defined, one for the ground plane simplification and another for the roof simplification.

3D Building Aggregation

Even though the simplification algorithm fails to generate a valid model for buildings that are located slightly apart from each other, it already produces a cell decomposition with all the necessary building blocks for their aggregation. It is only due to the low overlap with the ground plan that the cells in the aggregation area are, at least from an algorithmic point of view, correctly classified as non-building cells and therefore discarded. Now in order to keep those cells in question for the intended building aggregation, the computation of the overlap must be performed on an altered ground plan where the areas in between the buildings positively contribute to the overlap value. As will be seen, this is accomplished by letting the buildings grow towards each other in order to close the relevant areas, but without having too much of a growing effect on the other parts of the ground plan.

Regarding the generalization of 3D building models, Mayer (1998) and Forberg (2004) have conducted similar work by using mathematical morphology on vector data as a tool to merge closely adjacent buildings. However, their models feature only rectangular structures and it is not clear how morphology would work on arbitrary vectorial shapes. It is therefore more common to apply morphology to raster data (Serra 1982). It has already been suggested by Li (1996) to use dilation, erosion, opening and closing operations to transform arbitrarily shaped raster objects to different scale dimensions. So the idea for filling the areas in between buildings in this study is to use mathematical morphology on a raster representation of the ground plan, and then perform the overlap test in raster space.

For this purpose, the vectorial 2D ground plan and the 2D information of the cell decomposition are first converted to raster representations, which for the sake of simplicity consist of two equally sized grids of square cells covering the same area. The size of the cells is at this time fixed to a value of 0. lm, which results in a representation of high enough resolution to allow generalizations with very short distance thresholds. However, the resolution could veiN likely be put in relation to the distance threshold in order to lower memory requirements and improve processing performance. Because the buildings need to be able to grow in all directions, the raster representation also covers a broad empty area around the ground plans. As for the raster cell's values, identifiers of buildings are stored therein in order to keep track of which building grew into the corresponding areas. This information can later be used to determine a suitable roof landscape for the aggregated building model.

The stepwise filling of the area in between buildings can now be performed on the raster representation of the ground plan by repeatedly applying the dilation operation. A detailed description of all morphological operations can be found in Serra (1982). In short, a new raster grid of the same size and dimension as the original one is generated, where the values of the new raster cells are determined from values of the original grid that are identified by a structuring element. Here, a 3 x 3 square mask around the probed raster cell is applied. The dilation operation, however, is slightly altered as the grid stores building identifiers instead of binary or gray-scale values. If the original raster cell has a stored value, then it should not change and it is just copied to the new grid cell. In the other case where the original cell is empty, the eight neighbor cells have to be regarded. If they are all empty too, then the cell remains empty. Otherwise, the building that occupies the most neighbor cells grows and its identifier is stored therein. If two or more buildings occupy the same number of neighbor cells, one building is randomly chosen. This way, all buildings will grow by the same amount, generating a fuzzy border area at the grid cells where the buildings meet.

The number of dilation operations that need to be applied for the filling is easily computed by dividing the simplification distance by the raster grid's cell size. As the areas in between the buildings are filled from at least two sides, half that number is actually sufficient. However, to counteract errors due to inaccuracies, a few more repetitions are added for reliability reasons. Otherwise, grid cells that remain empty will open up the area again in the subsequent erosion step. The erosion operation has the inverse effect as dilation, and by applying it the same number of times to the grid restores the original boundary of the ground plan as best as possible. This is accomplished by clearing all grid cells of their building identifiers if at least one of their neighbor cells (determined by the structuring element) is not occupied by a building. As there are no empty grid cells in the filled areas in between buildings, they will not open up by this operation. The described morphological operations applied on two example buildings are depicted in Figure 5. It should be noted that the images of the ground plan grids are rotated to better resemble the 3D models.

When overlaid with the cell decomposition (Figure 6), it becomes visible that the cell that contains the red building in the back has a low overlap due to the gap in between the buildings. The morphological operations help to increase the value of this cell from 78% to 98%. Also the courtyard of the building from Figure 1 is filled, which is necessary when the simplification distance becomes greater than one of its dimensions. Otherwise the cell that overlaps this area will get discarded. However, the overlap for this particular cell could be increased from 52% to 99%, which is more than other cells in this example feature.

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

Another example with small buildings that are spread further apart is shown in Figure 7. The blue cell that is second from the right exhibits a low overlap of only 64%. Although the threshold that classifies a 2D cell as a building block could in this case also be lowered without any consequences to the new ground plan, this is generally not a viable solution. The 3D overlap threshold would need to be lowered also when determining the roof structure, which could negatively affect the classification of 3D cells. However, with the morphologically altered ground plan the overlap of the aforementioned cell increases to 99%. With such high values, all above mentioned examples allow for a reliable classification of cells as building blocks after morphology, and these problem areas are eliminated.

[FIGURE 7 OMITTED]

After morphology, the overlap test can now be carried out by overlaying the raster representation of the cell decomposition with the one of the ground plan. Then for each cell the ratio of the number of its raster elements that are also set in the grid representation of the ground plan to its overall number is determined. If this ratio is greater than the overlap threshold, then the vectorial representation of the cell is regarded a building cell and its vectorial representation is kept for further processing. Otherwise it is discarded. The whole process of the overlap test is depicted in Figure 8. Note that the generation of the approximating planes is omitted here. Also the vectorial representation is considered as an input to the overlap test because the cells get flagged with regard to the test result.

As for the overlap threshold, a much higher value is possible with morphology than without. But as can be seen in Figure 6, morphology will not change the overlap value in the border area (lower right cell on right example), so this value has still to be chosen carefully to allow for some overlap tolerance of these cells.

[FIGURE 8 OMITTED]

One problem that morphology exhibits is that the boundaries are changed if they are not aligned with the edges of the structuring element. After repeatedly applying the aforementioned operations, the boundaries are forced to align with the structuring element. This is depicted in Figure 9 for one of the previous examples.

[FIGURE 9 OMITTED]

To counteract this phenomenon, all buildings are rotated prior to their generalization so that their main directions coincide with one of the axis of the Cartesian coordinate system. This lessens the effect, but cannot completely remove it, especially for building models whose two mayor directions are not perpendicular to one another. The raster representation cannot easily be adapted to this, as those buildings usually have even more than two main directions.

Roof Shapes

Up to now, we have only discussed the part of the ground plan generalization and left out how to handle roof structures. For 3D building groups, where the objects are directly adjacent to one another, the original approach can be used: approximating planes are first generated from the roof surfaces, then the ground plan cells are decomposed and the overlap of the resulting cells with the original model determined in 3D. For spaced out buildings, the morphological operations are in addition applied, similar to the 2D case, but now with a 9 x 9 cubic mask as a structuring element on a volumetric raster representation. Figure 10 shows two aggregation results for a group of four buildings with 3m and 2m ground plan simplification threshold. To obtain a fairly detailed roof structure, the responsible roof simplification threshold is 2m in both examples. For their aggregation, the raster model of 0.1m resolution was dilated 15 times in order to include all four buildings in the result. This example shows that the simplification thresholds for the ground plan and the roof and the aggregation threshold can all be independently set in order to allow for highest flexibility. As overlap threshold, 80% was set to allow for some overlap tolerance in the border areas.

[FIGURE 10 OMITTED]

As mentioned in the previous section, morphological operations smooth structural concavities if their faces are not aligned to the elements of the raster model. However, saddleback roofs with ridges that follow a line like in Figure 10 are not affected too much. If the slopes form a valley, then morphology closes them and the cells in between gain more overlap. As the overlap values of the cells with the altered building models are in general more effective, using a higher overlap threshold can help to avoid the erroneous classifications of cells.

A general question is how should the roof shapes of aggregated 3D building models look, if for example the gables of saddleback roofs are not facing towards each other, but towards the other way? Figure 11 shows the front view of two buildings with saddleback roofs and their decomposition planes (as dashed lines) determined from the roof faces. As the morphological operations fill the space between the two buildings, the area below the eaves will be closed and shall at this point not be considered anymore. The simplification distance is less than the perpendicular distances between the two pairs of parallel roof faces, so there are four decomposition planes, which results in a building model with two ridges. As depicted in the middle of Figure 11, the two ridges remain at their original position and the roof slopes are the same. The valley that is formed therefore lies below the eaves (dashed line on 3D model). The further the buildings are apart from each other, the lower the valley and the larger the asymmetry of the two saddleback roof parts. To correct for this, the ridges could be pushed towards the middle until the valley is at the same height as the eaves (Figure 11 right). However, the roof generalization with decomposition planes does not accommodate for this.

[FIGURE 11 OMITTED]

A workaround could be to add horizontal decomposition planes at the eaves and ridge heights (dashed lines in Figure 12). Depending on how much of the space between the planes gets filled by the morphological operations, the result would be the partially flat roof shape as depicted Figure 12. Both results have their drawbacks: in the first version, a small flat element is introduced, which stands against the goal of generalization to simplify shapes, and in the second version the saddleback roofs are not apparent anymore and thus an important characteristic of the buildings is lost.

[FIGURE 12 OMITTED]

A third alternative is to include the (gray) cell in the middle of the four decomposition planes as depicted in Figure 13. The result is a large building with a saddleback roof. However, it is unclear how the rather generic algorithm would need to be altered for this. Even after the morphological operations, the raster model will only fill a small portion of this cell. But once the saddleback roof is generated, the height of the eaves and ridge could be altered to better fit the original shape.

[FIGURE 13 OMITTED]

Even for this simple example of two buildings, the handling of the roof for the aggregation of 3D building models proves to be very difficult and offers many shape variations as potential results. Not all are possible to generate with the presented algorithm. In this author's opinion, the resulting roof type should be at least the same as the most dominant one of the original buildings. General shapes that are correct from an algorithmic point of view, but do not resemble a real shape are not acceptable. It is therefore suggested to use parameterized roof shapes as presented in (Kada, 2007). Here, the roof types of the original model are determined and the most dominant one given to the generalized version. The advantage is that the roof shapes can be defined to produce all the results as seen in this subsection, so that different applications can get specific models.

Conclusion

The extension of the generalization algorithm for 3D building models presented in this article allows for a more reliable classification of cells into building and non-building cells for both the simplification of single buildings as well as for the handling of buildings groups. By converting the building models into 2D and 3D raster representations, morphological operations are now possible and allow for an aggregation of spaced out buildings without changing the underlying generalization algorithm. Examples and results are given from the authoritative data set provided by the City Surveying Office of Stuttgart.

One limitation of the morphological operations is that their repeated execution can change the shape of the objects' boundaries. The data sets need therefore be first rotated, so that the buildings' main directions are aligned with the structuring elements. This is most often possible with ground plans and therefore leads to good results for this part of the algorithm. However, the problem does remain for the handling of the 3D roof structures. If the roof does not form valleys, the problem does not become apparent and the algorithm has shown to produce valid results. Some possible results have been discussed, but not all are possible without severely altering the algorithm. The use of parameterized roof shapes seems therefore to be the most promising solution. It restricts the roof shapes to be symmetric and offers a high degree of freedom to adjust the generalization results to different application fields.

Concerning the scalability of the algorithm, the memory usage and computing time increases with the number of raster cells in each dimension, and are approximately cubic (O(n3)). It has not yet been evaluated what raster size is necessary to achieve the most representative results. But the cell size can most likely be put in relation to the aggregation threshold, which is by nature a few meters wide and therefore results in only a few thousand cells per building block. As the morphological evaluation of each raster cell is performed independently from any other cell, the approach can be highly parallelized so that an efficient processing is possible even for raster representations of large areas.

REFERENCES

Anders, K.-H. 2005. Level of Detail Generation of 3D Building Groups by Aggregation and Typification. In: Proceedings of the XXII International Cartographic Conference, La Coruna, Spain.

Buchholz, H. and J. Dollner. 2005. View-Dependent Rendering of Multiresolution Texture-Atlases. In: IEEE Visualization 2005 (VIS 2005), IEEE Computer Society Press, pp. 215-222.

Coors, V. 2001. Feature-Preserving Simplification in Web-Based 3D-GIS. In Proceedings of the 1st International Symposium on Smart Graphics. Hawthorne, USA, pp. 22-28.

Foley, J., A. van Dam, S. Feiner and J. Hughes. 1990. Computer Graphics: Principles and Practice (2nd Edition), Addison-Wesley

Forberg, A. 2004. Generalization of 3D Building Data based on a Scale-Space Approach. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Istanbul, Turkey, Vol. XXXV, Part B, pp. 195-199.

Glander, T. and J. Dollner. 2009. Abstract Representations for Interactive Visualization of Virtual 3D City Models. Computer, Environment and Urban Systems 33(5): 375-387.

Haunert, J.-H. and A. Wolff. 2010. Optimal and Topologically Safe Simplification of Building Footprints. In Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems ACM-GIS'10, pp. 192-201.

Kada, M. 2002. Automatic Generalization of 3D Building Models. In Proceedings of the Joint International Symposium on Geospatial Theory, Processing and Applications, Ottawa, Canada.

Kada, M., S. Roettger, K. Weiss, T. Ertl and D. Fritsch. 2003. Real-Time Visualization of Urban Landscapes using Open-Source Software. In Proceedings of the 24th Asian Conference on Remote Sensing & 2003 International Symposium on Remote Sensing. ACRS 2003 ISRS, Busan, Korea.

Kada, M. 2007. Scale-Dependent Simplification of 3D Building Models Based on Cell Decomposition and Primitive Instancing. In Proceedings of the International Conference on Spatial Information Theory: COSIT'07, Melbourne, Australia, pp. 222-237.

Li, Z. 1996. Transformation of Spatial Representation in Scale Dimension: A New Paradigm for Digital Generalization of Spatial Data. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXI, Part B3, Vienna, Austria, pp. 453-458.

Mayer, H. 1998. Model-Generalization of Building Outlines Based on Scale-Spaces And Scale-Space Events. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXII, Part 3, Columbus, Ohio, USA, pp. 530-536.

Poupeau, B. and A. Ruas. 2007. A Crystallographic Approach to Simplify 3D Building. In Proceedings of the 23rd International Cartographic Conference, Moscow, Russia.

Rau, J.Y., L.C. Chen, F. Tsai, K.H. Hsiao and W.C. Hsu. 2006. Automatic Generation of Pseudo Continuous LoDs for 3D Polyhedral Building Model. In Innovation in 3D Geo Information Systems, Springer Verlag, Berlin.

Serra, J. 1982. Image Analysis and Mathematical Morphology. Academic Press, London.

Thiemann. E and M. Sester. 2004. Segmentation of Buildings for 3D-Generalisation. In Working Paper of the ICA Workshop on Generalisation and Multiple Representation, Leicester, UK.

Thiemann. E and M. Sester. 2006.3D-Symbolization using Adaptive Templates. In Proceedings of the GICON, Wien, Austria.

Martin Kada, Institute for Geoinformatics and Remote Sensing (IGF), University of Osnabruck, Barbarastr. 22b, 49076 Osnabruck, Germany. Email:<martin.kada@uniosnabrueck.de>

DOI: 10.1559/15230406382154

The adequate presentation of 3D landscape models--particularly of urban regions--becomes increasingly important as the availability of such data sets increases. Although it has already been demonstrated that the real-time rendering of completely textured 3D city models is possible with current commodity 3D graphics hardware (Kada et al. 2003; Buchholz and Dollner 2005), different levels of detail are still essential for network transmission visibility, analysis and visualization, especially for mobile applications like pedestrian navigation systems. As photorealistic views pose huge information loads on humans, the 3D building models need to be generalized under cartographic considerations with the purpose to make spatial situations easier and faster to comprehend.

While there has been and continues to be much work done in the 2D domain (Haunert and Wolff 2010), the topic of 3D generalization is rather new. Only few approaches have so far been presented, and most focus on the geometric simplification of single buildings. Whereas surface simplification approaches known from the field of computer graphics are meant for general shapes, the simplification of 3D building models in a cartographic sense is commonly expected to preserve existing shape symmetries and regularities like co-planar, parallel, and rectangular alignment of facade walls. For this purpose, 3D generalization approaches have been proposed that add restrictions to surface simplification operators (Coors 2001; Kada 2002; Rau et al. 2006), use mathematical morphology and specially designed curvature-space operators (Forberg 2004), apply feature segmentation, recognition, and elimination (Thiemann and Sester 2004), match and replace complex shapes with coarse parameterized templates (Thiemann and Sester 2006), and detect shape symmetries by crystallographic analyses (Poupeau and Ruas 2007).

However, for 3D city models that are currently being produced for large areas, their geometric complexity does not come from the individual buildings, as the majority thereof are of rather low detail, but from the large number of entities that can easily reach into the hundreds of thousands. Only few landmarks are modeled by means of terrestrial data, or by hand feature high detail. Therefore, the simplification process on its own has a natural limit up to which the complexity of such models can be reduced without violating the above-mentioned restrictions. For example, a single-family house with a saddleback roof can be simplified to a rectangular ground plan with four facade sides and two roof faces; maybe one if the roof is generalized to a flat roof. But a further simplification is not possible without losing the characteristics of a building or deleting it entirely from the data set.

The classic motivation of cartographic generalization states that if a feature cannot be properly presented in a map due to its scale, then it should be eliminated, accentuated, or replaced by something that allows for better readability Regarding closely located buildings that are often found in urban areas that cannot be distinguished as single objects, their aggregation to a larger building block can help to further reduce the complexity without changing the appearance of the spatial situation. Small gaps or even wider openings between the buildings are eliminated in the process with regard to some distance criteria. One of the few approaches for the geometric aggregation of 3D buildings is presented in Anders (2005): building groups are projected into three orthogonal directions, their silhouettes simplified in 2D with the ground plan generalization software CHANGE, the results extruded and then intersected to form the generalized 3D building group. For the purpose of interactive visualizations of 3D city models, Glander and Dollner (2009) show abstraction techniques that also include the aggregation of city blocks. Depending on the context, important landmarks are maintained in their original state to better help the viewer to focus on the current task. However, both aggregation approaches have only shown to produce flat roof shapes.

In this paper, we introduce an extension of a simplification algorithm that aggregates buildings with their specific roof shapes. The algorithm relies on an overlap test, which is altered with the use of morphological operations to allow for an aggregation of buildings. As these operations are not well-defined for vector models, the polygonal models need first to be transformed into raster representations, thus motivating the hybrid data approach. Although the purpose is to aggregate buildings, the modification also helps to close holes and concavities by the generalization with large simplification thresholds. Such cases are, however, rather uncommon and the focus is therefore on the aggregation. Because the generation of the roof structure for aggregated buildings is quite difficult in certain cases, a discussion and some possible solutions are also provided.

[FIGURE 1 OMITTED]

3D Building Simplification

In previous research (Kada 2007), a generalization approach was proposed that generates low detailed versions of any given vectorial 3D building model. In contrast to general surface simplification approaches or many 2D generalization algorithms for ground plans, the simplification is not performed in an iterative process, where the most "insignificant" detail of the model is step by step identified and removed. Rather, a new model with a simplified shape is constructed from scratch in the solid modeling representation called cell decomposition (Foley et al. 1990). In short, cell decomposition can be considered as a restricted form of constructive solid geometry (CSG). The predominantly simple cells must not intersect one another, but can be "glued" together to construct more complex shapes. However, models in cell decomposition are usually not constructed, but rather generated in a decomposition process in order to gain cells of simple shape for which geometric computations become much easier.

Here, the simplification of a 3D building model in cell decomposition works as follows (see Figure 1). In the first phase, a ground-plan decomposition is generated from the building facade. For this purpose, a minimum set of vertical planes is determined by averaging the plane equations of similarly oriented facade polygons that are located within some user-defined simplification distance. Facade faces with a non-zero z-value in their normal direction are at this point ignored. Then, a solid block with a size that is much larger than the original building is taken and divided approximately along these facade planes, thereby producing the initial cell decomposition. The resulting cells are now tested against the original ground plan and only the ones with an overlap value that is higher than a given threshold are kept for further processing; the other cells are discarded. The intermediate result is a cell decomposition that approximates the original ground plan and therefore is a good 2D generalization. Now in order to gain a real 3D building model with a simplified roof structure, the former three steps of finding approximating planes, further decomposing the extruded ground plan cells, and testing the overlap are repeated in the second phase, but now with planes generated from the roof polygons.

In an alternative approach for the second phase of the algorithm, the original roof structure can be analyzed in order to determine the general building roof type. Each cell is then given a parameterized roof shape that best fits the original shape. Special care has to be taken for cells that form corners and junctions, so that different roof types fit well to one another. Whereas the first approach for roof generalization works on general shapes, the second one is restricted to standard shapes like flat, pent, saddleback, hipped roof, etc. However, due to its restrictions, the second approach always produces valid roof shapes, which is not guaranteed for the first.

If the simplification algorithm receives more than one building as input, it considers them as one object with many parts and processes them as described, aggregating the buildings if they are closer to one another than the above mentioned simplification threshold (see e.g. Figure 2). The approximating planes are in this case determined from all buildings facades, which results in a common facade and roof structure. Although additional planes are generated in between buildings, they do not affect the result as long as they do not come in pairs, because adjacent cells are "glued" together.

[FIGURE 2 OMITTED]

However, as illustrated in Figure 3, the algorithm produces less reliable results if there es empty space between buildings. On the left side in Figure 3, the two rectangular building footprints are depicted with increasing distances from top to bottom, which leads to differences in the cell decomposition (dotted lines in the middle column). If the distance remains shorter than the simplification threshold, then the space in between the buildings is decomposed once (top and middle row). As the responsible decomposition plane approximates the facades of both buildings, the plane lies exactly in the middle of the two buildings, with results in two elongated cells that adjoin at this position. The elongated area of the cells has no overlap with the original building footprint (highlighted in red) and will lower the overlap value of these cells. Whereas the overlap values of the top row cells are still over 90%, the values in the middle row drop to around 75%. If the overlap threshold is for example 80%, the cells in the middle row are considered non-building cells and are consequently discarded and no resulting model is constructed at all (dashed rectangles). The problem could be counteracted by lowering the overlap threshold, however, this is not a sound solution as it will inevitably lead to additional problems and not improve the reliability- of the algorithm. Now as the distance becomes greater than the simplification threshold (bottom row), two decomposition planes are generated because one plane can no longer approximate both facades. The decomposition produces additional cells in between the planes, but they have no overlap with the original ground plan, so no aggregation occurs for this case. To make an aggregation of the two buildings possible, the area in between them must also be considered as being part of the original ground plan. Only then can it positively contribute to the overlap value of the cells located in between the building that are needed to fill the respective space.

[FIGURE 3 OMITTED]

The desired level of detail is controlled by the simplification distance. The greater the simplification distance, the fewer planes that are needed to approximate the original shape. This subsequently results in fewer cells and therefore a model with fewer details (Figure 4). Also, the overlap values of the cells decrease, which is a general problem of the algorithm and becomes especially apparent for the purpose of aggregation. In summary, the simplification approach is able to aggregate adjoining buildings, but produces less reliably valid models if more than one object is processed at a time and if the simplification distance threshold increases. The solution must somehow increase the overlap values of the cells that are to be retained so that the overlap threshold must not be lowered, which makes the whole process less likely to produce valid results.

[FIGURE 4 OMITTED]

As a side note, to allow for more flexibility in the simplification process, two distance thresholds can be defined, one for the ground plane simplification and another for the roof simplification.

3D Building Aggregation

Even though the simplification algorithm fails to generate a valid model for buildings that are located slightly apart from each other, it already produces a cell decomposition with all the necessary building blocks for their aggregation. It is only due to the low overlap with the ground plan that the cells in the aggregation area are, at least from an algorithmic point of view, correctly classified as non-building cells and therefore discarded. Now in order to keep those cells in question for the intended building aggregation, the computation of the overlap must be performed on an altered ground plan where the areas in between the buildings positively contribute to the overlap value. As will be seen, this is accomplished by letting the buildings grow towards each other in order to close the relevant areas, but without having too much of a growing effect on the other parts of the ground plan.

Regarding the generalization of 3D building models, Mayer (1998) and Forberg (2004) have conducted similar work by using mathematical morphology on vector data as a tool to merge closely adjacent buildings. However, their models feature only rectangular structures and it is not clear how morphology would work on arbitrary vectorial shapes. It is therefore more common to apply morphology to raster data (Serra 1982). It has already been suggested by Li (1996) to use dilation, erosion, opening and closing operations to transform arbitrarily shaped raster objects to different scale dimensions. So the idea for filling the areas in between buildings in this study is to use mathematical morphology on a raster representation of the ground plan, and then perform the overlap test in raster space.

For this purpose, the vectorial 2D ground plan and the 2D information of the cell decomposition are first converted to raster representations, which for the sake of simplicity consist of two equally sized grids of square cells covering the same area. The size of the cells is at this time fixed to a value of 0. lm, which results in a representation of high enough resolution to allow generalizations with very short distance thresholds. However, the resolution could veiN likely be put in relation to the distance threshold in order to lower memory requirements and improve processing performance. Because the buildings need to be able to grow in all directions, the raster representation also covers a broad empty area around the ground plans. As for the raster cell's values, identifiers of buildings are stored therein in order to keep track of which building grew into the corresponding areas. This information can later be used to determine a suitable roof landscape for the aggregated building model.

The stepwise filling of the area in between buildings can now be performed on the raster representation of the ground plan by repeatedly applying the dilation operation. A detailed description of all morphological operations can be found in Serra (1982). In short, a new raster grid of the same size and dimension as the original one is generated, where the values of the new raster cells are determined from values of the original grid that are identified by a structuring element. Here, a 3 x 3 square mask around the probed raster cell is applied. The dilation operation, however, is slightly altered as the grid stores building identifiers instead of binary or gray-scale values. If the original raster cell has a stored value, then it should not change and it is just copied to the new grid cell. In the other case where the original cell is empty, the eight neighbor cells have to be regarded. If they are all empty too, then the cell remains empty. Otherwise, the building that occupies the most neighbor cells grows and its identifier is stored therein. If two or more buildings occupy the same number of neighbor cells, one building is randomly chosen. This way, all buildings will grow by the same amount, generating a fuzzy border area at the grid cells where the buildings meet.

The number of dilation operations that need to be applied for the filling is easily computed by dividing the simplification distance by the raster grid's cell size. As the areas in between the buildings are filled from at least two sides, half that number is actually sufficient. However, to counteract errors due to inaccuracies, a few more repetitions are added for reliability reasons. Otherwise, grid cells that remain empty will open up the area again in the subsequent erosion step. The erosion operation has the inverse effect as dilation, and by applying it the same number of times to the grid restores the original boundary of the ground plan as best as possible. This is accomplished by clearing all grid cells of their building identifiers if at least one of their neighbor cells (determined by the structuring element) is not occupied by a building. As there are no empty grid cells in the filled areas in between buildings, they will not open up by this operation. The described morphological operations applied on two example buildings are depicted in Figure 5. It should be noted that the images of the ground plan grids are rotated to better resemble the 3D models.

When overlaid with the cell decomposition (Figure 6), it becomes visible that the cell that contains the red building in the back has a low overlap due to the gap in between the buildings. The morphological operations help to increase the value of this cell from 78% to 98%. Also the courtyard of the building from Figure 1 is filled, which is necessary when the simplification distance becomes greater than one of its dimensions. Otherwise the cell that overlaps this area will get discarded. However, the overlap for this particular cell could be increased from 52% to 99%, which is more than other cells in this example feature.

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

Another example with small buildings that are spread further apart is shown in Figure 7. The blue cell that is second from the right exhibits a low overlap of only 64%. Although the threshold that classifies a 2D cell as a building block could in this case also be lowered without any consequences to the new ground plan, this is generally not a viable solution. The 3D overlap threshold would need to be lowered also when determining the roof structure, which could negatively affect the classification of 3D cells. However, with the morphologically altered ground plan the overlap of the aforementioned cell increases to 99%. With such high values, all above mentioned examples allow for a reliable classification of cells as building blocks after morphology, and these problem areas are eliminated.

[FIGURE 7 OMITTED]

After morphology, the overlap test can now be carried out by overlaying the raster representation of the cell decomposition with the one of the ground plan. Then for each cell the ratio of the number of its raster elements that are also set in the grid representation of the ground plan to its overall number is determined. If this ratio is greater than the overlap threshold, then the vectorial representation of the cell is regarded a building cell and its vectorial representation is kept for further processing. Otherwise it is discarded. The whole process of the overlap test is depicted in Figure 8. Note that the generation of the approximating planes is omitted here. Also the vectorial representation is considered as an input to the overlap test because the cells get flagged with regard to the test result.

As for the overlap threshold, a much higher value is possible with morphology than without. But as can be seen in Figure 6, morphology will not change the overlap value in the border area (lower right cell on right example), so this value has still to be chosen carefully to allow for some overlap tolerance of these cells.

[FIGURE 8 OMITTED]

One problem that morphology exhibits is that the boundaries are changed if they are not aligned with the edges of the structuring element. After repeatedly applying the aforementioned operations, the boundaries are forced to align with the structuring element. This is depicted in Figure 9 for one of the previous examples.

[FIGURE 9 OMITTED]

To counteract this phenomenon, all buildings are rotated prior to their generalization so that their main directions coincide with one of the axis of the Cartesian coordinate system. This lessens the effect, but cannot completely remove it, especially for building models whose two mayor directions are not perpendicular to one another. The raster representation cannot easily be adapted to this, as those buildings usually have even more than two main directions.

Roof Shapes

Up to now, we have only discussed the part of the ground plan generalization and left out how to handle roof structures. For 3D building groups, where the objects are directly adjacent to one another, the original approach can be used: approximating planes are first generated from the roof surfaces, then the ground plan cells are decomposed and the overlap of the resulting cells with the original model determined in 3D. For spaced out buildings, the morphological operations are in addition applied, similar to the 2D case, but now with a 9 x 9 cubic mask as a structuring element on a volumetric raster representation. Figure 10 shows two aggregation results for a group of four buildings with 3m and 2m ground plan simplification threshold. To obtain a fairly detailed roof structure, the responsible roof simplification threshold is 2m in both examples. For their aggregation, the raster model of 0.1m resolution was dilated 15 times in order to include all four buildings in the result. This example shows that the simplification thresholds for the ground plan and the roof and the aggregation threshold can all be independently set in order to allow for highest flexibility. As overlap threshold, 80% was set to allow for some overlap tolerance in the border areas.

[FIGURE 10 OMITTED]

As mentioned in the previous section, morphological operations smooth structural concavities if their faces are not aligned to the elements of the raster model. However, saddleback roofs with ridges that follow a line like in Figure 10 are not affected too much. If the slopes form a valley, then morphology closes them and the cells in between gain more overlap. As the overlap values of the cells with the altered building models are in general more effective, using a higher overlap threshold can help to avoid the erroneous classifications of cells.

A general question is how should the roof shapes of aggregated 3D building models look, if for example the gables of saddleback roofs are not facing towards each other, but towards the other way? Figure 11 shows the front view of two buildings with saddleback roofs and their decomposition planes (as dashed lines) determined from the roof faces. As the morphological operations fill the space between the two buildings, the area below the eaves will be closed and shall at this point not be considered anymore. The simplification distance is less than the perpendicular distances between the two pairs of parallel roof faces, so there are four decomposition planes, which results in a building model with two ridges. As depicted in the middle of Figure 11, the two ridges remain at their original position and the roof slopes are the same. The valley that is formed therefore lies below the eaves (dashed line on 3D model). The further the buildings are apart from each other, the lower the valley and the larger the asymmetry of the two saddleback roof parts. To correct for this, the ridges could be pushed towards the middle until the valley is at the same height as the eaves (Figure 11 right). However, the roof generalization with decomposition planes does not accommodate for this.

[FIGURE 11 OMITTED]

A workaround could be to add horizontal decomposition planes at the eaves and ridge heights (dashed lines in Figure 12). Depending on how much of the space between the planes gets filled by the morphological operations, the result would be the partially flat roof shape as depicted Figure 12. Both results have their drawbacks: in the first version, a small flat element is introduced, which stands against the goal of generalization to simplify shapes, and in the second version the saddleback roofs are not apparent anymore and thus an important characteristic of the buildings is lost.

[FIGURE 12 OMITTED]

A third alternative is to include the (gray) cell in the middle of the four decomposition planes as depicted in Figure 13. The result is a large building with a saddleback roof. However, it is unclear how the rather generic algorithm would need to be altered for this. Even after the morphological operations, the raster model will only fill a small portion of this cell. But once the saddleback roof is generated, the height of the eaves and ridge could be altered to better fit the original shape.

[FIGURE 13 OMITTED]

Even for this simple example of two buildings, the handling of the roof for the aggregation of 3D building models proves to be very difficult and offers many shape variations as potential results. Not all are possible to generate with the presented algorithm. In this author's opinion, the resulting roof type should be at least the same as the most dominant one of the original buildings. General shapes that are correct from an algorithmic point of view, but do not resemble a real shape are not acceptable. It is therefore suggested to use parameterized roof shapes as presented in (Kada, 2007). Here, the roof types of the original model are determined and the most dominant one given to the generalized version. The advantage is that the roof shapes can be defined to produce all the results as seen in this subsection, so that different applications can get specific models.

Conclusion

The extension of the generalization algorithm for 3D building models presented in this article allows for a more reliable classification of cells into building and non-building cells for both the simplification of single buildings as well as for the handling of buildings groups. By converting the building models into 2D and 3D raster representations, morphological operations are now possible and allow for an aggregation of spaced out buildings without changing the underlying generalization algorithm. Examples and results are given from the authoritative data set provided by the City Surveying Office of Stuttgart.

One limitation of the morphological operations is that their repeated execution can change the shape of the objects' boundaries. The data sets need therefore be first rotated, so that the buildings' main directions are aligned with the structuring elements. This is most often possible with ground plans and therefore leads to good results for this part of the algorithm. However, the problem does remain for the handling of the 3D roof structures. If the roof does not form valleys, the problem does not become apparent and the algorithm has shown to produce valid results. Some possible results have been discussed, but not all are possible without severely altering the algorithm. The use of parameterized roof shapes seems therefore to be the most promising solution. It restricts the roof shapes to be symmetric and offers a high degree of freedom to adjust the generalization results to different application fields.

Concerning the scalability of the algorithm, the memory usage and computing time increases with the number of raster cells in each dimension, and are approximately cubic (O(n3)). It has not yet been evaluated what raster size is necessary to achieve the most representative results. But the cell size can most likely be put in relation to the aggregation threshold, which is by nature a few meters wide and therefore results in only a few thousand cells per building block. As the morphological evaluation of each raster cell is performed independently from any other cell, the approach can be highly parallelized so that an efficient processing is possible even for raster representations of large areas.

REFERENCES

Anders, K.-H. 2005. Level of Detail Generation of 3D Building Groups by Aggregation and Typification. In: Proceedings of the XXII International Cartographic Conference, La Coruna, Spain.

Buchholz, H. and J. Dollner. 2005. View-Dependent Rendering of Multiresolution Texture-Atlases. In: IEEE Visualization 2005 (VIS 2005), IEEE Computer Society Press, pp. 215-222.

Coors, V. 2001. Feature-Preserving Simplification in Web-Based 3D-GIS. In Proceedings of the 1st International Symposium on Smart Graphics. Hawthorne, USA, pp. 22-28.

Foley, J., A. van Dam, S. Feiner and J. Hughes. 1990. Computer Graphics: Principles and Practice (2nd Edition), Addison-Wesley

Forberg, A. 2004. Generalization of 3D Building Data based on a Scale-Space Approach. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Istanbul, Turkey, Vol. XXXV, Part B, pp. 195-199.

Glander, T. and J. Dollner. 2009. Abstract Representations for Interactive Visualization of Virtual 3D City Models. Computer, Environment and Urban Systems 33(5): 375-387.

Haunert, J.-H. and A. Wolff. 2010. Optimal and Topologically Safe Simplification of Building Footprints. In Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems ACM-GIS'10, pp. 192-201.

Kada, M. 2002. Automatic Generalization of 3D Building Models. In Proceedings of the Joint International Symposium on Geospatial Theory, Processing and Applications, Ottawa, Canada.

Kada, M., S. Roettger, K. Weiss, T. Ertl and D. Fritsch. 2003. Real-Time Visualization of Urban Landscapes using Open-Source Software. In Proceedings of the 24th Asian Conference on Remote Sensing & 2003 International Symposium on Remote Sensing. ACRS 2003 ISRS, Busan, Korea.

Kada, M. 2007. Scale-Dependent Simplification of 3D Building Models Based on Cell Decomposition and Primitive Instancing. In Proceedings of the International Conference on Spatial Information Theory: COSIT'07, Melbourne, Australia, pp. 222-237.

Li, Z. 1996. Transformation of Spatial Representation in Scale Dimension: A New Paradigm for Digital Generalization of Spatial Data. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXI, Part B3, Vienna, Austria, pp. 453-458.

Mayer, H. 1998. Model-Generalization of Building Outlines Based on Scale-Spaces And Scale-Space Events. In International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXII, Part 3, Columbus, Ohio, USA, pp. 530-536.

Poupeau, B. and A. Ruas. 2007. A Crystallographic Approach to Simplify 3D Building. In Proceedings of the 23rd International Cartographic Conference, Moscow, Russia.

Rau, J.Y., L.C. Chen, F. Tsai, K.H. Hsiao and W.C. Hsu. 2006. Automatic Generation of Pseudo Continuous LoDs for 3D Polyhedral Building Model. In Innovation in 3D Geo Information Systems, Springer Verlag, Berlin.

Serra, J. 1982. Image Analysis and Mathematical Morphology. Academic Press, London.

Thiemann. E and M. Sester. 2004. Segmentation of Buildings for 3D-Generalisation. In Working Paper of the ICA Workshop on Generalisation and Multiple Representation, Leicester, UK.

Thiemann. E and M. Sester. 2006.3D-Symbolization using Adaptive Templates. In Proceedings of the GICON, Wien, Austria.

Martin Kada, Institute for Geoinformatics and Remote Sensing (IGF), University of Osnabruck, Barbarastr. 22b, 49076 Osnabruck, Germany. Email:<martin.kada@uniosnabrueck.de>

DOI: 10.1559/15230406382154

Printer friendly Cite/link Email Feedback | |

Author: | Kada, Martin |
---|---|

Publication: | Cartography and Geographic Information Science |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Apr 1, 2011 |

Words: | 4981 |

Previous Article: | A new construction method for circle cartograms. |

Next Article: | Completing fragmentary river networks via induced terrain. |

Topics: |