更充分利用独立弯曲结构的线状要素Morphing变换方法

彭东亮，邓 敏，刘慧敏

中南大学地球科学与信息物理学院，湖南 长沙 410083

更充分利用独立弯曲结构的线状要素Morphing变换方法

彭东亮，邓 敏，刘慧敏

中南大学地球科学与信息物理学院，湖南 长沙 410083

提出更充分利用独立弯曲结构的线状要素Morphing变换方法。该方法首先对不同比例尺表达的对应线状要素分别构建约束Delaunay三角网并建立弯曲森林，然后进行弯曲匹配以获得对应弯曲。鉴于对应弯曲“背面”的独立弯曲结构隐藏于更高层次的大弯曲中，将对应弯曲重新构建约束Delaunay三角网进而建立其“背面”的弯曲森林并进行弯曲匹配得到新的对应弯曲。依此递归，更充分地挖掘对应弯曲结构。在此基础上，将所有对应弯曲的对应起点和对应终点都作为断点切割原线状要素，获得对应线段。最后，采用线性插值算法建立各对应线段之间的对应点，并以对应点之间的直线段作为移位路径进行Morphing变换。通过实例分析，验证了本文充分利用独立弯曲结构的方法能够提高对应弯曲特征点的识别能力，从而能够更好地保持弯曲特征点并改善Morphing变换效果。

Morphing；形状内插；弯曲；线状要素；制图综合

1 引 言

在信息化地图制图学时代，空间数据的自动综合仍是国际上制图领域最具挑战性和创造性的研究难题，这亦是GIS空间数据多尺度表达的需要［1］。近年来，用户对电子地图提出了连续尺度表达的新要求，这一方面有助于用户在进行放大、缩小等操作时保持视点，另一方面使得用户能够从任意尺度查询地图信息。为了适应这一要求，文献［2］提出了地图连续综合技术，该技术通过对地图进行连续微小的变形以实现地图的连续尺度变换。Morphing变换技术是一种同时顾及形状和颜色的图像内插技术，用于实现从源图像到目标图像的平滑渐变，在动画制作、图像压缩以及医学图像重构等计算机可视化领域有广泛应用［3－5］。由于Morphing变换平滑渐变的思想与地图连续综合技术相契合，其在地图连续综合中亦逐渐受到重视。按照数据模型的不同，Morphing变换可以分为基于矢量数据的Morphing变换［6－11］和基于栅格数据的Morphing变换［12－14］。目前，基于矢量数据的Morphing变换主要用于道路、河流等线状要素的形状内插，以生成所需尺度线状要素形态［9－10］。

基于矢量数据的Morphing变换可分为两个步骤：首先，对不同尺度上两对应要素建立对应点；然后，以一定的移位路径进行形状内插。文献［15］指出，一般情况下由于Morphing变换幅度较小，不易产生拓扑问题，因此可以用对应点之间的直线段作为移位路径。可以看出，在移位路径确定的前提下，对应点的精度决定了Morphing变换结果的精度。在建立对应点方面，文献［9］鉴于较小比例尺线状要素顶点数相对较少，提出对其重复搜索最长边，并在最长边中点增加顶点的策略，使得两不同比例尺线状要素具有相等的顶点数，进而按点号顺序建立顶点之间的一一对应关系。文献［10］考虑到数据量对时间复杂度的影响，利用贝塞尔曲线筛选两线状要素弧度较大处的顶点作为特征点，然后以特征点、相邻特征点间的线段为基本单位，借助动态规划的方法进行匹配，这一方法既提高了运行效率，又在一定程度上保证了对应点精度。文献［16］对于线状要素的每一个顶点，分别连接前后一定范围内的顶点，并选取有较大夹角的顶点作为候选点，然后从候选点中选取一定范围内夹角值最大的顶点作为特征点［17］，进而基于位移最小的原则建立特征点间对应关系。综上分析，目前已有的矢量数据Morphing变换方法在建立对应点时是基于线状要素的局部结构，而忽视了整体结构。在这种情况下，容易得到错误的对应点，且这些错误将无法得到有效纠正，进而导致不合理的Morphing变换结果。为此，本文立足于线状要素的整体结构建立对应线状要素间的对应点。

