留言板

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

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

线要素综合的形状相似性评价方法

李兆兴 翟京生 武芳

李兆兴, 翟京生, 武芳. 线要素综合的形状相似性评价方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
引用本文: 李兆兴, 翟京生, 武芳. 线要素综合的形状相似性评价方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
LI Zhaoxing, ZHAI Jingsheng, WU Fang. A Shape Similarity Assessment Method for Linear Feature Generalization[J]. Geomatics and Information Science of Wuhan University, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
Citation: LI Zhaoxing, ZHAI Jingsheng, WU Fang. A Shape Similarity Assessment Method for Linear Feature Generalization[J]. Geomatics and Information Science of Wuhan University, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164

线要素综合的形状相似性评价方法

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

国家重点研发计划 2016YFC1401203

详细信息
    作者简介:

    李兆兴, 博士生, 主要从事海陆数据融合研究。hoops@whu.edu.cn

  • 中图分类号: P208;P283

A Shape Similarity Assessment Method for Linear Feature Generalization

Funds: 

The National Key Reasearch and Development Program of China 2016YFC1401203

More Information
    Author Bio:

    LI Zhaoxing, PhD candidate, majors in data fusion of earth and sea.E-mail:hoops@whu.edu.cn

图(6) / 表(3)
计量
  • 文章访问数:  822
  • HTML全文浏览量:  112
  • PDF下载量:  169
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-09-13
  • 刊出日期:  2019-12-05

线要素综合的形状相似性评价方法

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

    国家重点研发计划 2016YFC1401203

    作者简介:

    李兆兴, 博士生, 主要从事海陆数据融合研究。hoops@whu.edu.cn

  • 中图分类号: P208;P283

摘要: 针对线要素综合质量评价中的形状相似性评价问题,提出一种基于双侧弯曲森林形状表示模型的线要素形状相似性评价方法。引入约束Delaunay三角网及其凸包,生成线要素的双侧根弯曲序列,并在每个根弯曲上生成弯曲树,使用三角形表达每个层次上的弯曲,从而建立基于双侧弯曲森林的线要素形状表示模型。在该模型基础上,顾及线要素的地理位置特征,对综合前后线要素的形状相似性进行评价。实验结果表明,该方法能够区别不同层次上的形状特征,与形状认知的层次一致,能够有效辨识综合质量是否存在问题。

English Abstract

