留言板

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

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

线要素化简及参数自动设置的案例推理方法

何海威 钱海忠 段佩祥 谢丽敏 罗登瀚

何海威, 钱海忠, 段佩祥, 谢丽敏, 罗登瀚. 线要素化简及参数自动设置的案例推理方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
引用本文: 何海威, 钱海忠, 段佩祥, 谢丽敏, 罗登瀚. 线要素化简及参数自动设置的案例推理方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
HE Haiwei, QIAN Haizhong, DUAN Peixiang, XIE Limin, LUO Denghan. Automatic Line Simplification Algorithm Selecting and Parameter Setting Based on Case-Based Reasoning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
Citation: HE Haiwei, QIAN Haizhong, DUAN Peixiang, XIE Limin, LUO Denghan. Automatic Line Simplification Algorithm Selecting and Parameter Setting Based on Case-Based Reasoning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250

线要素化简及参数自动设置的案例推理方法

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

国家自然科学基金 41571442

国家自然科学基金 41171305

详细信息
    作者简介:

    何海威, 博士生, 主要从事空间数据自动综合方法研究。adai928@126.com

    通讯作者: 钱海忠, 博士, 教授。haizhongqian@163.com
  • 中图分类号: P208

Automatic Line Simplification Algorithm Selecting and Parameter Setting Based on Case-Based Reasoning

Funds: 

The National Natural Science Foundation of China 41571442

The National Natural Science Foundation of China 41171305

