临近特征点类型匹配的多边形渐变表达模型

刘鹏程 ，揭 毅 ，杨文博

1.华中师范大学 城市与环境科学学院，武汉 430079

2.地理过程分析与模拟湖北省重点实验室，武汉 430079

网络地图是GIS发展到网络时代的产物，也是GIS适应IT技术潮流发展和全球化的必然要求，同时也是进行地理空间资源共享的主要手段。随着网络可视化技术在相关领域的快速发展，静态的、单一尺度的地图可视化方式已经无法满足人们的实际应用与分析需要，人们更希望能够实现空间信息可视化表达的多视角、多视点和多层次[1-3]。然而在网络环境下，地图可视化环境的任意性、地图综合的复杂性造成了地图综合算法的耗时与地图多尺度度实时响应需求的矛盾，因而网络地图适应性表达也一直是GIS发展的一个瓶颈[4]。

Morphing连续变形技术最初产生于对图像的连续平滑过渡渐变处理，随着地图综合技术的发展，也被逐渐应用于地图自动综合领域。其主要原理是依据同一目标要素的两个不同尺度下的实体要素数据，实现从一个尺度数据到另一个尺度数据的渐变，实现中间任意尺度数据的获取，目前主要应用于道路、河网、等高线等线性要素的综合研究领域[5]。

本文将Morphing连续变形技术扩展应用于多边形要素的连续尺度表达，依据输入的同一多边形的两个不同尺度数据内插获取中间任意尺度的多边形数据。Morphing连续变形技术在多边形要素连续尺度表达的实现主要需解决以下几方面关键技术：（1）多边形轮廓形状特征点的探测。特征点是指那些能够代表当前要素形状特征的点，是对两个尺度数据进行匹配的控制点。对于线型要素特征点的探测，Chetverikov提出通过探测曲线弯曲的方式，以高曲率点作为曲线特征点[6]；Nöllenburg利用贝塞尔曲线来筛选原曲线上弧度较大处的顶点作为特征点[7]；Cecconi通过打断最长边的方法实现两个尺度曲线节点数量相等且一一对应，以打断后的节点作为特征点[8]；邓敏通过构建曲线弯曲树和弯曲森林，以各个弯曲的起始点作为曲线特征点[9]；彭东亮对线要素构建BLG树，以BLG树节点作为特征点[10-11]。本文认为两个尺度多边形虽然存在位置、形状细节的差异，但在总体轮廓上仍然具有相当的相似性，因此采用构建凸壳剖分树的方法，以凸壳上的点作为多边形的特征点。（2）建立曲线特征点的匹配关系。在这一问题上，彭东亮利用缓冲区探测匹配河流[10-11]；Cecconi以位移路径距离最小进行特征点弧段匹配[7]；邓敏从弯曲度量指标中提取出弯曲面积比作为特征点的匹配指标[9]。总体来说，这些方法没有在多个层次结构上实施特征点的匹配。本文利用凸壳特征树建立特征点的层次结构，利用特征点的邻近关系和类型匹配特征点使其匹配更有效，从而当尺度变化时多边形变化更为连续流畅。

1 多边形多层次特征点的建立及层次曲线的分段

特征点的探测是Morphing技术实现中一个重要的前提条件，多边形上两个连续的特征点之间的弧段是Morphing技术实施的基本图形单元，Morphing技术是以各个单元的渐变组合而成的。多边形的特征点是包含图形信息较多的点，多边形凸壳上的点是多边形凸起和凹陷的过渡点，能够反应多边形图形在这些点变化。本文对多边形边界特征点的探测采用多边形的凸壳多层次模型[12-14]。具体方法如下：

首先，对多边形构建凸壳层次结构，本文采用文献[13]提出的方法，构建多边形的凸壳多叉树，如图1（a）和1（b）所示。其次，在多边形凸壳多叉树上，将多边形及其子树上的多边形的弧段分为两类：I类弧段：它们是多边形的连续两点或者多点。图2（a）以根节点多边形C0为例，0-1、52-53、70-71为相邻连续两点构建的弧段，25-26-27、32-33-34、40-41-42、60-61-62-63为连续多点构成的弧段，分别构成该多边形边界上的凸起类型弧段。II类弧段：凸壳上连续两点，它们在多边形上为不连续的点，多边形上这两点之间的弧段为II类弧段。如图2（a）上的 1-20、20-25、27-32、34-40、42-52、53-60、63-70、70-0节点构成的弧段，表现为多边形边界上的凹陷部分。这样便可以将多边形的边界分为凸凹两种弧段形状的组合。