对于一线状要素，将较大比例尺线状要素记为A，较小比例尺线状要素记为B，并令f：［0，1］→A为一连续函数，且f（0）和f（1）分别为A的起点和终点；令g：［0，1］→B为一连续函数，且g（0）和g（1）分别为B的起点和终点。对A和B建立对应关系，使得A上一点f（u），在B上的对应点为g（u），其中0≤u≤1。此时，即可通过一定的移位路径内插生成线状要素Ct。本文以对应点之间的直线段作为移位路径，不妨令h（t，u）：［0，1］2→R2，且h（t，0）和h（t，1）分别为Ct的起点和终点，建立Ct与A、B的关系为［9］

式中，h（t，u）是与f（u）、g（u）对应的内插点；t为形状内插的程度，并与目标比例尺有关。据式（1），当t＝0时，内插结果Ct为A；当t＝1时，内插结果Ct为B；当0＜t＜1时，内插结果即为中间比例尺线状要素。如何更充分地利用独立弯曲结构提高对应点精度是本文研究重点。对线状要素而言，其空间结构特征信息主要通过弯曲特征来表现［18－19］。分析可以发现，对应线状要素在形态结构上的区别在于较大比例尺线状要素更为细致，但这种区别并不影响人们对弯曲层次结构的整体感官认知。从整体上看，不同比例尺线状要素的弯曲结构具有相似性，这些相似弯曲结构可以为建立对应点映射关系提供重要约束。而在识别弯曲的过程中，部分独立弯曲结构由于隐藏于其他弯曲中而难以被发现，影响了对相似弯曲结构的利用。因此，本文以独立弯曲结构为切入点充分挖掘线状要素的弯曲结构，提出一种更充分利用独立弯曲结构的线状要素Morphing变换方法，采取从整体到局部的策略建立线状要素之间的对应点，以提高对应点的精度。具体策略如图1所示。

2 更充分利用独立弯曲结构的Morphing变换方法

2．1 弯曲的相关概念

文献［18］基于约束Delaunay三角网（简称CDT）模型提出了一种方法描述线状要素弯曲特征在深度上的层次结构，通过对三角网覆盖区域由外向内的三角形“剥皮”操作，以“剥皮”行进过程中不同特征的三角形为依据构建二叉树，实现了对线状要素大弯曲套小弯曲层次结构的表达。这是一个基于Gestalt对称性和连续性原则的方法，符合人们的视觉感官认知，因此本文亦采用该方法识别弯曲结构。为了能够更好地描述本文方法，下面首先讨论弯曲的相关概念。

图1 本文方法流程图Fig．1 The framework of Morphing transformation of linear features proposed

对于一个复合弯曲I，分别以ILeft代表I的左孩子弯曲，IRight代表I的右孩子弯曲；以IStart代表I的第一个顶点，IEnd代表I的最后一个顶点。相应的，以ILeftStart和ILeftEnd分别代表弯曲ILeft的第一个和最后一个顶点；以IRightStart和IRightEnd分别代表弯曲IRight的第一个和最后一个顶点。于是，这些顶点的序号大小具有如下关系

据文献［20］，不包含孩子弯曲的弯曲为基本弯曲，以图2（a）为例（左下角箭头指示线状要素A1的方向），如弯曲ILeft1、IRight1、J1、KLeft1、KRight1；由若干个弯曲套合组成的复杂弯曲称为复合弯曲，如弯曲I1、K1；若一弯曲不是任何其他弯曲的孩子弯曲，则该弯曲为独立弯曲，如弯曲I1、J1、K1。不难发现，独立弯曲可能是基本弯曲，也可能是复合弯曲。对于一个线状要素，其往往存在多个独立弯曲，这些独立弯曲无法表达于同一个二叉树中，为此，下面提出弯曲树和弯曲森林的概念。

图2 线状要素的弯曲结构表达Fig．2 Bend structural representation of linear features

