Journal of Multimedia Processing and Technologies

DLINE Journals portal

Home

New Journals

Browse Journals

Journal Prices

For Authors

Print ISSN: 0976-4127
Online ISSN: 0976-4135

About JMPT
	DLINE Portal Home Home Aims & Scope Editorial Board Current Issue Next Issue Previous Issue Sample Issue Upcoming Conferences Self-archiving policy Alert Services Be a Reviewer Publisher Paper Submission Subscription Contact us

How To Order
	Order Online Price Information Request for Complimentary Print Copy

For Authors
	Guidelines for Contributors Online Submission Call for Papers Author Rights

RELATED JOURNALS

Journal of Digital Information Management (JDIM)

International Journal of Computational Linguistics Research (IJCL)

International Journal of Web Application (IJWA)

Journal of Multimedia Processing and Technologies

Method for Identifying the Polygons with Maps

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

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.

Keywords: Polygons, Optimization, Maps Study Method for Identifying the Polygons with Maps

DOI:https://doi.org/10.6025/jmpt/2021/12/4/95-109

Full_Text PDF 1.86 MB Download: 202 times

References:

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

DLINE Journals portal