More Information
    Author Bio:

    HE Haiwei, PhD candidate, specializes in spatial data auto‑generalization. E-mail: adai928@126.com

    Corresponding author: QIAN Haizhong, PhD, professor. E-mail: haizhongqian@163.com
  • 摘要: 目前,线要素化简的人机协同机制研究得较少,化简算法的选择以及参数设置依赖于人工反复修正,影响了算法的易用性。针对该问题,提出了通过案例进行类比推理得到线要素化简算法及参数的寻优方法。该方法采用案例推理(case-based reasoning,CBR)思想,计算机参考专家化简案例,通过相似性评价指标和参数寻优策略对参数候选集进行类比推理,自动筛选出与案例同一类区域和比例尺下的线要素化简算法及参数的最佳设置,从而省去制图员不断试错的繁琐过程。实验结果表明,该方法能够自动得到算法和参数的最优组合,化简结果与已有成果数据吻合度较高,能够有效地提高参数设置的效率和准确性,降低化简算法工具的使用难度。
  • 图  1  基于人工判断的算法选择及其参数设置

    Figure  1.  Algorithm Selection and Parameter Setting Based on Artificial Judgment

    图  2  基于CBR的算法及其参数设置

    Figure  2.  Line Simplification Algorithm and Its Parameter Setting Using CBR

    图  3  一组专家化简案例数据示例

    Figure  3.  Example of Line Elements in a Simplification Case

    图  4  线要素化简案例自动获取示意图

    Figure  4.  Automatic Acquisition of a Line Simplification Case

    图  5  缓冲区限差评价效果示例

    Figure  5.  Example of Buffer Zone Coverage

    图  6  Li-Openshaw化简效果随阈值变化示例

    Figure  6.  Example of Li-Openshaw Simplification Result Changing with Threshold

    图  7  各指标相似性变化曲线及最优化简效果

    Figure  7.  Similarity Curves and Optimization Results of All Indicators

    图  8  3种算法的最大阈值计算

    Figure  8.  Maximum Threshold Calculation of Three Algorithms

    图  9  算法和参数寻优计算流程

    Figure  9.  Algorithm and Parameter Optimization Calculation Process

    图  10  实验数据及测试区域示意图

    Figure  10.  Test Data and Test Area Schematic Diagram

    图  11  3种算法类比寻优得到的最优阈值分布

    Figure  11.  Distribution of Different Thresholds of Three Simplification Methods

    图  12  本文测试区域化简结果与1:25万数据对比

    Figure  12.  Comparison of Result of CBR Algorithm and Data in Scale of 1:250 000

    图  13  本文方法与最小可视距离计算化简程度对比

    Figure  13.  Results Comparison Between Our Method and the Minimum Visual Distance Calculation

    表  1  实验类比推理寻优结果统计值

    Table  1.   Statistics Result of the Experiment

    化简算法 阈值平均值T 相似度平均值S 变异系数C 综合系数E
    D-P算法 34.64 m 0.845 0.497 0.425
    Li-Openshaw 120.27 m 0.882 0.269 0.645
    弯曲组算法 4 481.02 m2 0.860 0.654 0.298
    下载: 导出CSV

    表  2  化简前后平均相似性指标统计

    Table  2.   Statistics of Average Similarity Index

    指标名称 化简前 CBR化简 最小可视距离化简
    相似度 0.545 0.801 0.653
    下载: 导出CSV
  • [1] 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]. The Canadian Cartographer, 1973, 10(2):112-122 doi:  10.3138/FM57-6770-U75U-7727
    [2] Li Zhilin, Openshaw S.Algorithms for Line Generalization Based on Natural Objective Principles[J]. International Journal of Geographic Information Systems, 1992, 6(5):373-389 doi:  10.1080/02693799208901921
    [3] 钱海忠, 何海威, 王骁, 等.采用三元弯曲组划分的线要素化简方法[J].武汉大学学报·信息科学版, 2017, 42(8):1096-1103 http://ch.whu.edu.cn/CN/abstract/abstract5802.shtml

    Qian Haizhong, He Haiwei, Wang Xiao, et al. Line Feature Simplification Method Based on Bend Group Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8):1096-1103 http://ch.whu.edu.cn/CN/abstract/abstract5802.shtml
    [4] 王家耀.关于数字地图制图综合中的人机协同问题[J].测绘科学技术学报, 1999, 16(2):121-124 http://www.cnki.com.cn/Article/CJFDTotal-JFJC199902013.htm

    Wang Jiayao. Problems on Coordination Between Human and Computer in Digital Map Generalization[J]. Journal of Geomatics Science and Technology, 1999, 16(2):121-124 http://www.cnki.com.cn/Article/CJFDTotal-JFJC199902013.htm
    [5] 江南, 白小双, 曹亚妮, 等.基础电子地图多尺度显示模型的建立与应用[J].武汉大学学报·信息科学版, 2010, 35(7):768-772 http://ch.whu.edu.cn/CN/abstract/abstract982.shtml

    Jiang Nan, Bai Xiaoshuang, Cao Yani, et al. Establishment and Application of Multi-scale Display Model in Basic Electronic Map[J]. Geomatics and Information Science of Wuhan University, 2010, 35(7):768-772 http://ch.whu.edu.cn/CN/abstract/abstract982.shtml
    [6] 王家耀, 李志林, 武芳.数字地图综合进展[M].北京:科学出版社, 2011

    Wang Jiayao, Li Zhilin, Wu Fang.Advances in Digital Map Generalization[M].Beijing:Science Press, 2011
    [7] 谢丽敏, 钱海忠, 何海威, 等.基于CBR的居民地选取方法[J].测绘学报, 2017, 46(11):1910-1918 doi:  10.11947/j.AGCS.2017.20170061

    Xie Limin, Qian Haizhong, He Haiwei, et al. A Habitation Selection Method by Using Case-Based Reasoning[J].Acta Geodaetica et Cartographica Sinica, 2017, 46(11):1910-1918 doi:  10.11947/j.AGCS.2017.20170061
    [8] 郭敏, 钱海忠, 黄智深, 等.采用案例类比推理进行道路网智能选取[J].测绘学报, 2014, 43(7):761-770

    Guo Min, Qian Haizhong, Huang Zhishen, et al. Intelligent Road Network Selection Using Cases Based Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(7):761-770
    [9] Kolodner J L. An Introduction to Case-Based Reasoning[J]. Artificial Intelligence Review, 1992, 6(1):3-34 doi:  10.1007-BF00155578/
    [10] Weibel R, Keller S, Reichenbacher T. Overcoming the Knowledge Acquisition Bottleneck in Map Generalization: The Role of Interactive Systems and Computational Intelligence[M]. Spatial Information Theory: A Theoretical Basis for GIS. Berlin, Heidelberg: Springer, 1995
    [11] 何海威, 钱海忠, 谢丽敏, 等. CBR的制图综合应用背景与方法[J].测绘科学技术学报, 2017, 34(4):427-432

    He Haiwei, Qian Haizhong, Xie Limin, et al. Application Background and Method of Case Based Reasoning in Cartographic Generalization[J]. Journal of Geomatics Science and Technology, 2017, 34(4):427-432
    [12] 刘鹏程, 罗静, 艾廷华, 等.基于线要素综合的形状相似性评价模型[J].武汉大学学报·信息科学版, 2012, 37(1):114-117 http://ch.whu.edu.cn/CN/abstract/abstract102.shtml

    Liu Pengcheng, Luo Jing, Ai Tinghua, et al. Evaluation Model for Similarity Based on Curve Generalization[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1):114-117 http://ch.whu.edu.cn/CN/abstract/abstract102.shtml
    [13] 黄博华, 武芳, 许俊奎, 等.一种面向同名线要素的距离度量方法[J].武汉大学学报·信息科学版, 2017, 42(3):395-401 http://ch.whu.edu.cn/CN/abstract/abstract5692.shtml

    Huang Bohua, Wu Fang, Xu Junkui, et al.A Method of Distance Measurement for Corresponding Linear Feature[J]. Geomatics and Information Science of Wuhan University, 2017, 42(3):395-401 http://ch.whu.edu.cn/CN/abstract/abstract5692.shtml
    [14] Yan Haowen.Fundamental Theories of Spatial Similarity Relations in Multi-scale Map Spaces[J]. Chinese Geographical Science, 2010, 20(1):18-22 doi:  10.1007/s11769-010-0018-z
    [15] 安晓亚, 孙群, 尉伯虎.利用相似性度量的不同比例尺地图数据网状要素匹配方法[J].武汉大学学报·信息科学版, 2012, 37(2):224-228 http://ch.whu.edu.cn/CN/abstract/abstract118.shtml

    An Xiaoya, Sun Qun, Wei Bohu. Feature Matching from Network Data at Different Scales Based on Similarity Measure[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2):224-228 http://ch.whu.edu.cn/CN/abstract/abstract118.shtml
    [16] 付仲良, 邵世维, 童春芽.基于正切空间的多尺度面实体形状匹配[J].计算机工程, 2010, 36(17):216-217 http://d.old.wanfangdata.com.cn/Periodical/jsjgc201017073

    Fu Zhongliang, Shao Shiwei, Tong Chunya. Multi-scale Area Entity Shape Matching Based on Tangent Space[J]. Computer Engineering, 2010, 36(17):216-217 http://d.old.wanfangdata.com.cn/Periodical/jsjgc201017073
    [17] 唐炉亮, 杨必胜, 徐开明.基于线状图形相似性的道路数据变化检测[J].武汉大学学报·信息科学版, 2008, 33(4):367-370 http://ch.whu.edu.cn/CN/abstract/abstract1506.shtml

    Tang Luliang, Yang Bisheng, Xu Kaiming. The Road Data Change Detection Based on Linear Shape Similarity[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4):367-370 http://ch.whu.edu.cn/CN/abstract/abstract1506.shtml
    [18] 刘慧敏, 邓敏, 徐震, 等.线要素几何信息量度量方法[J].武汉大学学报·信息科学版, 2014, 39(4):500-504 http://ch.whu.edu.cn/CN/abstract/abstract2970.shtml

    Liu Huimin, Deng Min, Xu Zhen, et al. Geometric Information Content Measurement of Individual Line Feature[J]. Geomatics and Information Science of Wuhan University, 2014, 39(4):500-504 http://ch.whu.edu.cn/CN/abstract/abstract2970.shtml
    [19] 武芳, 朱鲲鹏.线要素化简算法几何精度评估[J].武汉大学学报·信息科学版, 2008, 33(6):600-603 http://ch.whu.edu.cn/CN/abstract/abstract1621.shtml

    Wu Fang, Zhu Kunpeng. Geometric Accuracy Assessment of Linear Features' Simplification Algorithms[J]. Geomatics and Information Science of Wuhan University, 2008, 33(6):600-603 http://ch.whu.edu.cn/CN/abstract/abstract1621.shtml
    [20] 陈竞男, 钱海忠, 王骁, 等.提高线要素匹配率的动态化简方法[J].测绘学报, 2016, 45(4):486-493 http://d.old.wanfangdata.com.cn/Periodical/chxb201604014

    Chen Jingnan, Qian Haizhong, Wang Xiao, et al. Improving the Matching Rate of Line Feature Using Dynamic Simplification[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):486-493 http://d.old.wanfangdata.com.cn/Periodical/chxb201604014
  • [1] 李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星.  Delaunay三角网支持下的海图等深线化简 . 武汉大学学报 ● 信息科学版, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
    [2] 谢天, 李精忠, 陈凯.  顾及线状要素综合要求的Morphing算法 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 792-797. doi: 10.13203/j.whugis20150513
    [3] 江净超, 余洁, 秦承志, 刘军志, 李润奎, 朱良君, 朱阿兴.  知识驱动下的水文模型参数智能化设置方法 . 武汉大学学报 ● 信息科学版, 2017, 42(4): 525-530. doi: 10.13203/j.whugis20150044
    [4] 钱海忠, 何海威, 王骁, 胡慧明, 刘闯.  采用三元弯曲组划分的线要素化简方法 . 武汉大学学报 ● 信息科学版, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
    [5] 巩现勇, 武芳, 钱海忠, 马克楠.  建筑群多连通直线模式的参数识别方法 . 武汉大学学报 ● 信息科学版, 2014, 39(3): 335-339. doi: 10.13203/j.whugis20120708
    [6] 潘东华, 王静爱, 贾慧聪, 赵金涛.  自然灾害风险地图中的制图综合研究——以点状承灾体为例 . 武汉大学学报 ● 信息科学版, 2011, 36(1): 51-55.
    [7] 董卫华, 李志林, 郭庆胜.  基于动态分段的道路网示意性地图模型综合 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 892-895.
    [8] 黄丽娜, 费立凡.  采用3D D-P算法的等高线三维综合实验研究 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 55-58.
    [9] 宋鹰, 何宗宜.  基于粒计算的制图综合知识获取模型研究 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 748-751.
    [10] 王家耀, 邓红艳.  基于遗传算法的制图综合模型研究 . 武汉大学学报 ● 信息科学版, 2005, 30(7): 565-569.
    [11] 李雯静, 毋河海.  地图目标在制图综合中的分形衰减机理研究 . 武汉大学学报 ● 信息科学版, 2005, 30(4): 309-312.
    [12] 费立凡.  用计算机模拟人类制图员解决地图缩编中的图形冲突 . 武汉大学学报 ● 信息科学版, 2004, 29(5): 426-432. doi: 10.13203/j.whugis2004.05.012
    [13] 应申, 李霖.  基于约束点的曲线一致性化简 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 488-491.
    [14] 何宗宜, 阮依香, 尹为利, 陈涛.  基于分形理论的水系要素制图综合研究 . 武汉大学学报 ● 信息科学版, 2002, 27(4): 427-431.
    [15] 王桥.  数字环境下制图综合若干问题的探讨 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 208-213.
    [16] 郭庆胜, 费立凡.  等高线的树结构模型 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 44-46.
    [17] 郭庆胜.  点状要素与线状、面状要素的关系处理 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 68-71.
    [18] 郭庆胜.  线状要素与面状要素的关系处理 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 72-74.
    [19] 张克权, 祝国瑞.  试论地图制图学的理论体系 . 武汉大学学报 ● 信息科学版, 1990, 15(2): 28-33.
    [20] 张文星.  制图综合专家系统MAPGEN中多种语言工具的结合 . 武汉大学学报 ● 信息科学版, 1988, 13(2): 86-94.
  • 加载中