李兆兴, 翟京生, 武芳. 线要素综合的形状相似性评价方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
引用本文: 李兆兴, 翟京生, 武芳. 线要素综合的形状相似性评价方法[J]. 武汉大学学报 ● 信息科学版, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
LI Zhaoxing, ZHAI Jingsheng, WU Fang. A Shape Similarity Assessment Method for Linear Feature Generalization[J]. Geomatics and Information Science of Wuhan University, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
Citation: LI Zhaoxing, ZHAI Jingsheng, WU Fang. A Shape Similarity Assessment Method for Linear Feature Generalization[J]. Geomatics and Information Science of Wuhan University, 2019, 44(12): 1859-1864. doi: 10.13203/j.whugis20180164
  • 线要素自动综合始终是制图综合及其相关领域研究的一个热点问题,各国学者设计了大量线综合模型与方法[1-2]。但是,这些方法在使用过程中仍需大量人工干预[3],并未实现真正的自动综合。许多学者意识到,除算法本身局限外,自动综合质量评价方法的匮乏也是自动综合难以实现的原因之一[4]

    线要素综合的过程是一个破坏空间精度、形状等特征,使线要素满足目标尺度的表达需求的过程,因此其质量评价也必须结合该特点,对空间精度、拓扑关系、形状相似度等多个方面进行评价。由于形状表示与建模的复杂性,目前线要素形状相似性的相关标准及框架体系仍未出现,亟待进一步研究[5]

    形状是空间认知的重要特征,其表示应满足仿射变换的不变性[6]。在制图领域,形状相似性始终被认为是线综合中的一个基础质量指标[7-8], 并已提出基于距离、角度、长度等几何特征的形状相似性评价方法[9-10]。但此类方法大都规避了形状表示,直接将几何特征的相似性等同于形状相似性,本质上偷换了形状的概念[11],且不满足对于仿射变换的不变性要求,因此往往难以取得合理的结果。

    针对上述问题,本文提出一种线要素的双侧弯曲森林形状表示模型(two-side bend forest shape representation model, TBF),并在该模型的基础上,提出一种综合前后线要素的形状相似性评价方法。

    • 线要素的形状表示模型需要尽量与线要素形状特性及形状认知规律相一致,即满足对于仿射变换的不变性同时符合人类形状认知呈现由简及繁的层次性[12],具备多层次、多尺度特性。

      弯曲常被认为是构成线要素形状特征的基本单元[13],具有多尺度性、弯曲内的层次性、弯曲间的独立性与连续性等共性特征[14-15],能够满足线要素形状表示的需求。已有的线要素的弯曲划分方法[2, 14-16]中,基于约束Delaunay三角网(constrained Delaunay triangulation,CDT)的弯曲划分方法能够有效表示弯曲的层次关系,更加契合弯曲的层次化特征。因此,本文在基于CDT的弯曲划分方法基础上,提出一种线要素的TBF形状表示模型。

      由于借助超级三角形构建CDT的方法对于弯曲间的连续性等空间关系的表达并不充分,本文借鉴文献[14]的方法,不添加超级三角形,直接在线要素上构建CDT。完成CDT构建后,可将所有的边分为约束边、非约束边、凸包边3类,具体如图 1所示。

      图  1  线要素AK的CDT示意图

      Figure 1.  CDT Diagram of Linear Feature AK

    • 若规定约束边两侧区域为非连通关系,则凸包边与非约束边将线要素凸包面划分为若干相邻但不连通的子区域,每个区域包含一段凸包边,称为根弯曲,其中凸包边为弯曲树的根是弯曲树生成的起点,包含两段约束边的三角形为弯曲树的叶,是弯曲树生成的终点。根据基线是否是约束边,可将根弯曲分为两类:①平弯曲,即基线是约束边的根弯曲;②非平弯曲,即基线不是约束边的根弯曲,非平弯曲中至少包含一个三角形。

      根据基线与线要素的位置关系,可将跟弯曲划分到线要素两侧。如图 1中的根弯曲可分为左侧{AK}和右侧{ABBJJK}。

    • 在任意根弯曲上生成多层次弯曲树的流程如图 2所示。

      图  2  弯曲树的生成方法

      Figure 2.  Generation Method of Bend Tree

      通过图 2的方法,可在每个根弯曲上生成弯曲树(平弯曲的弯曲树为空),进而生成线要素的双侧弯曲森林。图 1中的线要素AK生成的TBF如图 3所示。

      图  3  线要素AK的TBF示意图

      Figure 3.  TBF Structural Diagram of Linear Feature AK

      图 3的方法构建的TBF中,每个根弯曲构成一颗弯曲树,同侧弯曲树之间首尾相连,满足弯曲间的连续性。除平弯曲外,曲线的TBF内其他弯曲的内部层次往往大于1,而每个层次上的节点可以共同构成相应尺度上的表达,满足弯曲表达的层次性。

      上述步骤实现了基于基线的弯曲层次结构表达,但基线是一维的,无法有效地对二维的弯曲形状进行表达,仍需定义适当的弯曲形状表示模型[17]。基本二维形状中,当底边确定时,引入距离和方位两个度量指标可以唯一确定一个三角形,因而三角形具有二维形状表达的唯一性和计算的简明性[18]。考虑到特征点选取的唯一性,本文在弯曲基线基础上,加入最大矢高点来表达弯曲形状。

    • 正确的线要素综合在形状细节被简化的同时能够保留主要形状特征。相应地,进行线要素的形状相似性度量时,应当强调高层次弯曲形状特征对相似性度量的影响,并弱化低层次形状细节的影响。

    • 为消除由于旋转、平移等综合操作带来的影响,本文将线要素起点移动至坐标原点处,并将终点旋转至坐标横轴正方向重叠。

    • 综合前的线要素上某弯曲B0与其综合后的对应弯曲B1在预处理后将形成3个区域:重叠区域S0=B0B1;损失区域S1=B0-B1;新增区域S2B1-B0。考虑到线要素的空间位置特征,弯曲B0B1之间的相似度Sim(B0B1)可表示为:

      $${\rm{Sim}}\left( {{B_0}, {B_1}} \right) = \frac{{{\rm{Area}}\left( {{S_0}} \right)}}{{{\rm{Area}}\left( {{B_0}} \right)}}$$ (1)
    • 形状认知中,被认知对象的面积越大,其对形状识别的结果影响也就越大。因此,本文基于弯曲面积,对根弯曲间和根弯曲内各层次间的权重进行分配,实现各弯曲间的相似度的有机整合,方法如下。

      1)将整个TBF的总权重设为1。

      2)每一侧弯曲森林的总权重按照本侧区域面积在凸包面积AreaCDT中的占比进行分配,即:

      $$\left\{ {\begin{array}{*{20}{l}} {{\rm{Are}}{{\rm{a}}_{{\rm{CDT}}}} = {\rm{Are}}{{\rm{a}}_{{\rm{Left}}}} + {\rm{Are}}{{\rm{a}}_{{\rm{Right}}}}}\\ {{\omega _{{\rm{Left}}}} = \frac{{{\rm{Are}}{{\rm{a}}_{{\rm{Left}}}}}}{{{\rm{Are}}{{\rm{a}}_{{\rm{CDT}}}}}}}\\ {{\omega _{{\rm{Right}}}} = \frac{{{\rm{Are}}{{\rm{a}}_{Right}}}}{{{\rm{Are}}{{\rm{a}}_{{\rm{CDT}}}}}}} \end{array}} \right.$$ (2)

      3)各根弯曲间的权重根据其面积与本侧区域面积之比进行分配,即:

      $${\omega _{{\rm{RootBend}}}} = \frac{{{\rm{Are}}{{\rm{a}}_{{\rm{RootBend}}}}}}{{{\rm{Are}}{{\rm{a}}_{{\rm{Side}}}}}}$$ (3)

      4)同一根弯曲内,除根层次外,其余层次弯曲的权重继承自其父节点,兄弟节点间按照面积比进行权重分配,即对于弯曲C的两个子弯曲AB,其权重ωAωB为:

      $$\left\{ {\begin{array}{*{20}{c}} {{\omega _A} = \frac{{{\rm{Are}}{{\rm{a}}_A}}}{{{\rm{Are}}{{\rm{a}}_C}}}{\omega _C}}\\ {{\omega _B} = \frac{{{\rm{Are}}{{\rm{a}}_B}}}{{{\rm{Are}}{{\rm{a}}_C}}}{\omega _C}} \end{array}} \right.$$ (4)

      基于上述方法,综合前后线要素LL'之间的形状相似性指标S (LL')可表示为:

      $$S\left( {L, L'} \right) = \left( {1 - \sum\limits_{{\rm{Side}}k} \sum\limits_{{\rm{Level}}j} \sum\limits_{{\rm{Bend}}i} {\omega _i}\left( {1 - {\rm{Sim}}\left( {{B_i}, {B_i}{\rm{'}}} \right)} \right)} \right)$$ (5)

      式中,k∈{Left,Right},表示当前一侧;ji分别表示当前层次和当前弯曲。

      由于该方法建立在TBF形状表示模型上,故称之为基于双侧弯曲森林的形状相似性评价法(two-side bend forest based shape similarity assessment method, TBF-SS)。

    • 选取Length Ratio[19]、Hausdorff距离[20]和转角函数法[21]作为对比方法,在图 4~6的数据上对本文方法进行实验验证。

      图  4  实验数据集Ⅰ

      Figure 4.  Experimental Dataset Ⅰ

      图  5  实验数据集Ⅱ

      Figure 5.  Experimental Dataset Ⅱ

      图  6  实验数据集Ⅲ

      Figure 6.  Experimental Dataset Ⅲ

      1)从1:25万Digital Atlas of the Earth 2012 (DAE 2012)的某图幅中,选取河流和边界两类要素,使用Douglas-Peucker方法[22]进行两个程度的综合,作为实验数据集Ⅰ,如图 4所示。

      2)从实验数据Ⅰ中选取一段形状复杂、存在大量细小弯曲的河流(图 4中圆形标识)和一段形状细节特征较少、但整体趋势性明显的边界(图 4中矩形标识),使用Douglas-Peucker算法进行化简,作为实验数据集Ⅱ, 如图 5所示。

      3)为测试各方法对于综合过程中出现的不足及错误的敏感性,从实验数据集Ⅱ所使用河流中截取一段复杂弯曲,且已经使用Douglas-Peucker算法化简至11个节点作为综合的原始数据,通过手动删除不同的两个节点,模拟不同质量的综合方案,作为实验数据集Ⅲ,如图 6所示。

      实验数据集Ⅰ的形状相似性评价结果如表 1所示。

      表 1  不同方法下实验结果Ⅰ(均值)

      Table 1.  Experimental Results Ⅰ of Different Methods (Mean Value)

      要素类 容差/10-4° Length Ratio/% Hausdorff距离/10-5° TBF-SS/% 转角函数/((°)·m-1)
      河流 3 97.73 26.574 5 91.48 24.765 1
      8 94.38 65.791 2 70.95 29.523 7
      边界 3 99.72 29.259 4 93.03 1.671 3
      8 99.17 75.377 7 82.77 17.845 6

      理论上,对于相同线要素,综合后节点保留率越低,综合程度越高,综合前后线要素的形状相似度也就越低。从实验结果上看,对于每一类要素,全部4种评价方法均能够在节点容差较小时取得更高的评价结果,符合理论预期。

      总体上,实验数据集Ⅱ的形状相似性评价结果与实验数据集Ⅰ的实验结果类似。在两条线要素上,4种评价方法在节点保留率为80%时均取得更高的评价结果,如表 2所示。

      表 2  不同方法下实验结果Ⅱ

      Table 2.  Experimental Results Ⅱ of Different Methods

      要素类别 节点保留率/% Length Ratio/% Hausdorff距离/(10-5°) TBF-SS/% 转角函数/((°)·m-1)
      河流 80 99.74 5.874 3 96.15 3.999 7
      10 92.12 91.892 5 74.30 43.712 8
      边界 80 100.00 2.597 2 95.87 0.286 1
      10 98.21 179.638 5 85.46 22.936 6

      另一方面,线要素形状细节越丰富,在相同综合强度条件下损失的细节特征越多,综合前后的形状相似度也就越低,因此图 5中河流的形状相似度应当相对较低。从实验结果上看,Length Ratio、TBF-SS和转角函数法的结果符合理论预期,但Hausdorff距离方法则得到了相反的结果。分析可知,由于Hausdorff距离是一种绝对距离度量,而该边界空间跨度更大,因而其空间位置变化较大,导致Hausdorff距离法的结果较差。这一现象与文献[11]的结论也相吻合,即基于距离度量的形状相似性方法无法胜任形状相似性的评价需求。

      图 6的综合结果中,实验数据集Ⅲ线2、线3和线4对形状特征保持较好,线5次之,线6则明显改变了该线要素的显著形状特征。具体地,由于线2导致线左侧第3层次的弯曲ABC消失,线3导致左侧第3层次的弯曲CDE消失,而线4仅造成了双侧第4层次上两个弯曲的消失,因此线4的形状相似度应当最高,则上述线要素与线1之间的形状相似性按照降序排列大致应为线4 > 线3 > 线2 > 线5 > 线6。对上述线要素使用上述方法的评价如表 3所示。

      表 3  不同方法下实验结果Ⅲ

      Table 3.  Experimental Results Ⅲ of Different Methods

      线要素 删除节点 Length Ratio/% Hausdorff距离/m TBF-SS /% 转角函数/((°)·m-1)
      线2 BC 98.57(1) 1.128 4(4) 83.52(3) 28.686 7(5)
      线3 DF 98.17(5) 0.742 2(1) 90.23(2) 10.669 4(2)
      线4 EG 98.37(3) 0.885 4(2) 91.03(1) 10.146 4(1)
      线5 HI 98.44(2) 1.021 5(3) 85.39(4) 12.277 6(3)
      线6 IJ 98.25(4) 2.431 4(5) 41.52(5) 17.258 7(4)
      注:3~6列中括号内数值表示线号

      排序结果上,各对比方法均未能与主观目视判别形状认知一致。具体地,由于删除点D致使边CDDE消失,Length Ratio法认为线3的相似度最低;由于AB边相对较长,尽管删除BC节点前后ABAD夹角不大,但其节点间距离变化较大,因此Hausdorff距离法认为线2的质量仅好于线6;由于AB边较长,转角函数法计算中该部分影响较大,因此线2的相似性最低。通过对线要素的形状进行多层次表达,TBF-SS法能够识别形状所在层次,强化全局形状特征影响,弱化局部细节形状特征影响,因此能够在多种不同综合方案的形状相似性评价中取得与主观认知一致的结果。此外,从数值上看,TBF-SS法的评价结果在综合上存在明显质量问题时显著降低,能够有效辨别综合质量是否存在缺陷。

    • 本文针对线要素综合质量评价中的形状相似性评价问题,基于约束Delaunay三角网和凸包理论与方法,提出了一种线要素的双侧弯曲森林形状表达模型,并在该模型基础上,对综合前后线要素间的形状相似性进行评价。该方法能够有效区分不同层次的形状特征,结果与主观形状认知一致。

      本文方法适用于对综合中保持完整性的线要素形状相似性进行评价,如何对完整性被综合过程破坏的线要素进行局部形状相似性评价,仍有待进一步研究。

参考文献 (22)

目录

    /

    返回文章
    返回