层次特征点控制的线状要素Morphing方法

裴洪星

(信息工程大学，河南 郑州 450001)

层次特征点控制的线状要素Morphing方法

裴洪星

(信息工程大学，河南 郑州 450001)

针对多尺度表达中同名线要素的变换问题，提出一种层次特征点控制下的线状要素Morphing变换方法，在已有的线性插值Morphing变换基础上，利用层次特征点对线要素进行分段控制，按对应弧段的结点的相对位置在本弧段的相同的相对位置处插入点，提高插值过程中点的位置对应精度，使中间比例尺的插值表达得到优化，提高Morphing变换的精度。

线状要素；Morphing；插值；层次特征点

Morphing又称图形渐变技术，最早应用于计算机图形处理领域，其基本思想是采用某种内插方法使得初始图形连续、平滑地渐变到目标图形，具体实施涉及两个基本过程，即图形特征匹配和形状插值[1]。近年来，由于电子地图多尺度表达的发展，要求变换过程中地图要素能够连续、平滑地显示，这与Morphing的目标相一致，由此促进了Morphing技术在地图制图领域的应用与发展，目前Morphing技术在地图制图领域主要应用于道路、河流以及居民地边界等线状要素的形状内插，以生成所需尺度的线状要素形态[2-4]。

传统的基于综合方法的尺度变换模式是在某一比例尺数据下对线要素进行化简，实现尺度变化过程中的要素形态变化。要素在进行化简时，往往采用的是传统的经典算法，如Douglas-Peucker算法[5]、Li-Openshaw算法[6]，其缺点在于缺少要素变换方向的控制，容易产生几何、拓扑不一致，无法做到控制数据向另一端的数据渐进变换[7]。借鉴Morphing思想，通过某一尺度变换区间两端的同名要素控制变换的方向，实现不同比例尺同名道路的连续、平滑变换，在多尺度表达中更加合理。基于矢量数据的Morphing变换可分为两个步骤：首先，对不同尺度上两对应要素建立对应点；然后，以一定的移位路径进行形状内插。一般情况下由于Morphing变换幅度较小，不易产生拓扑问题，因此可以用对应点之间的直线段作为移位路径[8]。可以看出，在移位路径确定的前提下，对应点的精度决定了Morphing变换结果的精度。对于线状要素的Morphing变换，李精忠利用模拟退火的思想建立线要素之间点的最优匹配，实现了真实数据的Morphing渐变效果[9]；邓敏、彭东亮对线状要素的弯曲结构进行提取，通过对线要素整体结构分析建立弯曲对应关系实现Morphing变换[10-11]，提高了匹配精度。虽然都实现了线状要素Morphing变换，且在一定程度上提高了精度，但是算法本身存在设计较复杂、耗时长、对要素的结构相似性要求较高，不利于快速生成所需尺度的表达。为此，本文提出层次特征点控制下的线状要素Morphing变换方法。

1 基本原理

对于不同比例尺的同名线状要素，设其大比例尺表达为A，小比例尺表达为B，它们分别是不同函数的连续表达，设A的函数表达为f(x)(0≤x≤1),f(0)和f(1)分别对应A的起点和终点，B的函数表达为h(x)(0≤x≤1),h(0)和h(1)分别对应A的起点和终点。本文研究的目标就是利用Morphing思想在不同比例尺的同名曲线A和B之间进行一系列中间比例尺处的形状插值，实现两者之间连续、平滑的变换。设中间插值生成的连续表达为M，其函数表达为g(x),它的定义域为[0,1]，g(0)和g(1)分别对应M的起点和终点。A和B可以通过对应点之间的连线作为移位路径，插值生成中间比例尺的表达M。设t为要素A对中间插值表达的影响因子(0≤t≤1)，

(1)

式中：S0和S1分别为大、小比例尺数据的分母，S是中间插值表达的比例尺分母。则中间某一具体比例尺处插值的函数表达为[3]

(2)

