随着网络技术的发展，地图服务需要满足不同层次用户的个性化需求，在地图内容上提供任意尺度的表达，这需要连续地图综合技术的支持^[1]。图像融合中的Morphing技术，其形状渐变特性符合空间数据多尺度表达与渐进式综合的技术需求，故成为实现连续地图综合技术的重要方法^[2-12]。Morphing变换通常包含特征匹配和形状插值两个基本过程^[13]。

特征匹配旨在初始图形和目标图形的特征点或特征线之间建立一一对应关系。对于线状要素而言，文献[2]提出在最长边上增加顶点直至始末图形具有相等顶点数，从而按顺序建立对应关系；文献[3]提出取线状要素弧度较大处的顶点为特征点，采用动态规划法对特征点间的线段建立对应关系；文献[4]则是选取一定范围内具有最大夹角值的顶点作为特征点。上述方法均基于线状要素的局部结构，文献[6]指出忽视线状要素的整体结构，易导致无法有效纠正的匹配错误，提出了一种立足于线状要素整体结构的匹配方法，利用文献[5]提出的曲线弯曲深度层次结构的二叉树表达方法识别弯曲结构，进而对弯曲进行匹配。二叉树结构虽然实现了对线状要素大弯曲套小弯曲层次结构的表达，但并不符合人们对弯曲结构层次性的感官认知，掩盖了弯曲间的等级关系。因此，文献[7]为了更充分地利用弯曲结构，只能将弯曲匹配分割为独立弯曲匹配和子弯曲匹配，不断切割独立弯曲，反复构建Delaunay三角网。本文改进了二叉树表达方法，基于Delaunay三角网，利用弯曲的属性构建更能充分描述弯曲层次结构的多叉树，利用多叉树的特性进行递归匹配，保证了匹配精度及效率。

形状插值旨在将初始图形各部分沿一定路径变换到目标图形对应部分所在位置，获取中间状态图形系列。传统的插值方法^[8-12]虽能实现中间状态图形的渐变，但不符合线状要素的综合要求，如弯曲的化简、舍去、夸大，且不能保持要素的类型特征、各线段上的曲折系数和单位长度上的弯曲个数的对比。另一方面，顾及了线状要素综合要求的方法^[14-18]，由于仅针对单一比例尺下的线状要素进行综合，只是几何层面地删除小的弯曲，不仅无法实现弯曲的夸大，还易导致错误地删除重要的弯曲。而文献[19]通过整合地理层次的综合决策与几何层次的综合操作，以谷底地貌成因为依据进行数字高程模型(digital elevation model，DEM)综合，以及文献[20]提出以曲线骨架点作为特征点，以模拟退火方法建立特征点与初始曲线顶点之间的全局最优匹配的Morphing方法，都因顾及了多尺度、综合要求、地理层次等多个方面，获得了顾及综合要求、能保持要素结构特征的综合结果。本文提出了一种满足线状要素综合要求的插值方法，对初始图形中匹配到的对应弯曲进行线性插值，完成夸大操作，对未匹配到的弯曲进行重要性评估，依据尺度逐渐删除，完成舍去和化简操作。

1 顾及线状要素综合要求的算法原理

1.1   概念模型

设大比例尺T_a下的线状要素为a，小比例尺T_b下的线状要素为b，中间比例尺T_m下的曲线要素为m，a较之b具有更详细的表达，m表达的详略介于a、b之间。设a的弯曲集合为S_a, b的弯曲集合为S_b，m的弯曲集合为S_m, S_a包含最多的弯曲，S_b包含最少的弯曲，且S_a⊇S_b，令S_M=S_a∩S_b，S_M是a中匹配到的弯曲集合，在插值过程中与S_b进行线状插值，b中所有弯曲都是由a变化而来，故S_M=S_b。令S_U=S_a-S_b，S_U是a中未匹配到的弯曲集合，在插值过程中逐渐化简和舍去。

本文采用文献[21]提出的弯曲定义方法，定义不包含孩子弯曲的简单弯曲为基本弯曲，如图 1中的基本弯曲1；由多个弯曲套合而成的复杂弯曲为复合弯曲，如图 1中的复合弯曲1；不是孩子弯曲的弯曲为独立弯曲，如图 1中的基本弯曲1、复合弯曲1。任何线状要素都是由多个独立弯曲组成，独立弯曲可能是基本弯曲(如基本弯曲1)，也可能是复合弯曲(如复合弯曲1)，而复合弯曲中又包含更深层次的复合弯曲(如复合弯曲1圈中的复合弯曲2)和基本弯曲(如复合弯曲1中的基本弯曲2)。

图  1  弯曲概念示意图

Figure  1.  Diagram of Bend Conception

下载: 全尺寸图片 幻灯片

线状要素除了独立弯曲，还包含连接独立弯曲的曲线段，在Morphing过程中，这些曲线段并未发生变化，因而可以用于线状要素的匹配。依次连接这些曲线段所形成的曲线，可以唯一确定一个线状要素，本文称之为线状要素主干。如图 1中的虚线弯曲主干。线状要素主干的定义如下。

