Relationship between scale change and median Hausdorff distance of river elements

doi:10.11947/j.AGCS.2023.20210573

Abstract

Abstract: Map generalization is essentially a similar transformation process, and the quantitative analysis of this particular process is of great practical significance. In this paper, the universal functional relationship between scale change and median Hausdorff distance of river elements is obtained via large sample statistics. Firstly, randomly selecting river samples from a 1∶10 000 vector river database, and a multi-scale river element dataset is constructed via manual simplification. The median Hausdorff distance is used to measure the multi-scale similarity of river elements, and a quantitative functional relationship between scale change and median Hausdorff distance is presented via curve fitting. Subsequently, a preliminary applicative exploration of applying the functional relationship to the control of the map generalization process is presented, and the automatic determination of thresholds for BS (bend-simplify) algorithm, DP (Douglas-Peucker) algorithm, and WA (weighted-area) algorithm is achieved. Experimental results show the strong useability of the proposed functional relationship, which contribute to the full automation of the existing semi-automatic map generalization algorithms.

Key words: river element, median Hausdorff distance, scale, similarity, map generalization

CLC Number:

P284

ZHANG Xingang, YAN Haowen. Relationship between scale change and median Hausdorff distance of river elements[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(8): 1364-1374.

References

[1] 武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10): 1645-1664.DOI: 10.11947/J.AGCS.2017.20170287. WU Fang, GONG Xianyong, DU Jiawei. Overview of the research progress in automated map generalization[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10): 1645-1664.DOI: 10.11947/J.AGCS.2017.20170287.
[2] 郭庆胜. 地图自动综合问题的分解和基本算子集合[J]. 武汉测绘科技大学学报, 1999, 24(2): 149-153. GUO Qingsheng. The decomposement and operators set of automatic map generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping (Wtusm), 1999, 24(2): 149-153.
[3] 王家耀. 空间数据自动综合研究进展及趋势分析[J]. 测绘科学技术学报, 2008, 25(1): 1-7, 12. WANG Jiayao. The progress and trend of automatic generalization of spatial data[J]. Journal of Geomatics Science and Technology, 2008, 25(1): 1-7, 12.
[4] LIU Minshi, HE Guifang, LONG Yi. A semantics-based trajectory segmentation simplification method[J]. Journal of Geovisualization and Spatial Analysis, 2021, 5(2): 1-15.
[5] YAN Haowen. Fundamental theories of spatial similarity relations in multi-scale map spaces[J]. Chinese Geographical Science, 2010, 20(1): 18-22.
[6] WANG Z, MVLLER J C. Line generalization based on analysis of shape characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1): 3-15.
[7] RMAER U. An iterative procedure for the polygonal approximation of plane curves[J]. Computer Graphics and Image Processing, 1972, 1(3): 244-256.
[8] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica: the international journal for geographic information and geovisualization, 1973, 10(2): 112-122.
[9] ZHOU Sheng, CHRISTOPHER B J. Shape-aware line generalisation with weighted effective area[C]//Proceedings of 2005 Developments in Spatial Data Handling.Berlin:Springer, 2005, 369-380.
[10] YAN Haowen. Description approaches and automated generalization algorithms for groups of map objects[M]. Berlin: Springer International Publishing, 2019.
[11] YAN Haowen. Quantitative relations between spatial similarity degree and map scale change of individual linear objects in multi-scale map spaces[J]. Geocarto International, 2015, 30(4): 472-482.
[12] YAN Haowen, JONATHAN Li. Applications of spatial similarity relations in map generalization[M]. Berlin: Springer International Publishing, 2015.
[13] YANG Weifang, YAN Haowen, JONATHAN Li. Formula for calculating spatial similarity degrees between point clouds on multi-scale maps taking map scale change as the only independent variable[J]. Geodesy and Geodynamics, 2015, 6(2): 113-125.
[14] 程绵绵, 孙群, 徐立, 等. 面轮廓线相似性和复杂性度量及在化简中的应用[J]. 测绘学报, 2019, 48(4): 489-501.DOI: 10.11947/j.AGCS.2019.20180124. CHENG Mianmian, SUN Qun, XU Li, et al. Polygon contour similarity and complexity measurement and application in simplification[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 489-501.DOI: 10.11947/j.AGCS.2019.20180124.
[15] SCHWERING A. Approaches to semantic similarity measurement for geo-spatial data: a survey[J]. Transactions in GIS, 2008, 12(1): 5-29.
[16] TONG Xiaohua, LIANG Dan, JIN Yanmin. A linear road object matching method for conflation based on optimization and logistic regression[J]. International Journal of Geographical Information Science, 2014, 28(4): 824-846.
[17] DENG Min. Extended Hausdorff distance for spatial objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4): 459-475.
[18] TÖPFER F, PILLEWIZER W. The principles of selection[J]. The Cartographic Journal, 1966, 3(1): 10-16.
[19] CHEN Lei, TAMERÖZSU M, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of 2005 ACM SIGMOD international conference on Management of data. Baltimore: ACM Press, 2005: 491-502.
[20] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories[C]//Proceedings of the 18th International Conference on Data Engineering.San Jose: IEEE, 2002: 673-684.
[21] KEOGH E J, PAZZANI M J. Derivative dynamic time warping[C]// Proceedings of 2001 SIAM international conference on data mining. [S.l.]: SIAM, 2001.
[21] KEOGH E J, PAZZANI M J. Derivative dynamic time warping[C]//Proceedings of 2001 SIAM International Conference on Data Mining. Philadelphia:IEEE,2001.
[22] TECHNISCHE U W, THOMAS E,MANNILA H,et al.Computing discrete Fréchet distance[J].See Also, 1994, 64(3): 636-637.
[23] BELOGAY E, CABRELLI C, MOLTER U, et al. Calculating the Hausdorff distance between curves[J]. Information Processing Letters, 1997, 64(1): 17-22.
[24] LIN Bin, SU Jianwen. One way distance: for shape based similarity search of moving object trajectories[J]. GeoInformatica, 2008, 12(2): 117-142.
[25] PELEKIS N, KOPANAKIS I, MARKETOS G, et al. Similarity search in trajectory databases[C]//Proceedings of the 14th International Symposium on Temporal Representation and Reasoning (TIME'07).Alicante: IEEE, 2008: 129-140.
[26] CHAIRUNNANDA P, GOPALKRISHNAN V, CHEN Lei. Enhancing edit distance on real sequences filters using histogram distance on fixed reference ordering[C]//Proceedings of the 18th International Conference on Pattern Recognition (ICPR'06). Hong Kong: IEEE, 2006: 582-585.
[27] KHAN R, ALI I, ALTOWAIJRI S M, et al. LCSS-based algorithm for computing multivariate data set similarity: a case study of real-time WSN data[J]. Sensors (Basel, Switzerland), 2019, 19(1): 166.
[28] CUTURI M, BLONDEL M. Soft-DTW: a differentiable loss function for time-series[C]//Proceedings of the 34th International Conference on Machine Learning. Sydney: ACM Press, 2017: 894-903.
[29] DRIEMEL A, PSARROS I. ANN for time series under the Fréchet distance[C]//Proceedings of 2021 Workshop on Algorithms and Data Structures Conference. Cham: Springer, 2021.
[30] JAVAHERI A, BRITES C, PEREIRA F, et al. A generalized Hausdorff distance based quality metric for point cloud geometry[C]//Proceedings of 2020 Twelfth International Conference on Quality of Multimedia Experience.Athlone: IEEE, 2020: 1-6.
[31] GUO Wenyue, YU Anzhu, SUN Qun, et al. A multisource contour matching method considering the similarity of geometric features[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(3): 76-87.
[32] 王靖, 朱梦宇, 赵保军, 等. 基于小波和改进型Hausdorff距离的遥感图像配准方法[J]. 电子学报, 2006, 34(12): 2167-2169. WANG Jing, ZHU Mengyu, ZHAO Baojun, et al. A remote sensing image registration method based on wavelet decomposition and the improved Hausdorff distance[J]. Acta Electronica Sinica, 2006, 34(12): 2167-2169.
[33] LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data. Beijing: ACM Press, 2007: 593-604.
[34] DYSON F. A meeting with enrico Fermi[J]. Nature, 2004, 427(6972): 297.
[35] 程绵绵, 孙群, 李少梅, 等. 多尺度点群广义Hausdorff距离及在相似性度量中的应用[J]. 武汉大学学报(信息科学版), 2019, 44(6): 885-891. CHENG Mianmian, SUN Qun, LI Shaomei, et al. Generalized Hausdorff distance of multi-scale point group and its application in similarity measurement[J]. Geomatics and Information Science of Wuhan University, 2019, 44(6): 885-891.