Document Open Access Logo

Bicriteria Aggregation of Polygons via Graph Cuts

Authors Peter Rottmann, Anne Driemel , Herman Haverkort, Heiko Röglin, Jan-Henrik Haunert

PDF
Thumbnail PDF

File

LIPIcs.GIScience.2021.II.6.pdf
  • Filesize: 3 MB
  • 16 pages

Document Identifiers

Author Details

Peter Rottmann
  • Institute of Geodesy and Geoinformation, University of Bonn, Germany
Anne Driemel
  • Hausdorff Center for Mathematics, University of Bonn, Germany
Herman Haverkort
  • Institute of Computer Science, University of Bonn, Germany
Heiko Röglin
  • Institute of Computer Science, University of Bonn, Germany
Jan-Henrik Haunert
  • Institute of Geodesy and Geoinformation, University of Bonn, Germany

Cite As Get BibTex

Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, and Jan-Henrik Haunert. Bicriteria Aggregation of Polygons via Graph Cuts. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.GIScience.2021.II.6

Abstract

We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions.

Subject Classification

ACM Subject Classification
  • Information systems → Geographic information systems
  • Theory of computation → Computational geometry
Keywords
  • map generalization
  • aggregation
  • graph cuts
  • bicriteria optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karl-Heinrich Anders and Monika Sester. Parameter-free cluster detection in spatial databases and its application to typification. In Proc. 19th ISPRS Congress, volume 33 of International Archives of Photogrammetry and Remote Sensing, pages 75-83, 2000. Google Scholar
  2. Michael Bleyer and Margrit Gelautz. Graph-cut-based stereo matching using image segmentation with symmetrical treatment of occlusions. Signal Processing: Image Communication, 22(2):127-143, 2007. URL: https://doi.org/10.1016/j.image.2006.11.012.
  3. Fritz Bökler and Petra Mutzel. Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems. In Proc. 23rd Annual European Symposium on Algorithms (ESA '15), pages 288-299, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_25.
  4. Annika Bonerath, Benjamin Niedermann, and Jan-Henrik Haunert. Retrieving α-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '19), pages 249-258, 2019. URL: https://doi.org/10.1145/3347146.3359087.
  5. Yuri Boykov and Olga Veksler. Graph cuts in vision and graphics: Theories and applications. In Handbook of Mathematical Models in Computer Vision, chapter 5, pages 79-96. Springer, Boston, MA, USA, 2006. URL: https://doi.org/10.1007/0-387-28831-7_5.
  6. Dirk Burghardt and Alessandro Cecconi. Mesh simplification for building typification. International Journal of Geographical Information Science, 21(3):283-298, 2007. URL: https://doi.org/10.1080/13658810600912323.
  7. Dirk Burghardt, Stefan Schmid, and Jantien Stoter. Investigations on cartographic constraint formalisation. In Proc. 11th ICA Workshop on Generalisation and Multiple Representation, 2007. URL: https://kartographie.geo.tu-dresden.de/downloads/ica-gen/workshop2007/Burghardt-ICAWorkshop.pdf.
  8. Jared L. Cohon. Multiobjective Programming and Planning. Academic Press, New York, NY, USA, 1978. Google Scholar
  9. Jonathan Damen, Marc van Kreveld, and Bert Spaan. High quality building generalization by extending the morphological operators. In Proc. 11th ICA Workshop on Generalisation and Multiple Representation, pages 1-12, 2008. URL: https://kartographie.geo.tu-dresden.de/downloads/ica-gen/workshop2008/04_Damen_et_al.pdf.
  10. Steven J. D'Amico, Shoou-Jiun Wang, Rajan Batta, and Christopher M. Rump. A simulated annealing approach to police district design. Computers & Operations Research, 29(6):667-684, 2002. URL: https://doi.org/10.1016/S0305-0548(01)00056-9.
  11. Constantinos Daskalakis, Ilias Diakonikolas, and Mihalis Yannakakis. How good is the chord algorithm? SIAM Journal on Computing, 45(3):811-858, 2016. URL: https://doi.org/10.1137/13093875X.
  12. Matt Duckham, Lars Kulik, Mike Worboys, and Antony Galton. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition, 41(10):3224-3236, 2008. URL: https://doi.org/10.1016/j.patcog.2008.03.023.
  13. Herbert Edelsbrunner, David Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory, 29(4):551-559, 1983. URL: https://doi.org/10.1109/TIT.1983.1056714.
  14. Yu Feng, Frank Thiemann, and Monika Sester. Learning cartographic building generalization with deep convolutional neural networks. ISPRS International Journal of Geo-Information, 8(6), 2019. URL: https://doi.org/10.3390/ijgi8060258.
  15. Martin Galanda. Automated polygon generalization in a multi agent system. PhD thesis, University of Zurich, Zürich, 2003. URL: https://doi.org/10.5167/uzh-163108.
  16. Sven Gedicke, Johannes Oehrlein, and Jan-Henrik Haunert. Aggregating land-use polygons considering line features as separating map elements. Cartography and Geographic Information Science, 48(2):124-139, 2021. URL: https://doi.org/10.1080/15230406.2020.1851613.
  17. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  18. Jan-Henrik Haunert and Alexander Wolff. Area aggregation in map generalisation by mixed-integer programming. International Journal of Geographical Information Science, 24(12):1871-1897, 2010. URL: https://doi.org/10.1080/13658810903401008.
  19. Christopher B. Jones, Geraint Ll. Bundy, and Mark J. Ware. Map generalization with a triangulated data structure. Cartography and Geographic Information Systems, 22(4):317-331, 1995. URL: https://doi.org/10.1559/152304095782540221.
  20. Kamyoung Kim, Denis J. Dean, Hyun Kim, and Yongwan Chun. Spatial optimization for regionalization problems with spatial interaction: a heuristic approach. International Journal of Geographical Information Science, 30(3):451-473, 2016. URL: https://doi.org/10.1080/13658816.2015.1031671.
  21. Chengming Li, Yong Yin, Xiaoli Liu, and Pengda Wu. An automated processing method for agglomeration areas. ISPRS International Journal of Geo-Information, 7(6):204, 2018. URL: https://doi.org/10.3390/ijgi7060204.
  22. Jingzhong Li and Tinghua Ai. A triangulated spatial model for detection of spatial characteristics of GIS data. In Proc. 2010 IEEE International Conference on Progress in Informatics and Computing (PIC '10), volume 1, pages 155-159, 2010. URL: https://doi.org/10.1109/PIC.2010.5687417.
  23. Adrien Maudet, Guillaume Touya, Cécile Duchêne, and Sébastien Picault. Multi-agent multi-level cartographic generalisation in CartAGen. In Proc. 12th International Conference on Advances in Practical Applications of Heterogeneous Multi-Agent Systems (PAAMS '14), pages 355-358, 2014. URL: https://doi.org/10.1007/978-3-319-07551-8_37.
  24. Robert B. McMaster and K. Stuart Shea. Generalization in digital cartography. Association of American Geographers, Washington, DC, USA, 1992. Google Scholar
  25. Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. JGraphT - a Java library for graph data structures and algorithms. ACM Transactions on Mathematical Software, 46(2), 2020. URL: https://doi.org/10.1145/3381449.
  26. Adriano Moreira and Maribel Y. Santos. Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points. In Proc. 2nd International Conference on Computer Graphics Theory and Applications (GRAPP '07), pages 61-68, 2007. URL: http://hdl.handle.net/1822/6429.
  27. Johannes Oehrlein and Jan-Henrik Haunert. A cutting-plane method for contiguity-constrained spatial aggregation. Journal of Spatial Information Science, 15(1):89-120, 2017. URL: https://doi.org/10.5311/JOSIS.2017.15.379.
  28. OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org , 2020.
  29. James B. Orlin. Max flows in O(nm) time, or better. In Proc. 45th Annual ACM Symposium on Theory of Computing (STOC '13), page 765–774, 2013. URL: https://doi.org/10.1145/2488608.2488705.
  30. Bo Peng and Olga Veksler. Parameter selection for graph cut based image segmentation. In Proc. British Machine Vision Conference (BMVC '08), pages 16.1-16.10, 2008. URL: https://doi.org/10.5244/C.22.16.
  31. Ekaterina S. Podolskaya, Karl-Heinrich Anders, Jan-Henrik Haunert, and Monika Sester. Quality assessment for polygon generalization. In Quality Aspects in Spatial Data Mining, chapter 16, pages 211-220. CRC Press, Boca Raton, FL, USA, 2007. URL: https://doi.org/10.1201/9781420069273.ch16.
  32. Anthony Przybylski, Xavier Gandibleux, and Matthias Ehrgott. A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS Journal on Computing, 22(3):371-386, 2010. URL: https://doi.org/10.1287/ijoc.1090.0342.
  33. Azimjon Sayidov, Robert Weibel, and Stefan Leyk. Recognition of group patterns in geological maps by building similarity networks. Geocarto International, pages 1-20, 2020. URL: https://doi.org/10.1080/10106049.2020.1730449.
  34. David Sedlacek and Jiri Zara. Graph cut based point-cloud segmentation for polygonal reconstruction. In Proc. 5th International Symposium on Advances in Visual Computing (ISVC '09), pages 218-227, 2009. URL: https://doi.org/10.1007/978-3-642-10520-3_20.
  35. Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000. URL: https://doi.org/10.1109/34.868688.
  36. Stefan Steiniger, Dirk Burghardt, and Robert Weibel. Recognition of island structures for map generalization. In Proc. 14th Annual ACM International Symposium on Advances in Geographic Information Systems (ACM GIS '06), pages 67-74, 2006. URL: https://doi.org/10.1145/1183471.1183484.
  37. Guillaume Touya, Xiang Zhang, and Imran Lokhat. Is deep learning the new agent for map generalization? International Journal of Cartography, 5(2-3):142-157, 2019. URL: https://doi.org/10.1080/23729333.2019.1613071.
  38. Edward R. Tufte. The visual display of quantitative information. Graphics Press, Cheshire, CT, USA, 1992. URL: https://doi.org/10.1119/1.14057.
  39. Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(11):1101-1113, 1993. URL: https://doi.org/10.1109/34.244673.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact