留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于Fréchet距离的复杂线状要素匹配方法

邵世维 刘辉 肖立霞 王恒

邵世维, 刘辉, 肖立霞, 王恒. 一种基于Fréchet距离的复杂线状要素匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
引用本文: 邵世维, 刘辉, 肖立霞, 王恒. 一种基于Fréchet距离的复杂线状要素匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
SHAO Shiwei, LIU Hui, XIAO Lixia, WANG Heng. A Complex Linear Feature of Fréchet Distance Matching Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
Citation: SHAO Shiwei, LIU Hui, XIAO Lixia, WANG Heng. A Complex Linear Feature of Fréchet Distance Matching Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677

一种基于Fréchet距离的复杂线状要素匹配方法

doi: 10.13203/j.whugis20150677
基金项目: 

用地网络化综合监管信息平台建设及应用示范 2013BAJ05B02-1

详细信息
    作者简介:

    邵世维, 博士, 高级工程师, 主要从事空间数据库更新中不一致性处理的理论与方法研究。shaoshiwei@163.com

    通讯作者: 刘辉, 硕士。liuhuiwhu@126.com
  • 中图分类号: P208

A Complex Linear Feature of Fréchet Distance Matching Method

Funds: 

Land Use Networked Integrated Supervision Information Platform Construction and Application Demonstration 2013BAJ05B02-1

More Information
    Author Bio:

    SHAO Shiwei, PhD, specializes in the theories and methods of inconsistency handling of spatial database updating.E-mail: shaoshiwei@163.com

    Corresponding author: LIU Hui, master. E-mail: liuhuiwhu@126.com
  • 摘要: 在不同空间数据集中,同名实体往往有不同的空间表现形式,识别多源异构数据集中的同名实体是空间数据集成和应用的关键。集成不同来源的空间数据是提高GIS数据质量的重要方法,识别同名实体是数据集成和分析的先决条件。根据线要素的形状将其分为简单线要素和复杂线要素,针对现有复杂线要素匹配方法中的不足,提出了Fréchet距离的复杂线状要素匹配方法。该方法首先通过曲线要素的几何和拓扑特性获取候选匹配集,然后结合基于Fréchet距离和要素简化方法实现要素的简化。最后提出基于Fréchet距离的要素匹配改进方法,通过引入简化要素的三元组信息来存储简化后的复杂线要素的属性信息,再根据三元组信息选取要素间的匹配对,完成对不同类型匹配对的检测,实现复杂线状要素匹配。试验结果表明,该匹配方法能有效解决复杂线要素的匹配问题,并能够识别1:0、1:NM:N匹配。
  • 图  1  复杂线的几种特征

    Figure  1.  Several Characteristics of Complex Line

    图  2  基于Fréchet距离的匹配方法

    Figure  2.  Matching Method Based on Fréchet Distance

    图  3  基于Fréchet距离简化与Douglas-Peucker算法的简化结果

    Figure  3.  Simplification of Curves Based on Fréchet Distance and Douglas-Pecuker Algorithm

    图  4  在不同阈值下, 基于Fréchet的简化方法和Douglas-Peucker算法的比较

    Figure  4.  Comparing Running Times of Fréchet Simplification and Douglas-Pecuker Algorithm for Different Thresholds

    图  5  边界线目标的匹配

    Figure  5.  Matching Case of Border Target

    图  6  河流线目标的匹配

    Figure  6.  Matching Case of River Target

    图  7  正确识别1:0的匹配情况

    Figure  7.  Correctly Identification of 1:0 Matching Case

    表  1  三种匹配方法的比较

    Table  1.   Matching Results of the Three Matching Methods in the Test Area

    匹配方法 边界线数据集 河流数据集
    f(C) f(W) f(U) P/(%) R/(%) f(C) f(W) f(U) P/(%) R/(%)
    文献[2] 102 48 15 68.0 87.1 123 58 30 67.7 80.3
    文献[9] 110 42 18 72.4 85.9 118 63 34 65.2 77.6
    本文 127 22 15 85.0 89.4 155 20 22 88.6 87.5
    下载: 导出CSV
  • [1] Li L, Goodchild M F. Automatically and Accurately Matching Objects in Geospatial Datasets[J]. Adv. Geo-Spat. Inf. Sci, 2012, 10:71-79 http://www.isprs.org/proceedings/XXXVIII/part2/Papers/51_Paper.pdf
    [2] Tong X, Liang D, Jin Y. 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 doi:  10.1080/13658816.2013.876501
    [3] 张桥平, 李德仁, 龚健雅.城市地图数据库面实体匹配技术[J].遥感学报, 2004, 8(2):107-112 doi:  10.11834/jrs.20040203

    Zhang Qiaoping, Li Deren, Gong Jianya. Areal Feature Matching Among Urban Geographic Databases[J]. Journal of Remote Sensing, 2004, 8(2):107-112 doi:  10.11834/jrs.20040203
    [4] 张云菲, 杨必胜, 栾学晨.利用概率松弛法的城市路网自动匹配[J].测绘学报, 2012, 41(6):933-939 http://www.docin.com/p-1473550349.html

    Zhang Yunfei, Yang Bisheng, Luan Xuechen.Automated Mathcing Urban Road Networks Using Probalistic Relaxation[J]. Acta Geodaeticaet Cartographica Sinica, 2012, 41(6):933-939 http://www.docin.com/p-1473550349.html
    [5] 吴长彬, 闾国年. 复杂线-线对象的拓扑关系描述与计算方法[J]. 地球信息科学学报, 16(6): 839-845 doi:  10.3724/SP.J.1047.2014.00839

    Wu Changbin, Lv Guonian. Representation and Calculation Method of Topological Relationships for Complex Line Object[J]. Geo-information Science, 16(6): 839-845 doi:  10.3724/SP.J.1047.2014.00839
    [6] 安晓亚, 刘平芝, 杨云, 等.一种线状要素几何相似性度量方法及其应用[J].武汉大学学报·信息科学版, 2015, 40(9):1225-1229 http://ch.whu.edu.cn/CN/abstract/abstract3325.shtml

    An Xiaoya, Liu Pingzhi, Yang Yun, et al.A Geometric Similarity Measurement Method and Applications to Linear Feature[J]. Geomatics and Information Science of Wuhan Univeristy, 2015, 40(9):1225-1229 http://ch.whu.edu.cn/CN/abstract/abstract3325.shtml
    [7] D M, L Z, C X. Extended Hausdorff Distance for Spatial Objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4):459-475 doi:  10.1080/13658810601073315
    [8] Brakatsoulas S, Pfoser D, Salas R, et al. On Map-matching Vehicle Tracking data[C]. The 31st International Conference on very Large Data Bases, Trondheim, Norway, 2005
    [9] Song X, Raghavan V, Yoshida D. Matching of Vehicle GPS Traces with Urban[J]. Current Science, 2010, 98(12):1592-1598 http://cat.inist.fr/?aModele=afficheN&cpsidt=23638047
    [10] Fréchet M M. Sur Quelques Points du Calcul Fonctionnel[J]. Rendiconti del Circolo Matematico di Palermo(1884-1940), 1996, 22(1):1-72 http://www.oalib.com/references/14078099
    [11] Alt H, Godau M. Computing the Fréchet Distance Between two Polygonal Curves[J]. International Journal of Computational Geometry & Applications, 1995, 5(01n02):75-91 http://www.doc88.com/p-9049470981059.html
    [12] Samal A, Seth S, Cueto K. A Feature-Based Approach to Conflation of Geospatial Sources[J]. International Journal of Geographical Information Science, 2004, 18(5):459-489 doi:  10.1080/13658810410001658076
    [13] 张桥平. 地图数据库实体匹配与合并技术研究[D]. 武汉: 武汉大学, 2002

    Zhang Qiaoping. Areal Feature Matching and Conflation Among Geographic Databases[D]: Wuhan: Wuhan University, 2002
    [14] 罗国玮, 张新长, 齐立新, 等.矢量数据变化对象的快速定位与最优组合匹配方法[J].测绘学报, 2014, 43(12):1285-1292 doi:  10.13485/j.cnki.11-2089.2014.0191.html

    Luo Guowei, Zhang Xinchang, Qi Lixin, et al. The Fast Positioning and Optimal Combination Matching Method of Change Vector Object[J]. Acta Geodaeticaet Cartographica Sinica, 2014, 43(12):1285-1292 doi:  10.13485/j.cnki.11-2089.2014.0191.html
    [15] Schuessler N, Axhausen K W. Map-Matching of GPS Traces on High-Resolution Navigation Networks Using the Multiple Hypothesis Technique (MHT)[J]. 2009 doi:  10.1007/978-3-319-49466-1_2/fulltext.html
    [16] Guibas L J, Hershberger J E, Mitchell J S B, et al. Approximating Polygons and Subdivisions with Minimum-link Paths[J]. International Journal of Computational Geometry & Applications, 1993, 3(4):383-415 doi:  10.1007%2F3-540-54945-5_59.pdf
    [17] Saalfeld A. Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm[J]. Cartography and Geographic Information Science, 1999, 26(1):7-18 doi:  10.1559/152304099782424901
    [18] Rote G. Computing the Fréchet Distance Between Piecewise Smooth Curves[J]. Computational Geometry, 2007, 37(3):162-174 doi:  10.1016/j.comgeo.2005.01.004
  • [1] 方文江, 李精忠.  一种基于形状上下文特征匹配的线状要素Morphing方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 963-967. doi: 10.13203/j.whugis20150674
    [2] 高孝杰, 简季, 戴晓爱, 陈婉佳.  基于Fréchet距离的光谱曲线匹配应用分析 . 武汉大学学报 ● 信息科学版, 2016, 41(3): 408-414. doi: 10.13203/j.whugis20140147
    [3] 安晓亚, 刘平芝, 杨 云, 侯溯源.  一种线状要素几何相似性度量方法及其应用 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1225-1229. doi: 10.13203/j .whu g is20130495
    [4] 许俊奎, 武芳, 钱海忠, 马芳博.  一种空间关系相似性约束的居民地匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 484-485.
    [5] 罗安, 王艳东, 龚健雅.  顾及上下文的空间信息服务组合语义匹配方法 . 武汉大学学报 ● 信息科学版, 2011, 36(3): 368-372.
    [6] 赵彬彬, 邓敏, 徐震, 刘慧敏.  多尺度地图面目标匹配的统一规则研究 . 武汉大学学报 ● 信息科学版, 2011, 36(8): 991-994.
    [7] 冯其强, 李宗春, 陈新, 李广云.  基于核面约束的近景摄影测量影像人工标志点匹配方法 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 979-982.
    [8] 邓敏, 徐凯, 赵彬彬, 徐锐.  基于结构化空间关系信息的结点层次匹配方法 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 913-916.
    [9] 应申, 李霖, 刘万增, 王红.  版本数据库中基于目标匹配的变化信息提取与数据更新 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 752-755.
    [10] 纪松, 范大昭, 张永生, 杨靖宇.  多视匹配MVLL算法及其在ADS40线阵影像中的运用 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 28-31.
    [11] 章莉萍, 郭庆胜, 孙艳.  相邻比例尺地形图之间居民地要素匹配方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(6): 604-607.
    [12] 余瑞星, 朱冰, 张科, 吕梅柏.  基于小波的ICM不变特征在图像匹配识别中的应用 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1225-1228.
    [13] 陈军, 胡云岗, 赵仁亮, 李志林.  道路数据缩编更新的自动综合方法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(11): 1022-1027.
    [14] 张鹏林, 关泽群, 王新洲.  时间序列影像特征点提取与匹配算法研究 . 武汉大学学报 ● 信息科学版, 2004, 29(4): 329-332.
    [15] 周焰, 李德仁, 徐长勇.  一种基于区域分割的三角划分方法 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 227-232.
    [16] 李德仁, 郭丙轩, 王密, 雷霆.  基于GPS与GIS集成的车辆导航系统设计与实现 . 武汉大学学报 ● 信息科学版, 2000, 25(3): 208-211.
    [17] 王密, 郭丙轩, 雷霆, 李德仁.  车载GPS导航系统中GPS定位与道路匹配方法研究 . 武汉大学学报 ● 信息科学版, 2000, 25(3): 248-251.
    [18] 时晓燕.  非地形要素与DTM叠加的方法初探 . 武汉大学学报 ● 信息科学版, 1989, 14(3): 68-76.
    [19] 张祖勋.  新的核线相关算法——跨接法 . 武汉大学学报 ● 信息科学版, 1988, 13(4): 19-27.
    [20] 张剑清.  基于特征的最小二乘匹配理论精度 . 武汉大学学报 ● 信息科学版, 1988, 13(4): 82-90.
  • 加载中