定义1：弯曲树。表达一个独立弯曲层次结构的二叉树。弯曲树的叶子结点对应基本弯曲，根结点对应独立弯曲，其他结点对应复合弯曲，结点的层次关系表达了弯曲的层次结构。如图2（b）所示，弯曲树I1、J1、K1分别为图2（a）中独立弯曲I1、J1、K1的弯曲层次结构表达。

定义2：弯曲森林。一个线状要素拥有两侧，即左侧和右侧，每一侧都通常含有多个独立弯曲，每个独立弯曲对应一颗弯曲树，同一侧的弯曲树按线状要素方向依次排列，构成弯曲森林。据此，一个线状要素有左、右两个弯曲森林。如图2所示，弯曲树I1、J1、K1共同构成线状要素A1右侧的弯曲森林ARight1。

2．2 匹配指标

对两线状要素分别建立弯曲森林后，即可对弯曲树及其孩子弯曲进行匹配，以获得对应弯曲。由于两线状要素的形态结构并不完全一致，对应的弯曲森林也可能不一致，主要体现在两个方面：①对应弯曲森林中弯曲树的数量不一定相等；②对应弯曲树的形态结构可能不一致。另外，对于孩子形态结构一致的两对应弯曲，它们的这两对孩子弯曲也不一定是对应弯曲。因此，仅从弯曲森林及弯曲树的角度，难以准确地进行弯曲匹配，必须引入度量弯曲相似性的指标，以指导弯曲匹配。

文献［21］在裁剪弯曲以对线状要素进行简化时基于CDT模型提出了面积、周长、深度、平均宽度、宽度标准差和裁剪前后基线与线状要素间夹角变化量等6种有关弯曲的度量指标。由于两对应线状要素间的差异度与比例尺的跨度有关，并且同一对应线状要素各局部的差异度也不尽一致，所以这些指标值会有较大波动，不利于对应弯曲的识别。分析发现，弯曲的基线不依赖于弯曲的内部结构，因此受上述差异度的影响较小。这里，弯曲基线是由弯曲的起点和终点连接而成的直线段。例如在图2（a）中，弯曲I1的基线为直线段，记为B（I1）；弯曲的基线为直线段，记为B。下面将采用弯曲基线夹角和弯曲基线长度比这两个指标作为两弯曲是否为对应弯曲的判定标准。

定义3：弯曲基线夹角。对于两个弯曲，将一个弯曲基线移向另一个弯曲基线，使它们的起点重合，则这两个弯曲基线之间大小为［0，π］的夹角即为弯曲基线夹角。以弯曲I1、I2为例，它们的弯曲基线夹角记为ABL（I1，I2）。

理想状况下，弯曲基线夹角应该等于0。但由于数据生产过程中误差不可避免，从而使得弯曲基线夹角并不一定严格等于0。因此，必须给出适当的阈值TA以容忍误差。具体地，若弯曲I1、I2为对应弯曲，则其弯曲基线夹角须满足

定义4：弯曲基线长度比。以弯曲I1、I2为例，B（I1）与B（I2）的长度比值称为弯曲I1、I2的弯曲基线长度比，记为RBL（I1，I2），表达为

理想状况下，弯曲基线长度比应该等于1。同样考虑到误差不可避免，这里给定阈值范围U，使得若弯曲I1、I2为对应弯曲，则须满足

式中，U定义为

式中，TL∈［0，1］是一个控制阈值范围U的参数，其大小可根据数据的实际情况而定。值得注意的是，当TL取值较小时，阈值范围U较大，此时差异较大的两个弯曲可能被视作对应弯曲；当TL取值较大时，阈值范围U较小，一些实际对应弯曲可能无法正确识别。因此，一个适当的TL非常重要。

综上分析，只有当两个弯曲同时满足式（3）和式（5）时，这两个弯曲才可被当做对应弯曲。

2．3 弯曲匹配

弯曲匹配分为两个主要步骤：独立弯曲匹配和子弯曲匹配。独立弯曲匹配是对弯曲森林中的独立弯曲进行匹配以发现对应独立弯曲的过程。子弯曲匹配是匹配当前对应弯曲的子弯曲的过程，该步骤使弯曲匹配可以递归深入到较低层次的弯曲结构中。下面将对整个弯曲匹配过程进行详细描述。

