面状居民地Morphing变换的转向角函数法

谢 天，李精忠

武汉大学资源与环境科学学院，湖北 武汉 430079

随着网络技术的发展，地图服务需要满足不同层次用户个性化需求，在地图内容上提供任意尺度的表达，这需要连续地图综合技术的支持［1］。基于图像融合中的morphing技术，其形状渐变特性符合空间数据多尺度表达与渐进式综合的技术需求，故成为实现连续地图综合技术的重要方法。morphing变换通常包含两个基本过程，即特征匹配和形状插值［2］。目前，大多 morphing算法都针对这两个基本过程研究，如文献［3］基于优化技术实现的线状要素morphing变换方法，文献［4—7］基于BLG和层次弯曲结构实现的线状河流及道路要素的morphing变换方法，文献［8］研究基于同构平面三角网格的多边形保凸morphing变形方法，文献［9］提出的一种基于类正切空间的多边形渐变方法等，是针对特征匹配过程的研究；而文献［10］提出的常用线性插值方法，文献［11］提出的基于目标边界插值的morphing方法，文献［12—13］提出的顾及目标内部区域插值的morphing方法，文献［14］提出的基于四元素插值的空间曲线边界约束变形方法等，是针对形状插值研究。就空间数据而言，这些方法往往从纯几何特征入手展开匹配和插值，没有顾及地理要素几何细节背后所隐含的地理特征，如居民地要素的类直角边界特征。而顾及要素的地理特征近年来成为连续地图综合技术的重要要求，如文献［15］提出顾及研究对象所处的环境和背景进行地图综合选取，文献［16］提出的面向多重空间的解决地图综合中移位冲突的移位场模型，文献［17］提出顾及地理特征保持的溺谷海岸线化简算法，文献［18］提出保持道路目标stroke特征的道路网自动综合方法，文献［19］提出的考虑建筑物轮廓形态和面积保持的建筑物多边形化简方法。顾及要素的地理特征是应用morphing技术实现连续地图综合的重要挑战。

目前没有顾及居民地要素类直角化特征的morphing算法。在已发表的morphing算法中，或产生具有平滑边界特征的中间系列图形，不符合居民地要素空间表达和认知的基本规律；或不适用于居民地要素的连续渐变，如文献［6］提出的基于弯曲结构的morphing算法因居民地不存在文中所述的典型弯曲而不适用，文献［7］提出的更充分利用独立弯曲结构的morphing算法因居民地不存在文中所述层次弯曲而不适用。本文提出一种基于转向角函数的morphing方法，其基本思想是将同名要素在空间域的坐标串表达形式转换为转向角函数，通过特征点约束下的边的方位角匹配找出两个不同尺度下图形的转向角函数的变化规律，按此规律得到的任意中间尺度下的转向角函数，函数展开后可获得对应中间尺度下插值形状，且保持原多边形类直角化边界特征，从而实现居民地多边形的连续综合与多尺度表达。

1 原 理

1.1 概念模型

对于不同尺度下的对应同名居民地实体，设大比例尺Ta下的居民地要素为a，小比例尺Tb下的居民地要素为b，中间比例尺TMid下的居民地要素为Mid，a较之b具有更详细的表达，Mid表达的详略介于a、b之间，则morphing变换问题转换为对居民地要素a和b进行形状插值。设morphing变换模型表示为 Mid＝f（a，b，g），其中f是通过转向角函数建立的morphing形状表达函数，f（a，b）为在转向角表达形式下对a、b完成的特征匹配，g为一个决定morphing变换程度的参数，f（a，b，g）为通过以参数g为位移路径完成形状插值。对于任意0≤g≤1，Mid关于g单调连续：当g＝1时，Mid＝a；当g＝0时，Mid＝b；当0＜g＜1时，Mid为介于a与b之间的表达。在一定程度上，参数g可以表征内插图形与a、b的相似程度；g与比例尺有关，表示内插结果随比例尺的不同而变化，g与其对应的Mid所在比例尺TMid的关系如下

式中，h为一个由实际制图综合中Mid与TMid的约定关系决定的函数，当TMid为Ta时，g＝1＝h（0），当TMid为Tb时，g＝0＝h（1）。故转换关系满足约束条件

h使得g转换为TMid，morphing变换程度由TMid决定。基于转向角函数的morphing算法由3个步骤组成：①将同名实体图形转为转向角函数表达形式；②在转向角函数表达形式下完成对图形的特征匹配；③通过改变参数得到中间状态图形系列。