图(7) / 表(1)
计量
  • 文章访问数:  956
  • HTML全文浏览量:  110
  • PDF下载量:  321
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-07-20
  • 刊出日期:  2018-04-05

一种基于Fréchet距离的复杂线状要素匹配方法

doi: 10.13203/j.whugis20150677
    基金项目:

    用地网络化综合监管信息平台建设及应用示范 2013BAJ05B02-1

    作者简介:

    邵世维, 博士, 高级工程师, 主要从事空间数据库更新中不一致性处理的理论与方法研究。shaoshiwei@163.com

    通讯作者: 刘辉, 硕士。liuhuiwhu@126.com
  • 中图分类号: P208

摘要: 在不同空间数据集中,同名实体往往有不同的空间表现形式,识别多源异构数据集中的同名实体是空间数据集成和应用的关键。集成不同来源的空间数据是提高GIS数据质量的重要方法,识别同名实体是数据集成和分析的先决条件。根据线要素的形状将其分为简单线要素和复杂线要素,针对现有复杂线要素匹配方法中的不足,提出了Fréchet距离的复杂线状要素匹配方法。该方法首先通过曲线要素的几何和拓扑特性获取候选匹配集,然后结合基于Fréchet距离和要素简化方法实现要素的简化。最后提出基于Fréchet距离的要素匹配改进方法,通过引入简化要素的三元组信息来存储简化后的复杂线要素的属性信息,再根据三元组信息选取要素间的匹配对,完成对不同类型匹配对的检测,实现复杂线状要素匹配。试验结果表明,该匹配方法能有效解决复杂线要素的匹配问题,并能够识别1:0、1:NM:N匹配。