2．3．1 独立弯曲匹配

由于每个线状要素有两个弯曲森林，因此本步骤亦需对两线状要素的左、右侧弯曲森林中的独立弯曲分别进行匹配。尽管在2．2节中已提出ABL、RBL作为两弯曲是否为对应弯曲的判定指标，但仅根据这两个指标判断两个独立弯曲是否为对应弯曲仍有可能导致错误。这是因为两同侧弯曲森林中都含有多个独立弯曲，可能出现两独立弯曲位置相差很大但弯曲参数接近（即满足式（3）和式（5））的情况，而这样的两个独立弯曲不应被当做对应独立弯曲。因此，进一步提出限制条件，以避免这种错误发生。

定义5：沿线状要素长度。假设p0是线状要素D上的一个点，其沿线状要素长度为D的起点沿着D到p0的线段长度。

定义6：相对位置（relative location）。假设p0是线状要素D上的一个点，其相对位置为p0的沿线状要素长度与D 的长度之比，记为RLo（p0）。显然，RLo（p0）∈［0，1］。

一般的，若两个弯曲I、J为对应弯曲，则它们起点和终点的相对位置应该接近，即相对位置之差的绝对值｜RLo（IStrart）－RLo（JStart）｜和｜RLo（IEnd）－RLo（JEnd）｜都应该很小。这样，可以为相对位置之差的绝对值设定一个阈值以限定匹配目标搜索范围。这个阈值的设定需要考虑两个方面：其一，从缩小搜索范围、避免错误匹配的角度，该阈值应尽可能小；其二，从避免漏掉真对应独立弯曲的角度，该阈值应尽可能大。下面将借助相对长度以确定这个合适的阈值。

定义7：相对长度（relative length）。假设I是线状要素D上的一个弯曲，I的相对长度为I的长度与D的长度之比，记为RLe（I），RLe（I）∈［0，1］。在实际应用中，RLe（I）＝RLo（IEnd）－RLo（IStart）。

分析可知，两弯曲相对长度的差距越大，则它们是对应弯曲的可能性越小。这里，以LIB（larger independent bend）表示当前遍历的两个独立弯曲中相对长度大的独立弯曲，以SIB（smaller independent bend）表示相对长度较小的独立弯曲，提出如下假设：

假设1：对于两个独立弯曲，当RLe（SIB）＞0．5RLe（LIB）时，这两个独立弯曲才有可能被判定为对应独立弯曲。这里，将参数设置为0．5亦是基于两个方面的原因：其一，当RLe（SIB）≤0．5 RLe（LIB）时，这两个独立弯曲几乎不可能是对应独立弯曲，因此参数0．5能够识别并直接摈弃差异较大的非对应独立弯曲；其二，参数0．5给独立弯曲匹配留有足够大的差异空间，不会漏掉真对应独立弯曲。根据此假设，可以得到如下关系：（RLo（LIBEnd）－RLo（SIBEnd））－（RLo（LIBStart）－

如上所述，相对位置之差的绝对值｜RLo（LIBStrart）－RLo（SIBStart）｜和｜RLo（LIBEnd）－RLo（SIBEnd）｜都应该很小，因此把差异空间平分为两半，分别容忍两个独立弯曲起点的差异和终点的差异，进一步提出如下假设：

假设2：对于两个独立弯曲，仅当满足以下公式时，它们才有可能被判定为独立弯曲。即

值得注意的是，式（8）、式（9）是式（7）的充分不必要条件。这里，根据假设1和假设2推导出来的参数0．25能够保证搜索范围内不会出现两个独立弯曲位置相差很大但弯曲参数接近的情况，又留有足够大的差异空间保证了不会漏掉真正对应的独立弯曲。因此，参数0．25是合理的，且具有普适意义。到此为止，两弯曲被判定为对应独立弯曲的条件已全部给出，即若两个独立弯曲同时满足式（3）、式（5）、式（8）和式（9）时，这两个独立弯曲将被判定为对应独立弯曲。

