留言板

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

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

采用三元弯曲组划分的线要素化简方法

钱海忠 何海威 王骁 胡慧明 刘闯

钱海忠, 何海威, 王骁, 胡慧明, 刘闯. 采用三元弯曲组划分的线要素化简方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
引用本文: 钱海忠, 何海威, 王骁, 胡慧明, 刘闯. 采用三元弯曲组划分的线要素化简方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
QIAN Haizhong, HE Haiwei, WANG Xiao, HU Huiming, LIU Chuang. Line Feature Simplification Method Based on Bend Group Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
Citation: QIAN Haizhong, HE Haiwei, WANG Xiao, HU Huiming, LIU Chuang. Line Feature Simplification Method Based on Bend Group Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239

采用三元弯曲组划分的线要素化简方法

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

国家自然科学基金 41571442

国家自然科学基金 41171305

详细信息
    作者简介:

    钱海忠, 博士, 教授, 现从事空间数据自动综合、自动更新、应急制图等研究。haizhongqian@163.com

    通讯作者: 何海威, 博士生。adai928@126.com
  • 中图分类号: P208

Line Feature Simplification Method Based on Bend Group Division

Funds: 

The National Natural Science Foundation of China 41571442

The National Natural Science Foundation of China 41171305

More Information
    Author Bio:

    QIAN Haizhong, PhD, professor, specializes in spatial data auto-generalization, E-mial: haizhongqian@163.com

    Corresponding author: HE Haiwei, PhD candidate, E-mail: adai928@126.com
图(11) / 表(3)
计量
  • 文章访问数:  757
  • HTML全文浏览量:  61
  • PDF下载量:  322
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-04-28
  • 刊出日期:  2017-08-05

采用三元弯曲组划分的线要素化简方法

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

    国家自然科学基金 41571442

    国家自然科学基金 41171305

    作者简介:

    钱海忠, 博士, 教授, 现从事空间数据自动综合、自动更新、应急制图等研究。haizhongqian@163.com

    通讯作者: 何海威, 博士生。adai928@126.com
  • 中图分类号: P208

摘要: 当前基于弯曲的线要素化简在化简过程中对于连续小弯曲的化简处理有所欠缺。针对此提出了基于三元弯曲组的化简方法。该方法首先将连续的弯曲划分到各个弯曲三元组中;然后针对三元弯曲的不同组合类型采用不同的化简方式进行化简;最后设计循环化简判断规则,重复化简过程直到所有弯曲满足化简阈值,从而实现连续弯曲的间隔化简。实验表明,该方法能够有效地保持弯曲的形态特征以及不同化简阈值结果间的层次性。

English Abstract

