DTW算法支持下的线状要素连续地图综合方法

康二梅, 毛凯楠

(1. 甘肃省基础地理信息中心,甘肃 兰州 730000; 2. 武汉大学资源与环境科学学院,湖北 武汉 430072)

地图综合是通过对地图中的点、线、面、注记等要素进行选取和概括以实现地图数据的抽象与尺度变换,是地图制图、空间数据库建设及空间分析的理论和技术基础,长期以来,众多学者对该问题进行了研究[1]。当今,随着Web2.0技术的发展,人们不再满足于有限比例尺的传统地图服务模式,任意比例尺地图数据的动态生成技术成为研究的热点,因此出现连续地图综合技术[2],即通过拓展地图综合理论与方法实现对地图数据的连续尺度变换,动态派生任意比例尺的地图数据。

连续地图综合方法大致可分为两类,一类是对传统地图综合方法的改进,增加其尺度敏感性,使得算法输出数据变化粒度更加精细,从而实现连续地图综合[3-4];另一类是基于尺度融合技术,通过对同一区域一大一小两套比例尺数据的融合,动态派生任意中间尺度的数据[5]。当前,我国已经建立了基本比例尺系列地图数据库[6],可以作为基于尺度融合的连续地图综合方法的数据基础。

与专题覆盖图斑类地图不同[7-10],在普通地图中,河流、道路、管网和等高线等线状地图要素占据了很大的比例,本文聚焦于线状要素的连续地图综合,提出一种基于DTW算法的线状要素连续地图综合新方法。

1 DTW算法支持下的线状要素连续地图综合模型

基于尺度融合概念的连续地图综合模型可表达为[11-12]

Rs=F(S1,S2,T)

(1)

式中,S1和S2分别为同一地理实体在大小比例尺中的两种几何表达;F为尺度融合函数;T为与比例尺有关的归一化参数,用于控制融合结果随比例尺的不同而逐渐变化。对任意0≤T≤1,Rs关于T是单调、连续的,当T=0时,Rs=S1;当T=1时,Rs=S2;当0

上述连续地图模型的实现,涉及2个基本过程。一是几何表达S1和S2之间顶点对应关系的建立;二是插值路径的选择[13-14],因任何中间表达状态Rs与S1和S2都属于同一地理实体,故插值路径选用简单的线性插值[15]。对于同名实体不同比例尺的几何表达,S1和S2往往具有不同数目的坐标点数,其坐标点的集合具有不同基数。在不同基数的两个集合之间建立映射关系,必然存在非一对一映射关系,对于空间数据而言,表现为S1和S2的顶点之间存在一对多的对应关系。显然,这种映射关系可以有多种,如何建立两者之间的最优匹配,是连续地图综合模型实施的关键。