式中:f(u)与h(u)分别为A和B上相对应的点，g(t,u)为二者之间对应点生成的中间比例尺表达。其中代表中间插值受两端比例尺影响的程度。t=0时，M的内插表达为A；t=0时，M的内插表达为B。

特征点控制线状要素的基本形态，同一线状要素，在不同比例尺下其细节层次存在一定的差异，但其整体的形态往往是高度一致的，因此，通过提取控制要素整体结构的特征点对不同比例尺的同名要素进行分段约束，使线要素整体对应变为线要素之间的弧段之间的对应，从而提高了对应精度，使形状插值更加精确，提高Morphing精度。

2 层次特征点控制的Morphing变换

本文提出一种方法，利用Douglas-Peucker算法思想对线要素逐层提取特征点，建立层次特征点的二叉树结构，使线要素被不同层次特征点的逐级分割，将同名线要素整体的对应关系转换为线要素之间弧段的一一对应关系，从而提高整体的对应精度，在对应的弧段对之间进行插值，实现任意中间比例尺要素的生成。

2.1 提取层次特征点

Douglas-Peucker算法是一种经典的线状要素化简方法[3]，其实质是根据线状要素上具有较大意义的一系列特征点提取其主要形态。借鉴其思想，本文利用Douglas-Peucker算法的循环迭代提取曲线上控制其整体基本形态的特征点。提取特征点的过程如下：

1)设定阈值d，利用道格拉斯-普克法提取距离曲线首末点连线的距离最大点，记录其ID号，将其作为二叉树根结点，以该点为界将曲线划分为左右子曲线。

2)对左右子曲线计算各自范围内的距离首末结点连线最大的结点，并分别存储在二叉树的下一层左右子结点中，并记录他们各自的ID号，若某一子曲线中不存在大于阈值的点，则记录为空，存储在相应的二叉树子结点处。

3)循环进行，直到二叉树的最后一层叶子结点全部为空，循环停止。加入首末结点至此提取出所有特征点。

提取的特征点组织上构成了一棵完全二叉树，同名线要素对应特征点处在二叉树中的相同位置。提取出的结点具有层次性，对线要素形成逐级划分，使同名线要素被分为不同弧段并逐级对应。理论上，提取的特征点越多，对曲线进行的分段控制效果就越好，Morphing的精度就越高，但是当阈值过小时，线要素的小弯曲会对特征点的提取造成干扰，从而提取到小弯曲上的点作为错误的特征点，破坏同名线要素特征点二叉树结点的对应性。因此，需要设定合理的阈值，尽可能提取到多的特征点，同时使同名线要素之间的特征点准确对应，如图1所示。

2.2 结点相对位置插值

提取特征点的目的是通过特征点对曲线进行分段，使不同比例尺的同一曲线能够分段对应，再进行插值，从而提高插值的精度。上一节中，利用道格拉斯-普克法的思想提取了不同比例尺同一线状要素的特征点并将特征点分层存储在二叉树的结点中，小比例尺下线状要素的表达是从大比例尺下的表达经过顶点抽稀、弯曲删除、弯曲夸大等操作得到的，小比例尺下提取的特征点能在大比例尺中找到对应点，反之则未必[5]。因此，本文根据小比例尺二叉树中的特征点，在大比例尺特征点二叉树中的相同位置寻找对应点，从而建立不同比例尺同名曲线之间特征点的对应关系。曲线的特征点将曲线划分不同层级为若干弧段，根据特征点的层次建立曲线间弧段的对应关系。由特征点划分得到的弧段称为控制弧段。

建立控制弧段之间的对应关系后，在对应控制弧段对上分别进行点的插值，以完成控制弧段内结点的对应关系。为了便于说明确定插值的位置，定义如下：

定义1结点的位置p。结点到曲线起点的所有线段的长度之和L与曲线的长度L0的比值，p=L/L0。

插值过程如下：