定义1  线状要素主干：依次连接线状要素非弯曲曲线段所形成的曲线。

骨架线一般用于描述面状要素的轮廓形状^[22]。弯曲结构虽是线状要素，但其轮廓形状与面状要素类似，依然可以使用骨架线研究其轮廓结构。文献[6]通过对线状要素增加包络外围三角形，进而建立Delaunay三角网，以外围三角形为入口，根据三角形的不同特征深入行进，直至遍历整个弯曲, 其行进路线即是骨架线。基本弯曲的骨架线可以唯一确定一个基本弯曲，复合弯曲的骨架线具有层次性，去掉复合弯曲骨架线中隶属于孩子弯曲的骨架线所形成的曲线，同样可以唯一确定一个复合弯曲，本文称之为弯曲主干，如图 1中的点线。以弯曲主干进行匹配，简化了匹配指标，提高了匹配效率。弯曲主干的定义如下。

定义2  弯曲主干：去掉弯曲骨架线中隶属于孩子弯曲的骨架线所形成的曲线。

1.2   构建多叉树

对于本文中线状要素的多叉树表达，弯曲的套合关系表达为多叉树节点的父子关系，弯曲的属性记录在对应节点中，根节点为线状要素主干，其余节点为弯曲主干，线状要素的独立弯曲中为基本弯曲的对应多叉树的叶节点，为复合弯曲的对应多叉树的子树。同样地，复合弯曲中套合的基本弯曲对应子树的叶节点，套合的复合弯曲对应子树的子树。因此，线状要素的多叉树表达可以递归到最深层次。其中，本文用弯曲位置、弯曲主干方位、弯曲主干长度3个属性描述弯曲。

定义3  弯曲位置P：弯曲主干起点的坐标, 也称线状要素主干起点的坐标为线状要素的弯曲位置。

定义4  弯曲主干方位θ：自弯曲主干起点的指北方向起，依顺时针方向到弯曲主干起终点连线之间的水平夹角。

定义5  弯曲主干长度L：弯曲主干的长度。

本文的多叉树算法描述为：利用文献[6]的“剥皮”算法获取线状要素所有独立弯曲的骨架线，以线状要素主干为根节点，以独立弯曲主干为子节点，进而递归进入第一个独立弯曲，视独立弯曲主干为子树根节点，套合在独立弯曲中的弯曲主干为子节点。若存在复合弯曲，则进一步递归深入，以复合弯曲主干为子树的子树根节点，套合在复合弯曲中的弯曲主干为子节点，反复递归直到遍历完该独立弯曲。反复执行直至遍历完所有独立弯曲。如图 1线状要素的多叉树。

1.3   多叉树匹配

在Morphing过程中，弯曲只存在5种变化类型，故也只存在5种匹配类型，分别是：(1)a的基本弯曲被保留，匹配类型为节点对节点，如图 2中的基本弯曲2与对应基本弯曲1。设a的该弯曲属性为(P_a, θ_a, L_a)，b中对应的弯曲属性为(P_b, θ_b, L_b)，由于可能存在弯曲的夸大，故两者应近乎相等，即(P_a≈P_b, θ_a≈θ_b, L_a≈L_b)；(2)a的基本弯曲被舍去，匹配类型为节点对Ø，如图 2中的基本弯曲1。不能匹配到与该弯曲属性相近的弯曲。(3)a的复合弯曲被化简为基本弯曲，变化为b的基本弯曲，匹配类型为多叉树子树对节点，如图 2中的复合弯曲2与对应基本弯曲2。设a的该复合弯曲主干属性为(P_a, θ_a, L_a)，b中对应的基本弯曲属性为(P_b, θ_b, L_b)，其中包含两种可能性：①该复合弯曲的主干部分被保留，其余弯曲被舍去，则有(P_a≈P_b, θ_a≈θ_b, L_a≈L_b)；②保留的是该复合弯曲的某一基本弯曲，设其基本弯曲属性为(P′_a, θ′_a, L′_a)，这种情况下，无法直接匹配，须修改该复合弯曲套合的其他弯曲主干属性为(P_a, θ′_a, L_a+L′_a)，让所有套合的弯曲主干参与匹配，将问题转变为若干个节点对节点及子树对节点，对于子树对节点情形再进一步递归，直至找到满足(P_a≈P_b, θ′_a≈θ_b, L_a+L′_a≈L_b)的弯曲。(4)a的复合弯曲被舍去，匹配类型为多叉树子树对Ø，如图 2中的复合弯曲3。使用(3)所述方法仍未匹配对应弯曲，则视为该复合弯曲被舍去。(5)a的复合弯曲仍变化为复合弯曲，匹配类型为多叉树子树对子树，如图 2中的复合弯曲1和对应复合弯曲1。递归深入，转变为前4种情形。

图  2  弯曲匹配示意图

Figure  2.  Diagram of Bend Matching

下载: 全尺寸图片 幻灯片