图1 多边形凸壳剖分树及其结构图

图2 多边形分段和层次特征点图

最终多边形边界被分解为多个层次的多个凹凸弧段构成的树状结构，同一层次相邻弧段的连接点即为当前弧段所属层次的特征点。为了方便后续特征点的匹配需要，以顺时针方向为前进方向，根据特征点连接前后弧段的的类型，将特征点分为以下三个类型：u-u类：前后均为凹陷，图2（a）中的1-20和20-25相邻弧段的连接点20即为u-u类；u-n类：前为凹陷后为凸起，图2（a）中的20-25和25-27相邻弧段的连接点25即为u-n类；n-u类：前为凸起后为凹陷，图2（a）中的25-27和27-32相邻弧段的连接点27即为n-u类。为了便于分析，将特征点分为三个层次分，即根节点多边形的所有弧段连接节点构成的第一层次特征点、第二级凸壳树的凸壳点构成第二层次特征点和其他层次的所有凸壳点组成第三层次特征点，最终结果如图2（b）所示，黑色方块、灰色圆和黑色圆分别对应第一、二、三层次特征点。

整个多边形边界的各个弧段为一种层次关系，采用多叉树的数据结构来记录各个层次的分段状况：

2 基于位置临近的特征点类型匹配

2.1 首级特征点的匹配

设f和g分别为同一要素的大比例尺和小比例尺两个尺度下的面实体要素的边界线，f的首级特征点集合为{P(Xi,Yi)|2＜i≤m}，m为f的首级特征点数量；g的首级特征点结合为{P(Xj,Yj)|2＜j≤n}，n为g的首级特征点数量。由于f和g均为面实体要素的边界，边界线为闭合的曲线，因此有f和g的特征点数量m＞2且n＞2；同时由于大比例尺要素具有更加详细而复杂的轮廓信息，因此f的首级特征点数会多于g的首级特征点数，即m＞n＞2，因此特征点的匹配方向为由大比例尺图形特征点集合向小比例尺特征点集合方向进行映射匹配探测。

对于f上任意一点Pf(Xi,Yi)，以该点为起点，在g的特征点集合{P(Xj,Yj)|2＜j≤n}中查询与Pf(Xi,Yi)线性距离最为临近的点Pg(Xj,Yj)，建立最初的首级特征点匹配关系集合，如图3（a）所示；由于大比例尺多边形上的特征点多于小比例尺多边形的特征点，因此可能会出现多个Pf(Xi,Yi)对应一个Pg(Xj,Yj)的情况，如图3（a）中的25-14和27-14；因此需要对初次匹配后的特征点关系进行精细化的匹配处理，本文采用特征点类型匹配方法，即对应匹配的特征点的前后曲线凹凸类型必须保持一致。如图4（a）所示大比例尺曲线上的特征点25类型为u-n，27为n-u；小比例尺曲线上的特征点14的特征点类型为n-u，因此删除不匹配的特征点配对25-14，如图4（b）所示，最终f与g的首级特征点的匹配结果如图3（b）所示，灰色边框为大比例尺要素，特征点为灰色，点号以圆圈加数字表示；黑色边框为小比例尺要素，特征点为灰色，点号以方框加数字表示。

图3 首级特征点匹配

2.2 次级特征点的匹配