1.2 矢量图形的转向角函数表达

在图1中，设a的各条边相等且皆为一个单位，以点I为起始点，沿逆时针方向遍历所有顶点，将图形a的转向角函数反映到直角坐标系中。转向角函数仅能表达类直角的特性限定了本文方法的适用尺度：仅适用于类直角边界特征的居民地要素，而不适用于居民地融合产生非直角形状的情况。鉴于居民地融合大多出现在尺度小于1∶25万的地图上，本文方法的适用尺度应大于1∶25万。

图1 图形的转向角函数Fig.1 Steering angle function of polygon

1.3 基于转向角函数的边特征匹配

将同名实体图形转为转向角函数的表达形式后，对不同实体的不同转向角函数表达形式在频率域进行比较，以发现二者转向角函数间的共性与差异，得到二者转向角函数的变化规律，进而引入参数表征该变化规律，用于进行第3步的形状插值，这即是同名实体的转向角函数匹配。但不同实体往往具有不等的周长，故对应的转向角函数具有不同的定义域，导致无法进行对比。如图2，设图形a、b各边长相等，分别为1和3，二者的定义域分别为［0，12］和［0，20］，故转向角函数无法在区间［12，20］内进行对比。为此，需要首先统一定义域，然后进行边特征匹配。以图形周长作归一化，将转向角函数定义域统一为［0，1］，转向角函数转换为

图2 图形转向角函数的直接匹配Fig.2 Direct matching of polygon based on steering angle function

1.3.1 边特征分析

统一定义域后图3内初始多边形a的边中，唯有［0，0.05］、［0.15，0.2］、［0.3，0.35］、［0.4，0.45］、［0.55，0.6］、［0.65，0.7］、［0.8，0.85］、［0.95，1］为同边，其余均是异边。a到b的变化，在转向角函数形式下表现为转向角不变，异边减短至0，同边增长了异边的长度。本文称此变化方式为同增异减。

实际应用中，不同尺度下的同名实体可能有不同的制图精度，同边之间的方位角不一定完全相等，故差值在一定范围内的即可划定为同边，否则为异边。同边的划定条件改为

将异边的划定条件改为

式中，δ为匹配误差。匹配误差据实际情况而定，其值决定同名图形转向角函数匹配精度。

图3 定义域统一后的转向角函数匹配Fig.3 Matching of steering angle function unified domain

1.3.2 边匹配

在统一定义域的基础上转向角函数匹配可能存在以下两个问题：①如图4中，a的某些边不能满足同异边划定条件ta⊆tb，因而无法划定该边是同边还是异边；②从a到b的变化中，边t未发生改变，但在转向角函数匹配中被划定为异边。造成此问题的根本原因在于：图形转向角函数定义域的一致性与边长的差异性之间的矛盾。为此，仅仅统一定义域是不够的，在此基础上须进一步进行边匹配。

图4 特殊图形的匹配偏离Fig.4 Matching deviation of particular polygon

图5 边分割算法Fig.5 Algorithm of segmentation condition

1.4 基于转向角函数的形状插值

在a到b的同增异减变换模型中，异边表现为连续缩短直至消失，其缩减力度与参数g相关，故有

式中，S为a分割边集中同边的总数，t同总为a分割边集中同边的总和。Δt同总表征了分割边集内同边的变化，含同边越多的分割子集变化越小。此特性要求面向分割边集求同边增量，而非面向单个同边，亦非整个图形。异边的减量与边长成比例，同增异减变化可理解为异边转为同边，故同边的增量必与边长成比例

综上，同名多边形的同增异减变换模型，也即morphing变换模型，也即Mid的转向角函数构建为

Mid的图形形状由a、b和g共同决定。

图6 同边的增量Fig.6 Increment of uniform sides

2 试验分析

为了说明本文方法的可行性和有效性，基于C＋＋语言使用MFC构建试验平台，于深圳市1∶1万和1∶5万居民地地图中截取部分真实地图作为试验数据，该数据包含文献［20］提出的建筑物模式数据库中的所有模式，且部分数据间具有常见的共边等拓扑关系。数据的始末状态（也即g＝1和g＝0下的图形）如图7所示，图中黑点表示试验选取的起始点。如1.2节所述，起始点的选择对转向角函数形式下的表达至关重要，图7所示试验数据的起始点根据以下原则进行选择，可通过试验证明该选择原则是否可行：①须选取a、b间距离最近的点作为起始点，距离越近，出现误匹配的可能性越小，如图形a—h起始点的选择；②若存在多对距离最近的点，可在其中选取可决定图形位置的点作为起始点，如图形a、b、c、d起始点的选择；③若存在多对距离最近的点，可在其中选取顾及周围其他居民地的拓扑结构的点作为起始点，如图形e、f、g、h、i、j起始点的选择；④具备距离最近的基本条件，又能顾及图形位置和拓扑结构的点，是最优的起始点，如图形i、j起始点的选择。