2．3．2 孩子弯曲匹配

定义数组Corresponding Bends记录匹配成功的对应弯曲。首先，将一对对应独立弯曲添加到Corresponding Bends中；然后，将该对对应独立弯曲作为当前对应弯曲进行孩子弯曲匹配。对于当前对应弯曲：

（1）如果它们都有孩子弯曲且左、右子弯曲分别对应，即满足式（3）和式（5），则将左、右两对对应子弯曲都添加到Corresponding Bends中，并将它们分别作为当前对应弯曲进行更深层次子弯曲匹配。

（2）如果它们都有子弯曲，但左、右子弯曲并不分别对应，则有可能是图3所示的情况。I3和I4为对应弯曲，在它们的孩子弯曲中，还有L3和L4及M3和M4也分别是对应弯曲。这里，将J3和K3称为干扰弯曲。为了排除干扰弯曲并准确识别对应弯曲（L3，L4）和（M3，M4），分别计算RBL（LSBLaC，SSBLeC）和RBL（LSBLaC，SSBRiC）。其中，LSBLaC为较大比例尺线状要素上弯曲的较大孩子弯曲，SSBLeC为较小比例尺线状要素上弯曲的左孩子弯曲，SSBRiC为较小比例尺线状要素上弯曲的右子弯曲。这里，弯曲大小的依据为弯曲基线长度。如图3所示，需要计算RBL（K3，L4）和RBL（K3，M4）。如果这两个值都大于式（6）中所定义的TL，则将LSBLaC和较小比例尺线状要素上的当前弯曲LSB作为当前对应弯曲（但作为对应弯曲记录添加到Corresponding Bends）进行更深层次的子弯曲匹配。即将图3中的K3和I4作为对应弯曲进行孩子弯曲匹配，使得对应弯曲（L3，L4）和（M3，M4）能够被识别出来。（LSB：larger scale bend；LaC：larger child bend；SSB：smaller scale bend；LeC：left child bend；RiC：right child bend）。

图3 干扰弯曲示例Fig．3 An illustration of the abnormal bends

（3）否则，该分支的子弯曲匹配结束。

当采用子弯曲匹配对所有对应独立弯曲处理完毕后，最终将得到一个记录对应弯曲的数组Corresponding Bends。

2．3．3 更充分利用独立弯曲结构

独立弯曲的起点和终点通常为较明显的极值点，在制图过程中亦能够得到较好保留，且独立弯曲是最高级的弯曲，不受干扰弯曲的影响。因此，对应独立弯曲能够提供高精确度的对应弯曲特征点。但是，在构建CDT并建立弯曲森林的过程中，有部分独立弯曲结构隐藏于更高层次的大弯曲中无法被识别。这里，将描述如何更充分利用独立弯曲结构。

更充分利用独立弯曲结构这一思想体现在图1中的步骤③。对于一对对应弯曲（包括对应独立弯曲），对它们所含的弯曲线段分别重新构建CDT，并构建该对应弯曲异侧的弯曲森林（本侧实际上就是对应弯曲本身，已被识别），亦通俗地表述为建立对应弯曲“背面”的弯曲森林。然后，对于新得到的两个弯曲森林，又可重复利用弯曲匹配以识别对应弯曲。为便于统一，这里规定在重复利用弯曲匹配的过程中，RLo、RLe等参数值仍然参照原线状要素长度进行计算。

2．4 获取对应线段

对于Corresponding Bends中记录的每对对应弯曲，它们的对应起点和对应终点都将作为对应弯曲特征点以对原始线状要素进行切割。值得注意的是，由于同一对对应弯曲特征点可能属于不同的对应弯曲（如一对对应弯曲的对应终点同时又是另外一对对应弯曲的对应起点）导致这些对应弯曲特征点可能被重复识别。因此，对于重复的对应弯曲特征点应予以删除，仅保留一对即可。在此基础上，以对应弯曲特征点为断点将原始线状要素进行对应切割，即可得到若干对对应线段。

3 实例分析

