Automatic simplification of the geometry of a cartographic line using contractive self-mapping - illustrated with an example of a polyline band

• Autorzy: Bac-Bronowicz Joanna , Banasik Piotr , Chrobak Tadeusz

Identyfikatory

DOI

10.2478/pcr-2023-0007

• Języki publikacji: EN

Abstrakty

EN

The present article is another attempt to adapt map geometry to automatic digital cartography. The paper presents a method of digital polyline generalisation that uses contractive self-mapping. It is a method of simplification, not just an algorithm for simplification. This method in its 1996 version obtained a patent entitled “Method of Eliminating Points in the Process of Numerical Cartographic Generalisation” – Patent Office of the Republic of Poland, No. 181014, 1996. The first results of research conducted using the presented method, with clearly defined data (without singular points of their geometry), were published in the works of the authors in 2021 and 2022. This article presents a transition from the DLM (Digital Landscape Model) to the DCM (Digital Cartographic Model). It demonstrates an algorithm with independent solutions for the band axis and both its edges. The presented example was performed for the so-called polyline band, which can represent real topographic linear objects such as rivers and boundaries of closed areas (buildings, lakes, etc.). An unambiguous representation of both edges of the band is its axis, represented in DLM, which can be simplified to any scale. A direct consequence of this simplification is the shape of the band representing the actual shape of both edges of the object that is classified in the database as a linear object in DCM. The article presents an example performed for the so-called polyline band, which represents real topographic linear objects (roads, rivers) and area boundaries. The proposed method fulfils the following conditions: the Lipschitz condition, the Cauchy condition, the Banach theorem, and the Salichtchev’s standard for object recognition on the map. The presented method is objective in contrast to the previously used approximate methods, such as generalisations that use graph theory and fractal geometry, line smoothing and simplification algorithms, statistical methods with classification of object attributes, artificial intelligence, etc. The presented method for changing the geometry of objects by any scale of the map is 100% automatic, repeatable, and objective; that is, it does not require a cartographer’s intervention.

Słowa kluczowe

EN

digital generalisation; contractive self-mapping; Salichtchev’s minimum measures; geometry of polyline; binary tree structure; Lipschitz’s contraction triangle; Banach theorem

• Wydawca: Polskie Towarzystwo Geograficzne. Oddział Kartograficzny
• Czasopismo: Polish Cartographical Review
• Rocznik: 2023
• Tom: Vol. 55, No. 1
• Strony: 73--86
• Opis fizyczny: Bibliogr. 100 poz., mapy, rys., tab.

Twórcy

autor

Bac-Bronowicz Joanna

• Wroclaw University of Science and Technology, Faculty of Geoengineering, Mining and Geology Wrocław, Poland

• https://orcid.org/0000-0001-9038-1131

autor

Banasik Piotr

• AGH University of Kraków, Faculty of Geo-Data Science, Geodesy, and Environmental Engineering, Kraków, Poland

• https://orcid.org/0000-0002-3604-4019

autor

Chrobak Tadeusz

• Polish Academy of Arts and Sciences, Kraków, Poland

• https://orcid.org/0000-0002-4614-3432

Bibliografia