1)根据提取的特征点对曲线进行划分。对同名曲线上特征点二叉树进行遍历，只有两个二叉树同一位置特征点都存在且不为空时，才同时选择该处的特征点作为划分两条同名曲线特征点。选取所有满足条件的特征点，根据特征点在二叉树中的层次性将曲线逐级划分，使弧段一一对应。

2)对各控制弧段进行点插值。在特征点选取时，特征点之间严格的对应关系已经确定了控制弧段的匹配关系，对分段后的曲线A和B分别求取每个弧段的长度，并计算控制弧段内的结点的相对位置，记录在列表中。

3)对曲线进行分段插值求同名曲线的中间比例尺表达。对曲线A上的控制弧段A1，曲线B上与其对应的控制弧段B1，访问存储B1上的结点相对位置的列表，读取该弧段上各点的相对位置，然后在控制弧段A1内的同样的相对位置处插入点，同样在B1上相同的位置处插入A1上的对应点。循环继续进行，直到曲线A、B各控制弧段上都插入了对应的点，连接对应的结点，称之为插值路径，计算对应结点在插值路径上的插值点。插值点的坐标(x,y)计算公式为

(3)

式中：(x,y)为新插值点的坐标，(xs,ys)为插值路径的起点坐标，(xe,ye)为插值路径的末结点坐标，t为式(1)中大比例尺要素对插值表达的影响因子。

对同名线要素上所有的对应点插值得到插值点集。依次连接相邻插值路径上的插值点，得到曲线A和B的Morphing变换曲线，最后对插值得到的曲线进行平滑处理。

3 实验与分析

为了验证方法的可行性，基于C#语言使用Visual Studio 2010平台构建实验平台，选取宁波市1∶25万和1∶100万的某两条同名道路线状要素进行实验，对它们进行Morphing变换，生成它们的中间比例尺的表达。数据的初始状态和最终状态(即t=0和t=1时的图形)，如图2所示。

对实验数据中的同名线状道路分别提取特征点，经过多次试验，设定阈值d=300 m时，能够在同名道路线要素提取比较一致的特征点。如图3所示，根据提取到的特征点的层次性对道路整体进行逐级划分，实验中两条道路分别各自提取到9个特征点，这些特征点将它们各自划分为8条控制弧段，根据特征点的层次对应性建立控制弧段之间的一一对应关系。

图2 实验数据

图3 提取特征点

以控制弧段为单位，在进行Morphing变换前对控制弧段进行点加密处理。计算并记录控制弧段上的结点的相对位置，在控制弧段上读取与之匹配的弧段的结点的相对位置，并在同样的位置处插入结点。经过点插入操作，匹配弧段上的结点数量保持一致，即从道路线要素的起点开始，在两条同名道路之间建立了所有结点的一一对应关系。矢量道路数据是根据“结点—弧段”结构进行组织的，实际上线要素是一系列有序的点的集合，因此，两条同名道路线要素的Morphing中间变换时，本质上是求中间状态的点集。在点插入操作后，道路线要素间从起点开始所有结点依次一一对应，如图4所示。

图4 特征点控制下线要素结点对应

对应结点之间的连线就是结点的插值路径。由式(3)确定对应点的中间插值表达点，最终生成所有对应点的同一尺度的表达，将插值得到的点集转换为线要素，得到同名道路线要素的中间尺度表达，据此得到的Morphing变换曲线局部起伏较大，需要对其进行平滑处理，从而得到更好的视觉效果，经过逐步插值得到了不同比例尺下的中间表达，从而实现了同名道路从1∶25万到1∶100万的平滑过渡表达。图5、图6分别为线性插值算法和本文算法实现的Morphing变换。

