-
等深线形状化简在海图制图和海洋GIS多尺度变换中具有重要应用。由于海图等深线化简的复杂性,在海图生产中等深线化简仍然主要依靠手工作业完成,这严重制约了海图的生产效率和制图质量。等深线化简除了需要满足曲线化简的一般要求外,还要确保航行安全,即必须满足“扩前缩深”的原则,因而一般的曲线化简算法[1-4]很难应用于等深线化简。为此,国内外学者针对等深线化简问题进行了研究,常见的等深线化简方法有基于弯曲的化简方法[5]、改进D-P算法[6]、snake模型[7-8]、双缓冲区变换算法[9]等。其中,基于snake模型的化简结果比较光滑,但计算过程复杂;双缓冲区算法化简不够彻底;基于弯曲的化简算法中需要化简弯曲的探测不够准确,弯曲化简处理方法也比较单一。另外,当前算法也无法与尺度建立明确客观的关系。
本文利用约束Delaunay三角网(constrained Delaunay triangulation, CDT)在曲线结构化和邻近关系表达方面的优势,提出了一种CDT支持下的海图等深线化简算法。
-
为方便叙述,首先定义两个弯曲概念。
1) 完整弯曲,指基于CDT识别的弯曲单元。
2) 非完整弯曲,指完整弯曲上的部分曲线段构成的弯曲。
在比例尺缩小过程中,等深线的细节弯曲是逐渐退化消失的,故在目标比例尺下,需要化简的等深线弯曲除了完整弯曲外,还存在一些没有完全退化消失的非完整弯曲。然而,当前需要化简的等深线弯曲识别是以完整弯曲为基本识别单元的,故在识别过程中会遗漏一些非完整弯曲。如图 1(a)所示,bBC是一个较大的完整弯曲,按照当前识别策略,bBC需要保留,但弯曲内却存在需要化简的非完整弯曲(虚线椭圆标志部分)。为了避免上述问题,本文改进了识别策略,将需要化简的等深线弯曲分为3类:(1)微小完整弯曲,指基于CDT识别的较小完整弯曲;(2)微小非完整弯曲,指较大完整弯曲上局部无法清晰表达的非完整弯曲,如图 1(b)填充区域关联的曲线段;(3)狭窄“瓶颈”,指因间隙较小而无法清晰表达的等深线“瓶颈”,如图 1(c)填充区域。
-
等深线上需要化简的微小完整弯曲的识别方法为:对识别的完整弯曲的几何特征进行定量评价,根据评价结果判断其是否需要化简。常用的弯曲特征参量有弯曲面积、弯曲高、基线长度、弧长、骨架线长度、弯曲曲率等,本文选取弯曲高和弯曲面积作为弯曲几何特征的量化评价指标,因为弯曲高与曲线化简精度相关[12],弯曲面积反映了弯曲的大小。两参量对应阈值TH和TA的计算公式为:
$${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的填充区域。
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)弯曲凸壳化。弯曲凸壳化指删除弯曲上的部分节点,使弯曲与基线构成的多边形为凸多边形,如图 3(b)所示。凸壳化处理的目的是消除弯曲上的小“抖动”。
4)分裂。分裂是将等深线在“瓶颈”位置分解为两条等深线的化简操作,如图 3(c)所示。
-
考虑等深线化简的“扩浅缩深”原则,其化简过程如图 4所示。具体步骤如下。
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倍线宽。
图 6为实验得到的1:10万(部分数据)、1:20万、1:30万、1:40万4个目标比例尺下的化简结果(粗线表示),细线为原始等深线。从图 6中可以看出,各比例尺的等深线化简结果都位于原始等深线的深水侧,满足“扩浅缩深”的要求。各化简结果在目标比例尺下的主要形态特征得到了有效保持,次要、微小的细节特征得到了删除,对航行安全有影响的微小弯曲特征得到了夸大处理,达到了等深线化简的目的。
为了验证本文算法的优越性,选用等深线化简中最具代表性的双缓冲区算法进行对比实验。图 7为利用双缓冲区算法得到的1:10万和1:20万的化简结果,其中1:10万显示了部分数据。从视觉上看,两种算法都满足“扩浅缩深”的要求,但在化简形态方面,本文算法更具优势。首先,本文算法的化简结果在目标比例尺下能满足清晰表达的制图要求,化简更为彻底,而双缓冲区化简结果仍存在不可清晰表达的细节没有被化简的情况(图 7中圆圈所示);其次,本文化简结果有效地删除了细小弯曲,保留了主要的弯曲特征,而双缓冲区化简结果中存在小的弯曲特征被保留(图 7中虚线椭圆框所示)而大的弯曲(图 7中箭头所指处)被消除的情况;最后,本文化简结果保留了弯曲的凸凹性,而双缓冲区化简结果存在弯曲凸凹性发生变化的状况。图 8(a)、8(b)分别为双缓冲区算法和本文算法对图 7中矩形框标注区域的化简结果放大图,可以看出,原始等深线上的凹弯曲经过双缓冲区算法化简后变成了尖凸弯曲。
位置误差[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中可以看出,等深线的主要弯曲特征都能够清晰地表达,曲线形态较为光滑,而且没有自交的拓扑错误发生,有效地保持了海底地形的主要特征。
-
本文考虑等深线化简的特殊要求,提出了一种约束Delaunay三角网支持下的等深线化简算法。实验结果表明:
1)与尺度建立了明确的关系,具有尺度驱动性。
2)满足“扩浅缩深”的要求,能够确保航行安全。
3)等深线主要弯曲特征得到了有效保持和清晰表达,位置精度符合要求,且能够避免自交。
由于本文在进行等深线化简时没有考虑邻近等深线的影响,对等深线集进行化简时存在发生空间冲突的可能,未来将在这方面进行研究,以进一步改善算法的实用性。
-
摘要: 等深线化简是海图综合的重要研究内容。针对现有化简方法存在的化简弯曲识别不准确、化简不彻底等问题,提出了一种Delaunay三角网支持下的等深线化简算法。首先,对等深线构建约束Delaunay三角网,实现了等深线弯曲结构的二叉树表达;其次,基于约束Delaunay三角网结构,改善了等深线上需要化简弯曲的识别方法;最后,设计了多种化简手段,建立了新的等深线化简模型,实现了对等深线形状的彻底化简。实验结果表明,化简结果能够满足航行安全要求,等深线的主要弯曲特征得到了有效保持和清晰表达,化简精度符合制图要求,且能够有效避免自交。Abstract: Automated depth contour simplification is one of the common studying content in chart generalization. There are some problems such as inaccurately recognized bends and incompletely simplified bends in existing simplification methods. To overcome the drawbacks, a simplification method based on constrained Delaunay triangulation (CDT) is proposed. Firstly, CDT is constructed to achieve the binary tree representation of depth contour. Secondly, detection of bends which needs to be simplified is improved based on CDT. Finally, variety of generalization tools are designed and a new simplification model is built to realize the complete simplification of bends on depth contour. Tests illustrate that the proposed method meets navigation safety requirements, and the main bend characters are retained and represented clearly. The position accuracy meet the request of chart production. Besides, self-intersect can be avoided validly.
-
Key words:
- depth contour /
- curve simplification /
- cartographic generalization /
- marine topography
-
表 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 节点压缩统计表
Table 2. Point Numbers of Simplification Results
算法 1:10万 1:20万 本文算法 542 259 双缓冲区算法 3 056 2 113 -
[1] Douglas D H, Peucker T K.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line for Its Caricature[J].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 Geographical Information Science, 1992, 6(5):373-389 doi: 10.1080/02693799208901921 [3] 李成名, 郭沛沛, 殷勇, 等.一种顾及空间关系约束的化简算法[J].测绘学报, 2017, 46(4):498-506 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201704013 Li Chengming, Guo Peipei, Yin Yong, et al.A Line Simplification Algorithm Considering Spatial Relations Between Two Lines[J].Acta Geodaetica et Cartographica Sinica, 2017, 46(4):498-506 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=chxb201704013 [4] 翟仁健, 武芳, 朱丽, 等.利用地理特征约束进行曲线化简[J].武汉大学学报∙信息科学版, 2009, 34(9):1021-1024 http://ch.whu.edu.cn/CN/abstract/abstract1364.shtml Zhai Renjian, Wu Fang, Zhu Li, et al.Line Simplification Method Based on Geographic Feature Constraint[J].Geomatics and Information Science of Wuhan University, 2009, 34(9):1021-1024 http://ch.whu.edu.cn/CN/abstract/abstract1364.shtml [5] 何桂敏, 顾锦华, 林林.基于曲线特征的等深线自动综合方法研究[J].海洋测绘, 2014, 34(5):38-41 doi: 10.3969/j.issn.1671-3044.2014.05.010 He Guimin, Gu Jinhua, Lin Lin.Research on Depth Contour Generalization Method Based on Curve Characteristic[J].Hydrographic Surveying and Charting, 2014, 34(5):38-41 doi: 10.3969/j.issn.1671-3044.2014.05.010 [6] 张黎.等深线的形状化简[J].海洋测绘, 1995, 15(3):21-25 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK199500238885 Zhang Li.Shape Simplification of Depth Contour[J].Hydrographic Surveying and Charting, 1995, 15(3):21-25 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK199500238885 [7] Guilbert E, Lin Hui.Isobathymetric Line Simplification with Conflict Removal Based on a B-spline Snake Model[J].Marine Geodesy, 2007, 30:169-195 doi: 10.1080/01490410701296697 [8] 温连发, 张立华, 贾帅东.蛇模型在等深线自动化简中的应用[J].海洋测绘, 2016, 36(5):15-18 doi: 10.3969/j.issn.1671-3044.2016.05.004 Wen Lianfa, Zhang Lihua, Jia Shuaidong.Application of Snake Model in Auto Simplification of a Depth-Contour[J].Hydrographic Surveying and Charting, 2016, 36(5):15-18 doi: 10.3969/j.issn.1671-3044.2016.05.004 [9] Simth S.The Navigation Surface: A Multipurpose Bathymetric Database[D].New Hampshire: University of New Hampshire, 2003 [10] 王厚祥, 李进杰.海图制图综合[M].北京:测绘出版社, 1999 Wang Houxiang, Li Jinjie.Generalization of Nautical Charts[M].Beijing:Surveying and Mapping Press, 1999 [11] 艾廷华, 郭仁忠, 刘耀林.曲线弯曲深度层次结构的二叉树表达[J].测绘学报, 2001, 30(4):343-348 doi: 10.3321/j.issn:1001-1595.2001.04.013 Ai Tinghua, Guo Renzhong, Liu Yaolin.A Binary Tree Representation of Curve Hierarchical Structure in Depth[J].Acta Geodaetica et Cartographica Sinica, 2001, 30(4):343-348 doi: 10.3321/j.issn:1001-1595.2001.04.013 [12] Ai Tinghua, Ke Shu, Yang Min, et al.Envelope Generation and Simplification of Polylines Using Delaunay Triangulation[J].International Journal of Geographical Information Science, 2017, 31(2):297-319 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1080/13658816.2016.1197399 [13] 武芳, 朱鲲鹏.线要素化简算法几何精度评估[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 -