Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations where placing labels directly in the image is impossible or produces too much visual clutter. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or labels are too long, multiple layers of labels are needed. In this paper we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in k different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial-time algorithms based on dynamic programming that either minimize the number of rows to place all n labels, or maximize the number (or total weight) of labels that can be placed in k rows for a given integer k. For weighted labels, the problem is shown to be (weakly) NP-hard, and we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically-sized instances are computed instantaneously.

doi:10.1145/2093973.2094012

@inproceedings{GemsaEtAl2011,
    abstract = {Boundary labeling deals with placing annotations for objects in an image on the boundary of that image. This problem occurs frequently in situations where placing labels directly in the image is impossible or produces too much visual clutter. Previous algorithmic results for boundary labeling consider a single layer of labels along some or all sides of a rectangular image. If, however, the number of labels is large or labels are too long, multiple layers of labels are needed. In this paper we study boundary labeling for panorama images, where n points in a rectangle R are to be annotated by disjoint unit-height rectangular labels placed above R in k different rows (or layers). Each point is connected to its label by a vertical leader that does not intersect any other label. We present polynomial-time algorithms based on dynamic programming that either minimize the number of rows to place all n labels, or maximize the number (or total weight) of labels that can be placed in k rows for a given integer k. For weighted labels, the problem is shown to be (weakly) NP-hard, and we give a pseudo-polynomial algorithm to maximize the weight of the selected labels. We have implemented our algorithms; the experimental results show that solutions for realistically-sized instances are computed instantaneously.},
    author = {Gemsa, A. and Haunert, J.-H. and N\"{o}llenburg, M.},
    booktitle = {Proc. 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '11)},
    doi = {10.1145/2093973.2094012},
    file = {GemsaEtAl2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/GemsaEtAl2011.pdf:PDF},
    pages = {289--298},
    timestamp = {2012-04-12T14:43:51.000+0200},
    title = {Boundary-Labeling Algorithms for Panorama Images},
    year = {2011}
}

This paper presents an algorithmic approach to the problem of finding symmetries in building footprints. The problem is motivated by map generalization tasks, for example, symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in polygons that use algorithms for string matching. It detects both axial symmetries and repetitions of geometric structures. In addition to the existing string-matching approaches to symmetry detection, we consider the problem of finding partial symmetries in polygons while allowing for small geometric errors. Moreover, we discuss how to find optimally adjusted mirror axes and to assess the quality of a detected mirror axis using a least-squares approach. The presented approach was tested on a large building data set of the metropolitan Boston area. The dominant symmetry relations were found. Future work is needed to aggregate the obtained symmetry relations, for example, by finding sets of mirror axes that are almost collinear. Another open problem is the integration of information on symmetry relations into algorithms for map generalization.

doi:10.1007/978-3-642-19789-5_16

@inproceedings{Haunert2011,
    abstract = {This paper presents an algorithmic approach to the problem of finding symmetries in building footprints. The problem is motivated by map generalization tasks, for example, symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in polygons that use algorithms for string matching. It detects both axial symmetries and repetitions of geometric structures. In addition to the existing string-matching approaches to symmetry detection, we consider the problem of finding partial symmetries in polygons while allowing for small geometric errors. Moreover, we discuss how to find optimally adjusted mirror axes and to assess the quality of a detected mirror axis using a least-squares approach. The presented approach was tested on a large building data set of the metropolitan Boston area. The dominant symmetry relations were found. Future work is needed to aggregate the obtained symmetry relations, for example, by finding sets of mirror axes that are almost collinear. Another open problem is the integration of information on symmetry relations into algorithms for map generalization.},
    author = {Haunert, J.-H.},
    booktitle = {Advancing Geoinformation Science for a Changing World -- Proc. 14th AGILE International Conference on Geographic Information Science},
    doi = {10.1007/978-3-642-19789-5_16},
    editor = {Geertman, S. and Reinhardt, W. and Toppen, F.},
    file = {HaunertAgile2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertAgile2011.pdf:PDF},
    pages = {319--336},
    publisher = {Springer-Verlag, Berlin, Germany},
    series = {Lecture Notes in Geoinformation and Cartography},
    timestamp = {2011-11-07T12:01:01.000+0100},
    title = {Detecting Symmetries in Building Footprints by String Matching},
    url = {http://www.springerlink.com/content/u280281846852h08/},
    year = {2011}
}

Decades of research on map generalisation have resulted in an abundance of heuristic algorithms, evaluation of the performance of which is vital for choosing the most suitable for a certain application. Proper evaluation methods are, however, missing. The author proposes an approach based on optimisation methods adopted from the field of operations research.

@article{Haunert2011b,
    abstract = {Decades of research on map generalisation have resulted in an abundance of heuristic algorithms, evaluation of the performance of which is vital for choosing the most suitable for a certain application. Proper evaluation methods are, however, missing. The author proposes an approach based on optimisation methods adopted from the field of operations research.},
    author = {Haunert, J.-H.},
    journal = {GIM International},
    number = {1},
    pages = {31--33},
    timestamp = {2011-11-07T12:01:01.000+0100},
    title = {Map Generalisation -- Quality Benchmarks through Optimisation},
    url = {http://www.gim-international.com/issues/articles/id1644-Map_Generalisation.html},
    volume = {25},
    year = {2011}
}

Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems.

doi:10.1109/TVCG.2011.191

@article{haunertSering2011,
    abstract = {Mobile users of maps typically need detailed information about their surroundings plus some context information about remote places. In order to avoid that the map partly gets too dense, cartographers have designed mapping functions that enlarge a user-defined focus region such functions are sometimes called fish-eye projections. The extra map space occupied by the enlarged focus region is compensated by distorting other parts of the map. We argue that, in a map showing a network of roads relevant to the user, distortion should preferably take place in those areas where the network is sparse. Therefore, we do not apply a predefined mapping function. Instead, we consider the road network as a graph whose edges are the road segments. We compute a new spatial mapping with a graph-based optimization approach, minimizing the square sum of distortions at edges. Our optimization method is based on a convex quadratic program (CQP); CQPs can be solved in polynomial time. Important requirements on the output map are expressed as linear inequalities. In particular, we show how to forbid edge crossings. We have implemented our method in a prototype tool. For instances of different sizes, our method generated output maps that were far less distorted than those generated with a predefined fish-eye projection. Future work is needed to automate the selection of roads relevant to the user. Furthermore, we aim at fast heuristics for application in real-time systems.},
    author = {Haunert, J.-H. and Sering, L.},
    doi = {10.1109/TVCG.2011.191},
    file = {HaunertSering2011.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertSering2011.pdf:PDF},
    journal = {IEEE Transactions on Visualization and Computer Graphics},
    number = {12},
    pages = {2555--2562},
    timestamp = {2012-04-12T14:42:23.000+0200},
    title = {Drawing Road Networks with Focus Regions},
    volume = {17},
    year = {2011}
}

The automatic interpretation of dense three-dimensional (3D) point clouds is still an open research problem. The quality and usability of the derived models depend to a large degree on the availability of highly structured models which represent semantics explicitly and provide a priori knowledge to the interpretation process. The usage of formal grammars for modelling man-made objects has gained increasing interest in the last few years. In order to cope with the variety and complexity of buildings, a large number of fairly sophisticated grammar rules are needed. As yet, such rules mostly have to be designed by human experts. This article describes a novel approach to machine learning of attribute grammar rules based on the Inductive Logic Programming paradigm. Apart from syntactic differences, logic programs and attribute grammars are basically the same language. Attribute grammars extend context-free grammars by attributes and semantic rules and provide a much larger expressive power. Our approach to derive attribute grammars is able to deal with two kinds of input data. On the one hand, we show how attribute grammars can be derived from precise descriptions in the form of examples provided by a human user as the teacher. On the other hand, we present the acquisition of models from noisy observations such as 3D point clouds. This includes the learning of geometric and topological constraints by taking measurement errors into account. The feasibility of our approach is proven exemplarily by stairs, and a generic framework for learning other building parts is discussed. Stairs aggregate an arbitrary number of steps in a manner which is specified by topological and geometric constraints and can be modelled in a recursive way. Due to this recursion, they pose a special challenge to machine learning. In order to learn the concept of stairs, only a small number of examples were required. Our approach represents and addresses the quality of the given observations and the derived constraints explicitly, using concepts from uncertain projective geometry for learning geometric relations and the Wakeby distribution together with decision trees for topological relations.

doi:https://doi.org/10.1016/j.isprsjprs.2010.10.001

@article{Dehbi2011,
    abstract = {The automatic interpretation of dense three-dimensional (3D) point clouds is still an open research problem. The quality and usability of the derived models depend to a large degree on the availability of highly structured models which represent semantics explicitly and provide a priori knowledge to the interpretation process. The usage of formal grammars for modelling man-made objects has gained increasing interest in the last few years. In order to cope with the variety and complexity of buildings, a large number of fairly sophisticated grammar rules are needed. As yet, such rules mostly have to be designed by human experts. This article describes a novel approach to machine learning of attribute grammar rules based on the Inductive Logic Programming paradigm. Apart from syntactic differences, logic programs and attribute grammars are basically the same language. Attribute grammars extend context-free grammars by attributes and semantic rules and provide a much larger expressive power. Our approach to derive attribute grammars is able to deal with two kinds of input data. On the one hand, we show how attribute grammars can be derived from precise descriptions in the form of examples provided by a human user as the teacher. On the other hand, we present the acquisition of models from noisy observations such as 3D point clouds. This includes the learning of geometric and topological constraints by taking measurement errors into account. The feasibility of our approach is proven exemplarily by stairs, and a generic framework for learning other building parts is discussed. Stairs aggregate an arbitrary number of steps in a manner which is specified by topological and geometric constraints and can be modelled in a recursive way. Due to this recursion, they pose a special challenge to machine learning. In order to learn the concept of stairs, only a small number of examples were required. Our approach represents and addresses the quality of the given observations and the derived constraints explicitly, using concepts from uncertain projective geometry for learning geometric relations and the Wakeby distribution together with decision trees for topological relations.},
    author = {Dehbi, Y and Pl\"umer, L},
    doi = {https://doi.org/10.1016/j.isprsjprs.2010.10.001},
    issn = {0924-2716},
    journal = {ISPRS Journal of Photogrammetry and Remote Sensing},
    note = {Quality, Scale and Analysis Aspects of Urban City Models},
    number = {2},
    pages = {166--6176},
    title = {Learning grammar rules of building parts from precise models and noisy observations},
    url = {http://www.sciencedirect.com/science/article/pii/S0924271610000924},
    volume = {66},
    year = {2011}
}