图(13) / 表(2)
计量
  • 文章访问数:  860
  • HTML全文浏览量:  112
  • PDF下载量:  91
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-04-07
  • 刊出日期:  2020-03-05

线要素化简及参数自动设置的案例推理方法

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

    国家自然科学基金 41571442

    国家自然科学基金 41171305

    作者简介:

    何海威, 博士生, 主要从事空间数据自动综合方法研究。adai928@126.com

    通讯作者: 钱海忠, 博士, 教授。haizhongqian@163.com
  • 中图分类号: P208

摘要: 目前,线要素化简的人机协同机制研究得较少,化简算法的选择以及参数设置依赖于人工反复修正,影响了算法的易用性。针对该问题,提出了通过案例进行类比推理得到线要素化简算法及参数的寻优方法。该方法采用案例推理(case-based reasoning,CBR)思想,计算机参考专家化简案例,通过相似性评价指标和参数寻优策略对参数候选集进行类比推理,自动筛选出与案例同一类区域和比例尺下的线要素化简算法及参数的最佳设置,从而省去制图员不断试错的繁琐过程。实验结果表明,该方法能够自动得到算法和参数的最优组合,化简结果与已有成果数据吻合度较高,能够有效地提高参数设置的效率和准确性,降低化简算法工具的使用难度。