下面通过本文方法在实际数据中的应用来论证其有效性，同时亦将给出直接使用线性插值算法的结果和本文方法在图1中步骤③时（这里称之为基于弯曲结构的方法）的结果以作比较。这里采用加权Translation指标［10］对各方法的结果进行定量评价。加权Translation指标定义为一个线状要素e：［0，1］→E，使得e（u）＝g（u）－f（u），其中，u∈［0，1］，则∑ei（｜ai｜＋｜bi｜）／（｜A｜＋｜B｜）即为加权Translation指标值，其中，ei、ai、bi分别为线状要素E、A、B上的直线段。加权Translation指标反映了对应点之间“移位矢量”的加权变化情况，在移位路径为对应点之间直线段的情况下，其越小说明Morphing变换的效果越好。

试验数据采用中国铁路长林线，该数据来源于国家基础地理信息系统，如图4所示。其中，图4（a）为该段铁路在1∶500万比例尺地图上的表达，图4（b）为1∶1000万比例尺地图上的表达，该铁路两个不同比例尺线状要素间差异较大，比较容易体现出不同算法试验结果的差别。

本文试验程序在C＃2005与ArcGIS Engine 9．2的环境下编译运行，系统环境为Windows XP，CPU性能是Intel Core 2 Duo T6600 2．20 GHz，内存为2 GB（DDR3 1067 MHz）。试验中，本文2．2节介绍的参数TA取值15°，该值在文献［22］中用于多尺度线状要素目标匹配，并取得了良好的效果，而该应用与本文的弯曲基线匹配在原理上是相通的。TL根据本文试验数据实际情况及作者大量实践经验取值0．95（对于一般的数据而言，该值应该都是合适的）。

图4 长林线铁路数据Fig．4 Spatial data of the Changlin railway

图5显示了基于弯曲方法和更充分利用独立弯曲结构方法的对应弯曲特征点结果，其中每一根连接两线状要素的直线段的两个端点代表一对对应弯曲特征点。另外，图5中三角网背景为对整个线状要素构建CDT的结果。从图5可知，基于弯曲结构的方法识别出18对对应弯曲特征点，更充分利用独立弯曲结构的方法识别出25对对应弯曲特征点。因此，更充分利用独立弯曲结构的方法对对应弯曲特征点的识别能力有较大程度的提升（近40%）。

进一步地，将各方法的运行时间和加权Translation指标值列于表1。从表中可以看出，基于弯曲结构的方法由于涉及构建CDT、建立弯曲森林及进行弯曲匹配等步骤，与直接使用线性插值算法相比，增加了运行时间，但同时也改善了Morphing变换效果。而更充分利用独立弯曲结构的方法由于需多次构建CDT、建立弯曲森林及进行弯曲匹配，运行时间进一步增加，同时Morphing变换效果也得到了进一步改善。

图5 对应弯曲特征点识别结果Fig．5 Corresponding characteristic points detectedfrom the corresponding bends

表1 3种方法运行时间及加权Translation指标值Tab．1 The running time and weighted Translation values of the three approaches

最后，列出各方法的对应点结果及t＝0．25、0．5和0．75时的Morphing变换结果，如图6所示。图中每一根穿过线状要素的直线段的两个端点代表一对对应点，中间与原线状要素大致平行的3个线状要素从上到下即依次为t＝0．25、0．5和0．75时的Morphing变换结果。从图6中可以观察到，相对于线性插值算法，基于弯曲结构的方法和更充分利用独立弯曲结构的方法对弯曲结构的保持都有大幅度提升。当然，后两者的差别则难以从肉眼上进行区分。

图6 3个方法得到的对应点及Morphing变换结果Fig．6 The results of both corresponding points and morphing transformation by the three different approaches

4 结论与展望

