Study on Automated Aggregation of Depth Contour on Nautical Charts

Delaunay三角网是本文算法的基础。对于三角网中的三角形，给出如下概念：

1) 约束边。若三角形中的某条边为组成等深线的线段，则定义该边为约束边。

2) 邻近三角形。若两三角形存在一条公共边，则称这两三角形具有邻近关系。若公共边为非约束边，称这两个三角形为非约束边邻近；若公共边为约束边，则称这两个三角形为约束边邻近。

3) 三角形分类。根据等深线合并的需求，将三角形分为4类：Ⅰ类三角形, 三角形的3个顶点至少有一个顶点为开等深线的端点；Ⅱ类三角形, 只关联一条等深线的三角形；Ⅲ类三角形, 连接两条等深线的三角形；Ⅳ类三角形, 连接3条等深线的三角形。

4) 邻近距离。连接邻近等深线的三角形是度量等深线间距离的基础。三角形表达的邻近距离度量方法如下：对于Ⅲ类三角形，设A、B、C为三角形的顶点，A、B位于同一等深线上，C位于另一条等深线上，则以点C到直线AB的距离作为该三角形表达的邻近距离；对于Ⅳ类三角形，以三角形3条边的平均长度作为该三角形表达的邻近距离。三角形表达的邻近距离用d_N表示。

对待合并等深线进行自动探测是实现等深线自动合并的前提和基础。待合并等深线需满足3个条件：①邻近性，即待合并等深线必须是邻近的；②深度值相等，确保深度属性的统一；③待合并的等深线必须为表示“凸部”地形特征的等深线，确保航行安全。对于条件①和②，只需三角形表达的邻近距离小于设定阈值且连接等深线的深度值相等即可。这里主要讨论凸部地形特征等深线的判断方法。

当前，利用等深(高)线进行地形特征识别的方法主要是通过构建等深线树^[16-18]或面域图^[19-20]进行识别，计算过程复杂。为此，本文基于面域图提出一种简单的探测方法，该方法无需进行地形特征判断。基本方法是通过比较面域的深度范围和其关联等深线的深度值的大小关系。具体判断规则为：若面域关联的两条相邻等深线的深度值相同，且与该面域深度范围的最小深度值相等，则说明这两等深线间的中间区域为谷地，该两条等深线为表达凸地的等深线，可以进行合并。

位于同一面域内的三角形都能在本面域内寻找到非约束边邻近三角形，而位于不同面域的任意两个三角形都不是非约束边邻近，根据这一特点对制图区域内的非约束边邻近三角形进行聚类，进而实现面域的划分。设制图区域内的三角形集为T_set，N(T)表示三角形T在T_set中的非约束边邻近三角形集。面域识别的步骤为：

1) 从T_set中删除同时属于Ⅰ类和Ⅳ类的三角形，避免不同面域连通;

2) 从三角形集T_set中任取一个三角形T₀，添加到一个新建聚类集R中，将N(T₀)中的三角形放入临时集合S_temp内，并从T_set中删除T₀及S_temp中的三角形；

3) 从S_temp内任取一个三角形t₀，将t₀添加到R中，同时将其从S_temp中删除，然后将N(t₀)中的三角形添加到S_temp中，并从T_set中删除N(t₀)中的三角形；

4) 重复步骤3)直至S_temp为空，此时R中的三角形构成的区域即为一个面域；

5) 重复步骤2)~4)，得到不同面域，直到T_set为空，面域划分结束。

每个面域由三角形集及相关属性构成，数据结构定义为：

式中，T_R表示面域R中的三角形集；C_R表示面域关联的等深线集；D_min、D_max分别表示面域的最小、最大深度值。

本文把需要合并到一起的等深线称为一个合并对象，合并对象的提取方法如下：

1) 三角形筛选。根据等深线合并条件，对面域内的三角形进行筛选，筛选条件为：①三角形类型为Ⅲ类或Ⅳ类；②连接的等深线深度值相等；③连接等深线为表示凸部的等深线；④d_N小于规定阈值，该阈值可根据制图规范确定。

2) 桥接区域提取。根据邻近关系对初步筛选出来的三角形进行分组，每个三角形组表示一个桥接区域，同时记录每个桥接区域关联的等深线集。桥接区域集用集合B_set={{T_B1, C_B1}, { T_B2, C_B2}…{ T_Bp, C_Bp}}表示，每个元素{T_Bi, C_Bi }表示一个桥接区域，T_Bi表示构成该桥接区域的三角形集，C_Bi表示该桥接区域关联的等深线集。图 1中的粉红色区域为得到的桥接区域。

Figure 1.  Filtration of Bridge Areas

