留言板

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

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

Delaunay三角网支持下的海图等深线化简

李靖涵 武芳 杜佳威 巩现勇 行瑞星

李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星. Delaunay三角网支持下的海图等深线化简[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
引用本文: 李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星. Delaunay三角网支持下的海图等深线化简[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
LI Jinghan, WU Fang, DU Jiawei, GONG Xianyong, XING Ruixing. Chart Depth Contour Simplification Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
Citation: LI Jinghan, WU Fang, DU Jiawei, GONG Xianyong, XING Ruixing. Chart Depth Contour Simplification Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223

Delaunay三角网支持下的海图等深线化简

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

重点基础研究发展计划 613317

详细信息

Chart Depth Contour Simplification Based on Delaunay Triangulation

Funds: 

Basic Research Program of China 613317

More Information
图(9) / 表(2)
计量
  • 文章访问数:  256
  • HTML全文浏览量:  11
  • PDF下载量:  112
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-29
  • 刊出日期:  2019-05-05

Delaunay三角网支持下的海图等深线化简

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

    重点基础研究发展计划 613317

    作者简介:

    李靖涵, 博士生, 主要从事制图综合理论与方法研究。lijinghan2008jd@163.com

    通讯作者: 武芳, 博士, 教授。wufang_630@126.com
  • 中图分类号: P283;P229

摘要: 等深线化简是海图综合的重要研究内容。针对现有化简方法存在的化简弯曲识别不准确、化简不彻底等问题,提出了一种Delaunay三角网支持下的等深线化简算法。首先,对等深线构建约束Delaunay三角网,实现了等深线弯曲结构的二叉树表达;其次,基于约束Delaunay三角网结构,改善了等深线上需要化简弯曲的识别方法;最后,设计了多种化简手段,建立了新的等深线化简模型,实现了对等深线形状的彻底化简。实验结果表明,化简结果能够满足航行安全要求,等深线的主要弯曲特征得到了有效保持和清晰表达,化简精度符合制图要求,且能够有效避免自交。

English Abstract

李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星. Delaunay三角网支持下的海图等深线化简[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
引用本文: 李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星. Delaunay三角网支持下的海图等深线化简[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
LI Jinghan, WU Fang, DU Jiawei, GONG Xianyong, XING Ruixing. Chart Depth Contour Simplification Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
Citation: LI Jinghan, WU Fang, DU Jiawei, GONG Xianyong, XING Ruixing. Chart Depth Contour Simplification Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
  • 等深线形状化简在海图制图和海洋GIS多尺度变换中具有重要应用。由于海图等深线化简的复杂性,在海图生产中等深线化简仍然主要依靠手工作业完成,这严重制约了海图的生产效率和制图质量。等深线化简除了需要满足曲线化简的一般要求外,还要确保航行安全,即必须满足“扩前缩深”的原则,因而一般的曲线化简算法[1-4]很难应用于等深线化简。为此,国内外学者针对等深线化简问题进行了研究,常见的等深线化简方法有基于弯曲的化简方法[5]、改进D-P算法[6]、snake模型[7-8]、双缓冲区变换算法[9]等。其中,基于snake模型的化简结果比较光滑,但计算过程复杂;双缓冲区算法化简不够彻底;基于弯曲的化简算法中需要化简弯曲的探测不够准确,弯曲化简处理方法也比较单一。另外,当前算法也无法与尺度建立明确客观的关系。

    本文利用约束Delaunay三角网(constrained Delaunay triangulation, CDT)在曲线结构化和邻近关系表达方面的优势,提出了一种CDT支持下的海图等深线化简算法。

    • 弯曲是等深线化简的基本单元[10]。因此,曲线结构化的主要目的是对等深线弯曲的识别与组织。与其他方法相比,基于CDT的曲线结构化具有两方面优势:(1)基于CDT识别的弯曲更符合视觉感受,而且能够建立弯曲间的层次化结构;(2)有利于探测曲线上节点间的邻近关系。因此,本文选择基于CDT的曲线结构化方法。

      CDT的构建原理和曲线结构化方法可参考文献[11]。本文将CDT中的三角形分为3类:Ⅰ类三角形,只包含一条非约束边的三角形;Ⅱ类三角形,包含两条非约束边的三角形;Ⅲ类三角形,三条边都是非约束边的三角形。

    • 为方便叙述,首先定义两个弯曲概念。

      1) 完整弯曲,指基于CDT识别的弯曲单元。

      2) 非完整弯曲,指完整弯曲上的部分曲线段构成的弯曲。

      在比例尺缩小过程中,等深线的细节弯曲是逐渐退化消失的,故在目标比例尺下,需要化简的等深线弯曲除了完整弯曲外,还存在一些没有完全退化消失的非完整弯曲。然而,当前需要化简的等深线弯曲识别是以完整弯曲为基本识别单元的,故在识别过程中会遗漏一些非完整弯曲。如图 1(a)所示,bBC是一个较大的完整弯曲,按照当前识别策略,bBC需要保留,但弯曲内却存在需要化简的非完整弯曲(虚线椭圆标志部分)。为了避免上述问题,本文改进了识别策略,将需要化简的等深线弯曲分为3类:(1)微小完整弯曲,指基于CDT识别的较小完整弯曲;(2)微小非完整弯曲,指较大完整弯曲上局部无法清晰表达的非完整弯曲,如图 1(b)填充区域关联的曲线段;(3)狭窄“瓶颈”,指因间隙较小而无法清晰表达的等深线“瓶颈”,如图 1(c)填充区域。

      图  1  化简弯曲识别

      Figure 1.  Recognition of Simplifying Bends

    • 等深线上需要化简的微小完整弯曲的识别方法为:对识别的完整弯曲的几何特征进行定量评价,根据评价结果判断其是否需要化简。常用的弯曲特征参量有弯曲面积、弯曲高、基线长度、弧长、骨架线长度、弯曲曲率等,本文选取弯曲高和弯曲面积作为弯曲几何特征的量化评价指标,因为弯曲高与曲线化简精度相关[12],弯曲面积反映了弯曲的大小。两参量对应阈值THTA的计算公式为:

      $${T_H} = \alpha \times S \times w $$ (1)
      $${T_A} = \beta \times {A_{{\rm{SVO}}}} \times {S^2} $$ (2)

      式中,S表示目标比例尺分母;w表示图上曲线的宽度;ASVO表示图上最小可视目标(smallest visual object,SVO)的面积;αβ表示调节系数,可根据化简程度要求进行设置。

    • 微小非完整弯曲和狭窄“瓶颈”的识别步骤为:

      1)对三角形进行筛选。筛选规则为:(1)非约束边的长度小于阈值Linvisual的为Ⅰ类三角形;(2)两条非约束边长度都小于阈值Linvisual的为Ⅱ类三角形;(3)非分叉边的长度小于阈值Linvisual的为Ⅲ类三角形。Linvisual的计算公式为:

      $${L_{{\rm{invisual}}}} = S \times \left( {w + \alpha {d_{{\rm{visual}}}}} \right) $$ (3)

      式中,dvisual为图上最小可辨距离(通常取0.4 mm);α为调节系数。

      2)对筛选的三角形按照邻近关系进行合并,形成若干区域多边形,本文称之为化简区域。化简区域可分为两类:Ⅰ类,区域多边形由等深线上的连续节点构成,如图 2(a)中标号为1的填充区域;Ⅱ类,区域多边形由等深线上的非连续节点构成,如图 2(a)中标号为2的填充区域。

      图  2  化简区域识别

      Figure 2.  Recognition of Simplifying Areas

      3)“空白”区域处理。“空白”区域指由化简区域和等深线围成的区域,如图 2(a)中标号为3、4的区域。处理规则为:判断“空白”区域内是否包含水深注记,若不包含,则将该空白区域合并到邻近的化简区域。“空白”区域处理的目的是为了减少化简区域的破碎程度。图 2(b)为处理后的化简区域。

      4)化简弯曲类别判断。若化简区域为Ⅰ类,则该化简区域关联的等深线曲线段为微小非完整弯曲;若为Ⅱ类,则该化简区域关联的等深线曲线段为狭窄“瓶颈”(图 2(c))。

      5)微小非完整弯曲识别结果优化。识别的微小非完整弯曲中,会存在一些弯曲高很小的微小非完整弯曲,需要对其进行剔除。剔除的方法为:计算微小非完整弯曲的高度h和基线长度l的比值h/l,若该比值小于规定的阈值,则将其剔除。

    • 本文针对基于CDT的弯曲识别特点及等深线化简要求设计了以下弯曲化简方法:

      1)弯曲删除。

      2)夸大。包括弯曲的夸大和“瓶颈”的夸大。夸大方法为:首先基于三角网提取弯曲或“瓶颈”的骨架线,然后构建骨架线的缓冲区多边形,缓冲区半径为:

      $$R = 0.5\left( {{d_{{\rm{min}}}} + w} \right) \times S $$ (4)

      式中,dmin表示最小分辨距离或规定的最小间隔距离;w表示线的宽度。计算曲线上相应节点到缓冲区边界上的投影点,这些投影点构成的曲线段即为夸大后的局部形态(图 3(a)中的虚线)。

      图  3  弯曲化简处理方法

      Figure 3.  Means of Bend Simplification

      3)弯曲凸壳化。弯曲凸壳化指删除弯曲上的部分节点,使弯曲与基线构成的多边形为凸多边形,如图 3(b)所示。凸壳化处理的目的是消除弯曲上的小“抖动”。

      4)分裂。分裂是将等深线在“瓶颈”位置分解为两条等深线的化简操作,如图 3(c)所示。

    • 考虑等深线化简的“扩浅缩深”原则,其化简过程如图 4所示。具体步骤如下。

      图  4  等深线化简过程

      Figure 4.  Workflow of Depth Contour Simplification

      1)基于Delaunay三角网对等深线进行结构化。

      2)识别出深水侧需要化简的等深线弯曲,对识别出的微小完整弯曲、非完整弯曲进行删除,对“瓶颈”进行分裂操作。

      3)对等深线重新结构化,并分别在等深线两侧构建弯曲二叉树。

      4)识别浅水侧需要化简的等深线弯曲,对识别的“瓶颈”进行夸大处理。对需要化简的完整弯曲和非完整弯曲,判断异侧邻近弯曲的面积或深度是否满足删除阈值,若满足,则删除异侧邻近弯曲;否则,对微小非完整弯曲进行夸大处理,对微小完整弯曲进行凸壳化处理。

    • 利用C#语言基于ArcEngine二次开发平台对本文所提的等深线化简算法进行了实现。

      实验数据为从1:40 000的海图上选取的一条形态曲折复杂的等深线(图 5)。为清晰显示化简结果,各化简阈值参数设置为:线宽0.7 mm,弯曲高度化简阈值TH为2倍线宽,面积化简阈值TA为4倍SVO面积,异侧弯曲删除阈值分别为1.5TH和1.5TA,阈值Linvisual为2倍线宽。

      图  5  实验数据

      Figure 5.  Test Data

      图 6为实验得到的1:10万(部分数据)、1:20万、1:30万、1:40万4个目标比例尺下的化简结果(粗线表示),细线为原始等深线。从图 6中可以看出,各比例尺的等深线化简结果都位于原始等深线的深水侧,满足“扩浅缩深”的要求。各化简结果在目标比例尺下的主要形态特征得到了有效保持,次要、微小的细节特征得到了删除,对航行安全有影响的微小弯曲特征得到了夸大处理,达到了等深线化简的目的。

      图  6  多尺度等深线化简结果

      Figure 6.  Simplification Results of Multi-scaleDepth Contours

      为了验证本文算法的优越性,选用等深线化简中最具代表性的双缓冲区算法进行对比实验。图 7为利用双缓冲区算法得到的1:10万和1:20万的化简结果,其中1:10万显示了部分数据。从视觉上看,两种算法都满足“扩浅缩深”的要求,但在化简形态方面,本文算法更具优势。首先,本文算法的化简结果在目标比例尺下能满足清晰表达的制图要求,化简更为彻底,而双缓冲区化简结果仍存在不可清晰表达的细节没有被化简的情况(图 7中圆圈所示);其次,本文化简结果有效地删除了细小弯曲,保留了主要的弯曲特征,而双缓冲区化简结果中存在小的弯曲特征被保留(图 7中虚线椭圆框所示)而大的弯曲(图 7中箭头所指处)被消除的情况;最后,本文化简结果保留了弯曲的凸凹性,而双缓冲区化简结果存在弯曲凸凹性发生变化的状况。图 8(a)8(b)分别为双缓冲区算法和本文算法对图 7中矩形框标注区域的化简结果放大图,可以看出,原始等深线上的凹弯曲经过双缓冲区算法化简后变成了尖凸弯曲。

      图  7  双缓冲区化简结果

      Figure 7.  Simplification Results of Double Buffer Method

      图  8  两种算法的局部形状对比

      Figure 8.  Comparison of Local Shapes by Two Algorithms

      位置误差[13]是评价曲线化简前后的整体位置位移指标,反映了曲线的化简精度。本文选用位置误差对化简结果的位置精度进行评价。两种算法化简结果的位置误差统计如表 1所示。从表 1中可以看出,双缓冲区算法在位置精度上要高于本文算法,一方面是因为双缓冲区算法没有明确的尺度概念,得到的化简结果并非对应目标比例尺的结果;另一方面,双缓冲区算法只是对深水侧弯曲进行了化简,并没有对浅水侧弯曲进行化简处理,化简不够彻底。但从化简结果精度来看,本文方法1:10万和1:20万的化简结果位置误差分别为19.6 m和71.8 m,对应到图上的位置误差分别为0.20 mm和0.36 mm,符合制图精度要求。

      表 1  化简结果位置精度统计表

      Table 1.  Position Accuracies of Simplification Results

      算法 位置误差/m 图上位置误差/mm
      1:10万 1:20万 1:10万 1:20万
      本文算法 19.6 71.8 0.20 0.36
      双缓冲区算法 10.5 38.6 0.11 0.19

      节点压缩效率是等深线化简结果评价的重要方面。表 2列出了化简结果的节点压缩情况,原始等深线的节点数为1 044个。从统计结果可以看出,本文化简算法有效压缩了节点数据量,而双缓冲区算法由于构建缓冲区边界时构造了新的节点,使得化简结果的节点数不减反增。

      表 2  节点压缩统计表

      Table 2.  Point Numbers of Simplification Results

      算法 1:10万 1:20万
      本文算法 542 259
      双缓冲区算法 3 056 2 113

      此外,由于约束Delaunay三角网无重复、无间隙的平面剖分性质,任何一个三角形的边都不会穿越曲线本身,因此通过连接弯曲基线(实为三角形的一条边)进行弯曲删除或连接两个邻近点(同为三角形的一条边)进行分裂操作都不会引起自交问题。另外,由于对深水侧需要化简的弯曲进行了删除处理(弯曲删除和“瓶颈”分裂),使得深水侧任一非约束边连接的两邻近节点间距都大于Linvisual,而对浅水侧的弯曲或“瓶颈”进行夸大时,缓冲区半径小于等于Linvisual的一半,使得夸大后的局部曲线段也不可能与邻近的曲线段产生自交。因此,本文算法能够有效避免自交拓扑错误的发生。

      与双缓冲区算法相比,本文算法中的参数与比例尺建立了客观联系。曲线化简可视为在目标比例尺图上用一定宽度的铅笔重描曲线的过程[12]TH相当于模拟图上线的宽度,TA相当于模拟目标比例尺下最小表达弯曲的大小,Linvisual相当于模拟目标比例尺下小于人眼分辨力或容忍度的参数。本文通过删除位于线体内的弯曲、无法清晰表达的微小非完整弯曲及夸大重要的无法清晰表达的弯曲和“瓶颈”进行等深线化简,其实就是在模拟铅笔在目标比例尺图上重描的过程。因此,该算法具有尺度驱动性。

      为了检验算法在等深线集化简中的应用效果,本文对1:4万海图上的部分等深线数据进行了化简实验。图 9为1:8万和1:20万的化简结果,放大图与目标比例尺下的实际尺寸相同。从图 9中可以看出,等深线的主要弯曲特征都能够清晰地表达,曲线形态较为光滑,而且没有自交的拓扑错误发生,有效地保持了海底地形的主要特征。

      图  9  等深线集化简结果

      Figure 9.  Simplification Results of Depth Contour Dataset

    • 本文考虑等深线化简的特殊要求,提出了一种约束Delaunay三角网支持下的等深线化简算法。实验结果表明:

      1)与尺度建立了明确的关系,具有尺度驱动性。

      2)满足“扩浅缩深”的要求,能够确保航行安全。

      3)等深线主要弯曲特征得到了有效保持和清晰表达,位置精度符合要求,且能够避免自交。

      由于本文在进行等深线化简时没有考虑邻近等深线的影响,对等深线集进行化简时存在发生空间冲突的可能,未来将在这方面进行研究,以进一步改善算法的实用性。

参考文献 (13)

目录

    /

    返回文章
    返回