本文的多叉树匹配算法描述为：先以线状要素主干即根节点进行匹配，找到与之对应的线状要素，进而对线状要素的独立弯曲即第1层子节点进行匹配，前4种情形直接处理，第5种情形则递归深入，只对同一层次的节点进行匹配，唯有出现第3、4种情形时，才对节点与同一层次节点的子树中的低层次节点进行匹配。遍历多叉树，直至全部节点匹配完毕。如图 2所示的匹配结果。

1.4   插值

制图综合中线状要素的形状概括要求主要有3点^[14]：(1)舍去小于规定尺寸的弯曲，夸大特征弯曲，保持图形的基本特征。(2)保持弯曲图形的类型特征。(3)保持各线段上的曲折系数和单位长度上的弯曲个数的对比。本文对匹配到的弯曲进行线性插值，使得须夸大弯曲据尺度逐渐夸大；对未匹配到的弯曲据重要性逐渐舍去，同时保持曲折系数与弯曲个数的比值及弯曲图形的类型特征。

对于中间图形m，其包含的弯曲集合S_m与初始图形a的弯曲集合S_a间的差即是被舍去的弯曲集合，设m须舍去的弯曲集合为S_D, S_D=S_a-S_m，a-S_D=m。显然，m越接近a，S_D包含的弯曲个数越少，弯曲越次要。m越接近b，S_m包含的弯曲个数越多，弯曲越重要。本文以弯曲主干长度L、弯曲曲折系数R、弯曲对应节点的层次C 3个因子评价弯曲的重要性，其中曲折系数是曲线的实际长度与起止点直线距离。弯曲重要性的权重由3个因子加权计算得出，由于3个因子的数量级和度量不同，加权计算之前必须分别作归一化处理。对于弯曲B，其权值W(B)为：

式中，λ_L、λ_R和λ_C分别是3个因子的权重；L_max、L_min是所有弯曲主干长度的最大值和最小值；R_max、R_min是所有弯曲曲折系数的最大值和最小值。

设初始图形a的曲折系数为R_a，尺度为g_a，最终图形b的尺度为g_b，m的尺度为g_m，弯曲权值最大值为W(B)_max，最小值为W(B)_min，a与b匹配到的弯曲集合为S_M，则m须舍去的弯曲集合S_D为：

此时的S_D能保证m保留的弯曲依赖于尺度和重要性，但不能保持m各线段上的曲折系数和单位长度上的弯曲个数的对比。本文采用的策略是以复合弯曲为单位，即以子树为单位，对S_D进行调整，尽可能使最多的复合弯曲保持曲折系数与弯曲个数的比值。若该比值较高，则移除集合中重要性较高的弯曲; 若比值较低，则增加集合外重要性较高的弯曲，不能因此改变原集合的尺度相关性。

2 线状要素综合实验与分析

本文基于C++语言使用MFC构建平台，选取一段等高线要素为实验数据进行实验，数据始末状态如图 3所示。初始状态是1：1万比例尺地图上的表达，最终状态是1：5万比例尺地图上的表达。图 4为数据细部的放大图，圆圈中的部分是弯曲的逐渐夸大。实验结果表明，本文算法生成的中间图形较好地满足了线状要素的综合要求。

图  3  线状要素Morphing变换

Figure  3.  Morphing of Linear Features

下载: 全尺寸图片 幻灯片

图  4  细部Morphing变换

Figure  4.  Local Amplification Effect of Morphing

下载: 全尺寸图片 幻灯片

本文方法的算法复杂度为O(nlgn)。其中，多叉树构建的算法复杂度为O(n)，多叉树匹配的算法复杂度为O(nlgn)，插值的算法复杂度为O(n)。

3 结语

本文提出了一种满足线状要素综合要求的Morphing方法，该方法基于Delaunay三角网，利用弯曲的几何属性构建能够描述线状要素弯曲层次结构的多叉树，利用多叉树的特性进行递归匹配，对匹配到的弯曲进行线性插值，完成夸大操作，对未匹配到的弯曲依尺度逐渐删除，完成舍去操作。本方法经实验验证较好地满足了线状要素的综合要求, 不足之处在于：本文方法需要两个尺度下的线状要素数据，而目前的综合算法多是基于线状要素一侧的弯曲进行删除，其造成的数据源本身的局限性，使得本文方法同样无法保证中间图形两侧面积的平衡。另外，本文算法仅考虑同一条线状要素，未考虑线状要素的合并。鉴于上述原因，根据文献[23]提出的常见线状要素各自的综合原则，结合本文方法已满足的文献[14]提出的线状要素综合要求，本文方法不适于以下线状要素的综合：海岸线(无法保持海陆面积的对比)、湖泊岸线(无法保持湖泊与陆地的面积对比)、境界线(无法保证位置高度精确，无法避免被两侧符号压盖)；适用于以下线状要素的综合：等深线(能做到遵从“舍深扩浅”原则)、河流(能保证河流长度不过分缩短)、道路(能实现局部缩小以避免过多位移)、等高线形状化简(对两侧弯曲使用本文方法，可实现以正/负向形态为主的地貌，扩大正/负向形态，减少负/正向形态)、地类界(综合灵活性高，无须遵循太多原则)。