• Ajdacka, I., & Karsznia, I. (2022). Verifying and improving map specifications of river network selection for automatic generalization of small-scale maps. Polish Cartographical Review, 54(1), 75-91. https://doi.org/10.2478/pcr-2022-0006
• Arora, S., Ge, R., Neyshabur, B., & Zhang, Y. (2018). Stronger generalization bounds for deep nets via a compression approach. Proceedings of the 35th International Conference on Machine Learning, Stockholm, Sweden, 10-15 July.
• Balboa, J. L. G., & Lopez, F. J. A. (2000). Frequency filtering of linear elements by means of wavelets. A method and an example. The Cartographic Journal, 37(1), 39-50. https://doi.org/10.1179/caj.2000.37.1.39
• Balboa, J. L. G., & López, F. J. A. (2008). Generalization-oriented road line classification by means of an artificial neural network. Geoinformatica, 12(3), 289-312. https://doi.org/10.1007/s10707-007-0026-z
• Banasik, P., Chrobak, T., & Biegun, B. (2022). Algorithm of automatic digital cartographic generalisation with the use of contractive self-mapping. Polish Cartographical Review, 54(1), 1-10. https://doi.org/10.2478/pcr-2022-0001
• Barańska, A., Bac-Bronowicz, J., Dejniak, D., Lewiński, S., Krawczyk, A., & Chrobak, T. (2021). A unified methodology for the generalisation of the geometry of features. ISPRS International Journal of Geo-Information, 10(3), 107. https://doi.org/10.3390/ijgi10030107
• Berg, M., Kreveld, M., & Schirra, S. (1995). A new approach to subdivision simplification. Proceedings of the ACSM/ASPRS Annual Convention and Exposition Technical Papers, Charlotte NC, USA, 27 February - 2 March, 4, 79-88.
• Berg, M., Kreveld, M., & Schirra, S. (1998). Topologically correct subdivision simplification using the bandwidth criterion. Cartography and Geographic Information Science, 25(4), 243-257. https://doi.org/10.1559/152304098782383007
• Bjørke, J. T. (1996). Framework for entropy-based map evaluation. Cartography and Geographic Information Systems, 23(2), 78-95. https://doi.org/10.1559/152304096782562136
• Bjørke, J. T. (2003). Generalization of road networks for mobile map services: an information theoretic approach. Proceedings of the 21st International Cartographic Conference (ICA), Durban, RPA, 10-16 August.
• Blana, N., Kavadas, I., & Tsoulos, L. (2023). A constraint-based generalization model incorporating a quality control mechanism. Geographies, 3(2), 321-343. https://doi.org/10.3390/geographies3020017
• Borkowski, A., & Keller, W. (2003). Modelling of irregulary sampled surfaces by two-dimensional snakes. Journal of Geodesy, 77, 543-553.
• Boutoura, C. (1989). Line generalization using spectral techniques. Cartographica, 26(3&4), 33-48. https://doi.org/10.3138/G237-67W4-15N4-1R59
• Brassel, K. E, & Weibel, R. (1988). A review and conceptual framework of automated map generalization. International Journal of Geographical Information Systems, 2(3), 229-244. https://doi.org/10.1080/02693798808927898
• Bronsztejn, I. N., Siemiendiajew, K. A., Musiol, G., & Muhlig, H. (2011). Nowoczesne kompendium matematyki. PWN.
• Burghardt, D. (2005). Controlled line smoothing by snakes. GeoInformatica, 9(3), 237-252. https://doi.org/10.1007/s10707-005-1283-3
• Burghardt, D., & Meier, S. (1997). Cartographic displacement using the snakes concept. In W. Förstner & L. Förstner (Eds.), Semantic Modeling for the Acquisition of Topographic Information from Images and Maps: SMATI 97 (pp. 59-71). Birkhäuser Verlag.
• Burghardt, D., & Schmid, S. (2009). Constraint-based evaluation of automated and manual generalised topographic maps. In G. Gartner & F. Ortag (Eds.), Cartography in Central and Eastern Europe. Lecture Notes in Geoinformation and Cartography (pp. 147-162). Springer. https://doi.org/10.1007/978-3-642-03294-3_9
• Burghardt, D., Neun, M., & Weibel, R. (2005). Generalization services on the web-classification and an initial prototype implementation. Cartography and Geographic Information Science, 32(4), 257-268. https://doi.org/10.1559/152304005775194665
• Burghardt, D., Schmid, S., Duchêne, C., Stoter, J., Baella, B., Regnauld, N., & Touya, G. (2008). Methodologies for the evaluation of generalised data derived with commercial available generalisation systems. Proceedings of the 11th ICA Workshop on Generalization and Multiple Representation, Montpellier, France, 20-21 June, 1-16. https://doi.org/10.5167/uzh-6877
• Cebrykow, J. (2017). Generalizacja map statystycznych. Wydawnictwo UMCS.
• Chaudhry, O., & Mackaness, W. (2008). Partitioning techniques to make manageable the generalisation of national spatial datasets. Proceedings of the 11th ICA Workshop on Generalization and Multiple Representation, Montpellier, France, 20-21 June.
• Chrobak, T. (1999). Badanie przydatności trójkąta elementarnego w komputerowej generalizacji kartograficznej. UWND AGH.
• Chrobak, T. (2003). Metoda uogólnienia danych w procesie generalizacji obiektów liniowych. The Method of Generalization Data Objects Linear. Materiały Ogólnopolskiego Sympozjum Geoinformacji „Geoinformacja zintegrowanym narzędziem badań przestrzennych”, Wrocław-Polanica Zdrój, Poland, 15-17 September, Archiwum Fotogrametrii, Kartografii i Teledetekcji, 13 A, 33-38.
• Chrobak, T. (2007). Podstawy cyfrowej generalizacji kartograficznej. UWND AGH.
• Chrobak, T., Szombara, S., Kozioł, K., & Lupa, M. (2017). A method for assessing generalized data accuracy with linear object resolution verification. Geocarto International, 32(3), 238-256. https://doi.org/10.1080/10106049.2015.1133721
• Courtial, A., El Ayedi, A., Touya, G., & Zang, X. (2020). Exploring the potential of deep learning segmentation for mountain roads generalisation. ISPRS International Journal of Geo-Information, 9(5), 338. https://doi.org/10.3390/ijgi9050338
• Directive 2007/2/EC of the European Parliament and of the Council of 14 March 2007 establishing an Infrastructure for Spatial Information in the European Community (INSPIRE) Document 32007L0002 (2007) (European Union). http://data.europa.eu/eli/dir/2007/2/oj
• Douglas, D. H., & Peucker, T. K. (1973). Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10(2), 112-122 https://doi.org/10.3138/FM57-6770-U75U-7727
• Du, J., Wu, F., Yin, J., Liu, C., & Gong, X. (2022). Polyline simplification based on the artificial neural network with constraints of generalization knowledge. Cartography and Geographic Information Science, 49(4), 313-337. https://doi.org/10.1080/15230406.2021.2013944
• Dupuis, B., Deligiannidis, G., & Simsekli, U. (2023). Generalization bounds using data-dependent fractal dimensions. Proceedings of the 40th International Conference on Machine Learning, Honolulu, Hawaii, USA, 23-29 July, 358, 8922-8968. https://doi.org/10.48550/arXiv.2302.02766
• Dziubiński, I., & Świątkowski, T. (Eds.). (1982). Poradnik matematyczny. PWN.
• EPSG 2180. (2022). https://epsg.io/2180
• Jepsen, T. S., Jensen, C. S., & Nielsen, T. D. (2022). Relation fusion networks: graph convolutional networks for road networks. IEEE Transactions on Intelligent Transportation Systems, 23(1), 418-429. https://doi.org/10.1109/TITS.2020.3011799
• Jiang, B., & Claramunt, C. (2004). A structural approach to the model generalization of an urban street network. GeoInformatica, 8, 157-171. https://doi.org/10.1023/B:GEIN.0000017746.44824.70
• Jiang, B., Liu, X., & Jia, T. (2013). Scaling of geographic space as a universal rule for map generalization. Annals of the Association of American Geographers, 103(4), 844-855. https://doi.org/10.1080/00045608.2013.765773
• João, E. (1998). Causes and Consequences of Map Generalization. Taylor and Francis.
• Karsznia, I., Wereszczyńska, K., & Weibel, R. (2022). Make it simple: effective road selection for small-scale map design using decision-tree-based models. ISPRS International Journal of Geo-Information, 11(8), 457. https://doi.org/10.3390/ijgi11080457
• Kass, M., Witkin, A., & Terzopoulos, D. (1987). Snakes: active contour models. Proceedings of the 1st International Conference on Computer Vision (ICCV’87), London, UK, 8-11 June, 259–268.
• Kilpeläinen, T., & Sarjakoski, T. (1995). Incremental generalization for multiple representations of geographical objects. In J-P. Lagrange, R. Weibel & J-C. Muller (Eds.), GIS And Generalisation (pp. 209-218). CRC Press. https://doi.org/10.1201/ 9781003062646
• Kozioł, K. (2013). A line simplification algorithm using interpolation. Annals of Geomatics, 11(3(60)), 45-59.
• Kronenfeld, B. J., Stanislawski, L. V., Buttenfield, B. P., & Brockmeyer, T. (2020). Simplification of polylines by segment collapse: minimizing areal displacement while preserving area. International Journal of Cartography, 6(1), 22-46. https://doi.org/10.1080/23729333.2019.1631535
• Lagrange, F., Landras, B., & Mustiere, S. (2000). Machine learning techniques for determining parameters of cartographic generalisation algorithms. International Archives of Photogrammetry and Remote Sensing, 13(B4), 718-725.
• Lang, T. (1969). Rules for robot draughtsman. The Geographical Magazine, 42, 50-51.
• Li, Z. (2007). Digital map generalization at the age of enlightenment: a review of the first forty years. The Cartographic Journal, 44(1), 80-93. https://doi.org/10.1179/000870407X173913
• Li, Z., & Choi, Y. H. (2002). Topographic map generalization: association of road elimination with thematic attributes. The Cartographic Journal, 39(2), 153-166. https://doi.org/10.1179/caj.2002.39.2.153
• Li, Z., & Openshaw, S. (1992). Algorithms for automated line generalization based on a natural principle of objective generalization. International Journal of Geographical Information Systems, 6(5), 373-389. https://doi.org/10.1080/02693799208901921
• Li, Z., & Su, B. (1995). From phenomena to essence: envisioning the nature of digital map generalisation. The Cartographic Journal, 32(1), 45-47. https://doi.org/10.1179/000870495787073852
• Liu, Y., & Li, W. (2019). A new algorithms of stroke generation considering geometric and structural properties of road network. ISPRS International Journal of Geo-Information, 8(7), 304. https://doi.org/10.3390/ijgi8070304
• Mackaness, M., Ruas, A., & Sarjakoski, L. T. (2007). Generalisation of geographic information: cartographic modelling and applications. Elsevier.
• Maudet, A., Touya, G., Duchêne, C., & Picault, S. (2017). DIOGEN, a multi-level oriented model for cartographic generalization. International Journal of Cartography, 3(1), 121-133. https://doi.org/10.1080/23729333.2017.1300997
• McMaster, R. B. (1986). A statistical analysis of mathematical measures for linear simplification. The American Cartographer, 13(2), 103–116. https://doi.org/10.1559/152304086783900059
• McMaster, R. B. (1987). Automated line generalization. Cartographica: The International Journal for Geographic Information and Geovisualization, 24(2), 74-111, https://doi.org/10.3138/3535-7609-781G4L20
• McMaster, R. B., & Shea, K. S. (1992). Generalization in digital cartography. Association of American Geographers.
• Muller, J. C., & Mouwes, P. J. (1990). Knowledge acquisition and representation for rule based map generalization: an example from the Netherlands. Proceedings of the GIS/LIS ‘90, Anaheim, California, 7-10 November, 1, 58-67.
• Neun, M., Burghardt, D., & Weibel, R. (2009). Automated processing for map generalization with web services. GeoInformatica, 13(4), 425-452. https://doi.org/10.1007/s10707-008-0054-3
• Opheim, H. (1982). Fast data reduction of a digitized curve. Geo-Processing, 2, 33-40.
• Pannekoek, A. J. (1962). Generalization of coastlines and contours. International Yearbook of Cartography, 2, 55-75.
• Perkal, J. (1958). Próba obiektywnej generalizacji. Geodezja i Kartografia, 6(2), 130-142.
• Perkal, J. (1966). On the length of empirical curves, Discussion paper number 10. Michigan Inter-University Community of Mathematical Geographers.
• Plazanet, C., Affholder, J. G., & Fritsch, E. (1995). The importance of geometric modeling in linear feature generalization. Cartography and Geographic Information Systems, 22(4), 291-305. https://doi.org/10.1559/152304095782540276
• Regnauld, N. (2015). Generalisation and data quality. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-3/W3, 91-94. https://doi.org/10.5194/isprsarchives-XL-3-W3-91-2015
• Robinson, A., Sale, R., & Morrison, J. (1988). Podstawy kartografii. PWN.
• Rozporządzenie Ministra Rozwoju, Pracy i Technologii z dnia 27 lipca 2021 r. w sprawie bazy danych obiektów topograficznych oraz bazy danych obiektów ogólnogeograficznych, a także standardowych opracowań kartograficznych Dz.U. 2021 poz. 1412 (2021) (Polska). https://isap.sejm.gov.pl/isap.nsf/DocDetails.xsp?id=WDU20210001412
• Saalfeld, A. (1999). Topologically consistent line simplification with the Douglas–Peucker algorithm. Cartography and Geographic Information Science, 26(1), 7-18. https://doi.org/10.1559/152304099782424901
• Salichtchev, K. A. (1967). Задачи картограϐӥ и аϐтоматизацьѣ [Cartographic tasks and automation]. Izw. Wysszych Zawied. Gieod. i Aerofot., 4, 7-10.
• Salichtchev, K. A. (2003). Kartografia ogólna. PWN.
• Sester, M., Anders K-H., & Walter, V. (1998). Linking objects of different spatial data sets by integration and aggregation. GeoInformatica, 2, 335-358. https://doi.org/10.1023/A:1009705404707
• Sester, M., Feng, Y., & Thiemann, F. (2018). Building generalization using deep learning. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLII-4, 565-572. https://doi.org/10.5194/isprs-archives-XLII-4-5652018
• Srnka, E. (1970). The analytical solution of regular generalization in cartography. International Yearbook of Cartography, 10, 48-62.
• Stoter, J., Burghardt, D., Duchêne, C., Baella, B., Bakke, N., Blok, C., Pla, M., Regnauld, N., Touya, G., & Schmid, S. (2009b). Methodology for evaluating automated map generalization in commercial software. Computers, Environment and Urban Systems, 33(5), 311-324. https://doi.org/10.1016/j.compenvurbsys.2009.06.002
• Stoter, J., van Altena, V., Post, M., Burghardt, D., & Duchêne, C. (2016). Automated generalisation within NMAs in 2016. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLI-B4, 647-652. https://doi.org/10.5194/isprs-archives-XLI-B4-647-2016
• Stoter, J., van Smaalen, J., Bakker, N., & Hardy, P. (2009a). Specifying map requirements for automated generalization of topographic data. The Cartographic Journal, 46(3), 214-227. https://doi.org/10.1179/174327709X446637
• von Sydow, E. (1866). Drei Karten-Klippen. Geo-Kartographische Betrachtung. Geographisches Jahrbuch, 348-361.
• Tobler, W. R. (1964). Technical report No. 1, „An experiment in the computer generalization of maps”. Department of geography University of Michigan. https://deepblue.lib.umich.edu/bitstream/handle/2027.42/7972/aja5779.0001.001.pdf?sequence=5&isAllowed=y
• Touya, G. (2007). A road network selection process based on data enrichment and structure detection. Proceedings of the 10th ICA Workshop on Generalisation and Multiple Representation, Moscow, Russia, 2-3 August, 595-614.
• Touya, G., Zhang, X., & Lokhat, I. (2019). Is deep learning the new agent for map generalization? International Journal of Cartography, 5(2-3), 142-157. https://doi.org/10.1080/23729333.2019.1613071
• Trinder, J. C., & Li, H. (1995). Semi-automatic feature extraction by snakes. In A. Gruen, O. Kuebler & P. Agouris (Eds.), Monte Verità: Automatic extraction of man-made objects from aerial and space images (pp. 95-104). Birkhäuser Verlag. https://doi.org/10.1007/978-3-0348-9242-1_10
• Visvalingam, M., & Whyatt J. D. (1991). Cartographic algorithms: problems of implementation and evaluation and the impact of digitising errors. Computer Graphics Forum, 10(3), 225-235. https://doi.org/10.1111/1467-8659.1030225
• Visvalingam, M., & Whyatt, D. (1990). The Douglas - Peucker algorithm for line simplification: reevaluation through visualization. Computer Graphics Forum, 9(3), 213-225. https://doi.org/10.1111/j.1467-8659.1990.tb00398.x
• Visvalingam, M., & Whyatt, J. (1993). Line generalisation by repeated elimination of points. Cartographic Journal, 30(1), 46-51.
• Wang, Z., Muller, J-C. (1998). Line generalization based on analysis of shape characteristics. Cartography and Geographic Information Systems, 25(1), 3-15. https://doi.org/10.1559/152304098782441750
• Weibel, R. (1995). Three essential building blocks for automated generalization. In J-P, Lagrange, R. Weibel, & J-C, Muller (Eds.), GIS and Generalization: Methodology and Practice (pp. 56-69). Taylor & Francis.
• Weibel, R. (1996). A typology of constraints to line simplification. In M. J. Kraak & M. Molenaar (Eds.), Advances in GIS Research II (7th International Symposium on Spatial Data Handling) (pp. 533-546). Taylor & Francis.
• Weibel, R., & Dutton, G. H. (1998). Constraints-based automated map generalization. Proceedings of the 8th International Symposium on Spatial Data Handling, Vancouver, BC, Canada, 214-224.
• Weiss, R., & Weibel, R. (2014). Road network selection for small-scale maps using an improved centrality-based algorithm. Journal of Spatial Information Science, 9, 71-99. https://doi.org/10.5311/JOSIS.2014.9.166
• Werschlein, T., & Weibel, R. (1994). Use of neural networks in line generalization. Proceedings of the Fifth European Conference and Exhibition on Geographical Information Systems, Paris, France, 30 March-1 April, 76-85.
• White, E. R. (1985). Assessment of line-generalization algorithms using characteristic points. The American Cartographer, 12(1), 17-28. https://doi.org/10.1559/152304085783914703
• Wu, H. (1997). Structured approach to implementing automatic cartographic generalization. Proceedings of the 18th ICA International Cartographic Conference, Stockholm, Sweden, 23-27 June, 1, 349-356.
• Xiao, T., Ai, T., Yu, H., Yang, M., & Liu, P. (2023). A point selection method in map generalization using graph convolutional network model. Cartography and Geographic Information Science, 1-21. https://doi.org /10.1080/15230406.2023.2187886
• Yan, H. (2019). Description Approaches and Automated Generalization Algorithms for Groups of Map Objects. Springer.
• Yan, H., Yang, W., Lu, X., & Li, P. (2023). Quantitative expressions of spatial similarity between road networks in multiscale map spaces. International Journal of Cartography, 9(3), 554-570. https://doi.org/ 0.1080/23729333.2023.2236266
• Yan, H., Zhang, X., Lu, X., & Li, P. (2022). Approach to automating the DP algorithm – taking river simplification as an example. Geomatics and Information Science of Wuhan University. https://doi.org/10.13203/j.whugis20210412
• Yan, X., & Yang, M. (2023). A deep learning approach for polyline and building simplification based on graph autoencoder with flexible constraints. Cartography and Geographic Information Science, 1-18. https://doi.org/10.1080/15230406.2023.2218106
• Zasoby Głównego Urzędu Geodezji i Kartografii. Geoportal. https://mapy.geoportal.gov.pl/
• Zhang, Q. (2004). Road network generalization based on connection analysis. Proceedings of the 11th International Symposium on Spatial Data Handling, Leicester, UK, 23-25 August, 343-353.
• Zheng, J., Gao, Z., Ma, J., Shen, J., & Zhang, K. (2021). Deep graph convolutional networks for accurate automatic road network selection. ISPRS International Journal of Geo-Information, 10(11), 768. https://doi.org/10.3390/ijgi10110768
• Zheng, L., & Tian, Z. (1997). Refinement of Douglas–Peucker algorithm to move the segments toward only one side. Proceedings of 18th International Cartographic Conference, Stockholm, Sweden, 23-27 June, 830-835.
• Zhou, J., Shen, J., Yang, S., Yu, Z., Stanek, K., & Stampach, R. (2018). Method of constructing point generalization constraints based on the cloud platform. ISPRS International Journal of Geo-Information, 7(7), 235. https://doi.org/10.3390/ijgi7070235
• Zhou, Q., & Li, Z. (2014). Use of artificial neural networks for selective omission in updating road networks. The Cartographic Journal, 51(1), 38-51.