留言板

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

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

顾及三维形态特征的河流曲线化简方法

刘民士 龙毅 费立凡 何桂芳

刘民士, 龙毅, 费立凡, 何桂芳. 顾及三维形态特征的河流曲线化简方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
引用本文: 刘民士, 龙毅, 费立凡, 何桂芳. 顾及三维形态特征的河流曲线化简方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
LIU Minshi, LONG Yi, FEI Lifan, HE Guifang. Line Simplification of River Considering Three-Dimensional Shape Characteristics[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
Citation: LIU Minshi, LONG Yi, FEI Lifan, HE Guifang. Line Simplification of River Considering Three-Dimensional Shape Characteristics[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176

顾及三维形态特征的河流曲线化简方法

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

国家自然科学基金 41171350

国家自然科学基金 41271449

滁州学院校级培育基金 2014PY03

详细信息
    作者简介:

    刘民士, 博士生, 讲师, 主要从事地图自动综合的理论与方法研究。liuminshi1983@126.com

    通讯作者: 费立凡, 博士, 教授。feilifan@126.com
  • 中图分类号: P283;P208

Line Simplification of River Considering Three-Dimensional Shape Characteristics

Funds: 

The National Natural Science Foundation of China 41171350

The National Natural Science Foundation of China 41271449

the Cultivation Project of Chuzhou University 2014PY03

More Information
    Author Bio:

    LIU Minshi, PhD candidate, lecturer, specializes in automatic map generalization. E-mail: liuminshi1983@126.com

    Corresponding author: FEI Lifan, PhD, professor. E-mail: feilifan@126.com
图(5) / 表(2)
计量
  • 文章访问数:  1299
  • HTML全文浏览量:  71
  • PDF下载量:  311
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-09-14
  • 刊出日期:  2018-03-05

顾及三维形态特征的河流曲线化简方法

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

    国家自然科学基金 41171350

    国家自然科学基金 41271449

    滁州学院校级培育基金 2014PY03

    作者简介:

    刘民士, 博士生, 讲师, 主要从事地图自动综合的理论与方法研究。liuminshi1983@126.com

    通讯作者: 费立凡, 博士, 教授。feilifan@126.com
  • 中图分类号: P283;P208

摘要: 鉴于常规曲线化简方法应用于河流曲线化简时难以顾及河流要素的三维特征及其拓扑结构,提出了一种顾及三维形态特征的河流曲线化简方法。该方法利用河流曲线上散点的三维特征对散点进行选取进而实现河流曲线化简。在三维Douglas-Peucker(3D D-P)算法的基础上提出一种三维散点排队法,根据散点的三维特征对河流曲线的离散点集进行排队,并通过初始排队、"3合1"队列合并及约束点位置调整3个过程建立散点队列,然后根据压缩比从队列尾部删除相应比例的点数获得散点综合结果,将综合后的散点按照河流曲线的原始次序重构出化简后的河流曲线。实验结果表明,该方法既能最大程度地保留河流的三维形态特征,又能保证河流曲线之间的拓扑结构一致性。

English Abstract

刘民士, 龙毅, 费立凡, 何桂芳. 顾及三维形态特征的河流曲线化简方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
引用本文: 刘民士, 龙毅, 费立凡, 何桂芳. 顾及三维形态特征的河流曲线化简方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
LIU Minshi, LONG Yi, FEI Lifan, HE Guifang. Line Simplification of River Considering Three-Dimensional Shape Characteristics[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
Citation: LIU Minshi, LONG Yi, FEI Lifan, HE Guifang. Line Simplification of River Considering Three-Dimensional Shape Characteristics[J]. Geomatics and Information Science of Wuhan University, 2018, 43(3): 385-391. doi: 10.13203/j.whugis20150176
  • 地貌与水系是地图制图中最主要的自然地理要素,两者紧密配合,构成地形图的基本骨架。长期以来,等高线与河流图形(作为地貌与水系最主要的表示方式或组成部分)的综合问题一直是地理信息和地图制图界的研究热点,在整个地图自动综合中占据重要的地位[1]。对于河流的综合,目前在河流选取方法上取得了较多的成果[2-4],而对河流图形化简的研究较少,通常直接采用常规的曲线化简方法。曲线化简方法主要分为3类:(1)基于几何特征分析的曲线化简方法,这类方法也称为点位信息度量方法[5],即从几何特征角度分析曲线上各点的信息量大小,从而决定该点是否被选取,主要包括D-P法及其扩展方法[6-9]、BLG法[10]、Li-Openshow法[11-12]、渐进化简方法[13]以及基于遗传算法的曲线化简模型[14];(2)基于结构特征分析的曲线化简方法,它通过分析曲线的弯曲结构,进而对弯曲进行提取,分析结构组织与形状特征从而确定弯曲的保留与删除[15-17];(3)基于数学分析的曲线化简方法,通过数学方法来描述曲线的形状复杂度,从而建立曲线形状复杂度与某一指标间的关系,主要有分形分析方法[18-19]和小波分析方法[20-21]

    将以上曲线化简方法应用到河流曲线化简时,会面临两个问题:(1)虽然常规的河流数据表现为二维形式,但河流实质上是三维的,其表现形态应该具有三维特征,而以往化简方法都是在二维上进行处理,并不完全适用于河流曲线的化简。图 1为河流要素分别在二维与三维表达下的形态差别及化简差异。在常规二维曲线化简(图 1(a))中,A处特征明显应得到保留,B处特征不明显应被综合;而在三维曲线化简(图 1(b))中,B处的特征也较为明显,应该被保留。(2)上述化简方法仅仅针对单条河流曲线化简,没有考虑河流之间的汇流结构关系,即支流的汇点与干流相接的拓扑关系,若只针对单条河流曲线进行化简,可能会导致化简后的河流间出现拓扑不一致情况(见图 2),对干流L1曲线化简,删除点P4之后,就会破坏该点所在的汇流结构关系(红圈处)。文献[10]提出基于约束点的两种解决策略:(1)对线要素先分段再用D-P法化简;(2)通过BLG化简法对约束点所在分支点全部选取从而保证约束点不被删除。但是这两种方法都有不足,前者将一整条曲线分割成小段破坏了曲线的原有结构,后者会将本应该化简的点保留下来。

    图  1  河流在二维及三维中的曲线形态

    Figure 1.  River Curves' Morphological Feature in Two-Dimensional and Three-Dimensional

    图  2  河流曲线化简后拓扑不一致情况

    Figure 2.  Topological Inconsistency in River Curves After Simplification

    考虑到河流三维特性及其拓扑结构,本文尝试从三维散点综合的角度进行河流曲线选点及化简,通过对三维Douglas-Peucker(3D D-P)算法进行改进, 提出一种三维散点排队法,力求在化简过程中不但能顾及到河流曲线的三维特征,而且能兼顾河流间的拓扑关系。

    • 3D D-P算法是一种从三维视角对三维离散点集进行特征点选取的方法,选出的散点能最大程度保持三维形态特征。该方法在数字高程模型(digital elevation model, DEM)综合、等高线间接综合和地形特征线提取等方面已取得较好的效果[22-23]。文献[22]通过对D-P算法进行三维扩展提出了3D D-P算法,主要包括首基面构造和原点确定、点子初始排序、点子选取与新基面构造3个过程。鉴于首基面选择的效率及固定原点位置导致靠近原点的特征不够灵敏的情况,文献[23]对传统的3D D-P算法进行改进,提出了“3合1”3D D-P算法,以3个正交的表面分别作为首基面,3个互不重合的点作为原点,先综合再合并。

      “3合1”3D D-P算法能较大地提高综合效率,且能使特征点的选取结果与传统3D D-P方法非常接近,能较好地完成河流曲线化简中三维特征点的选取。但直接将其应用到河流曲线化简仍然存在以下问题:(1)压缩比不一致且大小难以控制,由于河流曲线中的散点特征只受河流曲线本身影响,因此需要将每条河流作为单独的散点集进行综合,这将导致各河流压缩比不一致;此外,由于3D D-P算法是通过阈值确定压缩比,难以得到固定的压缩比,更不用说任意的压缩比。(2)仍然很难解决前述拓扑一致性的问题,即对像河流交汇点等必须要保留的约束点没有更好的处理办法。本文通过对“3合1”3D D-P算法进行改进,提出一种三维散点排队法,并将其应用到河流曲线化简之中。

    • 采用三维散点综合这种间接的方式对河流曲线进行化简,其核心是建立三维散点的选取规则:一是使得选取结果能保持最主要的三维形态特征,通过借鉴3D D-P算法的选点思想实现; 二是能保证原有的拓扑结构不被破坏,实质是要保证所有的约束点优先被选取。本文采用排队的策略改进3D D-P算法,先对所有散点按照其三维特征依次进行排队,使得在排队过程中既能顾及到三维形态特征,又能通过约束点置于队列首部保证约束点不被删除,进而保证河流间拓扑结构的一致性。考虑到河流的数据通常为二维的线数据,因此整个河流曲线化简过程除了核心的三维散点排队过程外,还包括河流曲线与三维散点的转换过程,分为河流三维散点化与河流曲线重构二个步骤。

      河流三维散点化的关键在于对河流曲线上的点增加高程值,常用的方法是通过地形数据插值。文献[24]建议对河流的源点、汇点采用反距离加权插值方法,对内部点采用分段线性插值,该方法能在保证河流高程值精度的同时确保河流高程逻辑的正确性。由于综合后的散点失去在原始河流曲线中的次序关系,为了建立与原始河流相一致的次序关系,可将河流曲线上的散点从源点到汇点依次编码,综合之后再依据编码的顺序利用散点重构河流曲线。

    • 按照“3合1”3D D-P算法的首基面选取与处理方式,三维散点排队方法首先针对3个首基面分别进行3次初始排队; 在初始排队后,再进行“3合1”队列合并; 最后为了保证河流之间的拓扑结构,对合并队列进行约束点位置调整。

    • 定义1:分裂点,也叫特征点,是用于点集分裂、构建新基面的点,由散点坐标、点面距值、点在原始点集中的位置以及计算该点所用基面的锚点和漂浮点在原始点集中的位置5部分信息组成。分裂点结构记作s={pdmfr}。其中,s为分裂点结构;p为散点;d为点到基面的距离;m为点在原始点集中的位置;fr分别为计算该点所用基面的锚点和漂浮点的位置。

      定义2:分裂点候选集,存放已被计算但还未被选中的分裂点,是当前分裂点选取的备选集合,记为S={si|i=1, 2 … n}。

      定义3:散点队列,指散点按照特征大小计算构成的有序集合,每选出一个分裂点就将其对应的散点加入队列中,记为Q={qi|i=1, 2 … n}。

      定义4:原始三维离散点集,记为P={pi|i=1, 2 … n}。

    • 初始排队采用“自上而下”的选点思路,先选出三维特征最大的点,再选特征次大的点,依此类推直到最后一个特征最小的点。在每次选取过程中,先计算分裂点并将其加入分裂点候选集中,再从分裂点候选集中选取当前三维特征最大的点。具体过程包括当前处理子集构造、分裂点计算和当前分裂点选取与入队3步。

    • 1) 当前处理子集构造。在每一次分裂点计算之前,首先需要构造当前处理子集,当前处理子集由上一次选取的分裂点结构中的自身位置以及基面锚点与漂浮点位置确定。设分裂点s={pdmfr},则可同时获得两个当前处理子集,分别为(fm)和(mr)。当第一次构造当前处理子集时,当前处理子集只有一个且为整个点集,即(1,n),n为点数。如图 3所示(以二维点为例),对除AB外的点进行排队,整个初始散点序列为ACDEFGHIJKLMNB,图 3中黑色虚线为基线,绿色虚线为点面距,字母后面的数字表示该点初始序列。显然,第一次构造的当前处理子集只有1个且为(1, 14),对应的点分别为AB

      图  3  散点初始排队过程示意图

      Figure 3.  Initial Queuing Process of Scatter Point

      2) 分裂点计算。遍历点集P,确定从pfpmpmpr的两个当前处理子集,并分别为其构造新基面,随后依次计算各子集内所有点到基面的点面距,比较点面距的大小,从中分别选出点面距最大的点pipj。设其点面距分别为didj,则对应的分裂点分别为si={pidiifm}和sj={pjdjjmr},之后将其加入分裂点候选集S中。如图 3所示,首次选出距离最大点K,其值为dk,分裂点结构值为{P10dk,10,1,14},将其加入集合S中。

      3) 当前分裂点选取与散点入队。从集合S中选择点面距最大的分裂点smax,并从smax结构取出散点pmax (pmax=smaxp),将其加入散点队列Q中,并将smax从集合S中移除;然后返回步骤1),构造下一次的两个当前处理子集。由于当前集合S中只有一个分裂点sK,因此将其直接加入队列Q,且下一循环中当前处理子集为(1,10)和(10,14)。

      循环执行以上3个步骤,直到所有点都加入队列Q中,算法结束。图 3的排队结果如图 4(a)所示,散点上的数字表示该点排序位置顺序,点AB无条件置于队列首部。

      图  4  散点初始排队过程示意图及结果的二叉树表达

      Figure 4.  Initial Queuing Process of Scatter Point and the Result Expressed by Binary Tree

    • 初始排队是将点到基面的点面距作为点子排队的主要依据,且考虑了分层处理过程中形成的散点之间的层次关系。因此,其并不是完全按照距离优先或是层次优先排队,而是在“父子”关系约束下的距离优先选取与排队,这种选点思路体现了形态特征的层次嵌套性。如图 4(b)所示(结点上方的数字表示排队顺序),点JD为“父子”结点,即使子结点D的当前特征值(点面距)比父结点J大,父结点J要比子结点D先选取。这是因为子结点所蕴含的特征是父结点蕴含的特征的一个子集,父结点理应更重要,更优先选取;而对于点MD,即便点M的逻辑层次高于点D,点M仍然排在点D之后,这种非“父子”关系的层次关系不会影响排队结果。

      对于初始排队的效率来说,其时间复杂度取决于分裂点的计算和当前分裂点选取两个过程。从算法原理可知,分裂点计算需要遍历一次当前处理子集,而当前处理子集是逐渐收缩的,其集合点数最多为n;当前分裂点选取只需遍历一次分裂点候选集合,分裂点候选集合中的点数是先增加后减少的,最大的可能性为n/2,故选取一个点的平均时间复杂度为O(n),整个初始排队过程的时间复杂度为O(n2)。

    • 经过3次初始排队后,得到了3个初始队列。因为3个首基面面积差异描述了散点在3个维度上的总体空间分布形态,故可用首基面面积为权重对3次排队结果的位置顺序信息进行加权求和重新计算位置顺序。

      $$ {{P}_{S}}=\frac{\sum\limits_{i=1}^{3}{{{P}_{{{S}_{i}}}}\times {{S}_{i}}}}{\sum\limits_{i=1}^{3}{{{S}_{i}}}} $$ (1)

      式中,PS表示散点合并后的位置值,值越小,散点位置越靠前,散点特征越大;PSi表示各次排队后的位置值,其值根据位置顺序而来,分别为1, 2, 3…nSi表示各次排队的首基面面积大小。

    • 为了保持河流综合前的拓扑一致性,需要先确定包括河流源点、汇点和交汇点等所有约束点,然后重新调整这3类点的位置,排到队列的首部,约束点之间的先后顺序不影响结果。

      约束点的寻找过程为:一条河流曲线的源点与汇点可以通过曲线的首末点确定;而交汇点的确定则需要通过判断各条河流曲线与其他河流汇点的点线拓扑关系。如果河流数据没有方向,还要让所有的源点参与判断。如果一条河流上的点与其他河流的汇点重合,则该点就是此河流上的交汇点,由此找到所有的交汇点,确定所有的源点、汇点以及交汇点后,将其标识为约束点。

      约束点位置调整后得到最终的按照散点特征的排队结果。此时,只需根据散点压缩比,就可以得到散点综合结果,并且可同时得到任意多个不同压缩比的综合结果,这显然比常规3D D-P算法通过输入一个阈值得到一个结果更合理、高效。

    • 实验数据采用安徽某丘陵地区1:1万的水系数据,等高线间距为10 m,河流25条,交汇点数为24,河流二维总长度为36 074.4 m,三维总长度37 236.9 m。分别采用D-P法[6]和本文方法对实验数据进行5个尺度的化简。由于D-P法是通过阈值控制化简程度(压缩率),而本文方法可以直接得到任意压缩率的化简结果,因此先采用阈值为0.1、0.5、1、2、5的D-P法化简,在得到各化简结果并计算压缩率之后,再以该压缩率采用本文方法进行化简。

    • 从整体信息量上看,曲线特征的保持可通过曲线的线要素密度来定量表达,即在化简过程保留的点数相同的情况下,曲线越长,保留的点信息量越大、特征度越高,整体特征保持越好[25]。因此,本文利用化简后河流的二维长度和三维长度来分别评价其化简结果的二、三维特征保持情况。

      将本文方法与D-P方法在5个不同尺度下进行河流化简,对化简后的河流总长度进行统计,结果见表 1。从表 1中可知,对二维长度来说,D-P法化简结果比本文方法化简结果的长度更长;对三维长度来说,本文方法化简结果比D-P法化简结果长度更长。因此,D-P对二维特征的保持效果较好,而本文方法对三维特征保持效果更好。

      表 1  两种方法在5种化简尺度后的河流总长度对比

      Table 1.  Contrast Length of River System Using Two Methods on Five Generalization Scales

      压缩比例(%)
      (阈值)
      二维长度/m 三维长度/m
      D-P方法 本文方法 D-P方法 本文方法
      89.6(0.1) 35 922.2 35 899.7 36 930.0 37 011.8
      73.1(0.5) 35 978.6 35 960.2 37 027.9 37 097.6
      61.5(1) 36 007.7 35 991.9 37 081.4 37 139.6
      44.7(2) 36 031.1 36 018.8 37 128.5 37 173.7
      26.8(5) 36 053.3 36 043.2 37 172.2 37 205.6
    • 通过对两种化简方法在5个尺度化简结果上的交汇点拓扑一致性进行统计(见表 2),发现本文方法在各个尺度所有交汇点上都没有出现拓扑不一致,而D-P法在各个尺度上都出现拓扑不一致,且随着压缩比例的增大,其比例逐渐增加。如图 5所示,红色曲线为D-P法综合结果,绿色曲线为本文方法综合结果,黑色曲线为原始河流,本文方法能在河流交汇点处保持拓扑一致性,而D-P法因为删除了交汇点处对应的干流点破坏了原有的拓扑一致性。

      表 2  两种方法在5种化简尺度后的拓扑一致性对比

      Table 2.  Contrast Topological Consistency Using Two Methods on Five Generalization Scales

      压缩比例(%)
      (阈值)
      D-P方法拓扑不一致 本文方法拓扑不一致
      数量 比例(%) 数量 比例(%)
      89.6(0.1) 18 75.0 0 0
      73.1(0.5) 17 70.8 0 0
      61.5(1) 13 54.2 0 0
      44.7(2) 9 37.5 0 0
      26.8(5) 5 20.8 0 0

      图  5  本文方法与D-P法化简后拓扑一致性对比

      Figure 5.  Contrast Results of Topological Consistency Using the Proposed Method and D-P Algorithm

    • 本文提出了基于三维散点排队的河流曲线化简方法,在“3合1”3D D-P算法基础上提出了三维散点排队方法,通过对三维散点进行综合,进而实现对河流曲线的三维形态化简。结果显示,本文方法综合精度可靠,能最大程度地保留三维形态,且能保证河流间的拓扑关系,避免常规河流化简出现的拓扑不一致现象,还可以进行快速多尺度河流化简。该方法的不足之处在于常规方法河流数据大多不包含高程信息,因此在化简之前需要先将河流曲线数据三维化。

参考文献 (25)

目录

    /

    返回文章
    返回