在当前网络环境下,用户需要在任意比例尺下浏览连续变化的地图要素,解决该问题的一般策略是采用地理要素的增量式表达模型,并在网络中采用流媒体传输模式^[1-4]。这种多尺度地图要素表达模型只在地图大比例尺端进行控制,没有充分利用另一端的小比例尺数据,产生的数据系列属于阶梯尺度数据集,难以实现地理要素从一个已知尺度到另一已知尺度的连续过渡,也容易产生几何、拓扑的不一致性。借鉴动画中图形渐变技术（morphing）,近年来人们开始尝试使用2个关键尺度下的地图数据内插出中间尺度的地图数据^[5,6]。该技术主要应用于曲线要素,涉及4方面的关键技术：其一,关键尺度的选择。其二,2个关键尺度下曲线特征点的探测,这是实现本技术的难点之一,最好能以最少的特征点来描述曲线的主体特征,其算法的复杂度不能太高。在动画技术领域,常常以曲线的极值点、拐点、端点作为特征点。文献[7]计算多边形各个顶点的相关度,以其为依据删除相关度小的顶点,以简化了的多边形的顶点作为特征点;Nöllenburg考虑到上述方法产生的特征点数量的庞大,尝试用一系列贝塞尔曲线来拟合原曲线,以各个贝塞尔曲线的控制点作为曲线的特征点^[5];文献[8]考虑到曲线的形态单元的不可分割性,通过建立弯曲的层次结构,以弯曲的分界点作为特征点,但建立约束Delaunay三角网以及弯曲识别算法的复杂度较高^[8],只适合网络地图的离线计算。其三,建立两曲线特征点的匹配关系,这是实现本技术的难点之二,匹配关系务必保证对应弧段的形状相似性。在动画领域,常采用构造代价函数,以匹配代价最小作为最优方案^[9,10],但这些方法不太适合地图要素的匹配;文献[8]采用所识别弯曲的参量的比较而进行匹配,该方法十分简单,但当弯曲不能一一对应时可能存在一些问题^[8]。其四,由2个尺度的同名曲线内插得到中间尺度的曲线。

本文基于凸壳模型以及BLG树建立等高线多层次特征点树状结构,以距离邻近以及形状特征分析来逐层匹配特征点,提高了识别和匹配的可靠性。从实验的效果来看,当用户在放大缩小（Zoom in/out）过程中能得到连续平稳过渡的等高线连续尺度表达。

1 渐变技术支持下的等高线连续尺度的表达

1.1 多层次等高线特征点的识别

如图1a为1∶1 000下的一条闭合等高线,按照文献[11]的方法以其上的点建立凸壳(图1b),将凸壳上的边分为两类：Ⅰ类,曲线上连续两点构成的边,如图1b中点16~17、17~18、18~19、31~32构成的边;Ⅱ类：曲线上非连续两点构成的边,如图1b中点0~8、10~16、19~24、26~31、32~53、53~60构成的边。将一系列连续的Ⅰ类边组合在一起,便是原曲线的凸起部分,如图1b中的弧段60~61、61~62、62~63、63~0组合而成的60~0弧段便是原曲线的凸起;Ⅱ类边跨过的曲线段则是曲线的凹陷部分,如0~8、32~53弧段所跨过的曲线段为凹陷。

显示原图| 下载原图ZIP| 生成PPT

图1   等高线特征点的识别过程及曲线的分段

Fig.1   Recognition of multi-hierarchical characteristic points and segmenting of a contour