English Abstract

何海威, 钱海忠, 段佩祥, 谢丽敏, 罗登瀚. 线要素化简及参数自动设置的案例推理方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
引用本文: 何海威, 钱海忠, 段佩祥, 谢丽敏, 罗登瀚. 线要素化简及参数自动设置的案例推理方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
HE Haiwei, QIAN Haizhong, DUAN Peixiang, XIE Limin, LUO Denghan. Automatic Line Simplification Algorithm Selecting and Parameter Setting Based on Case-Based Reasoning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
Citation: HE Haiwei, QIAN Haizhong, DUAN Peixiang, XIE Limin, LUO Denghan. Automatic Line Simplification Algorithm Selecting and Parameter Setting Based on Case-Based Reasoning[J]. Geomatics and Information Science of Wuhan University, 2020, 45(3): 344-352. doi: 10.13203/j.whugis20180250
  • 在线要素化简过程中,化简算法的选择以及参数设置往往高度依赖于人工反复修正,其主要过程包括算法选择、参数设置和人工修正3个步骤,如图 1所示。各化简算法所产生的化简效果不尽相同,导致在算法的选择上需要反复比较。例如,Douglas‑Peucker(D‑P)算法在化简阈值较大时易产生锯齿;Li‑Openshaw算法光滑效果十分明显,但对于原有内点的位置精度改变较大;基于弯曲组的线要素化简算法对曲线的基本形态特征保持较好,但不同化简阈值之间的化简效果跳跃性较大[1-3]。为了适应多样化制图的需求,制图员需根据具体情况不断地进行算法和参数的调整,以达到预期的化简效果。

    图  1  基于人工判断的算法选择及其参数设置

    Figure 1.  Algorithm Selection and Parameter Setting Based on Artificial Judgment

    制图员往往不是算法的研究者,对于算法原理的把握存在一定的认知差距,制图员只能通过判断化简结果的好坏不断选择算法和修正参数设置;同样,算法的研究者对于实际生产要求也存在着认知差距,无法事先提供可靠的参数预设。

    目前的制图综合软件对各种算法进行了集成,具备强大的自动综合能力。然而,针对综合算法的使用,即制图综合过程中的人机协同机制研究较少[4]。研究化简算法及其参数的自动设置,单从建模的角度来看,是研究算法的综合程度与比例尺之间的关系。目前,已有不少针对该问题的研究成果,例如经典的开方根模型、等比数列法、最小可视距离、载负量约束等[5-6]。这些指标和模型在制图过程中具备一定的指导意义,然而由于都是采用统一的模型描述,参数理论值与实际值往往存在较大偏差,在实际应用中无法满足不同区域、不同要求下的个性化制图需求。

    根据案例推理(case-based reasoning,CBR)的思想,新的问题可以通过寻找与之相似的历史案例得到参考的解决方案[7-11]。专家人工化简结果即可视为案例,若计算机能够从这些少量的专家化简案例中自动得到线要素化简算法及参数的最优设置,而不是依赖于固定的模型,就能更加快速精确地得到合适的化简程度,从而满足不同区域、不同要求下的个性化制图需求。

    因此,本文提出了线要素化简算法及参数自动设置的案例类比推理方法。该方法采用CBR的思想,将算法化简的结果与专家化简案例进行类比推理,利用算法结果与专家化简案例结果间的相似性指标自动调整算法和参数,最终得到最符合预期化简程度的最优算法和参数组合(当前同一目标比例尺和制图需求下的线要素化简算法及参数的最佳设置),从而省去制图员不断试错的繁琐过程,提高参数设置的效率和准确性,降低化简算法工具的使用难度。

    • 本文提出的采用CBR的线化简算法及参数自动设置方法的原理可以简单概括为:制图员预先进行少量的化简(或者提供少量的化简案例)作为参照,计算机在参数候选集内不断地对同一线要素进行化简,通过相似性评价指标和参数寻优策略实现基于参照案例的类比推理,即自动筛选出与案例化简效果吻合度最高的算法和参数的组合。算法流程如图 2所示,案例的类比推理替代了图 1中人工反复修正参数的过程,并且参数的设置由制图员预先提供化简案例决定,更加符合特定制图任务的需求。

      图  2  基于CBR的算法及其参数设置

      Figure 2.  Line Simplification Algorithm and Its Parameter Setting Using CBR

      实现该方法的3个关键性步骤为:(1)案例的记录(自动获取);(2)面向案例类比推理的化简效果评估;(3)算法及参数的案例类比寻优。

    • 线要素化简案例的定义源于CBR中对于案例的定义。在该方法中,案例的含义是“历史解决方案以及方案所处环境的描述”,CBR的过程即寻找相似历史案例的过程[9]。据此,本文将线要素化简案例定义为相同环境下化简效果的范例数据,包括记录化简环境的元数据、化简前线要素、化简后线要素以及相似性评价函数4个部分。表示如下:

      $$C = < I, O, R, f > $$ (1)

      式中,C表示案例;I表示化简环境的元数据,记录所提供案例的化简环境信息,包括地图用途、制图区域类型、原始比例尺、目标比例尺以及相关专题需求;O={OL1OL2OLm}表示化简前线要素的集合;R={RL1RL2RLm}表示化简后线要素的集合;f表示算法化简结果ALi与案例结果RLi的相似性计算函数,用于评价化简程度是否符合预期。在实际的案例数据管理中,化简案例数据由单个线要素案例组成,其主体是一对化简前后矢量线状要素数据(OLi, RLi),如图 3所示。

      图  3  一组专家化简案例数据示例

      Figure 3.  Example of Line Elements in a Simplification Case

      图 3可以看出,制图员对该线要素上的节点进行了一定程度的取舍,以制图员手动化简结果为参照案例,自动匹配不同算法及参数设置下的最相似化简结果,即可实现将“隐藏化简信息”转化为算法和参数最优设置的目的。

    • 案例必须来源于可靠的综合结果,并且需要多组化简数据作为案例,以计算结果的平均值作为最后的参数寻优结果。本文将线要素化简案例的来源归纳为两种:

      1)由经验丰富的制图员提供化简案例;

      2)调取同一综合环境和制图需求下的成果数据,以小比例尺线要素数据为基准自动获取化简案例。

      其中,方式1)比较简单,利用计算机直接记录制图员的化简操作即可;方式2)能够在短时间内自动获得较多的化简案例,但需要借助同名要素匹配进行案例对象的识别[12],以及根据要素变化情况对识别的案例数据进行预处理。综合前后线要素为同源线要素数据,因此在进行匹配时只需要采用简单的缓冲区匹配算法即可。匹配后的关键步骤是对存在伪节点的线要素进行接链处理。例如,当匹配到多个线要素时需要进行接链处理,将其合并为同一条线要素,如图 4所示。

      图  4  线要素化简案例自动获取示意图

      Figure 4.  Automatic Acquisition of a Line Simplification Case

    • 算法结果ALi与案例结果RLi相似度评价函数f(ALi, RLi)的选择是实现自动求解最优化简算法和参数组合的关键之一。算法及参数设置的目的是使化简程度与制图员预期效果趋于一致。因此,评价指标的选择应考虑两个标准:

      1)“相同化简算法不同阈值”化简结果的纵向比较中,能够区分不同化简程度与案例结果在总体形态上的相似性,以衡量不同阈值化简程度的优劣;

      2)“不同化简算法最优阈值”化简结果的横向比较中,能够区分不同算法结果与案例结果在总体形态的相似性,以衡量不同算法化简结果的优劣。

    • 众多学者针对要素间的相似性度量指标进行了研究,线要素的相似性度量指标主要包括:(1)基于距离的Hausdorff方法;(2)基于形态描述函数的转角函数法;(3)顾及整体形态的缓冲区限差法[13-20]

      由3种评价指标的定义和原理可知,Hausdorff距离和转角函数法能够分别排除同名实体间突变和细节差异的干扰,这对于空间数据融合和更新中的同名实体匹配而言是十分有利的。然而,上文提出的两个标准与本文所要达到的目的正好相反,突变和细节差异是体现化简效果是否达到预期效果的重要方面。差异较大的突变结构和细节表达程度应在面向案例类比推理的相似性评价中起到消极的作用。即存在的突变结构越多或细节表达程度差异越大,则认为化简结果与案例结果的差异性越大,算法和参数设置越不合理;反之差异越小,算法和参数越趋近于最优解。

      相比较而言,缓冲区限差更加符合本文面向案例类比学习的算法化简结果相似性评价,其原理为:线段AB的相似度Sab等于A落在B缓冲区内线段长度LinA线段总长度La的百分比。其计算公式为:

      $${S_{ab}} = \left( {{L_{{\rm{in}}}}/{L_a}} \right) \times 100{\rm{\% }} $$ (2)

      图 5为缓冲区限差法计算的相似性示例,图 5中化简程度一致性较好的曲线有更高的相似性值。根据视觉上对于图上位置偏离的感知程度,缓冲区半径的大小一般设置为目标比例尺图上两个点要素之间最小距离值(0.2 mm)的1~2倍[19-20]

      图  5  缓冲区限差评价效果示例

      Figure 5.  Example of Buffer Zone Coverage

    • 为了更加客观地比较各指标用于化简效果评价的有效性,本文中采用D-P算法、Li-Openshaw算法和弯曲组算法分别对§2.1中3个不同的相似性度量指标进行适用性测试。

      判断评价指标是否适用于本文案例类比推理的关键在于观察指标随化简程度变化的情况。如图 6所示,随着算法阈值的增大,化简结果与案例结果(图 6中的绿色曲线)的相似度变化随着阈值的增大而增大,超过一定阈值后相似度随着过度化简而逐渐减小。这说明评价指标的变化应存在明显峰值,且峰值所对应的化简效果为最佳。

      图  6  Li-Openshaw化简效果随阈值变化示例

      Figure 6.  Example of Li-Openshaw Simplification Result Changing with Threshold

      本文对以上3个评价指标的适用性进行比较,分别测试各指标对3种线化简算法效果的区分能力。

      为直观地进行对比,图 7中采用图表的方式进行展示,并将各评价指标下的最优化简结果(图 7中(1)、(2)、(3)处)与案例结果(RLi)进行了对比。为了方便对比,对3个指标的评价值进行了归一化处理,统一称为相似度S;同时各算法的阈值用其最大化简阈值的百分比代替。由图 7中的对比可以得出:

      图  7  各指标相似性变化曲线及最优化简效果

      Figure 7.  Similarity Curves and Optimization Results of All Indicators

      1)Huasdorff距离指标的曲线呈现无规律波动。在化简阈值接近最大阈值时没有明显的减小,反而朝更大值波动,与化简过程中曲线形态变化的客观规律不相符(见图 7(a)左图);并且由Huasdorff距离指标得出的各算法最佳化简效果与案例结果差别十分明显(见图 7(a)右图)。

      2)转角函数指标的相似性曲线随着化简阈值的变化波动很小,波动范围在0.95~1.00之间,没有明显的峰值(见图 7(b)左图),表明转角函数无法有效区分不同化简程度之间的差别。

      3)缓冲区限差指标曲线最符合预期效果,存在明显的峰值(见图 7(c)左图),且曲线峰值所对应的各算法化简结果均与给定的案例化简结果在视觉效果上十分相近(见图 7(c)右图);同时,图 7(c)中(1)、(2)、(3)对应的相似性值分别为0.852、0.850、0.711,符合视觉上与案例相似程度(1)>(2)>(3)的客观事实,证明该指标能有效地对比不同算法间最优结果的优劣程度,较好地满足了两条相似性指标筛选标准。

      因此,缓冲区限差指标更加适用于案例类比学习中算法化简结果与案例结果的相似性评价。

    • 理论上任何化简算法和参数的组合都有可能是最优解。考虑到计算成本,需要预先计算出合理的参数候选集。候选集的计算可分为两步:(1)确定候选化简阈值范围;(2)内插得到阈值候选集。

      最大和最小化简阈值与化简前的案例对象OLi有关。根据各化简算法特点,本文将D-P算法和Li-Openshaw算法的最小化简阈值定为0,将基于弯曲的化简算法的最小阈值定为待化简对象的最小弯曲面积Amin;D-P算法的最大阈值为OLi上节点到线要素首尾节点连线的最大垂距Vmax,Li-Openshaw算法的最大半径阈值为起始点到线要素与首尾节点中垂线交点的距离Dmax,基于弯曲的化简算法最大阈值为弯曲中最大的弯曲面积值Amax,如图 8所示。

      图  8  3种算法的最大阈值计算

      Figure 8.  Maximum Threshold Calculation of Three Algorithms

      为了得到有限的参数候选集,需要进行一定等步长的离散化。D-P算法和Li-Openshaw算法采用确定步长的方式获取离散值,本文取最大化简阈值Tmax的1/100为基本步长k1,插值得到参数的初始候选集Tset。基于弯曲的化简算法,其阈值是离散的,本文取线要素OLi上所有弯曲的面积值组成的集合作为参数的候选集Tset

      需要说明的是,D-P算法理论上也具有不连续的特性,但由于线要素节点数量较多,且计算过程较为复杂,因此采用固定步长的方式计算候选参数集。

    • 寻优过程分为以下两个步骤:

      1)各化简算法逐个采用其参数候选集Tset中的参数值对案例源数据进行迭代化简,寻找该算法对于各组案例的最优阈值设置;

      2)根据各化简算法最优阈值的平均值以及其分布情况,得到最优算法和阈值参数的组合。

      步骤2)中对于各算法得到的多组结果,需要设计一个综合的评价指标以兼顾算法结果的相似性和稳定性。多组案例计算得到的最优阈值在一定范围内变化,其相似度S的平均值S反映了算法的准确性,其离散程度反映了算法的稳定性。在数理统计中, 变异系数常用来比较不同量纲下实测数据间的离散程度。因此步骤2)中采用变异系数C的反向指标1-C与相似性平均值S的乘积作为参数推理结果好坏的综合评价指标E,通过比较E的大小得到最优的化简算法,并取最优算法的平均阈值作为最终的最优阈值。

      $$C = D \times n/\sum\limits_{i = 1}^n {{S_i}} $$
      $$E = \bar S \times \left( {1 - C} \right) $$ (4)

      式中,D为各组案例计算得到最佳阈值的标准差。

      采用多组案例进行算法和阈值参数的自动寻优,计算流程如图 9所示。通过步骤1)完成在各个算法内寻找最优阈值参数设置,对于多组案例而言,这个最优参数为各组计算结果的均值;通过步骤2)完成各算法间的横向比较,利用E值得出最优的算法及阈值参数组合。

      图  9  算法和参数寻优计算流程

      Figure 9.  Algorithm and Parameter Optimization Calculation Process

    • 实验数据来源于宁波市附近1:5万和1:25万的两幅不同比例尺道路网数据,图 10中红色虚线框内区域为实验测试区域。实验流程如下:

      图  10  实验数据及测试区域示意图

      Figure 10.  Test Data and Test Area Schematic Diagram

      1)对实验数据进行预处理,消除伪节点以及对道路连接处进行断链,以便于案例获取和化简。

      2)化简案例获取。依据训练样本和测试样本相分离的原则,本文从非测试区域1:25万数据中抽取20条道路作为案例化简后的曲线集合R,同时识别出1:5万数据中与其相对应的20条道路作为案例化简前的曲线集合O

      3)计算最优算法和阈值。用3种不同的化简方法对20组案例数据进行化简,并进行基于案例结果的类比推理,得出最佳算法及其平均阈值T

      4)采用最优算法和参数组合对测试区域线要素进行化简,得到测试区域的化简结果。

      各组案例数据进行类比推理得到的3种算法最优阈值分布情况如图 11所示。从图 11中可以看出,对于本文给定的案例而言,Li-Openshaw算法得到的最优化简阈值在分布的紧密程度和整体的相似性上都优于其他两种算法。

      图  11  3种算法类比寻优得到的最优阈值分布

      Figure 11.  Distribution of Different Thresholds of Three Simplification Methods

      相关的统计结果如表 1所示,Li-Openshaw算法的S最高,表明该方法及其最优参数组合下的化简结果更趋近于预期的化简程度,且C值最低表明其化简的稳定性最强。

      表 1  实验类比推理寻优结果统计值

      Table 1.  Statistics Result of the Experiment

      化简算法 阈值平均值T 相似度平均值S 变异系数C 综合系数E
      D-P算法 34.64 m 0.845 0.497 0.425
      Li-Openshaw 120.27 m 0.882 0.269 0.645
      弯曲组算法 4 481.02 m2 0.860 0.654 0.298

      通过比较E值的大小最终得出,化简半径阈值为120.27 m的Li-Openshaw算法为当前制图环境下实施化简的最优算法和参数组合。

    • 本文将计算得到的最优化简算法和参数组合(Li-Openshaw, 120.27 m)对图 10中的测试区域进行化简,最终化简结果如图 12(a)所示。

      图  12  本文测试区域化简结果与1:25万数据对比

      Figure 12.  Comparison of Result of CBR Algorithm and Data in Scale of 1:250 000

      结合表 2数据,从图 12(b)的整体效果可以看出,化简程度与作为参照的1:25万成果数据吻合程度非常高,相似性值由原图的0.545增长到了0.801,反映了算法和参数设置的合理性。

      表 2  化简前后平均相似性指标统计

      Table 2.  Statistics of Average Similarity Index

      指标名称 化简前 CBR化简 最小可视距离化简
      相似度 0.545 0.801 0.653

      值得说明的是,本文是针对算法选择及阈值设定的优化,得到的结果是当前化简算法下的最优结果,算法计算的结果与人工结果之间的相似度不可避免地存在一定的差异,化简效果的进一步完善依赖于算法本身的改进。

      将本文算法与传统的基于最小可视距离方法的化简结果进行对比。最小可视距离的阈值为图上0.2 mm对应的实际长度,换算为1:25万图上距离为50 m。图 13为最优阈值化简结果与理论计算值的化简结果分别与1:25万成果数据叠加显示。

      图  13  本文方法与最小可视距离计算化简程度对比

      Figure 13.  Results Comparison Between Our Method and the Minimum Visual Distance Calculation

      由实验结果可以得出:

      1)传统的最小可视距离计算阈值方法存在不足。如表 2所示,根据最小可视化距离求解的化简阈值得到的化简结果与预想效果往往偏差较大,其相似度仅为0.653。具体体现为化简程度偏低,化简力度不够(图 13(b))。为了得到理想效果,制图员需要手动对化简算法和参数进行反复修正。

      2)本文提出的类比推理方法计算得到的化简参数和阈值所得化简程度更接近于已有成果数据。如图 13(a)所示,化简后的道路与已有成果图中的道路概括程度十分相近。对基于算法的化简而言,采用本文方法自动得出的算法和参数组合能够计算出最理想的化简结果,因此不再需要制图员对参数进行修正,达到了由少量案例自动进行化简方法选择和阈值设定的目的。

      3)本文方法的优势在于制图人员只需要进行少量化简(或提供少量案例)就可以实现算法和参数的自动设置,省去了反复试错的繁琐过程;且化简的程度由制图员提供的化简结果决定,易于制图员理解和控制。案例计算得到的结果可推广到对整个相似区域的自动化简,效率高,人工作业量小。

    • 本文基于CBR的思想,通过对少量专家化简案例进行类比推理的方式实现线要素化简算法及其参数的自动寻优。相比于人工设定和基于定量模型的参数计算方式,案例的自动类比推理替代了人工反复修正参数的过程,并且参数设置的合理性由制图员提供的化简案例决定,更加符合具体制图任务的需求。通过该方法,制图员能够高效准确地得到理想的制图综合算法及其参数设置的参考值,降低了化简算法工具的使用难度,提高了化简过程中人机协同的效率。

      进一步研究可考虑将本文方法应用于其他涉及到人工设置阈值的制图综合问题,通过CBR得出算法或模型设置的合理参数。

参考文献 (20)

目录

    /

    返回文章
    返回