3) 合并对象提取。该步骤的主要目的是将同属于一个合并对象的桥接区域及其关联等深线合并到一起得到合并对象。若两个桥接区域{T_B1, C_B1}和{T_B2, C_B2}满足C_B1 ∩C_B2≠∅，则这两个桥接区域同属于一个合并对象。合并对象的提取方法为：遍历步骤2)得到桥接区域B_set，并得到属于同一个合并对象的桥接区域集B_aggregation，B_aggregation关联的等深线集即为待合并到一起的等深线集，合并对象用M={{T_B1, T_B2…T_Bn}, C_aggregation}表示。其中{T_B1, T_B2…T_Bn}表示该合并对象关联的桥接区域，n表示桥接区域的数量，C_aggregation表示合并对象中涉及的等深线集。

扇形桥接区域或较狭窄的桥接区域(见图 2(a))在进行等深线合并时会形成拓扑错误等深线或形成无法清晰辨别的“瓶颈”形状，为此需要对这些桥接区域进行扩展。设W_d表示三角形两条非约束边中点连线的长度，w表示一个桥接区域宽度，它是桥接区域中所有三角形的W_d之和。扩展方法为：若w小于一定的阈值，则寻找桥接区域两边的邻近三角形，计算每个邻近三角形的邻近距离d_N，选择d_N最小三角形添加到桥接区域。更新桥接区域的宽度w，判断是否满足要求，若满足，则扩展结束；否则，重复上述方法，直到w满足要求或不存在连接相同等深线的邻近三角形。

Figure 2.  Link Reigon Expanding

对部分桥接区域进行扩展后，将邻近的桥接区域进行合并。图 2(b)为桥接区域扩展后得到的结果。

直接利用桥接区域将相关等深线进行合并会导致“孔”的出现，其中有些“孔”形成的闭合等深线不符合海图表达规范，需要对“孔”进行处理，具体方法如下：

1)“孔”的识别。若某三角形连接的等深线都是合并对象关联的等深线，且该三角形位于合并对象所在的面域内，则该三角形称为合并对象的关联三角形。设T_M表示合并对象{{T_B1, T_B2…T_Bn}, C_aggregation}关联的三角形集，_T_M表示从T_M中删除{T_B1, T_B2…T_Bn}中三角形后剩余的三角形集。根据邻近关系将_T_M中边邻近的三角形聚为一组，每个组表示一个独立的多边形区域，若多边形区域边界由合并对象关联等深线和桥接区域边界构成，则该区域多边形为一个“孔”。

2) 筛选需要删除的“孔”。筛选条件为：①“孔”内不存在水深注记，或②“孔”内存在水深注记，但在目标比例尺下内部水深注记与等深线发生压盖的符号冲突。得到的待删除“孔”集用H_set={H₁, H₂…H_m}表示，H_i表示一个待删除孔结构，由一组三角形构成。图 3中的绿色区域为得到的需要删除的“孔”。

Figure 3.  Extraction of Hole

利用C-Delaunay三角网在曲线弯曲结构化方面的优势，识别出合并结果曲线上的弯曲，将小弯曲消除，实现合并结果的化简。

若一个合并对象为{{T_B1, T_B2…T_Bn}, C_aggregation}，T_M表示其关联三角形集，H_set表示待删除的“孔”，则待删除小弯曲的识别方法如下：

1) 从T_M中删除{T_B1, T_B2…T_Bn}和H_set中的三角形，剩余的三角形集用T_bends表示，这些三角形覆盖了合并等深线在深水侧的弯曲区域。

2) 根据边邻近关系对T_bends中的三角形进行聚类分组，每组表示一个复合弯曲结构，用T_bend表示。图 4中的每个黄色区域内的三角形为一个T_bend。

Figure 4.  Extraction of Compound Bends

3) 弯曲结构识别。利用C-Delaunay三角网的弯曲识别方法，对每个T_bend进行弯曲识别，并建立弯曲的层次结构。

4) 对每个复合弯曲从根部向底层遍历，判断弯曲是否满足删除条件。删除条件为：①弯曲内部不包含水深注记；②弯曲的口径小于设定阈值或弯曲高小于设定阈值。该过程得到待删除弯曲集，用集合T_delete={b₁(tris), b₂(tris)…b_q(tris)}表示，其中b_i(tris)表示一个待删除弯曲。图 5中的紫色区域表示得到的待删除弯曲。

Figure 5.  Extraction of Bend Areas to Delete

等深线合并具体步骤如下：

1) 综合区域提取。通过边邻近关系将邻近的桥接区域、“孔”、化简弯曲单元合并为一个综合区域，得到若干综合区域集G_set={G₁, G₂…G_k}。图 6中的红色区域为得到的综合区域；

Figure 6.  Extraction of Generalizing Areas

2) 综合区域边界提取。提取G_set中每个综合区域的边界，得到综合区域边界集B_G={B_G1, B_G2…B_Gk}；