如上分段后,曲线便是由系列的凸起和凹陷组合而成,凸起和凹陷为曲线的基本形态单元,两形状单元的分界点为曲线的首级特征点,根据特征点前后形状单元的类型,为了后续特征点匹配分析的需要将其分为3类：“u·u”类：前后均为凹陷;“u·n”类：前为凹陷后为凸起;“n·u”类：前为凸起后为凹陷（以顺时针方向为前进方向,u表示凹陷,n表示凸起）。其中图1c中黑方块表示等高线的首级特征点,分别为0、8、10、16、19、24、26、31、32,其中0、10、19、26、32为“n·u”类,而8、16、24、31、60为“u·n”类,53为“u·u”类。不难发现,划分的结果实际上是识别了曲线上的2类弯曲：向内的凹陷和向外的凸起,并有效地保持了曲线形态单元的完整性^[8]。

在首级特征点识别及分段基础上,对每一形状单元,采用文献[12]提供的方法构建BLG树。具体过程是：分析每一个形态单元,若最大距离大于等于给定距离阈值D,则以最大距离的点作为二级特征点,并以该点将该形状单元分成两段,在每一段重新构建下一级形态单元结构,采用递归算法,依次探测下一级的特征点,直至弧段垂向最大距离小于阈值D或者两点间没有中间点为止。阈值D可按式（1）进行计算：

D=Scale×dsvo(1)

式中,d_svo为小比例尺下最小可辨目标 (smallest visible object)所对应的实际长度,S_cale为两比例尺下较小比例尺的分母,若两关键比例尺分别为1∶1 000、1∶5 000,取d_svo=0.4 mm,则D=S_cale×d_svo=5 000×0.4 mm=2 m。针对图1c取阈值D为2 m,产生的次级特征点如图1d所示,其中5、13、22、46、56为第2个特征点,在32~53弧段中存在4级特征点,其中40为3级特征点, 37、42为4级特征点。整个等高线各个弧段的层次关系可以用多叉树来表示,图2清晰地表达了图1所示等高线的各弧段的层次树结构。

显示原图| 下载原图ZIP| 生成PPT

图2   等高线弧段的层次结构

Fig.2   Multi-hierarchical arc structure of contour

本文研究的是2个关键尺度下的等高线内插技术,根据地图多尺度表达的基本原则,2个关键尺度下的同名等高线在总体轮廓形状上具有较高程度的相似性,因而首级特征点采用基于形状特征的识别方法,在曲线的细节层次上一般难以维持形状的一致性,曲线内的法向极值点常常具有很强的继承性。通过这两类方法识别不同级别的特征点,既顾及不同尺度下地理要素总体形态的相似性,又兼顾曲线上极值点对曲线形态的重要意义。

1.2 两个关键尺度下特征点的匹配