在完成首级特征点的匹配后，基本完成了对两个尺度多边形形状的各个基本分弧段的匹配，两个多边形的边界弧段被分划为数量相等、一一对应的弧段组合。在此基础上，进行下一等级的特征点匹配，同样以大比例尺特征点为起点，向小比例尺方向对应特征点弧段搜索最临近特征点；首先处理多个特征点对应一个特征点的情况，假如大比例尺要素f上有多个点同时对应小比例尺要素g上的一个点，D(Pf,Pg)表示f上的点到g上的点的距离，AvgD表示所有距离的平均值，如果f上当前点的D(Pf,Pg)>AvgD，则删除该匹配，如图5（b）所示；然后删除特征点类型（特征点前后弧段凹凸类型）不匹配的组合，最后得到该层次的特征点匹配组合结果；如果最后结果中还有多个特征点对应一个特征点的情况，我们将匹配线长度最小的匹配组合予以保留，使得特征点的匹配始终保持一一对应的组合，如图5（c）所示，以此类推，直到三个层次特征点全部匹配完成。如图5（d）所示，红色连接线表示第一层次特征点匹配连接，蓝色色连接线表示第二级特征点的匹配连接，绿色连接线表示三级特征点的匹配，多边形边界上相邻匹配特征点所构成的弧段即为多边形的匹配弧段，最后的两个尺度下的匹配弧段数量相等且一一对应。

图4 基于特征点类型的精细匹配

图5 次级特征点的匹配过程

特征点匹配是Morphing技术成功实施的关键，在在线式（on-line）地图多尺度的表达中，计算效率是应用得以实施的基础。文献[6]采用线性规划的原理进行形状相似性匹配，计算复杂度很高，比较适合离线式（off-line）的地图多尺度表达。本文采用基于位置临近的特征点类型匹配方法，一方面顾及了两个尺度下的多边形局部形状的相似性，另一方面充分考虑了不同尺度下同一要素的点位坐标的相对一致性，而且凸壳计算复杂度不高，每个层次的计算复杂度为O(n2)（n为多边形上点的个数），因而该算法是较为实用的算法。

为了验证本文算法的合理性，本文在文献[15]形状相似性模型的基础上提出了特征点匹配精度的验证模型，如式（1）。

表1 两种模型匹配精度比较

表1中，第2列为待匹配的两多边形的点数，第三列、第四列分别为按文献[6]的方法得到的分段数及匹配精度，第三列、第四列分别为按本文的方法得到的分段数及匹配精度，从匹配精度而言，本文的方法略高于文献[6]方法，这说明两模型都是可行的。

3 中间尺度多边形的获取

3.1 内插原理

式（2）中t为一个与比例尺相关的参数，h(t,μ)为由f(μ)和g(μ)内插得到的中间尺度下的点。如果已知小比例尺为1∶S1和已知大比例尺为1∶S2，中间比例尺为1∶S3的t值可用式（3）计算得到：

t=0、t=1分别对应小比例尺和大比例尺。

3.2 中间尺度多边形的获取操作

对于两个匹配好的不同尺度同名多边形，同样以大比例尺多边形的弧段向其匹配的小比例尺弧段为方向，将大比例尺多边形边界上位于该弧段的所有节点（包括弧段的起点和终点），映射到匹配好的小比例尺弧段上。映射方法为：计算大比例尺弧段各个节点沿多边形边界到其所处匹配弧段起点的距离与总弧段长度的比值，在小比例尺弧段上搜索到弧段起点的距离与弧段长度比值等于大比例尺弧段距离的点，这些新得到的点即为映射点；将大比例尺多边形的边界节点为起点与其映射点为终点连线构成用于进行数据内插的内插线，图6中，黑色闭合曲线为小比例尺多边形，灰色闭合曲线为大比例尺多边形，连接两个尺度多边形的红色线即为映射线，箭头指示映射方向；根据式（3）和数据两端比例尺以及所需的比例尺计算获得当前t值，将内插线的起点、终点和t值带入式（2）计算内插点，将内插得到的内插点集合按顺序连接并闭合构成所需比例尺的多边形数据，如图6中的浅黄色区域构成的多边形即为内插后得到的多边形。

图6 中间尺度数据的获取过程

4 实验和讨论

为了讨论本文模型的有效性，将本文的模型（以下简称A模型）和文献[10]提供的基于BLG二叉树的匹配模型（以下简称B模型）进行了比较：A模型中，特征点的匹配均为“一对一”，不存在“一对多”的情况，在图7（a）中，大尺度的特征点11与小尺度下的特征点19匹配，显然不合理，在地图要素的多尺度表达中，小尺度下的特征点19、21综合为大尺度下的特征点11，在这种情况下“一对一”的匹配是错误的。图7（b）是由A模型获得的匹配，小尺度下的特征点19、21与大尺度下的特征点11匹配，匹配情况正好与地图综合的点要素的删除相符。图7（a）中这样的情形还有多处，如大尺度的特征点2、4、6、13处都存在匹配错误。另外从得到的中间尺度的多边形的效果看，模型A的渐变效果更合理。