对两种方法进行的Morphing变换进行对比，线性变换在插值过程中，只是在对应结点之间进行插值，得到中间尺度的点集，再由点集转化为线要素，从而生成线要素中间尺度表达。其缺点在于原始线要素结点只是在顺序上互相对应，位置上并没有受到约束，因此，对应点之间在位置上存在偏差。Morphing变换过程中，插值在错误对应的位置之间进行，导致中间表达出现偏差，由图5(b)可以观察到线性插值后同名线要素同一拐点并没有成为对应点，而是出现了一定的位置偏差；本文方法则是在提取控制点的前提下，由控制点的对应关系约束相邻控制点之间的弧段对应关系，能控制Morphing变换过程的关键位置的偏差，图6与图5对比可以看出本文方法结点位置的对应精度更高，相比于线性插值方法， 其Morphing准确度更高。

图5 线性插值Morphing变换

图6 层次特征点控制下Morphing变换

4 结 论

本文方法利用计算机图形处理领域的Morphing渐变思想，对不同比例尺的线状要素进行插值变换，实现同名线要素间的平滑变换，对已有的线性插值方法进行了改进，在其原有的基础上提高了插值的精度，提高了Morphing变换的准确性，使其表达更合理。本方法还存在一定缺陷，需要提高匹配的控制弧段内的结点的位置对应的精度，可以考虑在控制弧段内的再次提取次特征点，提高弧段的对应精度，从而提高插值精度，进一步优化Morphing变换的表达。

[1] 李华,朱光喜,朱耀庭,等.物体渐变技术现状与发展[J].中国图象图形学报,2002,7(8): 745-751.

[2] CECCONI A. Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D]. Zurich: University of Zurich. Faculty of Mathematics & Science, 2003: 109-112.

[3] NÖLLENBURG M, MERRICK D, WOLFF A, et al. Morphing polylines: A step towards continuous generalization[J]. Computers, Environment and Urban Systems, 2008, 32: 248-260.

[4] ALBRECHT S. A solution to the vertex correspondence problem in 2D polygon morphing[D]. Osnabruck: University Osnabruck Department of Mathematics/Computer Science, 2006: 11-22.

[5] DOUGLAS D H,PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. The Canadian Cartographer, 1973, 10(2): 112-122.

[6] LI Zhilin, Openshaw S.基于客观综合自然规律的线状要素自动综合的算法[J].武测译文,1994(1):49-58.

[7] 李精忠.尺度空间地图多重表达的面向对象数据模型研究[D]. 武汉:武汉大学,2009:67-72.

[8] 马江林,赵忠明,孟瑜,等.海量遥感分类图连通域标记力法[J].计算机工程,2008,34(1): 262-264.

[9] 李精忠,吴晨琛,杨泽龙.一种利用模拟退火思想的线状要素Morphing方法[J].武汉大学学报(自然科学版),2014,39(12):1446-1451.

[10] 邓敏,彭东亮,徐震. 一种基于弯曲结构的线状要素Morphing方法[J].中南大学学报(自然科学版),2012,43(7):2674-2682.

[11] 彭东亮,邓敏,刘慧敏. 更充分利用独立弯曲结构的线状要素Morphine变换方法[J].测绘学报,2014,43(6),638-646.

[责任编辑：刘文霞]

A Morphing method based on hierarchical feature points for linear features

PEI Hongxing

(Information Engineering University, Zhengzhou 450001, China)

A new Morphing method for two linear features is proposed based on the feature points of the linear features to solve the problem of transformation between linear features of the same in multi-scale representation. To improve the position precision of points each other, hierarchical feature points are extracted so that linear features will be split into several parts. And every part can be matched with one of another linear features. Then new points will be added in one of the pairs the same relative position as others of the other one. Compared with the linear interpolation, the precision of Morphing of this method is improved, thus realizing a more reasonable representation between two linear features of two different scales.

linear features; Morphing; interpolation; hierarchical feature points

引用著录：裴洪星.层次特征点控制的线状要素Morphing方法[J].测绘工程，2017，26(4)：53-57.

10.19349/j.cnki.issn1006-7949.2017.04.010

2016-04-15；

2016-05-15

裴洪星(1991-)，男，硕士.

P208

A

1006-7949(2017)04-0053-05