3) 将合并对象关联等深线集C_aggregation与综合区域边界集B_G做图形对称差分拓扑运算，即可得到合并结果。图 7为图 6中的一个合并对象得到的合并结果。

Figure 7.  Aggregated Result

光滑的目的是删除合并等深线上的小“波动”及明显转折角，对应两个环节：

1) 利用拐点法识别深水侧弯曲，删除弯曲高小于设定的阈值或口径小于设定阈值的弯曲，直到所有等深线深水侧所有弯曲都不满足删除条件。该过程可以处理掉等深线上的小“波动”。

2) 曲线加密。针对合并等深线上存在的明显转折角问题，采用加密的方法进行消除，具体实现方法是对等深线进行多段Bezier曲线拟合。为了确保航行安全，对等深线上的凸向深水区弯曲和凹向浅水区弯曲分别采用不同的拟合方法。对于凸弯曲，在等深线的外部进行保凸Bezier曲线形状拟合：对于凹弯曲，在等深线内部进行Bezier曲线拟合。图 8为对应图 7的光滑结果，可以看出，得到的光滑结果形态比较光滑，小的形态“波动”及转折角都得到了有效的消除。

Figure 8.  Smoothing Result

为验证本文算法的可行性和正确性，本文利用实际数据对算法进行了验证，实验数据如图 9所示。合并对象统计如表 1所示。图 10显示了部分合并实例，红色曲线为合并后的等深线，黑色曲线为原始等深线。

Figure 9.  Test Data

Figure 10.  Examples of Aggregation

为了验证该探测方法的正确性，对实验中的所有合并对象与对应区域的1:80 000海图数据进行了对比。发现本文探测的9个合并对象中，有8个合并对象在1:80 000海图中是进行了合并操作，而其中的1个合并对象在1:80 000海图中是进行了删除操作，本文对该实例(见图 11)进行了分析。图 11(a)、11(b)分别为1:40 000的原始数据和对应的1:80 000海图数据，图 11(c)、11(d)为图中对应的等深线数据。图 11(c)中的红色箭头所指的两条等深线为120 m深度的等深线，在1:80 000的海图数据中得到了删除(见图 11(b)、11(d))，而本文算法将这两条等深线与绿色箭头指示的120 m邻近等深线进行了合并。通过分析发现，这3条120 m等深线表示的地貌特征都为凸部地貌特征，应该将这3条邻近等深线进行合并(见图 11(e))，而不能将其中的两个较小等深线进行删除。这也从侧面反映了人在进行合并操作时可能出现的误判现象。通过逐个检查发现本文的9个合并对象中的等深线都表示凸地貌特征，没有出现错误的情况，验证了待合并等深线探测算法的正确性。

Figure 11.  Comparison and analysis of detecting methods

在合并效果方面，选择实验中的一个合并实例采用多种方法进行了一组对比实验，实验选取的邻近距离阈值相同。图 12(a)为合并原始数据，图 12(b)、12(c)、12(d)、12(e)分别为传统Delaunay三角网合并方法、双向缓冲区方法、普通缓冲区方法^[12]、本文方法的合并结果，通过对比可以看出：①本文算法得到的合并结果次要弯曲特征得到了有效的化简，且图形表达较为光滑；②本文合并结果没有产生不合理的“孔”等深线，而在另外3种算法中都产生了这种不合理现象(图中红色箭头所指处)。③图形表达清晰可辨，不存在视觉冲突，而另外3种算法都存在无法清晰表达的“瓶颈”现象(图中短划线箭头所指处)；④本文算法和缓冲区方法对所有邻近距离小于设定阈值的等深线都进行了合并，而另外两种方法都存在遗漏的情况，如图 12(b)、12(c)中黑色点线箭头所指处。

Figure 12.  Comparison of Different Methods

确保航行安全是等深线综合特有的要求，是反映等深线综合质量的重要方面。本文对实验中合并得到的9条等深线进行了检查，检查结果显示所有合并结果全部位于原始等深线的深水侧，没有违反航行安全的情况。作为对比，本文对1:80 000的成图数据的合并等深线也进行了安全性检查，发现存在违反航行安全的合并结果。如图 13所示，通过将1:40 000的等深线数据(红色曲线)叠加到1:80 000的海图数据上，发现这两条合并等深线都未完全位于原始等深线的深水侧，不符合航行安全的要求。因此，本文算法能够确保航行安全，避免人工作业中因个人业务能力或精神状态造成的无法确保航行安全的错误。

Figure 13.  Analysis of Navigation Safety

实验表明本文方法具有以下特点：

1) 提出了一种待合并等深线的自动探测方法。该方法避免了复杂的地形特征识别过程，效率较高。

2) 实现了等深线合并与化简的一体化，得到的合并结果在形态特征表达方面清晰、光滑，符合海图对特征深线的形态要求。

3) 合并结果满足“扩浅缩深”的等深线综合原则。