留言板

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

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

一种傅里叶信息度量的曲线分形描述与多尺度表达方法

肖天元 刘鹏程 艾廷华 李精忠

肖天元, 刘鹏程, 艾廷华, 李精忠. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
引用本文: 肖天元, 刘鹏程, 艾廷华, 李精忠. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
XIAO Tianyuan, LIU Pengcheng, AI Tinghua, LI Jingzhong. A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
Citation: XIAO Tianyuan, LIU Pengcheng, AI Tinghua, LI Jingzhong. A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336

一种傅里叶信息度量的曲线分形描述与多尺度表达方法

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

国家自然科学基金 41531180

国家自然科学基金 41671448

国家重点研发计划 2017YFB0503500

中央高校自主科研项目 CCNU18CG010

数字制图与国土信息应用工程自然资源部重点实验室开放研究基金 ZRZYBWD201909

详细信息
    作者简介:

    肖天元, 硕士, 研究方向为地图综合及多尺度表达。963664361@qq.com

    通讯作者: 刘鹏程, 博士, 副教授。liupc@mail.ccnu.edu.cn
  • 中图分类号: P208

A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics

Funds: 

The National Natural Science Foundation of China 41531180

The National Natural Science Foundation of China 41671448

the National Key Research and Development Program of China 2017YFB0503500

Independent Research Project of the Central Universities CCNU18CG010

Digital Mapping and Land Information Application Engineering Open Research Fund Project of Key Laboratory of the Ministry of Natural Resources ZRZYBWD201909

More Information
    Author Bio:

    XIAO Tianyuan, master, specializes in map generalization and multi-scale representation. E-mail: 963664361@qq.com

    Corresponding author: LIU Pengcheng, PhD, associate professor. E-mail: liupc@mail.ccnu.edu.cn
图(5) / 表(3)
计量
  • 文章访问数:  1038
  • HTML全文浏览量:  110
  • PDF下载量:  284
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-12-06
  • 刊出日期:  2020-01-05

一种傅里叶信息度量的曲线分形描述与多尺度表达方法

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

    国家自然科学基金 41531180

    国家自然科学基金 41671448

    国家重点研发计划 2017YFB0503500

    中央高校自主科研项目 CCNU18CG010

    数字制图与国土信息应用工程自然资源部重点实验室开放研究基金 ZRZYBWD201909

    作者简介:

    肖天元, 硕士, 研究方向为地图综合及多尺度表达。963664361@qq.com

    通讯作者: 刘鹏程, 博士, 副教授。liupc@mail.ccnu.edu.cn
  • 中图分类号: P208

摘要: 提出了一种新的描述地理线要素复杂程度的方法。首先利用傅里叶级数将地理线要素从空间域转化到频率域进行分析,对不同的地理线要素进行傅里叶展开后得到其不同的傅里叶描述子,并采用设定面积阈值的方法,将傅里叶展开前后的地理要素产生的偏差控制在一定范围内,使经过傅里叶描述子还原的曲线可以近似代替原地理线要素。然后,在香农信息熵理论的基础上对傅里叶展开后的拟合曲线进行信息量的计算,再将频率域与分形理论相结合,在首尾分布以及Koch的"二八定律"的基础上对信息量数据进行进一步处理,从而提出了分布指数p的概念。最后将分布指数与方根模型相结合,利用最小二乘法得到了地图在不同尺度下的分布指数的近似表达式,并选取一片区域的等高线数据进行实验,验证了分布指数对不同尺度下的地理线要素复杂程度具有较好的表达效果,并可以将其运用于线要素的多尺度表达。

English Abstract