图形渐变的两端为不同尺度下的同名等高线,虽然二者可能存在一定的位移,但在位置上仍然具备足够的精度,本文将依据特征点的邻近性来搜索同名特征点。由于同名等高线的特征点大都不能一一对应,当匹配存在歧义时需要加以形状特征的辅助分析。如大比例尺下的等高线f与小比例尺下的等高线g为同名等高线,按上节的方法探测两等高线上特征点,其中等高线f的首级特征点集为{P_i(X_i,Y_i)|i为整数}（其中(X_i,Y_i)为首级特征点中第i个点的坐标,下同）,等高线g的首级特征点集为{P_j(X_j,Y_j）|j为整数}（图3a）。考虑到大比例尺下的等高线具有更详细的形状细节,因此,一般而言f的首级特征点多于g的首级特征点,可能会出现f的多个首级特征点匹配g的一个特征点,因而在探测同名特征点时的映射方向为大比例尺到小比例尺。顾及到2个尺度下要素的整体位移,对每个要素的特征点进行归一化处理：分别计算2个曲线的外接矩形R(f)和R(g),得到其中心坐标分别为（X_f,Y_f）和（X_g,Y_g）,对于f上的各个特征点P_i（X_i,Y_i）,其归一化处理后坐标为（X_i-X_f,Y_i-Y_f）,对于g上的各个特征点P_j（X_j,Y_j）,其归一化处理后的坐标为（X_i-X_g,Y_i-Y_g）。使用归一化处理后的坐标,计算f上特征点P_i到g上所有特征点的距离,找出距离最近的点,建立初步的特征点匹配关系（图3b）。设定距离阈值D,删除距离大于D的匹配,D的取值可按公式（1）获得（图3c）。经过处理后,可能还会存在大比例尺要素的多个特征点与小比例尺要素的一个特征点匹配的情况,如在图3c中f上的点8、10与g上的点9匹配,点31、32与27匹配,此时必须进行更为精细化的匹配。精细匹配的基本原则是两曲线的形状单元的匹配：针对一对二的情况,必须满足小比例尺特征点前方形状单元与大比例尺前点的前方形状单元一致,小比例尺的特征点后方形状单元与大比例尺后点后方的形状单元一致,即前后两端的形状单元必须保持一致,若其中一个不匹配,则删除该匹配。

显示原图| 下载原图ZIP| 生成PPT

图3   首级特征点的匹配过程

Fig.3   The matching procedure of characteristic points on first-level of the tree

对图3c中的2个一对二匹配的情况,参照图4进行详细地分析。图4a中小比例尺曲线的特征点27与大比例尺曲线的31、32对应,点31、32分别为“u·n”型与“n·u”型,省去中间段,则31~32两端的形状为“u·u”型,27的前后形状单元为“n·u”型,二者的后弧段类型不相符,删除不符的一端,即27~31的匹配关系。图4b中小比例尺曲线的特征点9与大比例尺曲线的8、10对应,省去中间段,则8~10两端的形状为“u·u”型,与9号点前后单元的形状类型一致,故仍保持一对二的匹配。经过精细匹配后,f与g的特征点匹配结果如图3d,其中点9与点8和点10匹配。

显示原图| 下载原图ZIP| 生成PPT

图4   根据弧段形态精细化特征点的一对二情况

Fig.4   Refining one to two matching relation of characteristic points according to shape character

首级特征点匹配完成后,再进行二级特征点匹配,图5a给出了2个同名等高线首级特征点的匹配及各个下级特征点,对大比例尺下任意一个二级特征点,在小比例尺所对应的首级特征点之间搜索最近的二级同名特征点,然后删除距离大于阈值的匹配。二级特征点匹配完成后,再进行下一级的特征点匹配,直到各级特征点匹配完成为止。图5b给出各级特征点匹配的结果。

显示原图| 下载原图ZIP| 生成PPT

图5   两个同名等高线的多级特征点及其匹配的结果

Fig.5   Multi-hierarchical characteristic points of correspondence contour and their matching results

1.3 对开等高线特征点识别与匹配

上文讨论的均是闭合等高线,对于开等高线以其首尾点的连线作镜像处理获得闭合曲线（图6）,用与上文同样的方法获取特征点并匹配。如果首尾点不能成为首级同名特征点,需要添加它们作为首级同名特征点。匹配完成后,除掉镜像的部分,后续的内插部分与闭合等高线的操作一样。

显示原图| 下载原图ZIP| 生成PPT

图6   开等高线经过镜像处理后构成闭合曲线

Fig.6   The open contour is processed into close curve through mirroring with the axis of symmetry including starting and ending points

1.4 中间尺度等高线数据的获取

对于2个关键尺度下的同名等高线的2个同名弧段,其曲线函数可设为α:[0,1]→f和β:[0,1]→g,其中α(0)和β(0)分别为2个同名弧段的起点,α(1)和β(1)为其终点,对于任意u (1≥u≥0),α(u)匹配β(u),根据线性内插原理^[5],按式（2）得到中间尺度的曲线γ:[0,1]→h。

γ(t,u)=(1-t) α(u)+tβ(u) (2)

式中,t为一个与比例尺相关的参数,γ(t,u)为由f(u)和 tβ(u) 内插得到的t对应的中间尺度下的点。如果已知小比例尺为1∶S₁(对应起点t=0,S₁为关键小比例尺分母)和大比例尺为1∶S₂（对应终点t=1,S₂为关键大比例尺分母）,中间比例尺1∶S₃（S₃为关键中间比例尺分母）的t可用式（3）计算得到：

t=(S₁-S₃)/(S₁-S₂) (3)

大比例尺等高线上点的密度一般大于小比例尺等高线上点的密度,因而在实际计算中将大比例尺等高线上的点按距离比例映射到小比例尺等高线上（图7a)。对于在弧段匹配中退化的特例,即大比例的一段弧段对应小比例尺一点的情况,则将大比例尺弧段上的所有点直接与小比例尺的一点进行映射,如图7a中的弧段8~10与小比例尺的点9为同名弧段,直接将弧段8~10内中间所有的点映射到小比例尺下的点9上。

