Analysis of the effectiveness of constraining metrics of geometric simplification algorithms based on expert evaluation of line detail

DOI: 10.35595/2414-9179-2021-2-27-253-267

View or download the article (Rus)

About the Authors

Timofey E. Samsonov

Lomonosov Moscow State University, Faculty of Geography,
Leninskie gory 1, 119991, Moscow, Russia;
E-mail: tsamsonov@geogr.msu.ru

Olga P. Yakimova

Demidov Yaroslavl State University,
Soyuznaya str., 144, 150008, Yaroslavl, Russia;
E-mail: polya@uniyar.ac.ru

Abstract

The paper reveals dependencies between the character of the line shape and combination of constraining metrics that allows comparable reduction in detail by different geometric simplification algorithms. The study was conducted in a form of the expert survey. geometrically simplified versions of three coastline fragments were prepared using three different geometric simplification algorithms—Douglas-peucker, Visvalingam-Whyatt and Li-Openshaw. Simplification was constrained by similar value of modified hausdorff distance (linear offset) and similar reduction of number of line bends (compression of the number of detail elements). Respondents were asked to give a numerical estimate of the detail of each image, based on personal perception, using a scale from one to ten. The results of the survey showed that lines perceived by respondents as having similar detail can be obtained by different algorithms. however, the choice of the metric used as a constraint depends on the nature of the line. Simplification of lines that have a shallow hierarchy of small bends is most effectively constrained by linear offset. As the line complexity increases, the compression metric for the number of detail elements (bends) increases its influence in the perception of detail. For one of the three lines, the best result was consistently obtained with a weighted combination of the analyzed metrics as a constraint. None of the survey results showed that only reducing the number of bends can be used as an effective characteristic of similar reduction in detail. It was therefore found that the linear offset metric is more indicative when describing changes in line detail.

Keywords

spatial data detail, geometric line simplification, expert survey

References

  1. Ai T. The drainage network extraction from contour lines for contour line generalization. ISPRS Journal of Photogrammetry and Remote Sensing, 2007. V. 62. No. 2. P. 93–103. DOI: 10.1016/j.isprsjprs.2007.04.002.
  2. Bayer T. Automated Building Simplification Using a Recursive Approach. Advances in Cartography and GIScience. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. V. 1. P. 121–146. DOI: 10.1007/978-3-642-03294-3_8.
  3. Douglas D.H., Peucker T.K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 1973. No. 10 (2). P. 112–122.
  4. Dubuisson M.-P., Jain A.K. A Modified hausdorff Distance for object. Proceedings of 12th International Conference on Pattern Recognition. IEEE Comput. Soc. Press, 1994. V. 1. P. 566–568. DOI: 10.1109/ICPR.1994.576361.
  5. Li Z., Openshaw S. Algorithms for Automated Line Generalization Based on a Natural Principle of Objective Generalization. International journal of geographical information systems, 1992. V. 6. No. 5. P. 373–389. DOI: 10.1080/02693799208901921.
  6. Mustiere S. Cartographic generalization of roads in a local and adaptive approach: A knowledge acquistion problem. International Journal of Geographical Information Science, 2005. V. 19. No. 8–9. P. 937–955. DOI: 10.1080/13658810509161245.
  7. Park W., Yu K. Hybrid line simplification for cartographic generalization. Pattern Recognition Letters, 2011. V. 32. No. 9. P. 1267–1273. DOI: 10.1016/j.patrec.2011.03.013.
  8. Samsonov T.E., Yakimova O.P. Regression modeling of reduction in spatial accuracy and detail for multiple geometric line simplification procedures. International Journal of Cartography, 2020. V. 6. No. 1. P. 47–70. DOI: 10.1080/23729333.2019.1615745.
  9. Samsonov T.E., Yakimova O.P. Shape-Adaptive Geometric Simplification of Heterogeneous Line Datasets. International Journal of Geographical Information Science, 2017. V. 31. No. 8. P. 1485–1520. DOI: 10.1080/13658816.2017.1306864.
  10. Touya G., Duchêne C., Ruas A. Collaborative Generalisation: Formalisation of Generalisation Knowledge to Orchestrate Different Cartographic Generalisation Processes. Theories and Methods of Spatio-Temporal Reasoning in Geographic Space. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. P. 264–278. DOI: 10.1007/978-3-642-15300-6_19.
  11. Visvalingam M., Whyatt J.D. Line Generalisation by Repeated Elimination of Points. The Cartographic Journal. 1993. V. 30. No. 1. P. 46–51. DOI: 10.1179/000870493786962263.
  12. Wang Z., Muller J.C. Complex Coastline Generalization. Cartography and Geographic Information Science, 1993. V. 20. No. 2. P. 96–106.

For citation: Samsonov T.E., Yakimova O.P. Analysis of the effectiveness of constraining metrics of geometric simplification algorithms based on expert evaluation of line detail. InterCarto. InterGIS. GI support of sustainable development of territories: Proceedings of the International conference. Moscow: MSU, Faculty of Geography, 2021. V. 27. Part 2. P. 253–267. DOI: 10.35595/2414-9179-2021-2-27-253-267 (in Russian)