本文针对部分独立弯曲结构隐藏于更高层次的大弯曲中而难以被发现这一实际情况，提出了更充分利用独立弯曲结构的线状要素Morphing变换方法。该方法的主要思想在于：①对原线状要素构建CDT并建立弯曲森林，通过弯曲匹配得到对应弯曲；②对于对应弯曲重新构建CDT，建立其“背面”的弯曲森林再次运用弯曲匹配得到新的对应弯曲，并可不断递归挖掘对应弯曲结构；③将所有对应弯曲的对应起点和对应终点作为断点切割原线状要素，获得对应线段。通过实例分析，论证了本文更充分利用独立弯曲结构的方法能够提高对对应弯曲特征点的识别能力，从而能够更好地保持弯曲特征点，并改善Morphing变换效果。

对于较为极端的情况，如两线状要素结构差异非常大或两线状要素本身并非对应线状要素，本文方法可能无法识别到对应弯曲。此时，本文方法可以对两线状要素直接采用线性插值算法识别对应点。也就是说，本文方法将蜕化为普通的线性插值算法，因此能够适应极端情况。

下一步研究工作将主要集中在两个方面：①充分挖掘线状要素的形态结构特征信息，进一步改善Morphing变换效果；②研究不同程度形状内插结果与比例尺的对应关系。

［1］ WANG Jiayao．Development Trends of Cartography and Geographic Information Engineering［J］．Acta Geodaetica et Cartographica Sinica，2010，39（2）：115－119．（王家耀．地图制图学与地理信息工程学科发展趋势［J］．测绘学报，2010，39（2）：115－119．）

［2］ SESTER M，BRENNER C．Continuous Generalization for Visualization on Small Mobile Devices［C］∥Proceedings of the 11th International Symposium on Spatial Data Handling．Berlin：Springer－Verlag，2004：355－368．

［3］ LI Z L，WONG M．Animating Basic Operations for Digital Map Generalization with Morphing Techniques［C］∥Proceedings of the International Archives of the Photogrammetry，Remote Sensing and Spatial Information Science．Beijing：ISPRS，2008：637－642．

［4］ LI Jingzhong．An Object－oriented Model for Map Data Multiple Representation over Scale Space［D］．Wuhan：Wuhan University，2009．（李精忠．尺度空间地图多重表达的面向对象数据模型研究［D］．武汉：武汉大学，2009．）

［5］ WOLBERG G．Image Morphing：A Survey［J］．The Visual Computer，1998，14（8－9）：360－372．

［6］ GUIBAS L，HERSHBERGER J，SURI S．Morphing Simple Polygons［J］．Discrete and Computational Geometry，2000，21（1）：1－34．

［7］ BEREG S．An Approximate Morphing between Polylines［J］．International Journal of Computational Geometry and Applications，2005，15（2）：193－208．

［8］ EFRAT A，HAR－PELED S，GUIBAS L J，et al．Morphing between Polylines［C］∥Proceedings of the 12th Annual ACM－SIAM Symposium on Discrete Algorithms．Philadelphia：Society for Industrial and Applied Mathematics，2001：680－689．

［9］ CECCONI A．Integration of Cartographic Generalization and Multi－scale Databases for Enhanced Web Mapping［D］．Zurich：University of Zurich，2003．

［10］ 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．

［11］ DANCIGER J，DEVADOSS S L，MUGNO J，et al．Shape Deformation in Continuous Map Generalization［J］．Geoinformatica，2009，13（2）：203－221．

［12］ REILLY D F，INKPEN K M．Map Morphing：Making Sense of Incongruent Maps［C］∥Proceedings of Graphics Interface．Waterloo：Canadian Human－computer Communications Society，2004，231－238．

［13］ PANTAZIS D，KARATHANASIS B，KASSOLI M，et al．Are the Morphing Techniques Useful for Cartographic Generalization？［C］∥Proceedings of Urban and Regional Data Management．London：CRC Press，2009：195－204．

［14］ PANTAZIS D，KARATHANASIS B，KASSOLI M，et al．Morphing Techniques：Towards New Methods for Raster Based Cartographic Generalization［C］∥Proceedings of the 24th ICC International Cartography Conference．Santiago：ICC，2009：15－21．

［15］ VAN KREVELD M．Smooth Generalization for Continuous Zooming［C］∥Proceedings of the 20th International Cartographic Conference．Beijing：ICC，2001：2180－2185．