显示原图| 下载原图ZIP| 生成PPT

图7   中间尺度的等高线获取过程

Fig.7   The procedure of interval contour being created

在地图数据库中,不同尺度的同名等高线以同一ID号进行标示,按网络地图的浏览范围将多个尺度的等高线数据传输到客户端。具体浏览地图时,根据当前的比例尺由式（3）计算得到与比例尺对应的t值,由式（2）计算得到大比例尺下所有等高线上各点在当前比例尺下对应的坐标,将新生成的各点按顺序连接构成曲线,从而实时表达当前尺度下的等高线图形（图7b）。

2 实验和讨论

本文使用C#程序语言在ArcEngine9.3环境中实现了图形渐变技术的试验,选取一定区域的2个关键尺度（1∶5 000和1∶1 000）下的等高线数据,利用凸壳与BLG树获取多层次的特征点,通过邻近距离与弧段的形态特性的比较实现同名特征点的匹配,当浏览的比例尺发生变化时自动获取与当前比例尺相适应的等高线表达。在图8a给出一定区域1∶1 000的等高线数据,图8a~d为在本文模型下从1∶5 000到1∶1 000中间尺度的等高线表达。为了考察算法的复杂度,实验中选取10条不同长度及复杂度的等高线,记录探测特征点以及同名特征匹配所需时间,并与文献[5]提供的方法所耗时间进行对比（表1）,从表1可看出本文的模型无论是在特征点探测还是特征点匹配所耗时间都明显少于文献[5]提供的模型,从总时间看,本模型所耗的时间为文献[5]提供的模型的42%,在算法复杂化度上明显优于对方。从图8显示的效果看各中间尺度图形等高线渐变效果良好,说明本模型的实用性。

显示原图| 下载原图ZIP| 生成PPT

图8   基于图形渐变技术的等高线连续尺度表达

Fig.8   Continual-scale representations of contours based on morphing technique

在全自动地图连续尺度表达中常常容易出现是要素自身或相互的拓扑冲突,而本文使用的图形渐变技术,中间尺度的数据受两尺度数据的严格控制,中间尺度的数据只是关键尺度数据的微调,因而出现拓扑冲突的可能性不大。

3 结 论

本文依据两关键尺度下的等高线数据,应用图形渐变技术内插出中间尺度的等高线数据,实现了等高线连续尺度的表达,模型的关键技术是基于形状分析的等高线特征点的探测及其匹配过程,通过实验验证了该模型的有效性。必须说明,由于地形的多样性和复杂性,即使是人工方法进行等高线的多尺度表达也是费脑费时,本模型最适应于地形起伏不大的大比例尺等高线连续尺度表达。对于地形复杂程度较高的等高线,特征点的探测与匹配是本模型能否实用的关键,下一步将充分吸收图像图形模式识别的成果,进一步提高特征点探测和匹配的精度和效率,以得到更为实用的实时多尺度的地图要素的表达。

The authors have declared that no competing interests exist.

参考文献

文献选项

• 原文顺序
• 文献年度倒序
• 文中引用次数倒序
• 被引期刊影响因子