图7 试验数据的始末状态Fig.7 Beginning and end state of the experimental data

分别令g等于0.9、0.8、0.7、0.6、0.5、0.4、0.3、0.2、0.1，借助试验平台绘制出如图8所示的中间状态居民地渐变图系列。由图8可知：①本文所述方法适用于所有建筑物模式，整个渐变过程均匀连续，保持了图形的重要特征，具有较好的效果。②上述的起始点选择原则是可行的，试验结果效果较好。本文算法中起始点的位置在整个morphing过程始终保持不变，且仅对边长进行插值，不改变转向角，因而也不存在旋转变化。如图形a、b、c、d在整个morphing过程中始终保持方形的布局；图形e、f、g、h、i、j在整个 morphing过程中始终保持与邻接图形的共边、包含的拓扑关系；图形k、l尽管相隔较近，在整个morphing过程中并未出现相交或分离。③通过选择合适的起始点，本文算法可以较好地维护居民地间拓扑关系的一致性。

为验证模型的尺度相关性，以area（a）表示初始状态下实体a的面积，以a∩b表示a与最终状态下实体b的重合部分，则定义Mid与a的相似度a＿degree为

定义Mid与b的相似度为b＿degree

式中，均减去a、b的重合部分是为了消除a、b本身的相似性对相似度造成的影响。表1列出了不同g值下的内插图形与实体始末状态的相似度，可见g值越大（即比例尺越大）中间状态Mid与a的重叠度a＿degree越大，与b的重叠度b＿degree越小，故模型参数g具有尺度相关性。本文算法的时间复杂度为O（N2），其中，第1步将同名实体图形转为转向角函数表达形式的复杂度为O（N）；第2步图形的特征匹配的复杂度为O（N2）；第3步得到中间状态图形系列的复杂度为O（N）。

表1 内插图形与实体始末状态的相似度Tab.1 Similarity of shape at intermediate scale with beginning and end state of polygon

3 总 结

本文提出了一种利用转向角函数的面状居民地morphing方法，该方法将图形的矢量坐标串的表达形式转换为转向角函数表达形式，再利用转向角函数的特性，经过边匹配分析大小比例尺下的两组图形的共性边与差异边，得到了任意中间尺度的转向角函数，并构建同增异减模型以实现矢量多边形的morphing变化。本方法经试验验证适用于多种表达形式的居民地。不足之处在于：在比例尺跨度较大的情况下，居民地的综合不仅局限于边界化简，可能存在居民地合并，本研究只考虑一对一的居民地渐变，没有考虑居民地合并的情形，后继将进一步研究适用于一对多的居民地morphing算法。

图8 建筑物的morphing变换Fig.8 Morphing of building

［1］ JONES C B，WARE J M.Map Generalization in the Web Age［J］.International Journal of Geographical Information Science，2005，19（8－9）：859－870.

［2］ LI Hua，ZHU Guangxi，ZHU Yaoting.A Survey of Object Metamorphosis［J］.Journal of Image and Graphics，2002，7（8）：745－751.（李华，朱光喜，朱耀庭.物体渐变技术现状与发展［J］.中国图象图形学报，2002，7（8）：745－751.）

［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（4）：248－260.

［4］ PENG Dongliang.A Methodology of Morphing Transformation of Linear Features for Map Continuous Generalization［D］.Changsha：Central South University，2012.（彭东亮.面向地图连续综合的线状要素Morphing变换方法研究［D］.长沙：中南大学，2012.）

［5］ PENG Dongliang，DENG Min，XU Feng.Morphing Linear Features Considering Their BLG－tree Structures［J］.Geomatics and Information Science of Wuhan University，2012，37（9）：1120－1125.（彭东亮，邓敏，徐枫.顾及BLG树结构特征的线状要素Morphing变换方法［J］.武汉大学学报：信息科学版，2012，37（9）：1120－1125.）

