A comparative study of an algorithm based on the Fourier descriptor with those on geometric criteria

Cartography

UDC:

528.914

DOI:

10.22389/0016-7126-2022-990-12-22-30

1 Yakimova О.P.

2 Teterin T.A.

Year:

2022

№:

990

Pages:

22-30

P.G. Demidov Yaroslavl State University

1,

2,

Abstract:

Line generalization is an essential data processing operation in geographic information systems and cartography. Many point reduction and simplification algorithms have been developed for this purpose. In 2020 a multi-scale representation model of polyline based on a Fourier descriptor was proposed. The authors present a comparative study of such an algorithm and several simplification ones (Douglas – Peucker, Visvalingham – Whyatt, Li – Openshaw, sleeve-fitting), with different criteria for vertex elimination. A brief description of each method involved in the comparison and a more detailed one for that based on the Fourier descriptor is provided. Generalization quality evaluations characterizing the accuracy of the location and geographical plausibility of the line are discussed. Three coastlines of 1 : 1 000 000 scale with different spatial features are used as the initial data for the experiments. The estimates are performed through a quantitative assessment of the results, utilizing shape distortion measures and horizontal position displacement ones. The results of comparing algorithms based on the selected characteristics and operating time are presented. The given conclusions can be used to select a geometric simplification algorithm for multiscale mapping.

Keywords:

cartographic generalization, comparison of algorithms, Fourier descriptor, geometric line simplification, quality assessment

This work was funded by the Demidov Yaroslavl State University (project No. P2-GM3-2021)

References:

1. Samsonov T. E. Mul'timasshtabnoe kartografirovanie – novoe napravlenie kartografii. Pod red. I. K. Lur'e i V. I. Kravtsovoi.Sovremennaya geograficheskaya kartografiya, Moskva: Data+, 2012, pp. 21–35.

2. Sventek Yu. V. Teoreticheskie i prikladnye aspekty sovremennoi kartografii. Moskva: Editorial URSS, 1999, 80 p.

3. Cheng X., Liu Z., Zhang Q. (2021) MSLF: multi-scale legibility function to estimate the legible scale of individual line features. Cartography and Geographic Information Science, no. 48 (2), pp. 151–168. DOI: 10.1080/15230406.2020.1857307.

4. 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. Canadian Cartographer, no. 10 (2), pp. 112–122.

5. Dubuisson M.-P., Jain A. . (1994) A modified hausdorff distance for object matching. Proceedings of 12th International Conference on pattern recognition. pp. 566–568. DOI: 10.1109/ICPR.1994.576361.

6. Dutton G. (1999) Scale, sinuosity, and point selection in digital line generalization. Cartography and Geographic Information Science, no. 26 (1), pp. 33–54. DOI: 10.1559/152304099782424929.

7. Li Z., Openshaw S. (1992) Algorithms for automated line generalization based on a natural principle of objective generalization. International Journal of Geographical Information Systems, no. 6 (5), pp. 373–389. DOI: 10.1080/02693799208901921.

8. Li Z., Zhai J., Wu F. (2018) Shape Similarity Assessment Method for Coastline Generalization. ISPRS International Journal of Geo-Information, no. 7 (7), DOI: 10.3390/ijgi7070283.

9. Liu H., Fan Z., Zhen X., Deng M. (2011) An improved local length ratio method for curve simplification and its evaluation. International Journal of Geographical Information Science, no. 27, pp. 45–48.

10. Liu P., Xiao T., Xiao J., Ai T. (2020) A multi-scale representation model of polyline based on head/tail breaks. International Journal of Geographical Information Science, no. 34 (11), pp. 2275–2295. DOI: 10.1080/13658816.2020.1753203.

11. McMaster R. B. (1986) A statistical analysis of mathematical measures for linear simplification. The American Cartographer, no. 13 (2), pp. 103–116. DOI: 10.1559/152304086783900059.

12. McMaster R. B. (1987) Automated line generalization. Cartographica: The International Journal for Geographic Information and Geovisualization, no. 24 (2), pp. 74–111. DOI: 10.3138/3535-7609-781G-4L20.

13. Raposo P. (2013) Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation. Cartography and Geographic Information Science, no. 40 (5), pp. 427–443. DOI: 10.1080/15230406.2013.803707.

14. Samsonov T. E., Yakimova O. P. (2020) Regression modeling of reduction in spatial accuracy and detail for multiple geometric line simplification procedures. International Journal of Cartography, no. 6 (1), pp. 47–70. DOI: 10.1080/23729333.2019.1615745.

15. Touya G. (2021) Multi-сriteria geographic analysis for automated cartographic generalization. The Cartographic Journal, no. 59 (1), pp. pp 1–17. DOI: 10.1080/00087041.2020.1858608.

16. Visvalingham M., Whyatt J. (1993) Line generalization by repeated elimination of points. Cartographic Journal, no. 30 (1), pp. 46–51. DOI: 10.1179/000870493786962263.

Citation:

Yakimova О.P.,

Teterin T.A.,

(2022) A comparative study of an algorithm based on the Fourier descriptor with those on geometric criteria. Geodesy and cartography = Geodezia i Kartografia, 83(12), pp. 22-30. (In Russian). DOI: 10.22389/0016-7126-2022-990-12-22-30