留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于傅里叶变换的光滑边界面状要素Morphing方法

李精忠 张津铭

李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
引用本文: 李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
LI Jingzhong, ZHANG Jinming. A Morphing Method for Smooth Area Features Based on Fourier Transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
Citation: LI Jingzhong, ZHANG Jinming. A Morphing Method for Smooth Area Features Based on Fourier Transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157

一种基于傅里叶变换的光滑边界面状要素Morphing方法

doi: 10.13203/j.whugis20150157
基金项目: 

国家自然科学基金 41001229

国家自然科学基金 41671448

国家863计划 2012AA12A404

虚拟地理环境教育部重点实验室资助 2012VGE03

国家基础科学人才培养基金《武汉大学地理科学理科基地》科研能力训练项目 J1103409

卫星测绘技术与应用国家测绘地理信息局重点实验室经费 KLSMTA-201308

详细信息
    作者简介:

    李精忠, 博士, 副教授, 主要从事DEM分析、空间数据库多尺度表达的理论与方法研究。lilideyx@126.com

  • 中图分类号: P208

A Morphing Method for Smooth Area Features Based on Fourier Transform

Funds: 

The National Natural Science Foundation of China 41001229

The National Natural Science Foundation of China 41671448

the High-tech R & D Program of China(863 Program) 2012AA12A404

the Virtual Geographic Environment, Ministry of Education Key Laboratory of Funded Projects 2012VGE03

the National Science Talents Fund "Geographical Sciences, Wuhan University of Science Base" Research Capacity Training Program J1103409

the Key Laboratory of Satellite Mapping Technology and Application, National Administration of Surveying, Mapping and Geoinformation KLSMTA-201308

More Information
    Author Bio:

    LI Jingzhong, PhD, associate professor, specializes in the DEM analysis and multiple representations of spatial data. E-mail: lilideyx@126.com

图(5) / 表(2)
计量
  • 文章访问数:  1131
  • HTML全文浏览量:  123
  • PDF下载量:  294
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-06-22
  • 刊出日期:  2017-08-05

一种基于傅里叶变换的光滑边界面状要素Morphing方法

doi: 10.13203/j.whugis20150157
    基金项目:

    国家自然科学基金 41001229

    国家自然科学基金 41671448

    国家863计划 2012AA12A404

    虚拟地理环境教育部重点实验室资助 2012VGE03

    国家基础科学人才培养基金《武汉大学地理科学理科基地》科研能力训练项目 J1103409

    卫星测绘技术与应用国家测绘地理信息局重点实验室经费 KLSMTA-201308

    作者简介:

    李精忠, 博士, 副教授, 主要从事DEM分析、空间数据库多尺度表达的理论与方法研究。lilideyx@126.com

  • 中图分类号: P208

摘要: 提出一种基于傅里叶(Fourier)变换的光滑边界面状要素Morphing方法。针对同名面状要素在两个不同比例尺下的表达,利用Fourier变换将多边形在空间域的矢量坐标串表达形式转换为频率域的函数表达形式,然后对二者的Fourier函数进行复合得到多边形在任意中间尺度的表达函数,最后将中间状态的Fourier函数展开为矢量坐标串表达形式获得多边形的中间插值形状。实验证明,该基于Fourier变换的面状要素Morphing方法,能在保持形状特征的基础上对于边界光滑的多边形要素实现光滑、连续的多尺度表达。

English Abstract