［6］ DENG Min，PENG Dongliang，XU Zhen，et al.A Morphing Method Based on Bend Structures for Linear Features［J］.Journal of Central South University：Science and Technology，2012，43（7）：2674－2682.（邓敏，彭东亮，徐震，等.一种基于弯曲结构的线状要素 Morphing方法［J］.中南大学学报：自然科学版，2012，43（7）：2674－2682.）

［7］ 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.）

［8］ SONG Weijie，JIANG Dawei，HUA Huichun，et al.Convexity－preserving Method for Morphing Compatible Planar Triangulations［J］.Journal of Computer－aided Design ＆ Computer Graphics，2005，17（6）：1252－1257.（宋伟杰，蒋大为，华回春，等.同构平面三角网格的保凸变形方法［J］.计算机辅助设计与图形学学报，2005，17（6）：1252－1257.）

［9］ HE Lei，JIANG Dawei，ZHANG Yongfeng，et al.Shape Blending Based on Representation of Simplified Polygons in the Similar Tangent Space［J］.Journal of Computeraided Design ＆ Computer Graphics，2007，19（3）：304－310.（何磊，蒋大为，张永锋，等.基于简化多边形类正切空间表示的图形渐变算法［J］.计算机辅助设计与图形学学报，2007，19（3）：304－310.）

［10］ SEDERBERG T W，GAO P S，WANG G J，et al.2－D Shape Blending：An Intrinsic Solution to the Vertex Path Problem［C］∥Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM，1993：15－18.

［11］ GOTSMAN C，SURAZHSKY V.Guaranteed Intersection Free Polygon Morphing［J］.Computers and Graphics，2001，25（1）：67－75.

［12］ SHAPIRA M，RAPPOPORT A.Shape Blending Using the Star－skeleton Representation［J］.IEEE Computer Graphics and Application，1995，15（2）：44－50.

［13］ CECCONI A，GALANDA M.Adaptive Zooming in Web Cartography［J］.Computer Graphics Forum，2002，21（4）：787－799.

［14］ LEI Kaibin，YANG Xianze，LI Bo，et al.3D－curves Shape Blending with Constrained Boundary Based on Quaternion Interpolation［J］.Journal of Computer Applications，2007，27（9）：2131－2133，2136.（雷开彬，杨宪泽，李播，等.基于四元素插值的空间曲线边界约束变形方法［J］.计算机应用，2007，27（9）：2131－2133，2136.）

［15］ YANG Min.Research on Feature Selection Considering Spatial Context in Map Generalization and Its Application［J］.Acta Geodaetica et Cartographica Sinica，2014，43（8）：877.（杨敏.顾及上下文特征的地图综合选取方法与应用研究［J］.测绘学报，2014，43（8）：877.）

［16］ ZHOU Qi，AI Tinghua，ZHANG Xiang.A Displacement Field Model to Resolve Multiple Spatial Conflicts［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：615－620.（周启，艾廷华，张翔.面向多重空间冲突解决的移位场模型［J］.测绘学报，2013，42（4）：615－620.）

［17］ HUANG Yafeng，AI Tinghua，LIU Yaolin，et al.Geographic Feature Oriented Ria Coastline Simplification［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：595－601.（黄亚锋，艾廷华，刘耀林，等.顾及地理特征保持的溺谷海岸线化简算法［J］.测绘学报，2013，42（4）：595－601.）

［18］ YANG Min，AI Tinghua，ZHOU Qi.A Method of Road Network Generalization Considering Stroke Properties of Road Object［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：581－587.（杨敏，艾廷华，周启.顾及道路目标Stroke特征保持的路网自动综合方法［J］.测绘学报，2013，42（4）：581－587.）

［19］ XU Wenshuai，LONG Yi，ZHOU Tong，et al.Simplification of Building Polygon Based on Adjacent Four－point Method［J］.Acta Geodaetica et Cartographica Sinica，2013，42（6）：929－936.（许文帅，龙毅，周侗，等.基于邻近四点法的建筑物多边形化简［J］.测绘学报，2013，42（6）：929－936.）

［20］ ZHAO Jie，LI Guangyao，PANG Chihai.Research on Building Recognition from Satellite Remote Sensing Image Based on Wavelet［J］.Computer Technology and Development，2008，18（11）：243－246.（赵洁，李光耀，庞池海，等.基于小波变换的卫星遥感地图中建筑物识别［J］.计算机技术与发展，2008，18（11）：243－246.）