［16］ ALBRECHT S．A Solution to the Vertex Correspondence Problem in 2D Polygon Morphing［D］．Osnabruck：Universitat Osnabruck，2006．

［17］ CHETVERIKOV D，SZABO Z．A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves［C］∥Proceedings of the 23rd Workshop of Australian Pattern Recognition Group．Steyr：［s．n．］，1999：175－184．

［18］ AI Tinghua，GUO Renzhong，LIU Yaolin．A Binary Tree Representation of Curve Hierarchical Structure in Depth［J］．Acta Geodaetica et Cartographica Sinica，2001，30（4）：343－348．（艾廷华，郭仁忠，刘耀林．曲线弯曲深度层次结构的二叉树表达 ［J］．测绘学报，2001，30（4）：343－348．）

［19］ PLAZANET C，AFFHOLDER J G，FRITSCH E．The Importance of Geometric Modeling in Linear Feature Generalization［J］．Cartography and Geographic Information Systems，1995，22（4）：291－305．

［20］ ZHAI Renjian，WU Fang，Zhu Li，et al．Structured Representation of Curve Shape［J］．Acta Geodaetica et Cartographica Sinica，2009，38（2）：175－182．（翟仁健，武芳，朱丽，等．曲线形态的结构化表达［J］．测绘学报，2009，38（2）：175－182．）

［21］ POORTEN P，JONES C B．Customisable Line Generalization Using Delaunay Triangulation［C］∥Proceedings of the 19th International Cartographic Association Conference．Ottawa：Canadian Institute of Geomatics．1999：35－42．

［22］ ZHANG M，SHI W，MENG L．A Generic Matching Algorithm for Line Networks of Different Resolutions［C］∥Proceedings of the 8th ICA Workshop on Generalization and Multiple Representation．La Coruña：ICA，2005：7－8．

（责任编辑：丛树平）

Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently

PENG Dongliang，DENG Min，LIU Huimin
School of Geosciences and Info－physics，Central South University，Changsha 410083，China

This paper proposes a morphing approach for linear features by using their independent bend structures more sufficiently．Firstly，the constrained Delaunay triangulations（CDT）of the pair of linear features are respectively constructed．Bend structures are identified and represented by bend forests．Secondly，corresponding bends are obtained by bend matching．To use independent bend structures more sufficiently，the CDT of every pair of the obtained corresponding bends are constructed．Then the new pairs of bend forests on the back－side of these corresponding bends are built．Again，bend matching is implemented on the new pairs of bend forests and new corresponding bends are obtained．This process is iteratively carried out until no more corresponding bends can be found．Thirdly，the starts and ends of all the pairs of corresponding bends are used to split the two original linear features so that corresponding segments are obtained．The linear interpolation algorithm is utilized to detect corresponding points for every pair of the corresponding segments．Lastly，straight－line trajectories are used for morphing．The experimental results show that the proposed approaches can improve the ability of identifying corresponding characteristic points and preserving characteristic points in the process of morphing．

Morphing；shape interpolation；bends；linear features；cartographic generalization

PENG Dongliang（1987—），male，PhD candidate，majors in cartographic generalization and multi－scale representation．

DENG Ming

P208

A

1001－1595（2014）06－0637－08

国家自然科学基金（41171351；41301515）；教育部新世纪优秀人才支持计划（NECT－10－0831）；湖南省国土资源厅科技项目（2010－20）；湖南省研究生科研创新项目（CX2012B039）

2013－01－15

彭东亮（1987—），男，博士生，研究方向为地图综合和多尺度表达的理论与方法。

邓敏

PENG Dongliang，DENG Min，LIU Huimin．Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently［J］．Acta Geodaetica et Cartographica Sinica，2014，43（6）：637－644，652．（彭东亮，邓敏，刘慧敏．更充分利用独立弯曲结构的线状要素Morphing变换方法［J］．测绘学报，2014，43（6）：：637－644，652．）

10．13485／j．cnki．11－2089．2014．0100

修回日期：2013－08－13

E－mail：pengdlzn＠163．com

E－mail：dengmin028＠yahoo．com