钱海忠, 何海威, 王骁, 胡慧明, 刘闯. 采用三元弯曲组划分的线要素化简方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
引用本文: 钱海忠, 何海威, 王骁, 胡慧明, 刘闯. 采用三元弯曲组划分的线要素化简方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
QIAN Haizhong, HE Haiwei, WANG Xiao, HU Huiming, LIU Chuang. Line Feature Simplification Method Based on Bend Group Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
Citation: QIAN Haizhong, HE Haiwei, WANG Xiao, HU Huiming, LIU Chuang. Line Feature Simplification Method Based on Bend Group Division[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1096-1103. doi: 10.13203/j.whugis20150239
  • 曲线化简是自动制图综合研究的一个经典课题。比较经典的曲线化简方法包括有Douglas-Peucher算法(D-P算法)、垂距法、BLG(binary line generalization tree)、Li-Open-Shaw算法等[1-6]。基于曲线弯曲识别的曲线化简方法的出现,不仅能够有效地避免化简中出现的曲线自相交问题,化简效果也比较符合人类对制图综合的认知规律。目前主要的弯曲识别算法有拐点法、单调链法、Delaunay三角网法、斜拉式弯曲识别算法以及基于通视性的弯曲识别及塑形法等[7-11]

    基于弯曲的线要素化简方法已应用于各类地图要素的化简中,如等高线、海岸线、水系以及道路等[12-15]。然而,当前的化简方法在处理连续细小弯曲时,对弯曲删除的判断过程考虑不够充分,未考虑相邻弯曲的相互影响。这对只需要考虑一侧弯曲化简的线要素(如等高线、海岸线)来说影响不大,但对于需要考虑两侧弯曲化简的线要素(如道路、河流)来说,若直接根据阈值删除弯曲,忽略化简时两侧相邻弯曲的相互影响,可能出现“一刀切”(即过度化简,如图 1所示)的情况。因此,需要设计一个合理的相邻弯曲删除策略,实现化简过程的渐进展开。

    图  1  直接根据阈值化简的结果

    Figure 1.  Simplify Road by Threshold Directly

    本文在分析基于弯曲化简的形态变化规律的基础上,提出了基于“三元弯曲组”划分的线要素化简方法。

    • 化简的层次性是指在不同化简阈值下,不同化简结果的曲线形态呈现由繁到简的渐进变化。在化简过程中,一个基本弯曲的删除会对与其相邻的弯曲形态产生影响。合理地利用相邻弯曲间的相互影响,可以在满足化简阈值的前提下,最大限度地保留弯曲的原始形态[15]。如图 1所示,假设原始曲线上的8个弯曲均刚好满足删除阈值,若直接按照阈值删除,则所有8个弯曲一次性全部删除,化简结果为一条直线。然而实际上,对该线要素进行间隔弯曲删除就能使结果满足化简阈值,同时最大限度地保留了弯曲的形态特性。

      图 2所示,间隔性地删除了3个弯曲,即得到由3个大弯曲组成的曲线,使化简结果满足阈值要求(图 2(a));若进一步扩大删除阈值则可得到如图 2(b)所示效果,不同程度的化简结果之间体现出一定的层次性关系。

      图  2  间隔式化简的结果

      Figure 2.  Interval Line Simplification

      但并不是所有的曲线都可以简单地采取等间隔的弯曲化简,图 2中示例的情况只在弯曲均匀分布时才适用。在实际应用中,连续排列的弯曲大小各异,等间隔删除可能会对不满足删除阈值的弯曲进行误删。

      由基本弯曲的性质以及弯曲化简的形态变化规律可推导出一个重要结论:一个弯曲化简后的影响不会超出以其为中心的异侧相邻弯曲的范围。因此本文提出了以3个相邻弯曲组成的“三元弯曲组”为划分单元,在各个弯曲组中进行弯曲化简的方法,整个曲线的化简则可以看做是n个“三元弯曲组”化简结果的组合,从而达到间隔化简的目的。

    • 三元弯曲组的定义为:以某一弯曲为参考,结合与其有邻近关系的两个弯曲所组成的弯曲组。例如,若与弯曲Ln有邻近关系的弯曲为RnRn+1,则(RnLnRn+1)为一个弯曲组。研究三元弯曲组的化简,对于保持曲线化简前后的整体形态特征具有十分重要的意义。

    • 三元弯曲组的构建关键在于邻近关系的探测。由弯曲的连续性可知,凹凸弯曲总是依次出现,因此可以直接通过弯曲的序号索引到该弯曲的相邻异侧弯曲,不需要进行繁琐的空间运算。

      图 3所示,图中弯曲依次交替出现,弯曲Ln的相邻弯曲为(Rn-1Rn)或(RnRn+1),三者组成一个弯曲组,具体组合形式与起始弯曲的类型有关。

      图  3  弯曲的邻近关系探测示例

      Figure 3.  Adjacent Relation of Bends

      图 3(a)所示,若起始弯曲为左弯曲L1,则L1的相邻弯曲只为R1Ln的相邻弯曲为(Rn-1Rn)(n>1);Rm的相邻弯曲为(LmLm+1)(m≥1)(在程序中判断时,需要先验证Lm+1Rn是否存在,若不存在则Ln的相邻弯曲只为Rn-1Rm的相邻弯曲只为Lm)。

      图 3(b)所示,若起始弯曲为右弯曲R1,则Ln的相邻弯曲为(RnRn+1)(n≥1);R1的相邻弯曲只为L1Rm的相邻弯曲为(Lm-1Lm)(m>1)(在程序中判断时,需要先验证LmRn+1是否存在,若不存在则Ln的相邻弯曲只为RnRm的相邻弯曲只为Lm-1)。

    • 三元弯曲组的化简归纳起来一共有10种不同的情况,具体可以分为3种类型。

      第一类    三元弯曲组中只有1个弯曲小于删除阈值时的化简。该类中又可分为图 4中的3种情况。对于该类情况的化简直接删除弯曲组中满足删除条件的弯曲即可(图 4中✘表示满足删除条件的弯曲,✔表示需要保留的弯曲)。

      图  4  只有1个弯曲小于删除阈值时的化简

      Figure 4.  Simplification when One Bend is Less than the Threshold

      第二类    三元弯曲组中有2个弯曲小于删除阈值时的化简。如图 5所示,该类也分为3种化简情况。针对不同情况,需要讨论弯曲间的位置关系和面积大小关系(为了方便表示,图 5中弯曲从左至右依次用ABC表示)。如图 5(a)5(b)所示,弯曲组中相邻弯曲BC均满足删除条件,则对BC的面积S进行判断,图 5(a)5(b)中分别是SBSCSB>SC,因此在图 5(a)5(b)中分别对弯曲组中的BC进行删除;当两个面满足删除条件的弯曲不相邻时,如图 5 (c)所示,则直接对两侧的弯曲进行删除。

      图  5  有2个弯曲满足阈值小于删除阈值时的化简

      Figure 5.  Simplification when Two Bends are Less than the Threshold

      第三类    三元弯曲组中3个弯曲均小于删除阈值时的化简,如图 6所示。对于该类型弯曲组的化简,主要考虑中间弯曲与两边弯曲之间的面积大小关系,可以概括为图 6所示的4种类型。

      图  6  当3个弯曲均小于删除阈值时的化简

      Figure 6.  Simplification when Three Bends are Less than the Threshold

      1) 中间弯曲B面积均大于两边的弯曲AC的面积,且弯曲AC面积之和也小于弯曲B,如图 6(a)所示,对于该情况直接删除面积较小的两边弯曲AC

      2) 中间弯曲B面积均大于两边的弯曲AC的面积,但弯曲AC面积之和大于弯曲B。如图 6(b)所示。对于该情况,采取位移误差最小原则,删除中间弯曲B

      3) 中间弯曲B面积最小,如图 6(c)所示,则直接删除弯曲B

      4) 中间弯曲B的面积处于AC两者面积值之间,如图 6(d)所示,SA>SB>SC(或者SC>SB>SA)。考虑如何达到化简弯曲组的目的且化简后整体位置误差较小,若只删除弯曲C则弯曲A不能得到化简,对于后续的化简来说仍要删除A,这样造成的位移误差更大。因此依据位移误差最小原则,对于此情况采取删除中间弯曲B的方法进行化简。

    • 一次化简并不能保证化简的结果均符合化简阈值的要求,因此需要制定循环化简的策略。在每次化简后对曲线重新进行弯曲识别,构造新的三元弯曲组,通过不断地化简合并弯曲组来实现曲线形态逐渐向化简目标形态靠拢。基本流程如图 7所示。

      图  7  基于弯曲组的线要素化简流程图

      Figure 7.  The Process of Line Simplification Based on Bend Groups

      具体循环化简步骤如下。

      1) 从第一个弯曲开始,每3个弯曲划分为一个弯曲组;

      2) 对弯曲组的类型进行判断,根据§2的化简策略对弯曲组中的弯曲进行化简;

      3) 对上一次化简的结果重新提取新的弯曲,并判断是否均满足删除阈值的要求,若是则化简结束,否则回到步骤1) 重新开始化简。

      本文中将道路弯曲基线长度作为阈值参数,例如把前比例尺下弯曲基线小于5 mm的弯曲视为弯曲待删除对象,下文中所提到的弯曲阈值也均采用弯曲基线长度作为判断标准。通过该循环化简过程后,曲线上的所有弯曲对象均满足删除阈值的要求,曲线形态以一种渐进化简的形式得到了完善。具体过程如图 8所示。图 8中展示了每一次循环后的道路形态,图 8中箭头指示的是典型变化区域放大示例。由放大部分可以看出,每一次被化简的弯曲对象之间均呈现间隔分布,使得化简过程能够有层次地展开。完成最后一次循环后,当前所有弯曲均满足化简阈值,不再需要化简,相关统计数据见表 1

      图  8  基于三元弯曲组的循环化简效果示例

      Figure 8.  Simplification Circulation Based on Three-Element-Bend Groups

      表 1  循环化简过程中的相关数据统计

      Table 1.  Statistics of Line Simplification Circulation

      相关统计项 第一次 第二次 第三次 最终
      删除弯曲数 23 4 2 2
      删除节点数 21 6 2 2

      图 8中的放大示例和表 1可以看出,随着循环次数的增加,化简的力度越来越小,整个循环过程可以看作是在不断对线要素化简结果进行修缮的过程。从最终的化简结果可以看出,该方法化简得到的曲线比较平滑,同时较好地保持了道路的主要形态特征。

    • 本文将基于三元弯曲组的化简方法与已有的D-P算法、基于弯曲的化简方法(直接删除满足阈值的弯曲)分别对北京周边某地区1:5万道路数据的局部区域进行化简对比实验,如图 9所示。该部分区域属于郊区,道路形态比较曲折,能够很好地检验各种化简方法的效果。

      图  9  实验数据图

      Figure 9.  Original Road Network Data

      为了保证化简前后道路网的拓扑一致性,在实验区对道路实验数据实现拓扑预处理(道路的断链、接链处理)。同时,对于D-P化简,通过强制保留道路网相交处的节点保持拓扑关系;对于基于三元弯曲组划分的化简以及基于弯曲的化简,通过强制保留存在交点的弯曲以及保留曲线的起止节点的方式来避免拓扑关系的改变。

      需要说明的是, 由于本文对比的是使用D-P化简方法与基于三元弯曲组的化简方法化简后曲线要素的局部形态特征变化,因此需要将两种化简方法置于相同的“化简程度”下进行对比。本文定义“化简程度”为被化简单元占总化简单元的百分比,也称为压缩率。D-P化简的化简单元是曲线节点,其化简程度只能用节点的压缩率来衡量;而基于三元弯曲组划分的化简单元是弯曲,其化简程度只能通过弯曲的压缩率来衡量。本文对两种化简方法在几组相同“化简程度”下的结果进行了对比,具体见表 2。原图的总节点数是1 159,总弯曲数是564。

      表 2  D-P化简方法与本文化简方法结果对比统计

      Table 2.  Statistics of Douglas-Peucher Method and Three-Element-Bend Group Based Method

      化简程度/% 化简后节点数量 化简后弯曲数量
      D-P化简 基于三元弯曲组化简 D-P化简 基于三元弯曲组化简
      50 600 877 319 280
      70 331 586 220 182
      80 237 354 169 115
      90 144 188 87 77

      表 2中的数据对比可知,在相同的化简程度下,D-P化简方法保留的节点数量要远少于基于三元弯曲组化简方法保留的节点数量,然而其弯曲的数量却比后者多。这意味着,组成D-P化简结果中基本弯曲所包含节点数要少一些,这将导致弯曲的平滑度降低,呈现锯齿状。由图 10的对比可以印证这一结论,在相同的化简程度下,图 10(a)10(b)中从左到右依次为化简程度70%、80%、90%。基于三元弯曲组的化简结果要更加平滑。

      图  10  基于三元弯曲组与D-P方法对比

      Figure 10.  Comparation of Douglas-Peucher Method and Three-Element-Bend Group Method

      同时, 本文还将基于三元弯曲组的化简方法与常用的基于弯曲的化简方法在相同的几组化简阈值下进行了对比实验。实验的统计结果见表 3。由表 3中统计数据对比可以看出,在相同的化简阈值下,基于弯曲的直接化简方法删除了更多的弯曲数量和节点数量,化简的力度较强。但是由于其采取的是直接删除不满足阈值的所有弯曲的方法,因此对相邻的细小弯曲一概进行了删除,不同阈值化简结果之间不能体现出较好的层次性。而基于三元弯曲组的化简方法则在层次性上表现较好,曲线在不同阈值处理下的细节呈现出依次增强的概括过程,如图 11所示。图 11(a)11(b)中从左到右依次为化简阈值2 mm、5 mm、10 mm和20 mm。

      表 3  基于弯曲的化简方法与本文化简方法结果对比统计

      Table 3.  Statistics of Regular Simplification Method and Three-Element-Bend Group Based Method

      化简阈值/mm 化简后节点数量 化简后弯曲数量
      基于弯曲的化简 基于三元弯曲组化简 基于弯曲的化简 基于三元弯曲组化简
      2 678 877 233 280
      5 316 586 113 182
      10 143 354 59 115
      20 64 188 5 77

      图  11  本文方法与基于弯曲的化简方法对比

      Figure 11.  Comparation of Curve Bend Based Method and Three-Element-Bend Group Method

      从以上化简的结果图和统计表中的数据可以得出以下结论。

      1) D-P化简虽然对曲线的形态化简效果明显,但是化简结果导致了大量的尖锐角的出现,对于地图道路要素来说是不符合自然规律的。如表 2所示,在弯曲压缩率相近的情况下,D-P化简算法保留的节点数明显小于基于弯曲组的化简算法,导致化简结果比较生硬,平滑度不够;结果图中可以看出对形态的保持效果较差,没有体现出“综合”的本质。

      2) 基于弯曲的化简方法,由于直接删除小于阈值的弯曲,使得在同一化简阈值下化简后的节点以及弯曲数量远少于基于弯曲组的化简方法,导致在化简时力度过猛,没有考虑到弯曲之间的相互影响和制约(表 3)。从化简的结果图可以看出,不同阈值的化简结果之间形态变化突然,由于对所有满足阈值的弯曲采取“一刀切”的处理方式,没有体现出不同显示尺度上的层次性。

      3) 基于三元弯曲组的化简,通过划分三元弯曲组以及采取循环化简策略,在保证化简结果满足化简阈值的情况下,对连续出现的相邻小弯曲尽量保持了较多的节点和弯曲结构。从图 10(b)来看,化简结果较好地保持了道路原本的形态特征,曲线形态平滑;从图 11(b)可以看出, 随着化简阈值的增大,不同阈值化简结果在显示尺度上体现出较好的层次性。

      由于本文的道路化简方法采取的是基于弯曲的方式,因此在化简结果的形态保持上比起基于节点的D-P算法更加平滑;又由于本文顾及了道路连续弯曲之间的影响,采取了基于“三元弯曲组”的间隔化简方式,避免了一般基于弯曲的直接化简所导致的“一刀切”的情况,不同阈值化简结果之间能够体现出层次性的过渡,使得化简的结果得到改善。

    • 针对线要素上连续细小弯曲的化简问题,本文提出了“三元弯曲组”的概念,并对“三元弯曲组”的特性进行分析,划分“三元弯曲组”类型,针对不同类型弯曲组制定不同的化简方法,并将其应用于线状道路要素的化简中。从化简的结果来看,该方法能够有效地对道路要素进行化简,弥补了以往基于弯曲化简方法对连续小弯曲化简的不足,化简结果在不同化简阈值下体现出递进的层次关系,在各阈值范围内较好地保持了道路本身的形态特征。该方法可有效应用于细小弯曲较多且需要同时考虑双侧弯曲化简的要素(如道路、河流等)化简中。

参考文献 (15)

目录

    /

    返回文章
    返回