肖天元, 刘鹏程, 艾廷华, 李精忠. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
引用本文: 肖天元, 刘鹏程, 艾廷华, 李精忠. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
XIAO Tianyuan, LIU Pengcheng, AI Tinghua, LI Jingzhong. A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
Citation: XIAO Tianyuan, LIU Pengcheng, AI Tinghua, LI Jingzhong. A Fractal Description and Multi-scale Expression Method of Fourier Information Metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 119-125. doi: 10.13203/j.whugis20180336
  • 地图多尺度表达过程中的地理要素复杂程度的度量问题一直是地理信息系统的研究热点。在香农提出的信息熵理论基础上,可以通过一系列算法求算出要素的信息量来描述曲线的复杂程度。一般情况下,线要素的形状越复杂,其包含的信息量就越大。因此,信息量的计算方法就成为了描述曲线复杂程度中的重点。

    在信号学领域,一般可以从时域和频域两种方式来对某个特定信号进行分析与处理[1-2]。在地理学领域,同样可以从空间域和频域两种方式对地理线要素进行分析,进而计算信息量,描述其复杂程度。在空间域范围内,刘慧敏等[3]提出了一种在空间域内基于拐点的线要素弯曲序列识别方法,分别通过线要素的几何形状、几何拓扑、几何分布来描述地理线要素中所包含的信息量。在频域范围内,刘鹏程等[4-6]通过傅里叶级数将曲线分解成各个频率的三角函数,实现了将地理线要素从空间域到频域的转换,从而将曲线用一系列傅里叶描述子来进行表达,并提出了一种利用傅里叶描述子计算地理线要素信息量的方法[7]

    在分形理论方面,传统的分形维数也可用于描述曲线的复杂程度[8]。本文提出了一种将分形理论运用在频域的方法来描述地理线要素的复杂程度。由于地理线要素在频域被分解成不同频率的三角函数的信息量呈重尾(Heavy-Tail)分布,因此,本文结合Jiang等提出的一种改进的首尾(Head-Tail)分布数据分类方案[9-14],以及Koch提出的“二八定律”[15],将地理线要素经过傅里叶级数展开后按照不同的频率所含的信息量进行Head-Tail分类,进而提出一种p分布的概念,建立数学模型计算其分布指数p,用于描述地理线要素的复杂程度;并将分布指数p与方根模型相结合,运用到基于傅里叶的线要素渐进传输模型中。

    • 一般来说,在GIS领域描述、表达与分析地理要素都是在选定的地理坐标系所构建的空间域的基础上进行的。在某些特定情况下,则需要将地理要素引申到频域,以深入分析要素的内部特征及规律。将地理要素从空间域转换到频域,并将地理线要素分解成不同频率的正弦波和余弦波的叠加,可以从频域的角度实现对地理要素复杂程度的分析。

      f(x)是周期为2L的周期函数,则f(x)的傅里叶级数收敛。记其和函数为S(x),则:

      $$S(x) = \sum\limits_{n = - \infty }^{ + \infty } {{c_n}} {{\rm{e}}^{{\rm{j}}\frac{{n{\rm{ \mathsf{ π} }}x}}{L}}} = \sum\limits_{n = - \infty }^{ + \infty } {{c_n}} \left( {\cos \frac{{n{\rm{ \mathsf{ π} }}x}}{L} + {\rm{j}}\sin \frac{{n{\rm{ \mathsf{ π} }}x}}{L}} \right)$$ (1)

      式中,

      $$\begin{array}{l} \;\;\;\;\;{c_n} = \frac{1}{{2L}}\mathop \smallint \limits_{ - L}^L f\left( x \right){{\rm{e}}^{ - {\rm{j}}\frac{{n{\rm{ \mathit{ π} }}x}}{L}}}{\rm{d}}x = \\ \frac{1}{{2L}}\mathop \smallint \limits_{ - L}^L f\left( x \right)\left( {{\rm{cos}}\frac{{n{\rm{ \mathit{ π} }}x}}{L} - {\rm{jsin}}\frac{{n{\rm{ \mathit{ π} }}x}}{L}} \right) \end{array}$$ (2)

      式中,j为虚数单位; n=0, ±1, ±2…。对于闭合的地理线要素,用点集P0, P1PN来描述其形状。将P0作为曲线的起点,则地理线要素上任意一点都可以由一个以线要素周长为周期的分段周期函数P(s)=X(s)+jY(s)来表达,如图 1所示。

      图  1  闭合曲线上点的函数表达

      Figure 1.  Point Function Expression on Closed Curve

      该分段周期函数通过傅里叶级数展开之后的表达式为[4]

      $$P(s) = \sum\limits_{n = - \infty }^{ + \infty } {{c_n}} {{\rm{e}}^{{\rm{j}}\frac{{2{\rm{n \mathsf{ π} }}s}}{L}}} = \sum\limits_{n = - \infty }^{ + \infty } {{c_n}} \left( {\cos \frac{{2n{\rm{ \mathsf{ π} }}s}}{L} + {\rm{j}}\sin \frac{{2n{\rm{ \mathsf{ π} }}s}}{L}} \right)$$ (3)

      式中,L为该闭合曲线的周长; 系数cn的表达式为:

      $$\begin{array}{l} {c_n} = \frac{1}{L}\sum\limits_{i = 0}^{N - 1} {\int_{{S_i}}^{{S_{i + 1}}} {\left\{ {{x_i} + \frac{{{x_{i + 1}} - {x_i}}}{{{S_{i + 1}} - {S_i}}}\left( {s - {S_i}} \right) + } \right.} } \\ \left. {j\left[ {{y_i} + \frac{{{y_{i + 1}} - {y_i}}}{{{S_{i + 1}} - {S_i}}}\left( {s - {S_i}} \right)} \right]} \right\}{{\rm{e}}^{ - {{\rm{j}}^{2n{\rm{ \mathsf{ π} }}s}}}}{\rm{d}}s \end{array}$$ (4)

      式中,Si表示从起点P0Pi的曲线长度。取式(4)中cn的模,即可构成向量V

      $$\mathit{\boldsymbol{V}} = \left( {\left\| {{c_1}} \right\|, \left\| {{c_2}} \right\| \ldots \left\| {{c_i}} \right\| \ldots \left\| {{c_N}} \right\|} \right)$$ (5)

      将式(5)中的向量V进行归一化处理,即得到曲线的归一化傅里叶描述子。归一化后的第i个傅里叶描述子di为:

      $$ {d_i} = \frac{{\left\| {{c_i}} \right\|}}{{\left\| {{c_1}} \right\|}}, i = 1, 2 \ldots N $$ (6)

      同样,不闭合的曲线可以通过轴对称的方法,将曲线以首尾点的连线为对称轴进行镜像处理。通过这种方法就可以得到不闭合曲线的傅里叶描述子[5]

    • 当曲线分别展开至第1, 2…i项时,傅里叶拟合曲线与原曲线的相似程度也会不断提高。为了描述这种相似程度,引入阈值t来表示曲线的拟合程度。如图 2所示,假设有一闭合曲线L,其通过傅里叶级数展开后的拟合曲线L_Fourier所围成面的面积分别为Area_Origin、Area_Fourier。将两个面进行求交运算,得出相交后的面积Area_Intersect。则阈值t的计算公式如下:

      $$ t = \frac{{2{\rm{Area}}\_{\rm{Intersect}}}}{{{\rm{Area}}\_{\rm{Origin}} + {\rm{Area}}\_{\rm{Fourier}}}} $$ (7)

      图  2  傅里叶拟合面与相交面示意图

      Figure 2.  Schematic Diagram of Fourier Fitting Area and Intersecting Area

      在阈值要求相同的情况下,越复杂的曲线,所需要的傅里叶展开项数就越大。在频率域中的一个信号或者一条曲线,经过傅里叶分解之后的低频部分决定其整体形状,高频部分决定其细部特征。因为低频部分的正弦曲线振幅较大,周期较长,在宏观上具有较强的决定性;而高频部分的正弦曲线振幅较小,周期较短,在微观上具有较好的表达性。此外,随着阈值要求的提升,曲线所需的傅里叶展开项数也会相应增加,且当阈值在0.995附近时,傅里叶拟合的地理线要素与原曲线基本难以观测出差异。因此,本文选用当阈值等于0.995的拟合曲线来近似替代原地理线要素。

    • 香农在1948年提出了信息熵的概念。信息熵的模型为:

      $$ I = - \sum\limits_{i = 1}^n {{p_i}} {\log _x}{p_i} $$ (8)

      式中,pi表示事件i发生的概率;当对数函数的底数x为2时,信息量I的单位为bit。根据信息熵模型,可以将傅里叶拟合后的曲线的归一化傅里叶描述子V=[d1, d2dn]作为信息整体,从而计算地理线要素在频率域上的信息量,其中n为当阈值等于0.995时曲线的傅里叶展开项数。则每个傅里叶算子在整体中所占的比例为:

      $$ {{\mathop{\rm prop}\nolimits} _i} = \frac{{{d_i}}}{{\sum\limits_{j = 1}^n {{d_j}} }} $$ (9)

      式中,$\sum\limits_{j = 1}^n {{d_j}} $代表所有傅里叶描述子的和。将每个傅里叶描述子所占的比例代入到信息熵模型中,即可得到地理线要素在频率中所包含的信息量IF

      $$ {I_F} = - \sum\limits_{i = 1}^n {{{{\mathop{\rm prop}\nolimits} }_i}} {\log _2}{{\mathop{\rm prop}\nolimits} _i} $$ (10)

      表 1对不同复杂程度的地理线要素信息量进行了比较。其中,地理线要素的复杂程度基本与其信息量呈正相关。且越复杂的地理要素,其所包含的信息量就越大。这与文献[3]的实验结果是一致的。

      表 1  不同复杂程度的开曲线和闭曲线的信息量比较

      Table 1.  Comparison of Information Between Closed Curves and Unclosed Curves with Different Complexity

      曲线类型 曲线形状 曲线点数 信息量/bit
      闭曲线 127 3.380
      415 3.640
      3 505 5.210
      5 436 5.716
      开曲线 268 4.743
      954 4.873
      7 252 6.262
      21 857 7.174
    • 近年来,分形理论中统计上的自相似性已成为GIS领域中的一个研究热点[8, 16-17]。传统的分形理论同样也可以用于地理要素的复杂程度表达中。一般情况下,地理线要素越复杂,其分形维数就越大。

      Koch将分形理论扩展到了自然科学及社会科学中,并由此提出了“二八定律”。近似呈“二八定律”分布的数据可以被称为是重尾分布的数据集。如图 3所示,将地理线要素进行傅里叶展开后,每个频率的信息量经过排序后所组成的数据同样是一个重尾分布的数据集。实际上,这种近似呈“二八定律”的数据可以逐次按照20%的比例,在20%~80%分类的基础上进行继续分类。按照所需层次和等级可以继续分类成4%~16%~80%、0.8%~3.2%~16%~80%等。这种分类方式被称为改进后的首尾分布。因此,需要建立一个数学模型来具体计算出这个分布指数p,将这个定律推广到具有普适性的p分布。

      图  3  傅里叶展开曲线各个频率信息量的重尾分布

      Figure 3.  Heavy-Tail Distribution of Information About Each Frequency of a Curve After Fourier Expansion

      Koch所提出的“二八定律”是一种理论上的模型,在实际情况中,数据的分布在统计学中不会完全符合20%~80%的比例。同样,不同的地理线要素在傅里叶展开下的信息量亦不会完全符合20%~80%的比例分布,而是一种普适性的p~(1-p)比例分布。

      选用地理线要素经过傅里叶展开后再进行排序并逐次相加后的信息量作为数据集。由此可以得到:

      $$ {I_n} = \sum\limits_{i = 1}^n {{A_i}} $$ (11)

      式中,Ai表示每个傅里叶算子经过排序后的信息量;n表示傅里叶算子个数;In表示排序后的前n个傅里叶算子的信息量的和。

      以式(11)中排序后的傅里叶算子个数n与前n个傅里叶算子的信息量之和In的分布为例,分别求出它们在傅里叶总展开项数所占比例x及在总信息量中所占比例y。如表 2所示,由于该分布中的项数比率x呈Head-Tail分布,而且信息量比率y与其相对应呈逆向Head-Tail分布,所以该分布实质上是一个二维的Head-Tail分布。

      表 2  符合p分布的数据集按Head-Tail分布分割n次后的结果

      Table 2.  Consequence of Datasets that Meet p-Distribution and are Split n Times by Head-Tail Distribution

      分类次数 傅里叶展开项数的Head比率x/% 信息量的Head比率y/%
      1 p 1-p
      2 p2 (1-p)2
      n pn (1-p)n

      表 2中的傅里叶项数比率x与信息量比率y分别作为平面直角坐标系中的x轴与y轴,并求自然对数可得:

      $$ \frac{{{\rm{ln}}y}}{{{\rm{ln}}x}} = \frac{{{\rm{ln}}\left( {1 - p} \right)}}{{{\rm{ln}}p}} $$ (12)

      在该线性模型中,斜率k=ln(1-p)/lnp;理想情况下截距为0。对式(12)求以e为底的指数函数,即可得出傅里叶展开项数比率与所含信息量比率关系的数学模型:

      $$ y = {x^{\frac{{{\rm{ln}}\left( {1 - p} \right)}}{{{\rm{ln}}p}}}} $$ (13)

      分别将不同的地理线要素排序后的傅里叶展开项数与信息量的自然对数值代入式(12)中,通过最小二乘法拟合,即可求得每个地理线要素的频率域信息量分布指数p

      表 3对不同地理线要素的分布指数及相关拟合参数R2进行了计算和比较。从表 3中可知,当地理线要素的复杂程度越大时,其频率域信息量的分布指数p就越小。因此,可以采用测定地理线要素的分布指数p的方法来描述地理线要素的复杂程度。

      表 3  不同地理线要素的分布指数p及拟合参数

      Table 3.  Distribution Index p and Fitting Parameters of Different Lines

      要素形状 总信息量/bit k R2 p
      3.380 0.568 0.976 0.405
      3.640 0.445 0.966 0.365
      5.210 0.217 0.926 0.259
      5.716 0.202 0.895 0.249
      4.743 0.439 0.980 0.363
      4.873 0.234 0.907 0.269
      6.262 0.184 0.915 0.237
      7.174 0.118 0.864 0.185
    • 在地图的多尺度表达研究领域中,地图尺度的变化实质上可以由地理要素复杂程度的变化来表达。而一般情况下,地理要素复杂程度在不同尺度下的变化又可以由它在不同尺度下所包含的地物数量的比例来表示。由方根模型[18]可知,地图在不同尺度下的地物数量的比例与地图比例尺比例的变化有关:

      $$ {n_F} = {n_A}\sqrt {\frac{{{M_A}}}{{{M_F}}}} $$ (14)

      式中,nA为简化前地图的地物数量;nF为简化后地图的地物数量;MA为简化前地图的比例尺分母;MF为简化后地图的比例尺分母。将式(14)变换后即可得到地图的尺度变化与地物数量之间的关系表达式:

      $$ \frac{{{M_A}}}{{{M_F}}} = {\left( {\frac{{{n_F}}}{{{n_A}}}} \right)^2} $$ (15)
    • 由于分布指数p与地物数量n都可以用于衡量地理线要素的复杂程度,因此,分布指数p也可以运用于地理要素的化简,进而实现地图的多尺度表达。将选定的曲线通过线简化工具分别选定不同的容差,得到经过简化后的各条线段。由于经过不同容差简化后的线要素所包含的地物数量(简化后点的数量)不同,因此它们的复杂程度也不相同。如图 4所示, 分别对简化后的不同复杂程度的线段求p值,即可得到每条曲线点的数量与分布指数之间的对应关系。经过比较发现,点数量开方的值m与分布指数p之间存在良好的线性关系。

      图  4  不闭合等高线的m-p函数关系图

      Figure 4.  Function Graph of m and p of Unclosed Contours

      图 4中的m-p关系图可知,通过最小二乘法拟合出的R2值接近于1,表明mp之间具有较强的相关性。因此,可以得到拟合直线的解析式:

      $$ p=km+b $$ (16)

      式中,b为拟合直线在纵轴上的截距,且$ b = \mathop {{\rm{lim}}}\limits_{m \to 0} p$;m为线要素上点数量的开方值。联立式(15)、式(16)即可得到在地图多尺度表达过程中,地图的不同尺度与其相对应分布指数p之间的关系:

      $$ \sqrt {\frac{{{M_A}}}{{{M_F}}}} = \frac{{{n_F}}}{{{n_A}}} = {\left( {\frac{{{m_F}}}{{{m_A}}}} \right)^2} = \frac{{{{({p_F} - b)}^2}}}{{{{({p_A} - b)}^2}}} $$ (17)

      式中,mAmF分别为简化前后地图点数的开方值;pA为简化前地图的分布指数;pF为简化后地图的分布指数。将式(17)变换后即可得到地图在尺度变化后分布指数的表达式:

      $$ {p_F} = \sqrt[4]{{\frac{{{M_A}}}{{{M_F}}}}}\left( {{p_A} - b} \right) + b $$ (18)

      根据式(18),由于原曲线的比例尺MA分布指数pA以及常量b已知,因此可以根据所需尺度MF的变化,得到适应不同比例尺的分布指数pF。再根据所求的p值得到适应相应尺度所需的傅里叶展开次数,从而动态地实现线要素的渐进传输。图 5显示了某区域的等高线在不同尺度下使用该方法进行简化的结果。可以看出,地理线要素的分布指数p对要素的多尺度表达也具有良好的效果。在实际应用中,可以利用分布指数p的变化来控制曲线的傅里叶展开次数,从而实现地图尺度的转变,可以进一步应用于基于傅里叶的线要素渐进传输模型中。

      图  5  某区域的等高线在不同比例尺下的简化结果

      Figure 5.  Simplification of the Contours of a Region at Different Scales

    • 本文综合频率域、分形以及信息熵理论提出了一种描述地理线要素复杂程度的新方法。该方法利用傅里叶级数将地理线要素由空间域转化到频率域,从频率域的独特视角获得含有地理要素形状信息的傅里叶描述子对地理要素进行分析及还原,并在设定的阈值要求下用傅里叶描述子还原曲线近似代替原地理线要素。同时,在香农信息熵理论的基础上,测定每个傅里叶描述子所包含的信息量大小。并结合分形理论,在Head-Tail分布的理论基础上与Koch的“二八定律”相结合,对地理要素各个频率的信息量数据进行分析,从而求出可以描述地理线要素复杂程度的频率域信息量分布指数p

      实验结果表明,分布指数p与曲线的复杂程度呈负相关关系。将分布指数的这一特性与传统方根模型相结合,即可得到地图比例尺M与分布指数p之间的函数关系,并在某区域的等高线不同比例尺简化过程中取得了良好的表达效果。由此可以认为,地理线要素的分布指数对地理线要素的复杂程度以及地图的尺度变化具有良好的表达性,并且可以将其应用于基于傅里叶的线要素渐进传输模型中。

参考文献 (18)

目录

    /

    返回文章
    返回