本文采用动态时间归整(dynamic time warping, DTW)方法对S1和S2的顶点集合进行最优匹配。DTW是时间序列匹配的经典方法[15],它通过对两个序列进行自适应空间扭曲和动态时间规整找出两序列间最优匹配,实现两个序列之间的精准时空对齐。对于地图目标S1和S2,其矢量坐标序列分别表示为集合Q和C。其中,集合Q的基数为n,Q={q1,q2,…,qi,…,qn};集合C的基数为m,C={c1,c2,…,cj,…,cm}。Q和C中每个分量qi和cj具有相同的维度,对于二维地图数据,该分量是一个由纵横坐标组成的二维向量。为了对齐Q和C中的顶点序列,如图1(a)所示,DTW首先构造一个n×m的矩阵网格,矩阵元素(i,j)表示点qi和cj对齐,其数值为qi与cj两坐标点之间的距离,记为d(qi,cj),可使用欧式距离,d(qi,cj)=(qi-cj)2。该距离反映了序列Q和C的每个点之间的相似度,距离越小则相似度越高。建立Q和C之间顶点对应关系的过程,表现为构造一条从方格点(1,1)到方格点(n,m)的几何路径W(W=w1,w2,…,wk)(wK(max(m,n)≤K≤(m+n-1)),其中K为对齐两个坐标序列所需的索引数。如图1(b)所示,该路径确定了待匹配序列Q与C上每个点之间的对应关系,该路径允许一对多对应,图中w4和w5分别表示Q中第4点同时对应于C中第4和第5两个点。

图1 DTW算法

几何路径W的生成需满足3个约束条件:①边界约束,W从第一个点对开始,在最后一个点对结束,即w1=(1,1),wK=(m,n);②连续性,路径上的任意两个相邻点wk=(a,b)与wk-1=(a′,b′)满足0≤|a-a′|≤1,0≤|b-b′|≤1;该约束要求路径不能跳过某些顶点进行匹配,当前点只能与自己相邻的点对齐,以保证Q和C中每个坐标均在路径中出现;③单调性约束,若wk=(a,b)与wk-1=(a′,b′)为路径上前后两个点,则需满足a-a′≥0,b-b′≥0。因n不一定等于m,这种匹配关系有多种可能性,每种匹配关系均可用一条弯曲路径表示,最短弯曲路径的长度即为序列Q与C之间的DTW距离,其对应的匹配即为Q和C的顶点之间的最优匹配。满足最短路径匹配的DTW距离可表示为

(2)

该优化问题可采用的动态规划算法进行求解,公式为

γ(i,j)=d(xi,yj)+min[γ(i-1,j-1),

γ(i-1,j),γ(i,j-1)]

(3)

式中,γ(i,j)表示当前单元格中的距离和相邻元素的最小累计距离。

线状地图要素在尺度变换过程中常采用的地图综合算子为弯曲的取舍、夸大,连续弯曲的典型化,以及节点的抽稀。其中,节点抽稀的结果也表现为细小弯曲的舍弃。

2 试验分析

本文将验证基于DTW的顶点匹配算法在曲线弯曲舍弃和连续弯曲典型化2种基本场景下的匹配效果。为了验证本文方法的可行性和有效性,分别采用模拟和实际数据进行试验。图2(a)为模拟数据在大比例尺S1和小比例尺S2下叠置显示的效果,分别记为曲线a和曲线b,该数据反映了多尺度环境下线状要素尺度变换的基本特征,图2(a)中虚线椭圆A和D所在区域的曲线b,由a经弯曲删除产生,椭圆B所在区域的曲线b由a经顶点抽稀产生,椭圆C所在区域由弯曲典型化产生。模拟数据在大比例尺S1中由72个顶点组成,记为a={a1,a2,…,a72},在小比例尺S2中由57个顶点组成,记为b={b1,b2,…,b57}。图2(b)为基于DTW算法在不同尺度下线状要素的顶点匹配关系。其中,b1对应于a1、a2和a3,因此在b1的位置将会插入2个与b1相同的点,记为b1-1、b1-2,分别对应于a2和a3。然后针对顶点匹配结果进行线性插值。

图2 模拟数据在不同比例尺下的叠置效果及其匹配关系

图3为模拟数据基于DTW算法的Morphing渐变效果。T=0和T=1分别为线状要素在大比例尺S1的表达a和小比例尺S2的表达b,T=0.1～0.9为不同程度的形状内插结果,T与中间比例尺Rs的关系为Rs=(1-T)S1+T·S2。可以看出,随着T的不断增大,中间比例尺Rs的曲线形态越来越逼近小比例尺S2,曲线弯曲特征的化简、舍弃及典型化操作实现了从左到右的光滑过渡,该结果符合空间数据的渐变特征,说明本文方法适用于Morphing渐变。

图3 基于DTW算法的模拟数据Morphing渐变效果

图4和图5分别为某区域1∶10 000和1∶50 000的真实河流及等高线数据在采用本文DTW算法后的形状内插结果,河流及等高线的数据来源于OpenStreetMap。其中,图4(a)与图5(a)为1∶10 000的原始形状,相应的T值为0;图4(f)与图5(f)为1∶50 000的目标形状,相应的T值为1;图4与图5中的(b)到(e)分别对应1∶18 000、1∶26 000、1∶34 000及1∶42 000的形状表达,对应的T值分别为0、0.2、0.4、0.6、0.8和1。可以看出,对于河流而言,Morphing的渐变结果保留了线状地物的连接性与网状结构;对于等高线而言,其结果保留了图形中山谷和山脊的形态特征且没有出现拓扑错误。因此本文方法可以较好地保持线状地物的几何形态及拓扑结构,并实现线状要素弯曲形态由复杂到简单光滑的过渡。

图4 基于DTW算法的河流数据Morphing渐变

图5 基于DTW算法的等高线数据Morphing渐变

3 结 语

本文提出了一种基于DTW算法的地图线状要素连续综合方法。该方法基于尺度融合的思想,以同一地理实体在大小比例尺下两种不同的几何表达作为输入,首先基于DTW算法建立两种几何表达坐标顶点之间的对应关系,然后采用线性内插方法动态派生任意中间尺度上几何数据,从而实现连续地图综合。插值的难点在于建立不同比例尺下同名地理实体坐标顶点之间的非一一对应关系,为建立最优匹配关系,本文方法以顶点距离为匹配代价,以整体最小距离为目标函数,采用DTW算法求解最优匹配。试验结果表明,基于DTW的顶点匹配方法可适应不同的河网、等高线等典型地图综合场景,该方法支持下的地图综合效果可实现连续、光滑渐变,符合地图表达规则和人类空间认知。不足之处为对于比例尺跨度较大的情况,可能存在实体的消亡(即删除),此类情形无法建立同名实体之间的对应关系,因此无法进行形状内插。后期将进一步研究此类情形的解决方法。