利用树编辑距离的等高线拓扑相似性度量方法
|
摘要
已有的拓扑相似性度量方法主要通过目标之间拓扑关系统计均值的差值,衡量目标之间的拓扑相似程度,在拓扑变化复杂区域由于拓扑关系的增减互补易产生度量误差。为此,提出一种顾及拓扑结构差异的等高线群拓扑相似性度量方法;引入Zhang-shasha算法将等高线群之间的拓扑变化转化为等高线树之间的转换编辑操作;构建基于树结构的拓扑差异表达;并利用动态规划方法求解等高线树之间的转换编辑距离;进而量化度量等高线群间的拓扑结构相似度。模拟数据实验和真实数据实验表明,该方法顾及了拓扑结构差异,能够有效度量多源多尺度等高线数据之间的拓扑相似程度,减少度量误差。
In previous topological similarity measure methods, the difference between statistical mean values are mainly calculated for the topological similarity and the topological structure variation are not considered, which may lead to measurement errors in areas with complex topological changes. Therefore, a topological similarity measure method is proposed based on topological structure variations. Based on Zhang-shasha algorithm, the topological changes between the contour groups are converted into the editing operation between the contour trees. Topology difference expression based on tree structure is constructed and the transformation distance between the contour trees is calculated through dynamic programming method. Then the topological similarity is quantitative measured based on transformation distance. Simulated and real datasets experiments prove the proposed measure method can effectively measure the topological similarity between multisource contours and reduce the measurement error.
In previous topological similarity measure methods, the difference between statistical mean values are mainly calculated for the topological similarity and the topological structure variation are not considered, which may lead to measurement errors in areas with complex topological changes. Therefore, a topological similarity measure method is proposed based on topological structure variations. Based on Zhang-shasha algorithm, the topological changes between the contour groups are converted into the editing operation between the contour trees. Topology difference expression based on tree structure is constructed and the transformation distance between the contour trees is calculated through dynamic programming method. Then the topological similarity is quantitative measured based on transformation distance. Simulated and real datasets experiments prove the proposed measure method can effectively measure the topological similarity between multisource contours and reduce the measurement error.
引文
[1] FRONTIERA P L.A probabilistic approach to spatial ranking for geographic information retrieval[D].Berkeley:University of California,2004:48-59.
[2] 邢汉发,周晓光,许礼林.基于线/线拓扑关系的局部变化等高线融合[J].武汉大学学报(信息科学版),2010,35(11):1322-1326.XING H F,ZHOU X G,XU L L.Local contour line fusion based on line/line topological relations[J].Geomatics and Information Science of Wuhan University,2010,35(11):1322-1326.
[3] 陈军,周晓光.基于拓扑联动的增量更新方法研究:以地籍数据库为例[J].测绘学报,2008,37(3):322-329.CHEN J,ZHOU X G.Incremental updating of spatial database based on topological linkage,taking cadastral database’s updating as an example[J].Acta Geodaetica et Cartographica Sinica,2008,37(3):322-329.
[4] 郑宇志,张青年.基于拓扑及空间相似性的面实体匹配方法研究[J].测绘科学技术学报,2013,30(5):510-514.ZHENG Y Z,ZHANG Q N.An approach to identical areal entity matching based on topology and spatial similarity[J].Journal of Geomatics Science and Technology,2013,30(5):510-514.
[5] 李国辉,许文帅,龙毅,等.面向等高线与河流冲突处理的多约束移位方法[J].测绘学报,2014,43(11):1204-1210.LI G H,XU W S,LONG Y,et al.A multi-constraints displacement method for solving spatial conflict between contours and rivers[J].Acta Geodaetica et Cartographica Sinica,2014,43(11):1204-1210.
[6] EGENHOFER M J,MARK D M,HERRING J.The 9-intersection:Formalism and its use for natural-language spatial predicates[R].Santa Barbara:National Center for Geographic Information and Analysis,1994.
[7] PAPADIAS D.Processing fuzzy spatial queries:A configuration similarity approach[J].International Journal of Geographical Information Science,1999,13(2):93-118.
[8] 周晓光,汪红松,吴志强.引入二维交细分类型的地表覆盖矢量数据增量更新[J].测绘学报,2017,46(1):114-122.ZHOU X G,WANG H S,WU Z Q.An incremental updating method for land cover database using refined 2-dimensional intersection type[J].Acta Geodaetica et Cartographica Sinica,2017,46(1):114-122.
[9] 刘涛,杜清运,毛海辰.空间线群目标相似度计算模型研究[J].武汉大学学报(信息科学版),2012,37(8):992-995.LIU T,DU Q Y,MAO H C.Spatial similarity assessment model and its application in line groups[J].Geomatics and Information Science of Wuhan University,2012,37(8):992-995.
[10] 刘涛,杜清运,闫浩文.空间点群目标相似度计算[J].武汉大学学报(信息科学版),2011,36(10):1149-1153.LIU T,DU Q Y,YAN H W.Spatial similarity assessment of point clusters [J].Geomatics and Information Science of Wuhan University,2011,36(10):1149-1153.
[11] 段晓旗,刘涛,武丹.基于层次分析法的多尺度点群目标相似度计算[J].地球信息科学学报,2016,18(10):1312-1321.DUAN X Q,LIU T,WU D.Spatial similarity assessment of point clusters in multi-scale map spaces based on analytic hierarchy process[J].Journal of Geo-Information Science,2016,18(10):1312-1321.
[12] 安晓亚,杨云,刘平芝.基于拓扑谓词的空间拓扑关系相似性度量模型与应用[J].地球信息科学学报,2013,15(2):159-165.AN X Y,YANG Y,LIU P Z.Similarity measuring of spatial topological relations based on topological predication[J].Journal of Geo-Information Science,2013,15(2):159-165.
[13] ZHANG K,SHASHA D.Simple fast algorithms for the editing distance between trees and related problems[J].Siam Journal on Computing,1989,18(6):1245-1262.
[14] ZHANG K,SHASHA D.Tree pattern matching[M]//APOSTOLICO A,GALIL Z.Pattern matching algorithms.UK:Oxford University Press,1997:341-371.
[15] AKUTSU T.Tree edit distance problems:algorithms and applications to bioinformatics[J].IEICE Transactions on Information and Systems,2010,93(2):208-218.
[16] 张亚芹,杨鹤标.基于Zhang-shasha算法的存储过程相似性匹配[J].计算机应用研究,2014,31(9):2692-2695.ZHANG Y Q,YANG H B.Study on similarity matching of store procedure based on Zhang-shasha algorithm[J].Application Research of Computers,2014,31(9):2692-2695.
[17] 宋敦江,岳天祥,杜正平.等高线树构建及高保真DEM构建[J].中国图象图形学报,2011,16(7):1255-1261.SONG D J,YUE T X,DU Z P.Constructing contour tree and DEM construction of high fidelity[J].Journal of Image and Graphics,2011,16(7):1255-1261.
[18] CRONIN T.Automated reasoning with contour maps[J].Computers and Geosciences,1995,21(5):609-618.
[19] CRONIN T.Classifying hills and valleys in digitized terrain[J].Photogrammetric Engineering and Remote Sensing,2000,66(9):1129-1137.
[20] ROUBAL J,POIKER T K.Automated contour labelling and the contour tree[C]//The Proceedings of Auto-Carto 7 Digital Representations of Spatial Knowledge.Washington D C,1985:472-481.
[21] 乔朝飞,赵仁亮,陈军,等.基于Voronoi内邻近的等高线树生成法[J].武汉大学学报(信息科学版),2005,30(9):801-804.QIAO C F,ZHAO R L,CHEN J,et al.A Voronoi interior adjacency-based approach for generating a contour tree[J].Gematics and Information Science of Wuhan University,2005,30(9):801-804.
[22] 张尧,樊红,黄旺.基于Delaunay三角网的等高线树生成方法[J].测绘学报,2012,41(3):461-467.ZHANG Y,FAN H,HUANG W.The method of generating contour tree based on contour Delaunay triangulation[J].Acta Geodaetica et Cartographica Sinica,2012,41(3):461-467.
[2] 邢汉发,周晓光,许礼林.基于线/线拓扑关系的局部变化等高线融合[J].武汉大学学报(信息科学版),2010,35(11):1322-1326.XING H F,ZHOU X G,XU L L.Local contour line fusion based on line/line topological relations[J].Geomatics and Information Science of Wuhan University,2010,35(11):1322-1326.
[3] 陈军,周晓光.基于拓扑联动的增量更新方法研究:以地籍数据库为例[J].测绘学报,2008,37(3):322-329.CHEN J,ZHOU X G.Incremental updating of spatial database based on topological linkage,taking cadastral database’s updating as an example[J].Acta Geodaetica et Cartographica Sinica,2008,37(3):322-329.
[4] 郑宇志,张青年.基于拓扑及空间相似性的面实体匹配方法研究[J].测绘科学技术学报,2013,30(5):510-514.ZHENG Y Z,ZHANG Q N.An approach to identical areal entity matching based on topology and spatial similarity[J].Journal of Geomatics Science and Technology,2013,30(5):510-514.
[5] 李国辉,许文帅,龙毅,等.面向等高线与河流冲突处理的多约束移位方法[J].测绘学报,2014,43(11):1204-1210.LI G H,XU W S,LONG Y,et al.A multi-constraints displacement method for solving spatial conflict between contours and rivers[J].Acta Geodaetica et Cartographica Sinica,2014,43(11):1204-1210.
[6] EGENHOFER M J,MARK D M,HERRING J.The 9-intersection:Formalism and its use for natural-language spatial predicates[R].Santa Barbara:National Center for Geographic Information and Analysis,1994.
[7] PAPADIAS D.Processing fuzzy spatial queries:A configuration similarity approach[J].International Journal of Geographical Information Science,1999,13(2):93-118.
[8] 周晓光,汪红松,吴志强.引入二维交细分类型的地表覆盖矢量数据增量更新[J].测绘学报,2017,46(1):114-122.ZHOU X G,WANG H S,WU Z Q.An incremental updating method for land cover database using refined 2-dimensional intersection type[J].Acta Geodaetica et Cartographica Sinica,2017,46(1):114-122.
[9] 刘涛,杜清运,毛海辰.空间线群目标相似度计算模型研究[J].武汉大学学报(信息科学版),2012,37(8):992-995.LIU T,DU Q Y,MAO H C.Spatial similarity assessment model and its application in line groups[J].Geomatics and Information Science of Wuhan University,2012,37(8):992-995.
[10] 刘涛,杜清运,闫浩文.空间点群目标相似度计算[J].武汉大学学报(信息科学版),2011,36(10):1149-1153.LIU T,DU Q Y,YAN H W.Spatial similarity assessment of point clusters [J].Geomatics and Information Science of Wuhan University,2011,36(10):1149-1153.
[11] 段晓旗,刘涛,武丹.基于层次分析法的多尺度点群目标相似度计算[J].地球信息科学学报,2016,18(10):1312-1321.DUAN X Q,LIU T,WU D.Spatial similarity assessment of point clusters in multi-scale map spaces based on analytic hierarchy process[J].Journal of Geo-Information Science,2016,18(10):1312-1321.
[12] 安晓亚,杨云,刘平芝.基于拓扑谓词的空间拓扑关系相似性度量模型与应用[J].地球信息科学学报,2013,15(2):159-165.AN X Y,YANG Y,LIU P Z.Similarity measuring of spatial topological relations based on topological predication[J].Journal of Geo-Information Science,2013,15(2):159-165.
[13] ZHANG K,SHASHA D.Simple fast algorithms for the editing distance between trees and related problems[J].Siam Journal on Computing,1989,18(6):1245-1262.
[14] ZHANG K,SHASHA D.Tree pattern matching[M]//APOSTOLICO A,GALIL Z.Pattern matching algorithms.UK:Oxford University Press,1997:341-371.
[15] AKUTSU T.Tree edit distance problems:algorithms and applications to bioinformatics[J].IEICE Transactions on Information and Systems,2010,93(2):208-218.
[16] 张亚芹,杨鹤标.基于Zhang-shasha算法的存储过程相似性匹配[J].计算机应用研究,2014,31(9):2692-2695.ZHANG Y Q,YANG H B.Study on similarity matching of store procedure based on Zhang-shasha algorithm[J].Application Research of Computers,2014,31(9):2692-2695.
[17] 宋敦江,岳天祥,杜正平.等高线树构建及高保真DEM构建[J].中国图象图形学报,2011,16(7):1255-1261.SONG D J,YUE T X,DU Z P.Constructing contour tree and DEM construction of high fidelity[J].Journal of Image and Graphics,2011,16(7):1255-1261.
[18] CRONIN T.Automated reasoning with contour maps[J].Computers and Geosciences,1995,21(5):609-618.
[19] CRONIN T.Classifying hills and valleys in digitized terrain[J].Photogrammetric Engineering and Remote Sensing,2000,66(9):1129-1137.
[20] ROUBAL J,POIKER T K.Automated contour labelling and the contour tree[C]//The Proceedings of Auto-Carto 7 Digital Representations of Spatial Knowledge.Washington D C,1985:472-481.
[21] 乔朝飞,赵仁亮,陈军,等.基于Voronoi内邻近的等高线树生成法[J].武汉大学学报(信息科学版),2005,30(9):801-804.QIAO C F,ZHAO R L,CHEN J,et al.A Voronoi interior adjacency-based approach for generating a contour tree[J].Gematics and Information Science of Wuhan University,2005,30(9):801-804.
[22] 张尧,樊红,黄旺.基于Delaunay三角网的等高线树生成方法[J].测绘学报,2012,41(3):461-467.ZHANG Y,FAN H,HUANG W.The method of generating contour tree based on contour Delaunay triangulation[J].Acta Geodaetica et Cartographica Sinica,2012,41(3):461-467.