李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
引用本文: 李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报 ● 信息科学版, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
LI Jingzhong, ZHANG Jinming. A Morphing Method for Smooth Area Features Based on Fourier Transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
Citation: LI Jingzhong, ZHANG Jinming. A Morphing Method for Smooth Area Features Based on Fourier Transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1104-1109. doi: 10.13203/j.whugis20150157
  • Morphing又称图形渐变技术,其基本思想是采用某种内插方法使得初始图形(图像)光滑连续地渐变到目标图形(图像)。传统的矢量图形Morphing变换涉及两个基本过程,即图形特征匹配和形状插值[1]。图形特征匹配通过特征分析提取始末图形上的特征点并建立二者之间的联系,常见的匹配方法有基于能量最小化的物理匹配方法和基于距离最邻近的几何匹配方法等[2-4]。形状插值是在特征匹配的基础上将初始图形的各部分沿一定路径变换到目标图形对应部分所在位置,获取中间状态图形,常见的插值方法包括线性插值方法、基于目标边界的插值方法和顾及目标内部区域的差值方法等[5-7]

    在GIS领域,Morphing的形状渐变特性符合空间数据多尺度表达与渐进式综合的技术需求,得到了广泛关注[8-14]。由于形状插值算法相对成熟,GIS领域的研究重点集中在形状特征匹配方面。最简单的匹配方法是按长度比例线性插值补齐始末图形顶点数目的差额,然后在相同点数的情况下按顶点序号一一对应[9],该方法以坐标序号进行始末图形顶点对应,没有考虑图形结构特征的匹配性,极易产生顶点误匹配,从而导致畸异中间状态的产生。为避免误匹配情况的发生,一些学者提出了基于特征点的匹配方法。如Nöllenburg等利用贝塞尔曲线筛选要素弧度较大处的顶点作为特征点,以动态规划的方法进行特征点的匹配[10];Albrecht等以弧度较大处的点为特征点,基于位移最小原则进行特征点的匹配[11];彭东亮等以线状要素的BLG(binary line generalization)树节点作为特征点,基于BLG树从根节点开始逐层向下进行节点匹配[12];李精忠等以模拟退火技术实现特征点的最优匹配[13];彭东亮等在线状要素弯曲匹配的基础上,进一步提取其“背面”的弯曲森林,进而递归挖掘更深层次的弯曲结构,实现更充分利用弯曲结构的特征匹配[14]

    基于特征匹配的矢量图形Morphing变换方法,对特征匹配算法要求较高。如邓敏等提出的基于线状要素的特征匹配,涉及到曲线形态的结构化表达[15],需首先对曲线弯曲深度层次结构进行二叉树表达[16],过程较为繁琐复杂,且一旦出现错误的特征匹配必将导致中间状态出现非同构几何特征甚至畸变。本文提出一种基于Fourier变换的面状要素Morphing方法,该方法无需进行特征匹配,其基本思想是利用Fourier变换将同名面状要素在空间域的坐标串表达形式转换为频率域的函数表达形式,然后对大小比例尺下两种表达对应的Fourier函数进行加权复合,得到多边形在任意中间尺度的表达函数,最后将中间状态的Fourier函数展开为矢量表达形式获得多边形的中间插值形状。

    • 基于一定的形状签名(shape signature),可以将二维矢量边界转化成一维的实函数或是复函数[17]。矢量多边形Fourier变换的基本思想是根据形状的空域频率成分获取形状的描述参量,其基本过程是将多边形的边界表示为一个以2π为周期的函数并通过Fourier算式展开,然后基于展开系数p(n)构建始末多边形特征向量f= [p(1), p(2), p(3), … p(n-1)],实现多边形表达从空间域向频率域的转换[18]。系数p(n)所含的形状信息具有平移、旋转和缩放不变性,低频段(小n值)捕获形状的主体轮廓信息而高频段(大n值)捕获形状的细节信息。通过逐渐增大n值,可获得对原始多边形逐渐逼近的表达。

      f1f2分别表示大比例尺和小比例尺下同名多边形两种表达各自对应的Fourier特征向量,则基于Fourier特征向量的多边形Morphing模型可以表示为:

      $$ \boldsymbol{f} = \left( {1 - g} \right) \times {\boldsymbol{f}_1} + g \times {\boldsymbol{f}_2},0 < g < 1 $$ (1)

      式中,g为介于大、小比例尺之间的归一化中间尺度参数。当g=0时,f= f1;当g=1时,f =f2;当0<g<1时,f为介于f1f2之间的中间表达,且g越大,ff2越相似,g越小,ff1越相似。设大、小比例尺的分母分别为r1r2,任意待插值的中间尺度的比例尺分母为rg,则归一化参数可计算为:

      $$ g = ({r_g} - {r_1})/({r_2} - {r_1}) $$ (2)

      f1f2的特征向量表达形式分别为:

      $$ \left\{ \begin{array}{l} {\boldsymbol{f}_1} = \sum\nolimits_{k = 1}^n {{d_1}\left( k \right)} \\ {\boldsymbol{f}_2} = \sum\nolimits_{k = 1}^n {{d_2}\left( k \right)} \end{array} \right. $$ (3)

      式中,n是描述形状所需的展开式阶次的截取值。截取的阶次n由Fourier描述式拟合形状与原始多边形逼近度决定。假定原多边形面积为Co,由Fourier描述子近似表达的多边形面积为CaCoCa的交集为CoCa。定义参数A_degree表示模型多边形与原始多边形拟合的逼近度,其计算公式表示如下:

      $$ {\rm{A\_degree}} = {\rm{area}}({C_o} \cap {C_a})/{\rm{area}}({C_o}) $$ (4)

      式中,area()为面积计算函数;参数A_degree的变化范围为[0, 1],其值越接近1,Fourier变换模型的逼近度越高。A_degree可看作是形状表达的精度,给定特定精度值,不同的形状区域的Fourier描述式要展开到不同阶次才能达到该精度。研究发现,具有高紧凑度、高的凸壳度和光滑边界的多边形,其Fourier描述式对原始形状的拟合收敛较快[19]。对于始末多边形图形,由于形状上的差异,达到相同的逼近度需要展开不同的阶次。为了进行形状插值,两个向量f1f2必须有相同的维数,选择大的终止阶次作为两向量的共同维数。

    • 为说明本文方法的可行性和有效性,采用具有类直角化边界特征的人文建筑物多边形和具有光滑边界特征的自然湖泊多边形两套实验数据展开实验验证。其中,图 1第一和第二行最左侧多边形分别为大、小比例尺下同名建筑物实体的两种表达B1B2,第三和第四行最左侧多边形分别为大、小比例尺下同名湖泊实体的两种表达H1H2。显然,大比例尺下建筑物和湖泊的表达较为详细,多边形边界细节特征丰富;小比例尺下建筑物和湖泊的表达较为概略,多边形边界细节特征少。建筑物边界平直,湖泊边界光滑。基于文献[18]矢量多边形的Fourier展开模型,对B1B2H1H2共4个输入多边形分别进行Fourier变换,频率阶次n从1逐渐增大至33,图 1中各行第2~10列对应多边形的展开阶次分别为1、5、9、13、17、21、25、29、33。

      图  1  部分展开阶次下建筑物、湖泊多边形的近似表达

      Figure 1.  The Approximate Representations of Buildings and Lakes at Some Fourier Orders

      表 1为按式(4) 计算的奇数阶次展开后的拟合多边形与原始多边形的逼近度。实验发现,边界相对简单的建筑物多边形较之边界相对复杂的湖泊多边形,其Fourier描述式对原始形状的拟合收敛更快;小比例尺下边界平直的建筑物多边形比大比例尺下边界复杂的建筑物多边形收敛更快;小比例尺下边界光滑的湖泊多边形比大比例尺下边界复杂的湖泊多边形收敛更快。如果以95%的逼近度为展开终止条件,大小比例尺的建筑物多边形的展开阶次分别为23和15,而大小比例尺的湖泊多边形的展开阶次分别为33和23。

      表 1  建筑物、湖泊多边形不同展开阶次的拟合度

      Table 1.  The Degree of Approximation of Building and Lake at Some Fourier Orders

      表达 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
      B1 0.615 0.640 0.694 0.763 0.803 0.898 0.906 0.926 0.935 0.935 0.943 0.951 0.956 0.960 0.963 0.966 0.969
      B2 0.644 0.653 0.719 0.825 0.858 0.926 0.940 0.950 0.955 0.958 0.967 0.967 0.974 0.976 0.978 0.980 0.985
      H1 0.578 0.613 0.643 0.774 0.806 0.813 0.855 0.868 0.879 0.885 0.913 0.920 0.923 0.928 0.933 0.946 0.952
      H2 0.592 0.635 0.711 0.786 0.819 0.826 0.867 0.904 0.913 0.920 0.949 0.957 0.958 0.961 0.971 0.973 0.979
    • 为使得插值结果与原始多边形有较高的相似度,需要Fourier展开级数足够高以确保模型输入尽可能逼近原始表达。此处以99%的逼近度作为Fourier展开阶次的终止条件。针对图 1中的两套实验数据,计算得出大、小比例尺建筑物多边形的展开阶次分别为43和39,大、小比例尺湖泊多边形的展开阶次分别为50和43。为确保对复杂边界也有较高的逼近度,两套实验数据分别采用展开级数n=43和n=50。为检验算法对尺度的敏感性,g从两个不同级别的尺度序列取值展开实验,序列1为{0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1},其中g间隔为0.1,实验结果如图 2所示;序列2为{0.95, 0.94, 0.93, 0.92, 0.91},其中g的间隔为0.01,实验结果如图 3所示。为便于观察,图 3中第一行和第三行为第二行中对应圆圈细节处的放大显示效果。

      图  2  g=0.1时中间尺度序列1的Morphing渐变效果

      Figure 2.  The Morphing Effects on Intermediate Scale Sequence One While g=0.1

      图  3  g=0.01时中间尺度序列2的Morphing渐变效果

      Figure 3.  The Morphing Effects on Intermediate Scale Sequence Two While g=0.01

      实验发现,在图 2中,随着g取值的逐渐增大,建筑物和湖泊多边形由大比例尺对应的表达逐渐变换为小比例尺下的表达;对于具有直角化特征的建筑物多边形,其中间状态(如g=0.5时)出现了非直角化的圆角特征,结果不符合建筑物的常规表达要求;对于具有光滑边界的湖泊多边形,其中间状态一直保持光滑平稳渐变,变换结果与手工综合类似。从图 3中第一、三两行的放大效果可以发现,即使g的微小变化(0.01),中间状态也会实现光滑、平稳的渐变。

    • 为进一步考察本文算法的内插效果和时间效率,展开一组对比试验。试验数据仍为§2.1中的两组多边形{B1B2}和{H1H2},试验方法采用常规的线性内插,即首先通过线性内插方式补齐小比例尺多边形B2H2的坐标点,使得两组数据各自的始末图形坐标点数相同,然后在对应的坐标点之间进行线性内插获得中间序列多边形。参与实验的居民地和湖泊多边形的坐标点数如下:B1多边形37个点,B2多边形26个点,H1多边形260个点,H2多边形196个点。实验效果如图 4所示,其中无论对于居民地或者湖泊多边形,中间状态都存在自相交的畸异情形。对比图 2中的实验效果,不难发现本文算法更能获得光滑渐变的内插效果。

      图  4  线性插值方法的Morphing渐变效果

      Figure 4.  The Morphing Effects of Linear Interpolation Method

      表 2为不同算法的时间开销,其中第2~6列分别为Fourier展开10级、20级、30级、40级和50级时做一次正变换和逆变换的时间之和,第7列为对应两组实验数据进行一次线性内插的平均时间开销,第8、9两列分别为两组实验数据在Fourier展开43级和50级后进行一次Morphing变换的平均时间。可见简单线性内插方法时间效率较高,而本文方法Fourier变换需要耗费相对较大的时间代价,其总的时间开销几乎为首末多边形Fourier变换和线性内插所花费时间之和。

      表 2  Fourier变换、线性内插及本文算法时间开销/μs

      Table 2.  Time Cost of FFT Transform, the Linear Interpolation and Our Algorithm/μs

      表达 FFT变换
      10级
      FFT变换
      20级
      FFT变换
      30级
      FFT变换
      40级
      FFT变换
      50级
      线性内插 本文算法
      (FFT展开43)
      本文算法
      (FFT展开50)
      B1
      1 575 3 298 4 701 6 240 7 812 867 12 282 16 740
      B2 1 087 2 183 3 272 4 537 5 424
      H1 10 954 21 819 32 333 44 045 54 572 35 103 128 439 178 302
      H2 8 223 19 395 24 304 32 384 40 423

      图 5为基于某标准分幅1:1万地形图和对应区域1:5万地形图中提取的植被数据所展开的Morphing实验,通过本文方法在Fourier展开50级的情况下内插生成了中间尺度1:2万、1:3万和1:4万比例尺下的植被数据,每幅图中包含61个植被多边形。从图面效果来看,渐变效果明显,可用于空间数据的连续尺度变换;在网络环境下,可采用并行计算技术进一步提供算法效率,从而实现在线连续地图综合。

      图  5  真实数据Morphing变换实验

      Figure 5.  The Morphing Transformation of Real Data Based on FFT Method

    • 本文提出了一种基于Fourier变换的面状要素Morphing方法,该方法利用Fourier变换将矢量多边形在空间域的坐标串表达形式转换为频率域的函数表达形式,然后对大小比例尺下两种表达对应的Fourier函数进行复合,得到多边形在任意中间尺度的表达函数,最后将中间状态的Fourier函数展开为矢量坐标串表达形式,以获得多边形的中间插值形状。研究表明,该方法对于具有光滑边界的多边形连续插值和多尺度表达具有较好的适应性和尺度敏感性,较小的尺度变化都产生光滑连续的渐变效果,但不适用于直角化特征的多边形的Morphing变换。原因在于, Fourier本身是以2π为周期的圆周对多边形边界进行频率展开,故多边形边界越光滑越接近圆其逼近效果越好。对于地图中的居民地等具有直角化特征的多边形,在较小的展开系数下会出现圆角现象,随着展开系数的增大圆角现象会有所改善但效率有所降低。

参考文献 (19)

目录

    /

    返回文章
    返回