English Abstract

邵世维, 刘辉, 肖立霞, 王恒. 一种基于Fréchet距离的复杂线状要素匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
引用本文: 邵世维, 刘辉, 肖立霞, 王恒. 一种基于Fréchet距离的复杂线状要素匹配方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
SHAO Shiwei, LIU Hui, XIAO Lixia, WANG Heng. A Complex Linear Feature of Fréchet Distance Matching Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
Citation: SHAO Shiwei, LIU Hui, XIAO Lixia, WANG Heng. A Complex Linear Feature of Fréchet Distance Matching Method[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 516-521. doi: 10.13203/j.whugis20150677
  • 随着空间信息获取与处理技术的快速发展,多源、多精度、多时相和多尺度空间信息的交换、融合成为一种发展趋势[1]。要素匹配是通过分析探测空间实体间的差异性和相似性,识别多源异构数据集中同名实体的方法[2, 3]。进行要素匹配有利于多源异构数据的集成、更新与共享,提高数据的精度与质量[2, 4]

    目前,线要素的匹配主要通过几何、拓扑或语义相似度来识别,通过空间距离来进行要素匹配是常用的方式[1, 2, 5, 6]。基于空间距离的匹配方法主要有Hausdorff距离和Fréchet距离等。文献通过Hausdorff距离度量要素中点集间的相似度,并与概率模型相结合,计算对象间的匹配指标,能较好地识别要素间1:NM:N的匹配情况。由于Hausdorff距离对形状及异常点非常敏感,很难适用于曲线要素的相似度计算[6, 8, 9]

    为了度量曲线间的相似度,文献提出了Fréchet距离, 并给出了连续Fréchet距离的计算方法。在此基础上,文献[9]通过构建Fréchet距离的自由空间图表和查找要素间的路径,实现了浮动车轨迹和道路网的匹配;但仅能识别要素间1:1的匹配情况,并且不能识别由浮动车数据精度引起的1:NM:N的匹配情况。文献[8]提出平均Fréchet距离来度量线要素间的相似性,能较好识别离散要素间1:1的匹配情况[6],但平均Fréchet距离易受要素点的分布和采样精度的影响,因此不适合连续线要素度量。

    现有文献中线要素匹配的研究[1, 2, 12]主要针对城市路网或GPS轨迹等简单线要素,无法匹配如城市水系、边界等复杂线要素。复杂线要素的匹配需要考虑要素的连续性和形状等特征[5],通常存在如图 1所示含多个结点和曲线段, 具有多变的曲率和复杂的拓扑关系(与自身相交、相接或重叠)存在封闭的区域等特点。

    图  1  复杂线的几种特征

    Figure 1.  Several Characteristics of Complex Line

    基于上述复杂线要素特征,本文提出了一种基于Fréchet距离的复杂线要素匹配的改进方法。首先,获取潜在的匹配对象,缩小要素搜索范围;然后,简化候选匹配集中的复杂线状要素,并用三元组记录其属性信息;在计算Fréchet距离的基础上,根据三元组信息选取匹配对,识别要素的实际匹配情况。

    • Fréchet距离是用于表达曲线和表面自然距离的函数[10, 13], 也是考虑曲线的连续性和点的顺序的相似度度量[7, 10, 14]。设两条曲线f:I=[lI, rI]→R2g:J=[lJ, rJ]→R2,‖.‖代表欧几里德范数[4, 7],则有Fréchet距离δF(f, g)定义为[3, 11]

      $$ {\delta _F}(\mathit{f, g}) = \{ (\mathit{s, t}) \in \mathit{I} \cdot J\left\| {f(\mathit{s})-\mathit{g}{\rm{(}}\mathit{t}{\rm{)}}\left\| { \le \varepsilon } \right.} \right.\} $$ (1)

      由此,Fréchet距离的匹配问题可以转化为在给定的参数ε下,基于曲线间的Fréchet距离构建自由空间图表,通过判定曲线的Fréchet距离是否大于参数,在自由空间图表中来搜寻可行路径的过程。文献[11]已经证明当且仅当在自由空间表中存在一条从左下角到右上角的单调曲线,若有δF(f, g) < ε,则两条曲线是匹配的。

    • 本文提出的基于Fréchet距离的匹配方法算法流程包括3个部分:①数据预处理;②获取和简化候选匹配集;③匹配对的选取。具体如图 2所示。

      图  2  基于Fréchet距离的匹配方法

      Figure 2.  Matching Method Based on Fréchet Distance

    • 候选匹配集是通过拓扑分析或几何方法[15]获取潜在的匹配集,在一定程度上有助于解决漏匹配和过匹配等问题[6]

      因此,本文以邻近结点为基础,用几何方法搜索待匹配数据集,并结合拓扑分析方法,获取最终候选匹配集。通过考虑结点间连通性和弧段结点间的拓扑关系,可以剔除异常要素对匹配。这不仅能降低异常要素对匹配结果的影响,还能保证复杂要素间的拓扑一致性。在候选匹配集内搜索同名实体,能避免全局搜索导致的匹配效率下降等问题。

    • 要素简化是制图综合的重要内容,可以在满足地图表达的前提下,保留重要的空间信息[16]。要素简化有利于降低存储量[11, 17],是匹配初始化的关键部分。通过采用Fréchet距离简化候选匹配集中的要素,得到简化后的要素集和简化要素的三元组信息,以(obji, attrj, leni)的信息存储信息,其中obji表示第i个要素,attrj为第i个要素的第j个分割段的属性,leni为第i个要素的长度。

      本文基于Fréchet距离对线要素进行简化,首先根据式(1)计算要素集的Fréchet距离,然后基于计算的Fréchet距离和阈值简化给定的要素。如给定曲线P=〈p1, p2, …, pn〉,简化后曲线为P′,阈值ε>0。设定P的初始点p1P′的初始始点〈$\mathop {{p_1}}\limits^ \gg $=p1〉,以p1为起点遍历P寻找下一点,计算P中各点到起点的Fréchet距离,寻找最小索引值j,使得δF(p1, pj)≤εδF(p1, pj+1)>ε,则将pj加入到p′中,由文献[18]可知,基于Fréchet距离的曲线简化的时间复杂度为ο(ij+1ij);然后,以pj为起点,重复以上步骤直到曲线P中最后一个顶点,完成对曲线P的搜索,并将P′集合作为曲线P的简化结果[18]

      本文从简化效果、阈值和时间复杂度等方面比较了该简化方法与DP(Douglas-Peucker)算法[17]的性能。图 3是基于Fréchet距离简化与DP算法的简化结果。以u1为阈值,图 3左侧是采用基于Fréchet距离对曲线fg的简化结果;图 3右侧是采用DP算法对曲线fg的简化结果。由图 3可知,本文方法能较好地保持曲线的整体形状和顺序,简化效果较好,而采用DP算法得到的简化曲线有严重的形变,失真度大。图 4是阈值与运行时间的关系图。由图 4可知,前者受阈值的影响小,性能稳定,而后者受阈值影响较大;从时间复杂度而言,前者时间复杂度随阈值变化近似为线性,而后者近似为指数关系,并且前者所用时间始终小于后者。

      图  3  基于Fréchet距离简化与Douglas-Peucker算法的简化结果

      Figure 3.  Simplification of Curves Based on Fréchet Distance and Douglas-Pecuker Algorithm

      图  4  在不同阈值下, 基于Fréchet的简化方法和Douglas-Peucker算法的比较

      Figure 4.  Comparing Running Times of Fréchet Simplification and Douglas-Pecuker Algorithm for Different Thresholds

    • 为了确定复杂线要素间的匹配关系,本文采用如下方法选取匹配对,以克服误匹配和漏匹配的现象。

      1) 计算Fréchet距离相似度。设定阈值ε值,依式(2)计算简化后要素间Fréchet距离,并构建自由空间图表v

      2) 选择匹配对。在自由空间图表v中,根据候选匹配集中“结点-弧段”的拓扑关系,构建有向图G,其中格网c(i, j)表示节点v(i, j)。在限制结点v(i, j)朝v(i+1, j)和v(i, j+1)两个方向搜索的条件下,采用广度优先搜索方法从v的左下角朝右上角迭代搜索,判断是否存在可行的路径保证δF(f′, g′) < ε

      3) 检测1:0、1:NM:N等匹配情况。根据三元组判定曲线的属性信息和长度信息,判定匹配对的匹配情况,分以下几种情况。①如果简化后曲线f′的长度大于曲线g′的长度,判定是否存在路径使f′和g′匹配,若存在,若f′的弧段数>1且g′的弧段数=1,则会存在1:N的匹配对;②若f′的弧段数>1且g′的弧段数>1,则会存在部分-整体的匹配情况;③如f′的长度近似等于g′的长度,则可能存在1:1的匹配对;④如果f′与g′间不存在可行的路径,则二者不匹配;⑤曲线f′与候选匹配集中要素间都不存在可行的路径,则判定为1:0的匹配对。

    • 为了验证本文提出方法的可行性,本文采用两类线状要素数据进行实验,分别为边界线数据和河流水系数据。其中,边界线数据包括1:10 000的湖北省市级边界线(数据集A)和1:2 000的湖北省地级边界线(数据集B),河流水系数据包括2010年武汉市测绘成果中的水系数据(数据集A′)和2014年遥感影像解译的水系数据(数据集B′)。首先利用FME软件对匹配数据集进行了统一格式转换、拓扑一致性检查、全局坐标转换和属性检查等处理,消除因数据源带来的系统误差。采用Microsoft Visual Studio 2010(C#)+ArcGIS Engine 10.1实现本文算法。

    • 1) 匹配情况分析

      根据本文提出的匹配方法,对轮廓线数据和水系数据进行了匹配实验。部分实验结果如图 5~7所示,图 5表示边界线数据的实验结果,黑虚线为湖北省市级边界线,灰实线为湖北省地级边界线,图 6图 7表示水系数据的实验结果,黑虚线为2010年测绘成果中的数据,灰实线为2014年遥感影像解译的水系数据。由图 5可知,边界线数据线形是曲线,曲率多变,本文方法能有效克服这种特性带来的影响;图 5(c)是本文方法识别的匹配情况之一。河流水系数曲线段,拓扑关系复杂,图 6图 7说明本文方法能较好识别河流水系数据集中M:N和1:0的匹配情况。

      图  5  边界线目标的匹配

      Figure 5.  Matching Case of Border Target

      图  6  河流线目标的匹配

      Figure 6.  Matching Case of River Target

      图  7  正确识别1:0的匹配情况

      Figure 7.  Correctly Identification of 1:0 Matching Case

      匹配结果表明,本文方法基于三元组综合考虑“结点-结点”、“结点-弧段”间匹配关系和Fréchet距离,能有效识别要素间1:NM:N和1:0的匹配关系。图 5(c)是从边界线数据中选取的正例之一,为1:N的匹配情况;文献[9]由于未考虑要素间结点关系和属性特征,将其匹配为1:1,导致了漏匹配的现象。图 6(b)图 7是河流水系数据集中选取的正例,是M:N和1:0的匹配情况。

      图 6(c)中,河流水系出现分支与河流时,Hausdorff距离HD=50.45 m小于阈值55 m,因此两个数据集被看作匹配对;但本文方法计算的Fréchet距离FD=62.29 m大于阈值,在构建的自由空间图表中无法找到有效的路径,因此两个数据集不匹配。图 7表明在河流水系中出现水系消失或新水系出现时,文献[2]方法根据概率值大于0.5,会将待匹配要素匹配到邻近要素导致误匹配。本文方法在简化候选匹配集的基础上,根据三元组信息会识别为1:0的匹配情况。由此可见,根据简化复杂线要素及其三元组信息,采用基于Fréchet距离的匹配方法能有效解决复杂线要素匹配中无法识别的多种匹配关系,如1:NM:N

      2) 算法比较

      本文采用人工检查的方法获取了实验数据集中所有的匹配情况,并将实际匹配结果作为评价基础。表 1统计了3种匹配方法(文献[9],文献[2]和本文方法)得到的正确匹配数、错误匹配数和漏匹配数、准确率和回召率,其中文献[9]为基于Fréchet距离的匹配方法,文献[2]为基于改进的Hausdorff距离的概率匹配方法。本文用f(C)表示正确的匹配数;f(W)表示错误的匹配数;f(U)表示漏匹配数,P表示准确率,R表示回召率[2, 4, 9]。3种匹配结果的比较见表 1

      表 1  三种匹配方法的比较

      Table 1.  Matching Results of the Three Matching Methods in the Test Area

      匹配方法 边界线数据集 河流数据集
      f(C) f(W) f(U) P/(%) R/(%) f(C) f(W) f(U) P/(%) R/(%)
      文献[2] 102 48 15 68.0 87.1 123 58 30 67.7 80.3
      文献[9] 110 42 18 72.4 85.9 118 63 34 65.2 77.6
      本文 127 22 15 85.0 89.4 155 20 22 88.6 87.5

      表 1可知,对于边界线和河流数据集,相比于文献[2, 9]中方法,本文方法的准确率和回召率都是最高的,正确匹配数也最高;本文方法的错误匹配数分别为22和20,而文献[2, 9]方法的错误匹配数都大于40,这表明本文更适于匹配复杂线要素集,能减少漏匹配和误匹配的情况。究其原因,是因为本文方法在简化要素后采用三元组记录属性信息,考虑要素间拓扑一致性,从整体优化角度降低了错误匹配数,进而提高匹配的准确率。

    • 本文主要探讨了基于Fréchet距离的复杂线状要素的匹配方法,研究了基于拓扑关系的候选匹配集的获取方式和线状要素的简化方法,设计了复杂线状要素的匹配方法,在保证复杂线要素特性的基础上,实现了边界线和河流水系等要素的匹配。实验结果表明,该方法对复杂的曲线要素具有较高的匹配精度,并能识别1:0、1:NM:N的匹配关系,能有效实现不同比例尺之间的边界线要素和不同时期内的河流水系要素的匹配,为复杂线状数据的融合提供了可行的解决方法。下一步研究会侧重于匹配效率的提高和扩展到多维度的对象匹配情况,如含有“岛”的多边形以及三维物体的匹配。

参考文献 (18)

目录

    /

    返回文章
    返回