图7 两种特征点匹配方法的比较

图8 基于Morphing变形技术的多边形内插实验结果

本文通过ArcGIS Server API for Flex对基于凸壳剖分树的层次特征点提取、匹配，以及映射线的构建和中间尺度数据的获取全过程进行了编程实现。并选取了四个不同关键尺度下的同名多边形数据进行试验分析；当对地图进行缩放操作时，根据当前比例尺与最邻近的前后两个关键比例尺计算获取t值，在两个相邻关键尺度间内插获得当前地图数据。如图8（a1）-（f1）和（a2）-（f2）为数据库中存储的四个相邻关键尺度数据，根据式（1）内插分别获取相邻关键尺度的中间尺度多边形数据，在两个相邻尺度中，分别取值t=0.2、t=0.4、t=0.6和t=0.8，可以看到随着t值的递增变化，多边形的形状实现了由一个关键尺度到其相邻关键尺度的平滑过渡。传统的地图综合过程完全由大比例尺一端控制，采取一定的综合算法以增量的方式派生出其他相邻比例尺，完成对小比例尺数据的输出和显示，随着尺度距离的增大，综合结果的形态难以控制；本文提出一种基于Morphing技术的多边形连续尺度表达方法，利用两个相邻关键尺度的地理要素数据集合，内插得到中间尺度数据的方法，实验表明从两端实现对综合结果的控制，能够很好的保持数据的几何以及拓扑特性。本文的下一步研究工作将主要集中于进一步提高Morphing在多边形中的内插精度和算法效率。

[1]李精忠.尺度空间地图多重表达的面向对象数据模型研究[D].武汉：武汉大学，2009.

[2]张强，武芳，钱海忠，等.基于关键比例尺的空间数据多尺度表达[J].测绘科学技术学报，2011，28（5）：383-386.

[3]江南，白小双，曹亚妮.基础电子地图多尺度显示模型的建立与应用[J].武汉大学学报：信息科学版，2010，35（7）：768-772.

[4]王艳慧，李娟，宫辉力.地理要素多尺度表达的基本问题[J].中国科学：E辑，技术科学，2006，36（增刊）：38-44.

[5]刘鹏程，龚冲亚，陶建斌，等.基于图形渐变技术的等高线连续尺度表达模型[J].地理科学，2014，34（3）：332-337.

[6]Chetverikov D.A simple and efficient algorithm for detection of high curvature points in planar curves[C]//Computer Analysis of Images and Patterns.Berlin Heidelberg：Springer，2003：746-753.

[7]Nöllenburg M，Merrick D，Wolff A，et al.Morphing polylines：A step towards continuous generalization[J].Computers，Environment and Urban Systems，2008，32（4）：248-260.

[8]Cecconi A.Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D].University of Zurich，2003.

[9]邓敏，彭东亮，徐震，等.一种基于弯曲结构的线状要素Morphing方法[J].中南大学学报：自然科学版，2012，43（7）：2674-2682.

[10]彭东亮，邓敏，徐枫.顾及BLG树结构特征的线状要素Morphing变换方法[J].武汉大学学报：信息科学版，2012，37（9）：1120-1124.

[11]彭东亮，邓敏，赵彬彬，等.河网多尺度Morphing的变换方法研究[J].遥感学报，2012，16（5）：953-968.

[12]Ai T，bZ，LiuY.Progressive transmission of vector data based on changesaccumulation model[C]//Proceedings of the 11th International Symposium on Spatial Data Handling.Leicester，UK.Berlin：Springer-Verlag，2004：85-96.

[13]艾廷华，李志林，刘耀林，等.面向流媒体传输的空间数据变化累积模型[J].测绘学报，2009，38（6）：514-519.

[14]艾廷华，成建国.对空间数据多尺度表达有关问题的思考[J].武汉大学学报：信息科学版，2005，30（5）：377-382.

[15]Arkin E M，Chew L P，Huttenlocher D P，et al.An efficiently computable metric for comparing polygonal shapes[J].IEEE Transactionson Pattern Analysisand Machine Intelligence，1991，13（3）：209-216.