Buildings and other man-made objects, for many reasons such as economical or aesthetic, are often characterized by their symmetry. The latter predominates in the design of building footprints and building parts such as façades. Thus the identification and modeling of this valuable information facilitates the reconstruction of these buildings and their parts. This article presents a novel approach for the automatic identification and modelling of symmetries and their hierarchical structures in building footprints, providing an important prior for façade and roof reconstruction. The uncertainty of symmetries is explicitly addressed using supervised machine learning methods, in particular Support Vector Machines (SVMs). Unlike classical statistical methods, for SVMs assumptions on the a priori distribution of the data are not required. Both axial and translational symmetries are detected. The quality of the identified major and minor symmetry axes is assessed by a least squares based adjustment. Context-free formal grammar rules are used to model the hierarchical and repetitive structure of the underlying footprints. We present an algorithm which derives grammar rules based on the previously acquired symmetry information and using lexical analysis describing regular patterns and palindrome-like structures. This offers insights into the latent structures of building footprints and therefore describes the associated façade in a relational and compact way.

doi:10.1111/tgis.12177

@article{DehbiEtAl2016,
    abstract = {Buildings and other man-made objects, for many reasons such as economical or aesthetic, are often characterized by their symmetry. The latter predominates in the design of building footprints and building parts such as façades. Thus the identification and modeling of this valuable information facilitates the reconstruction of these buildings and their parts. This article presents a novel approach for the automatic identification and modelling of symmetries and their hierarchical structures in building footprints, providing an important prior for façade and roof reconstruction. The uncertainty of symmetries is explicitly addressed using supervised machine learning methods, in particular Support Vector Machines (SVMs). Unlike classical statistical methods, for SVMs assumptions on the a priori distribution of the data are not required. Both axial and translational symmetries are detected. The quality of the identified major and minor symmetry axes is assessed by a least squares based adjustment. Context-free formal grammar rules are used to model the hierarchical and repetitive structure of the underlying footprints. We present an algorithm which derives grammar rules based on the previously acquired symmetry information and using lexical analysis describing regular patterns and palindrome-like structures. This offers insights into the latent structures of building footprints and therefore describes the associated façade in a relational and compact way.},
    author = {Dehbi, Y. and Gr{\"{o}}ger, Gerhard and Pl{\"{u}}mer, L.},
    doi = {10.1111/tgis.12177},
    journal = {Transactions in GIS},
    number = {5},
    pages = {645--663},
    title = {Identification and modelling of translational and axial symmetries and their hierarchical structures in building footprints by formal grammars},
    url = {http://dx.doi.org/10.1111/tgis.12177},
    volume = {20},
    year = {2016}
}

Formal grammars are well suited for the estimation of models with an a-priori unknown number of parameters such as buildings and have proven their worth for 3D modeling and reconstruction of cities. However, the generation and design of corresponding grammar rules is a laborious task and relies on expert knowledge. This thesis presents novel approaches for the reduction of this effort using advanced machine learning methods resulting in automatically learned sophisticated grammar rules. Indeed, the learning of a wide range of sophisticated rules, that reflect the variety and complexity, is a challenging task. This is especially the case if a simultaneous machine learning of building structures and the underlying aggregation hierarchies as well as the building parameters and the constraints among them for a semantic interpretation is expected. Thus, in this thesis, an incremental approach is followed. It separates the structure learning from the parameter distribution learning of building parts. Moreover, the so far procedural approaches with formal grammars are mostly rather convenient for the generation of virtual city models than for the reconstruction of existing buildings. To this end, Inductive Logic Programming (ILP) techniques are transferred and applied for the first time in the field of 3D building modeling. This enables the automatic learning of declarative logic programs, which are equivalent to attribute grammars and separate the representation of buildings and their parts from the reconstruction task. A stepwise bottom-up learning, starting from the smallest atomic features of a building part together with the semantic, topological and geometric constraints, is a key to a successful learning of a whole building part. Only few examples are sufficient to learn from precise as well as noisy observations. The learning from uncertain data is realized using probability density functions, decision trees and uncertain projective geometry. This enables the handling and modeling of uncertain topology and geometric reasoning taking noise into consideration. The uncertainty of models itself is also considered. Therefore, a novel method is developed for the learning of Weighted Attribute Context-Free Grammar (WACFG). On the one hand, the structure learning of façades - context-free part of the Grammar - is performed based on annotated derivation trees using specific Support Vector Machines (SVMs). The latter are able to derive probabilistic models from structured data and to predict a most likely tree regarding to given observations. On the other hand, to the best of my knowledge, Statistical Relational Learning (SRL), especially Markov Logic Networks (MLNs), are applied for the first time in order to learn building part (shape and location) parameters as well as the constraints among these parts. The use of SRL enables to take profit from the elegant logical relational description and to benefit from the efficiency of statistical inference methods. In order to model latent prior knowledge and exploit the architectural regularities of buildings, a novel method is developed for the automatic identification of translational as well as axial symmetries. For symmetry identification a supervised machine learning approach is followed based on an SVM classifier. Building upon the classification results, algorithms are designed for the representation of symmetries using context-free grammars from authoritative building footprints. In all steps the machine learning is performed based on real- world data such as 3D point clouds and building footprints. The handling with uncertainty and occlusions is assured. The presented methods have been successfully applied on real data. The belonging classification and reconstruction results are shown.

@phdthesis{dehbi2016statistical,
    abstract = {Formal grammars are well suited for the estimation of models with an a-priori unknown number of parameters such as buildings and have proven their worth for 3D modeling and reconstruction of cities. However, the generation and design of corresponding grammar rules is a laborious task and relies on expert knowledge. This thesis presents novel approaches for the reduction of this effort using advanced machine learning methods resulting in automatically learned sophisticated grammar rules. Indeed, the learning of a wide range of sophisticated rules, that reflect the variety and complexity, is a challenging task. This is especially the case if a simultaneous machine learning of building structures and the underlying aggregation hierarchies as well as the building parameters and the constraints among them for a semantic interpretation is expected. Thus, in this thesis, an incremental approach is followed. It separates the structure learning from the parameter distribution learning of building parts. Moreover, the so far procedural approaches with formal grammars are mostly rather convenient for the generation of virtual city models than for the reconstruction of existing buildings. To this end, Inductive Logic Programming (ILP) techniques are transferred and applied for the first time in the field of 3D building modeling. This enables the automatic learning of declarative logic programs, which are equivalent to attribute grammars and separate the representation of buildings and their parts from the reconstruction task. A stepwise bottom-up learning, starting from the smallest atomic features of a building part together with the semantic, topological and geometric constraints, is a key to a successful learning of a whole building part. Only few examples are sufficient to learn from precise as well as noisy observations. The learning from uncertain data is realized using probability density functions, decision trees and uncertain projective geometry. This enables the handling and modeling of uncertain topology and geometric reasoning taking noise into consideration. The uncertainty of models itself is also considered. Therefore, a novel method is developed for the learning of Weighted Attribute Context-Free Grammar (WACFG). On the one hand, the structure learning of façades -- context-free part of the Grammar -- is performed based on annotated derivation trees using specific Support Vector Machines (SVMs). The latter are able to derive probabilistic models from structured data and to predict a most likely tree regarding to given observations. On the other hand, to the best of my knowledge, Statistical Relational Learning (SRL), especially Markov Logic Networks (MLNs), are applied for the first time in order to learn building part (shape and location) parameters as well as the constraints among these parts. The use of SRL enables to take profit from the elegant logical relational description and to benefit from the efficiency of statistical inference methods. In order to model latent prior knowledge and exploit the architectural regularities of buildings, a novel method is developed for the automatic identification of translational as well as axial symmetries. For symmetry identification a supervised machine learning approach is followed based on an SVM classifier. Building upon the classification results, algorithms are designed for the representation of symmetries using context-free grammars from authoritative building footprints. In all steps the machine learning is performed based on real- world data such as 3D point clouds and building footprints. The handling with uncertainty and occlusions is assured. The presented methods have been successfully applied on real data. The belonging classification and reconstruction results are shown.},
    author = {Dehbi, Y.},
    school = {Rheinische Friedrich-Wilhelms-Universit{\"{a}}t Bonn, Germany},
    series = {Universitäts- und Landesbibliothek Bonn},
    title = {Statistical relational learning of semantic models and grammar rules for 3D building reconstruction from 3D point clouds},
    type = {Dissertation},
    url = {http://hss.ulb.uni-bonn.de/2016/4532/4532.htm},
    urn = {urn:nbn:de:hbz:5n-45329},
    year = {2016}
}

Data acquisition using unmanned aerial vehicles (UAVs) has gotten more and more attention over the last years. Especially in the field of building reconstruction the incremental interpretation of such data is a demanding task. In this context formal grammars play an important role for the top-down identification and reconstruction of building objects. Up to now, the available approaches expect offline data in order to parse an a-priori known grammar. For mapping on demand an on the fly reconstruction based on UAV data is required. An incremental interpretation of the data stream is inevitable. This paper presents an incremental parser of grammar rules for an automatic 3D building reconstruction. The parser enables a model refinement based on new observations with respect to a weighted attribute context-free grammar (WACFG). The falsification or rejection of hypotheses is supported as well. The parser can deal with and adapt available parse trees acquired from previous interpretations or predictions. Parse trees derived so far are updated in an iterative way using transformation rules. A diagnostic step searches for mismatches between current and new nodes. Prior knowledge on facžades is incorporated. It is given by probability densities as well as architectural patterns. Since we cannot always assume normal distributions, the derivation of location and shape parameters of building objects is based on a kernel density estimation (KDE). While the level of detail is continuously improved, the geometrical, semantic and topological consistency is ensured.

doi:10.5194/isprs-annals-III-3-311-2016

@inproceedings{isprs-annals-III-3-311-2016,
    abstract = {Data acquisition using unmanned aerial vehicles (UAVs) has gotten more and more attention over the last years. Especially in the field of building reconstruction the incremental interpretation of such data is a demanding task. In this context formal grammars play an important role for the top-down identification and reconstruction of building objects. Up to now, the available approaches expect offline data in order to parse an a-priori known grammar. For mapping on demand an on the fly reconstruction based on UAV data is required. An incremental interpretation of the data stream is inevitable. This paper presents an incremental parser of grammar rules for an automatic 3D building reconstruction. The parser enables a model refinement based on new observations with respect to a weighted attribute context-free grammar (WACFG). The falsification or rejection of hypotheses is supported as well. The parser can deal with and adapt available parse trees acquired from previous interpretations or predictions. Parse trees derived so far are updated in an iterative way using transformation rules. A diagnostic step searches for mismatches between current and new nodes. Prior knowledge on facžades is incorporated. It is given by probability densities as well as architectural patterns. Since we cannot always assume normal distributions, the derivation of location and shape parameters of building objects is based on a kernel density estimation (KDE). While the level of detail is continuously improved, the geometrical, semantic and topological consistency is ensured.},
    author = {Dehbi, Y and Staat, C and Mandtler, L and Pl{\"{u}}mer, L},
    booktitle = {Proc. XXIII ISPRS Congress},
    doi = {10.5194/isprs-annals-III-3-311-2016},
    pages = {311--316},
    series = {ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences},
    title = {Incremental refinement of facade models with attribute grammar from 3D point clouds},
    url = {http://www.isprs-ann-photogramm-remote-sens-spatial-inf-sci.net/III-3/311/2016/},
    volume = {III-3},
    year = {2016}
}

This paper introduces a novel method for the automatic derivation of building floorplans and indoor models. Our approach is based on a logical and stochastic reasoning using sparse observations such as building room areas. No further sensor observations like 3D point clouds are needed. Our method benefits from an extensive prior knowledge of functional dependencies and probability density functions of shape and location parameters of rooms depending on their functional use. The determination of posterior beliefs is performed using Bayesian Networks. Stochastic reasoning is complex since the problem is characterized by a mixture of discrete and continuous parameters that are in turn correlated by non-linear constraints. To cope with this kind of complexity, the proposed reasoner combines statistical methods with constraint propagation. It generates a limited number of hypotheses in a model-based top-down approach. It predicts floorplans based on a-priori localised windows. The use of Gaussian mixture models, constraint solvers and stochastic models helps to cope with the a-priori infinite space of the possible floorplan instantiations.

doi:10.5194/isprs-annals-IV-2-W1-265-2016

@inproceedings{isprs-annals-IV-2-W1-265-2016,
    abstract = {This paper introduces a novel method for the automatic derivation of building floorplans and indoor models. Our approach is based on a logical and stochastic reasoning using sparse observations such as building room areas. No further sensor observations like 3D point clouds are needed. Our method benefits from an extensive prior knowledge of functional dependencies and probability density functions of shape and location parameters of rooms depending on their functional use. The determination of posterior beliefs is performed using Bayesian Networks. Stochastic reasoning is complex since the problem is characterized by a mixture of discrete and continuous parameters that are in turn correlated by non-linear constraints. To cope with this kind of complexity, the proposed reasoner combines statistical methods with constraint propagation. It generates a limited number of hypotheses in a model-based top-down approach. It predicts floorplans based on a-priori localised windows. The use of Gaussian mixture models, constraint solvers and stochastic models helps to cope with the a-priori infinite space of the possible floorplan instantiations.},
    author = {Loch-Dehbi, S. and Dehbi, Y. and Gr\"oger, G. and Plümer, L.},
    booktitle = {Proc. 11th 3D Geoinfo Conference},
    doi = {10.5194/isprs-annals-IV-2-W1-265-2016},
    pages = {265--270},
    series = {ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences},
    title = {Prediction of building floorplans using logical and stochastic reasoning based on sparse observations},
    url = {https://www.isprs-ann-photogramm-remote-sens-spatial-inf-sci.net/IV-2-W1/265/2016/},
    volume = {IV-2/W1},
    year = {2016}
}

Body plan development in multi-cellular organisms is largely determined by homeotic genes. Expression of homeotic genes, in turn, is partially regulated by insulator binding proteins (IBPs). While only a few enhancer blocking IBPs have been identified in vertebrates, the common fruit fly Drosophila melanogaster harbors at least twelve different enhancer blocking IBPs. We screened recently compiled insect transcriptomes from the 1KITE project and genomic and transcriptomic data from public databases, aiming to trace the origin of IBPs in insects and other arthropods.

doi:10.1186/s12864-016-3205-1

@article{Vedder2016,
    abstract = {Body plan development in multi-cellular organisms is largely determined by homeotic genes. Expression of homeotic genes, in turn, is partially regulated by insulator binding proteins (IBPs). While only a few enhancer blocking IBPs have been identified in vertebrates, the common fruit fly Drosophila melanogaster harbors at least twelve different enhancer blocking IBPs. We screened recently compiled insect transcriptomes from the 1KITE project and genomic and transcriptomic data from public databases, aiming to trace the origin of IBPs in insects and other arthropods.},
    author = {Pauli, Thomas and Vedder, Lucia and Dowling, Daniel and Petersen, Malte and Meusemann, Karen and Donath, Alexander and Peters, Ralph S. and Podsiadlowski, Lars and Mayer, Christoph and Liu, Shanlin and Zhou, Xin and Heger, Peter and Wiehe, Thomas and Hering, Lars and Mayer, Georg and Misof, Bernhard and Niehuis, Oliver},
    doi = {10.1186/s12864-016-3205-1},
    issn = {1471-2164},
    journal = {BMC Genomics},
    number = {1},
    pages = {861},
    title = {Transcriptomic data from panarthropods shed new light on the evolution of insulator binding proteins in insects : Insect insulator proteins},
    url = {https://link.springer.com/article/10.1186/s12864-016-3205-1},
    volume = {17},
    year = {2016}
}

@article{knrssw-msbl-16,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    journal = {Algorithmica},
    month = {September},
    number = {1},
    pages = {225--258},
    title = {Multi-Sided Boundary Labeling},
    url = {http://dx.doi.org/10.1007/s00453-015-0028-4},
    volume = {76},
    year = {2016}
}

@inproceedings{nn-aaflr-16,
    author = {Niedermann, B. and N{\"o}llenburg, M.},
    booktitle = {Proceedings of the 9th International Conference on Geographic Information Science (GIScience'16)},
    pages = {308--322},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{An Algorithmic Framework for Labeling Road Maps}},
    volume = {9927},
    year = {2016}
}

doi:10.1145/2996913.2996957

@inproceedings{bnns-tmlan-16,
    author = {L. Barth and B. Niedermann and M. N{\"o}llenburg and D. Strash},
    booktitle = {Proc. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '16)},
    doi = {10.1145/2996913.2996957},
    pages = {23:1--23:10},
    publisher = {ACM},
    title = {{Temporal Map Labeling: A New Unified Framework with Experiments}},
    year = {2016}
}

Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortest-path trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.

doi:10.1111/cgf.12921

@article{vanDijkEtAl2016,
    abstract = {Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortest-path trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.},
    author = {Dijk, T. C. van and Haunert, J.-H and Oehrlein, J.},
    doi = {10.1111/cgf.12921},
    journal = {Computer Graphics Forum},
    number = {3},
    pages = {451{--}460},
    title = {Location-dependent generalization of road networks based on equivalent destinations},
    volume = {35},
    year = {2016}
}

In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der räumlichen Analyse grundlegende Entwurfstechniken für Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. AuSSerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, räumliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu lösen. Wir halten es für besonders wichtig, dass man neue Probleme sorgfältig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen überprüft, bevor man sich schnellen Heuristiken zuwendet, um groSSe Instanzen zu lösen.

doi:10.1007/978-3-662-46900-2_69-1

@incollection{Haunert2016,
    abstract = {In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der r{\"a}umlichen Analyse grundlegende Entwurfstechniken f{\"u}r Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. AuSSerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, r{\"a}umliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu l{\"o}sen. Wir halten es f{\"u}r besonders wichtig, dass man neue Probleme sorgf{\"a}ltig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen {\"u}berpr{\"u}ft, bevor man sich schnellen Heuristiken zuwendet, um groSSe Instanzen zu l{\"o}sen.},
    author = {Haunert, J.-H. and Wolff, A.},
    booktitle = {Handbuch der Geodäsie: 5 Bände},
    doi = {10.1007/978-3-662-46900-2_69-1},
    editor = {Freeden, W. and Rummel, R.},
    isbn = {978-3-662-46900-2},
    pages = {1--39},
    publisher = {Springer Berlin Heidelberg},
    title = {Räumliche Analyse durch kombinatorische Optimierung},
    url = {https://doi.org/10.1007/978-3-662-46900-2_69-1},
    year = {2016}
}

doi:10.1007/978-3-319-45738-3_2

@inproceedings{HaunertMeulemans2016,
    author = {Haunert, J.-H. and Meulemans, W.},
    booktitle = {Proc. 9th International Conference on Geographic Information Science (GIScience 2016)},
    doi = {10.1007/978-3-319-45738-3\_2},
    pages = {18{--}33},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Partitioning Polygons via Graph Augmentation},
    url = {https://doi.org/10.1007/978-3-319-45738-3\_2},
    volume = {9927},
    year = {2016}
}

doi:10.1007/978-3-319-33783-8_23

@inproceedings{PengEtAl2016,
    author = {Peng, D. and Wolff, A. and Haunert, J.-H.},
    booktitle = {Proc. 19th AGILE International Conference on Geographic Information Science},
    doi = {10.1007/978-3-319-33783-8_23},
    pages = {399{--}415},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Geoinformation and Cartography},
    title = {Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations},
    year = {2016}
}

@inproceedings{haunertwolff2016,
    author = {Haunert, J.-H and Wolff, A},
    booktitle = {Proc. XXIII ISPRS Congress},
    pages = {109{--}114},
    series = {International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences},
    title = {Beyond Maximum Independent Set: An Extended Model for Point-Feature Label Placement},
    volume = {XLI-B2},
    year = {2016}
}