EN中文

地球信息科学学报 >

2022 , Vol. 24 >Issue 12: 2309 - 2321

DOI: https://doi.org/10.12082/dqxxkx.2022.210795

地球信息科学理论与方法

基于离散傅里叶变换的线要素节点压缩方法

  • 何山 , 1, 2, 3 ,
  • 闫浩文 , 1, 2, 3, * ,
  • 李蓬勃 1, 2, 3
展开
  • 1.兰州交通大学测绘与地理信息学院，兰州 730070
  • 2.地理国情监测技术应用国家地方联合工程研究中心，兰州 730070
  • 3.甘肃省地理国情监测工程实验室，兰州 730070
*闫浩文（1969— ），男，甘肃民勤人，教授，主要从事地图综合、数字安全、微地图等研究。 E-mail:

何山（1998— ），男，甘肃兰州人，硕士生，主要从事地图综合研究。E-mail:

收稿日期: 2021-12-10

  修回日期: 2022-03-02

  网络出版日期: 2023-02-25

基金资助

国家自然科学基金项目(41930101)

青年科学基金项目(41801395)

收起

Polyline Generalization Method based on Discrete Fourier Transform

  • HE Shan , 1, 2, 3 ,
  • YAN Haowen , 1, 2, 3, * ,
  • LI Pengbo 1, 2, 3
Expand
  • 1. School of Surveying and Geographic Information System, Lanzhou Jiaotong University, Lanzhou 730070, China
  • 2. National-Local Joint Engineering Research Center of Technologies and Applications for National Geographic State Monitoring, Lanzhou 730070, China
  • 3. Gansu Provincial Engineering Laboratory for National Geographic State Monitoring, Lanzhou 730070, China
*YAN Haowen, E-mail:

Received date: 2021-12-10

  Revised date: 2022-03-02

  Online published: 2023-02-25

Supported by

National Natural Science Foundation of China(41930101)

National Natural Science Foundation of China(41801395)

Fold

摘要

相较于传统删减顶点的线要素综合方法，基于傅里叶变换的线要素综合更能保留曲线的全局特征,但现有的傅里叶综合方法无法自动减少和控制点数，更多适用于曲线的平滑及多尺度表达。因此本文提出一种利用离散傅里叶变换进行线要素综合的方法。对曲线进行离散傅里叶变换，获得有限项傅里叶描述子；根据期望的压缩比对傅里叶描述子进行截断；根据截断后的描述子项进行离散傅里叶逆变换获得化简曲线。本文提出的这种傅里叶方法能够减少化简后曲线顶点数，适用于地图综合领域。本文通过四组实验验证了算法的可行性，展示其如下优点：① 能够在相应尺度上对线性地物进行平滑、渐进的化简和表达② 在现有傅里叶变换法的基础上能够保留曲线原顶点；③ 以顶点数作为综合过程参数，能够自动减少曲线顶点数；④ 相较于传统节点压缩方法，更注重整体形态的化简，在综合过程中能更好地保留曲线的整体特征；⑤ 在转换尺度较大的综合过程中，相较于传统节点压缩方法所保留的几何精度更高。

关键词： 离散傅里叶变换; 线要素; 地图综合; 频率域; 节点压缩; 曲线化简; 多尺度表达; 小波变换

本文引用格式

何山 , 闫浩文 , 李蓬勃 . 基于离散傅里叶变换的线要素节点压缩方法[J]. 地球信息科学学报, 2022 , 24(12) : 2309 -2321 . DOI: 10.12082/dqxxkx.2022.210795

Abstract

Compared with traditional polyline generalization methods via deleting vertices, the line generalization based on Fourier transform can better retain the global characteristics of the polyline. However, the existing Fourier-based methods are more suitable for curve smoothing and multi-scale representation, and are not able to automatically control the targeting number of points on polylines. Therefore, a polyline generalization method using discrete Fourier transform is proposed in this paper. The discrete Fourier transform is first performed on the polyline to obtain a Fourier descriptor with finite terms. The Fourier descriptor then is truncated according to the desired compression ratio. Finally, the simplified polyline is obtained by inverse discrete Fourier transform based on the truncated descriptor. In this paper, a Fourier method which can reduce the number of vertex points of the simplified curve is proposed, which can be applied to the field of map generalization. In this paper, the feasibility of the proposed algorithm is verified by four groups of experiments, and its advantages are shown as follows: (1) it can simplify and express linear features smoothly and gradually on the corresponding scale; (2) it can retain the original vertices of the curve on the basis of the existing Fourier transform method; (3) the number of vertex points is taken as the generalization parameter, and the number of vertex points of the curve can be automatically reduced; (4) compared with the traditional node compression method, it pays more attention to the simplification of the overall shape, and can better retain the overall characteristics of the curve in generalization; (5) in the generalization process with large conversion scale, the geometric accuracy retained in this study is higher than that of the traditional node compression method.

Key words： Discrete Fourier Transform (DFT); polyline; cartographic generalization; frequency domain; node compression; curve simplification; multiscale representation; wavelet transform

1 引言

从源地图到目标地图的比例缩减,会不可避免地导致地图符号的冲突和拥挤。为使地图清晰易读，应删除、简化和概括地图特征，这便是地图综合[1]。线要素综合是地图综合中重要的一部分，其综合对象包含河流、道路网、等高线、海岸线等线要素地物以及部分面要素地物（如行政边界、建筑物）等。线要素综合主要涉及到线要素的选取和化简两部分，对于河流、道路网、等高线等线要素地物需要首先针对其独特的语义或属性信息进行线要素的选取，再对选取后的结果进行线要素形状化简的工作，从而得出综合结果。不同的线要素对象的综合规则和约束条件差别很大，这主要源于线要素选取对象的复杂性以及特殊性，但在线要素化简方面，各种算法存在一定共性，即概括和简化线要素的几何形状，针对单一线要素的研究，存在一定的通用化简算法。本文的研究范围主要针对线要素地物选取之后的化简工作，对于不同类型地物的综合约束条件不进行过多讨论。
传统的线要素化简算法常采用节点压缩方法，如D-P算法[2]、Visvalingam算法[3]等，因为节点压缩方法效率较高，稳定性好[4],节点压缩后的顶点源于原始线要素，能够在一定程度上保证综合结果的顶点精度，同时有效减少曲线点数，满足地图综合中的精确性原则。但传统节点压缩方法存在以下问题：① 综合过程由地图上不直观的隐性参数的设置控制，需要人为干预阈值，对于作业人员的经验需求较高；② 多数算法依赖于原始曲线特征点的保留，这在转换尺度较小的综合过程中能保证结果的几何精度，但在转换尺度较大的综合过程中会忽略曲线的整体形态变化，造成视觉上尖锐，不满足地图综合中的平滑性和整体性原则。
现有的基于傅里叶变换的线要素化简方法，可以有效保留地物的全局特征[5]。Boutoura[6]通过将曲线的曲率转换为频率系数，再将高频的系数赋值为0，对赋值后的频率系数进行傅里叶逆变换，获得平滑后的综合曲线。Fritsch等[7]将曲率替换为弯曲度进行傅里叶变换，将对频率系数赋值为0替换为放大/赋值为0，获得了细节增强/平滑化简的综合结果，并指出了去除某些频率时偶尔会产生共振效应。Lawford[5]通过复数域的傅里叶变化，将x和y的坐标同时进行变换操作，并通过人工评价综合结果，拟合出经验公式，将频率数与地图比例尺进行关联。刘鹏程等[8⇓⇓⇓-12]通过将矢量线要素表示为分段函数的形式，对函数式进行了连续傅里叶变换，获得了无限级数项的频率系数，同时通过信息熵以及二八定律，将化简程度与地图比例尺相关联，并将其应用于多种地物多尺度表达。李精忠等[13]通过赋权相加频率域的方式实现了面要素Morphing方法。以上基于傅里叶变换的综合方法，均能实现化简结果的多尺度表达，但这些化简结果多为平滑曲线或连续函数，其所保留的点数均大于或等于原始图形。如果将现有的傅里叶方法直接应用于实际的综合制图中，将会存在以下问题：① 综合后线要素不是离散矢量数据，同时顶点数并未减少，需要手动对综合后的平滑曲线进行重采样，这将一定程度上破坏傅里叶方法保留曲线整体特征的优势，同时回归到保留点数多少的问题上；② 综合后结果无法保留原曲线顶点，无法保证综合过程中的精度需求。
因此，本文提出了一种基于离散傅立叶变换的节点压缩方法，能够在综合过程中自动减少曲线点数同时保留曲线整体特征及曲线原顶点，使傅里叶方法的多尺度表达结果能够应用于地图综合领域。

2 研究方法

连续傅里叶变换法将矢量数据拟合为函数形式并表达在频域上，通过保留傅里叶描述子项的多少控制图像的表示细节，得到不同尺度上化简后的光滑曲线，实现不同尺度的线要素综合的表达。但由于是对函数而不是离散点进行变换，因此化简曲线无法与原曲线重合，理论上随着保留级数的增多能够无限逼近于原曲线。此外，由于得出结果不是离散的矢量数据而是连续函数，需要对函数曲线进行采样从而获得综合后的矢量曲线就会出现2种情形：① 使用等间距或等点采样会造成特征点的遗漏或信息冗余；② 使用顾及曲线特征（如曲率、凹凸面积等）采样，则需要人工设置阈值及参数，降低了效率，增加了复杂因素。为避免以上问题，本文以离散傅里叶变换进行线要素综合。
离散傅里叶变换是针对一段有限长的离散信号，找出它在各个频率上的正弦波的分量。
X k = ∑ n = 0 N - 1 x n e - j 2 π N k n ( 0 ≤ k < N - 1 )
x n = 1 N ∑ k = 0 N - 1 X k e j 2 π N k n ( 0 ≤ n < N - 1 )
式中：N为样本点数量； X k为傅里叶项系数，既傅里叶描述子；k表示谐波次数； x n为离散样本点；n为离散样本点序数； e - j 2 π N n为复指数形式的基波。在计算机中通过乘以傅里叶矩阵及逆矩阵对二者实现正逆傅里叶变换，如式（3）所示。
F n = W × c n
f 0 f 1 f 2 f 3 ︙ f N - 1 = 1 1 1 1 … 1 1 w w 2 w 3 … w N - 1 1 w 2 w 4 w 6 … w 2 N - 1 1 w 3 w 6 w 9 … w 3 N - 1 ︙ ︙ ︙ ︙ ︙ ︙ 1 w N - 1 w 2 N - 1 w 3 N - 1 … w N - 1 2 c 0 c 1 c 2 c 3 ︙ c N - 1
f n = w 0 n c 0 + w 1 n c 1 + … + w N - 1 n c N - 1 = ∑ k = 0 N - 1 w n k c k
式中： F n=（ f 0， f 1， f 2，…， f N - 1）原后曲线样本点集；W为傅里叶系数矩阵； c n=（ c 0， c 1， c 2，…， c N - 1）为傅里叶系数集，展开后如式（5）所示，式中w= e 2 π i N。对线要素进行离散傅里叶变换可以得到其频域图像如图1所示，在图1（c）中xy为原曲线所在平面，将原曲线沿z轴分解为由低频到高频的多个三角函数曲线，再将这些三角函数曲线投影在xz轴上便可得到该曲线的频域图像，此时z轴代表频率大小，x轴代表幅值。投影之后如图1（b）所示，其中 c 0为基值，本文中将曲线的x、y坐标提取为点集分别进行操作，可以看到原曲线x、y坐标的傅里叶系数在频域上的整体趋势相同。由于离散傅里叶频域图像的性质，除 c 0外频域图像左右对称，傅里叶系数的值均由两端的低频区域向中部的高频区域减少，因此对傅里叶系数 c n的操作需要对称进行。
图1 频域图像展示

注：图（a）中紫色区域为原曲线围成的面状地物；图（b）中红色部分为原曲线x坐标点集的傅里叶系数，蓝色部分为原曲线y坐标点集的傅里叶系数。c0和c1均表示频率的编号；图（c）中红色曲线为立体空间中频率不同的三角函数，蓝色部分为相应三角函数的振幅。

Fig. 1 Ployline in frequency domain

2.1 离散傅里叶变换——赋0法

lawford[5]、boutoura[6]、fritsch[7]等均通过离散傅里叶变换将高频傅里叶系数赋值为0从而实现曲线的细节化简。
f 0 ' f 1 ' ︙ f N 2 - 1 ' f N 2 ' ︙ f N - 1 ' = 1 1 1 1 … 1 1 w w 2 w 3 … w N - 1 ︙ ︙ ︙ ︙ ︙ ︙ 1 w N 2 - 1 w 2 ( N 2 - 1 ) w 3 ( N 2 - 1 ) … w N - 1 ( N 2 - 1 ) 1 w N 2 w 2 ( N 2 ) w 3 ( N 2 ) … w N - 1 N 2 ︙ ︙ ︙ ︙ ︙ ︙ 1 w N - 1 w 2 N - 1 w 3 N - 1 … w N - 1 2 c 0 c 1 ︙ 0 0 ︙ c N - 1
f n ' = w 0 n c 0 + w 1 n c 1 + … + 0 + 0 + … + w N - 1 n c N - 1
式中：w= e 2 π ⅈ N； F n '=（ f 0 '， f 1 '， f 2 '，…， f N - 1 '）为赋0处理还原后的点集； c n=（ c 0， c 1， c 2，…， c N - 1）为傅里叶系数集。
在连续函数中，常使用平方积分值之差来衡量2条函数曲线间的差异；在离散函数中，可通过累加所有离散值的和，其差值G来衡量2条曲线的差异性。
G = F n ' - F n = ∑ n = 0 N - 1 ( f n ' - f n ) = ∑ n = 0 N - 1 ∑ k = x N - x w n k c k
式中：x为开始赋0的低频系数序号；N-x为赋0结束的低频系数序号。由于从 c x到 c N - x是包含需要被省略细节的高频系数，其值远低于低频区域的系数值 c n，因此 c x到 c N - x的值可近似看作为0，式（8）中G的值接近于0，既赋0法还原出来 F n '与原 F n差异极小，两曲线相似，其相似性也随着保留的低频数增加而单调递增，实现了曲线的多尺度综合与渐进表达。每一项 f n '由相应的权重系数 w N - 1 n乘以傅里叶系数 c N - 1累加构成，当高频区域傅里叶系数 c N - 1被赋值为0，每一项 f n '之间的相对差值对减小，因此曲线整体较综合前更加平滑，且平滑程度随着保留的低频数增加而单调递减。需要注意的是，赋0法所进行的傅里叶逆变化用的是原来N维傅里叶矩阵，因此化简后的曲线点数与原曲线点数相同仍为N，与连续傅里叶变换面临同样的问题，仍需要进行重采样减少综合后曲线的点数。

2.2 离散傅里叶变换——截断法

为了控制综合后曲线点的数量，同时删除曲线的高频信息，本文提出一种新的离散傅里叶变换法——截断法。与赋0法相比，截断法直接删除高频傅里叶系数，使傅里叶矩阵变为指定维数，从而通过逆变换得到指定数目的输出点。
f 0 ' ' f 1 ' ' ︙ f x ' ' f x + 1 ' ' ︙ f 2 x ' ' = 1 1 … 1 1 … 1 1 w ' ' … w ' ' x 1 w ' ' x + 1 1 … w ' ' 2 x 1 ︙ ︙ ︙ ︙ ︙ ︙ ︙ 1 w ' ' 1 x … w ' ' x x w ' ' ( x + 1 ) x … w ' ' 2 x x 1 w ' ' 1 x + 1 … w ' ' x x + 1 w ' ' x + 1 2 … w ' ' 2 x x + 1 ︙ ︙ ︙ ︙ ︙ ︙ ︙ 1 w ' ' 1 2 x … w ' ' x 2 x w ' ' x + 1 2 x … w ' ' 2 x 2 c 0 c 1 ︙ c x c N - x ︙ c N - 1
f n ' ' = w ' ' 0 n c 0 + w ' ' 1 n c 1 + … + w ' ' x n c x + w ' ' x + 1 n c N - x + … + w ' ' 2 x n c N - 1 = ∑ k = 0 x w k n c k + ∑ k = N - x N - 1 w k - N + 2 x + 1 n c k
式中：w= e 2 π i 2 x + 1； F n ' '=（ f 0 ' '， f 1 ' '， f 2 ' '，…， f 2 x ' '）为截断处理还原后的点集； c n=（ c 0， c 1， c 2，…， c N - 1）为傅里叶系数集；x为开始截断的低频系数序号；N-x为截断结束的频率序号。其每项对应关系如表1所示。
表1 截断法中傅里叶系数对应关系

Tab. 1 correspondence of Fourier coefficients in paper method

原曲线点集 F n f 0 f 1 f 2 … f x … f N - x … f N - 2 f N - 1
傅里叶系数 c n c 0 c 1 c 2 … c x … c N - x … c N - 2 c N - 1
是否保留 保留 保留 保留 保留 保留 删除 保留 保留 保留 保留
还原后点集 F n ' ' f 0 ' ' f 1 ' ' f 2 ' ' … f x ' ' - f x + 1 ' ' … f 2 x - 1 ' ' f 2 x ' '
对离散函数依旧累加值的差来衡量曲线差异性，但由于截断法还原出的点集 F n ' '与原点集 F n '长度不等，因此在累加 f n ' '与 f 0的值后，需要除以它们对应的长度，求其平均值差H，该变量在几何意义上代表了两点集重心之间的距离。
H = F n ' ¯ - F n ' ' ¯ = ∑ n = 0 N - 1 ∑ k = 0 x w k n c k + ∑ k = N - x N - 1 w k n c k N - 1 - ∑ n = 0 2 x ∑ k = 0 x w ' ' k n c k + ∑ k = N - x N - 1 w ' ' k - N + 2 x + 1 n c k 2 x = E f ' - E f ' '
当N较大，x较大时，w与 w ' '均趋近于1，因此H≈0，既两曲线相似，且相似程度随原始图像点数增多及保留级数增多而单调递增。由于 F n ' '与 F n '整体相近，而2.1节中已推论过 F n '与 F n整体相近，因此截断法还原所得点集 F n ' '与原曲线点集 F n接近，综合后曲线与原曲线相似。需要注意的是，使用截断法通过傅里叶矩阵逆变换获得的输出值实际上为：
x n = 1 2 x + 1 ∑ k = 0 2 x X k e j 2 π N k n
式中：系数 1 N取决于傅里叶矩阵的维度，而截断法改变了傅里叶矩阵的维度，使其从由原来的N减小到了（2x+1），因此需要对输出点集 F n ' '内所有值乘以系数 2 x + 1 N。

2.3 比例尺与参数的关联

线要素综合主体分为线要素化简和线要素选取两部分，线要素化简中节点压缩方法凭借其高效性和稳定性受到广泛认同，但有学者认为节点压缩方法会破坏曲线的平滑程度，应算作信息压缩方式而非地图综合方式。实际上，地图综合的本质在于从源地图到目标地图的比例缩减，这不可避免地会导致地图符号的冲突和拥挤。为使地图清晰易读，应删除、简化和/或概括地图特征[1]。地图中线要素的平滑程度受限于人类视觉分辨率影响，越小尺度的图像对其图形复杂度的要求越低。随着地图比例不断减小，线要素的顶点数、复杂度逐渐降低，但从人类的视觉上看，曲线的光滑程度不一定随之降低。
现有的线要素化简方法众多，侧重点各有不同，但都需要依靠一个或多个参数/阈值控制综合程度。最简单的线要素化简方法为间隔取点法，每隔一定点数或一定长度保留曲线顶点，这些方法虽然从阈值选取的角度考虑到了线要素最直观、最基本的特征——顶点数，但由于忽略了线要素的特征而被淘汰。之后的算法为保留线要素的局部特征，依靠相邻点之间的关系进行顶点的选取与保留，如垂距法、Tobler法、偏角法等，也有的算法着重考虑线要素的整体特征，如Douglas-Peucker算法、Visvalingam-WHyatt算法以及基于傅里叶变换的算法等[14]。表2列出一些算法及其所采用的参数。
表2 常见曲线化简算法及其参数

Tab. 2 Common curve simplification algorithms and their parameters

算法 参数
Douglas-Peucker算法 垂距
光栅法 圆盘（限差）
线简化的优化算法 保留线段的数目（或百分比）
Li-Openshaw 最小可视尺寸
ε-圆滚动算法 圆半径ε
基于余弦值的算法 光滑因子m
Opheim算法 最大、最小距离
廊道搜索 廊道宽
基于QTM算法 QTM-level
遗传算法 M、pc、pm及终止条件
本体驱动的线化简方法 压缩比
Visvalingam-Villiamson 面积S
可以看到，线要素化简算法的功能逐渐完善，但所依靠的参数也越来越抽象、复杂，难以从地图上直观有效地获取该参数的信息。算法的重心也逐渐转移到对阈值的确定上，从而弱化了地图表达中的直观性和概括性需求[15]。因此，希望能以线要素最简单直观也最基本的特征——顶点数，作为唯一的衡量参数，同时保留线要素的整体特征进行综合。
为了使地图综合程度得到量化控制，需要将算法的参数与地图比例尺进行关联。许多学者均在此做出尝试，肖天原、刘鹏程等利用信息熵以及分型维数衡量曲线的复杂程度，通过传统的方根模型与地图比例尺相关联。Lawford[5]通过人工评价多尺度综合结果，使用回归方程拟合出了频域级数与地图比例尺的关系。Li-Openshaw[16]在已知比例尺下通过最小视距安排点的分布。王荣等[17]通过构建多尺度线要素间相似度评价模型实现D-P算法的全自动化。
不同的算法使用参数不同，适用范围也不同。参数与地图比例尺的关系作为地图综合中的难题现并未得出统一答案。本文采取经验拟合法进行比例尺及参数的关联，由于线要素由点集构成，在顶点数的保留上与点群的选择具有一定相似性，因此本文以开方根模型中的幂函数为基础，以现有的1：4500 000，1：10 000 000，1：50 000 000，110 000 000 4种比例尺世界地图下的海岸线轮廓对其相应的顶点数进行拟合（该数据来源于开源网站 https://www.naturalearthdata.com），表3列出了不同比例尺下对应地物的顶点数，所得如式（13）所示。
N A N F = 0.36 × M F M A 0.65
表3 多比例尺下线要素点数

Tab. 3 Points number of line features in multi scale

比例尺 1：450 000 1：10 000 000 1：50 000 000 1：110 000 000
澳洲海岸线点数 247 726 9463 1154 236
马达加斯加点数 - 1566 251 49
冰岛点数 58 023 3063 453 -
式中： N A、 M A为综合结果的点数及比例尺， N F、 M F为综合前原图的点数及比例尺。该公式相关系数 R 2=0.905，反映拟合结果具有较高的相关性。实际综合效果如图2所示，其中图2（a）为原始线要素，比例尺为1：10 000 000，点数为9463；图2（（b）为比例尺1：20 000 000下综合结果，点数为2171；图2（（c）为比例尺1：40 000 000下综合结果，点数为477；图2（d）为比例尺1：80 000 000下综合结果，点数为105；图2（e）为比例尺1：160 000 000下综合结果，点数为23。从图2中可看到随着比例尺减小，点数的减少在视觉上并未破坏目标地物的平滑程度。
图2 澳洲海岸线在实际比例尺下综合结果

Fig. 2 Generalization results of Australian coastline at actual scale

由于拟合的对象数量和类型有限，所得比例尺与顶点数拟合公式仅作参考，对于不同的线要素对象乃至不同的综合样本模板并不一概适用。探讨节点压缩程度与比例尺关系的方法并不局限于函数拟合一种，如本节介绍的其他学者的关联比例尺方法均具有很高的参考价值。本节仅通过实际应用于图2的效果证明点数的减少不会影响视觉平滑程度。

3 结果分析

本文针对离散傅里叶截断法的逐级表达能力，保留原图形几何相似度能力，对线群化简能力以及拓扑保留能力进行了单一地理要素的化简实验、单个地物下与赋0法的对比实验、线群地物下与赋0法的对比实验以及与传统节点压缩方法对等高线化简的对比实验。将于3.1节实验中验证新方法的多尺度表达能力，3.2节实验中论述相较现有傅里叶方法的改进，3.3节实验中与传统节点压缩方式做对比，论述傅里叶方法的特性，3.4节实验中验证新方法保留整体形态的能力。所用到的海岸线数据均来源于开源网站 https://www.naturalearthdata.com，3.4节实验中的等高线数据由Landsat 8遥感影像截选子区的等高线提取所得。需要注明的是，本文采取主要采用单一海岸线、海岸线群以及等高线群作为实验地物其目的为增加样本多样性，不意味将其视为完整的海岸线综合/等高线综合算法。不同线状要素约束规则不同，综合过程存在差异，本文算法的提出仅针对一般线要素的形状化简。
此外，在Visvalingam算法和Douglas-Peucker算法等算法中，常使用压缩率来衡量曲线化简的程度，为了控制不同算法在比较过程中化简力度相同，在实验部分本文主要采取压缩率作为指标来衡量曲线化简程度，其公式为：
α = m n
式中：α为压缩率；n为压缩前总点数；m为压缩后剩余点数。在后续实验中，会保证所有算法化简结果在重采样后的压缩率相等，即化简力度保持相同。

3.1 单一线要素的逐级表达结果

表4列出几种线要素的截断法化简结果，当压缩率α为1时代表原图。从表4中可以看出，该方法能实现不同种类线要素在任意压缩率上的化简，从而进一步实现任意比例尺上的渐进式化简结果。化简的最大程度为保留3个点，当保留点数小于3个点后该地物在综合后结果中省略。因此原曲线点数越多，其可支持的化简级数越多，符合越复杂的曲线在综合过程中易于保留的原则。需要注意的是，固定的压缩率仅仅作为实验参照，实际上截断法可以控制顶点数在0与原点数间的任意值。
表4 多尺度下不同地物采用截断法的化简结果

Tab. 4 Multi-scale simplification results of paper method for different line features in multi-scale

压缩率α
1.0 0.1 0.01 0.005 0.001
曲线a
点数/个 309 30 3
曲线b
点数/个 3063 306 30 15 3
曲线c
点数/个 1779 178 18 7
曲线d
点数/个 334 34 3
曲线e
点数/个 110 19
曲线f
点数/个 1853 186 18 8
曲线g
点数/个 1663 166 16 7
曲线h
点数/个 2501 250 26 11

3.2 与赋0法对单一线要素的对比实验

图3为对澳洲海岸线进行赋0法和截断法的对比实验，其中α为压缩率，n为顶点数。由于赋0法不会改变化简后的线要素点数，此处的项数比是保留傅里叶项数与原有傅里叶项数之比，对于赋0法，无论化简程度如何其化简后点数均不会发生变化，而对于截断法，化简后的点数会不断减少，始终能与保留项数保持一致，可以看出在原有的离散傅里叶变换法基础上，新的截断法能自动减少曲线顶点。
图3 截断法与赋0法化简结果对比

Fig. 3 Comparison of simplification results between paper method and traditional DFT

本文采用相对差来衡量化简前后的几何相似度。相对差为2个集合之间的全集减去交集，表明了2个集合之间的差异性。在几何学中，通过求综合图形前后的面积的相对差可以得到二者的几何相似性。公式为：
S = 1 - a A
式中：S为几何相似度；a为二者相对差面积；A为原地物面积。表5是澳洲海岸线在多尺度下截断法和赋0法的化简结果对比。由于赋0法不会自动减少顶点数，因此在横向对比时，对其采用间隔取点法使两者点数相等。从表中可以得到，尺度变化幅度较小时截断法与原地物的相似度不如赋0法，在压缩比降到0.01以下时，截断法的相似度开始高于赋0法。这与式（14）的推论一致， F n ' '接近于 F n '，因此相较于截断法，赋0法更接近于原曲线；但随着转换尺度逐渐增大，赋0法需要重采样来减少点数的劣势体现出来，尺度变化幅度越大，重采样对于原曲线特征的破环就越严重，而截断法能够严格地控制化简后曲线地点数，保证在各尺度上的相似度变化较为稳定。
表5 单个地物截断法与赋0法重采样后对比

Tab. 5 Comparison between the proposed method and traditional DFT method in single line

澳洲海岸线压缩率 点数/个 截断法相似度 点数/个 赋0法相似度
1.0000 9436 1.000 000 9436 1.000 000
0.1000 946 0.994 054 946 0.994 276
0.0750 710 0.992 483 728 0.992 808
0.0500 474 0.989 820 473 0.989 766
0.0250 236 0.983 389 236 0.983 603
0.0100 94 0.967 399 94 0.968 533
0.0075 70 0.956 143 69 0.956 019
0.0050 48 0.940 512 49 0.937 569
0.0025 24 0.890 934 24 0.888 050
0.0010 10 0.738 805 10 0.726 752
此外，本文算法可以通过最邻近顶点匹配操作，即检索化简后线要素上所有顶点，将其替换为原曲线上的最近顶点，实现保留原曲线顶点的能力，避免了传统傅里叶变换中的精度丢失问题。如图4（b）所示，其中红色线条为原曲线，蓝色线条为本文方法（截断法）的化简结果，绿色线条为进行最邻近顶点匹配后的结果。而传统傅里叶变换如图4（a）所示，其中红色线条为原曲线，黑色线条为传统傅里叶法化简结果，由于不能减少点数，因此无法与原曲线进行最邻近顶点的匹配。综合本实验可见，本文算法不仅在化简后在尺度变化较大的综合中几何相似度较传统傅里叶方法更高，同时能够解决其无法保留原曲线顶点的问题，将傅里叶变换法从多尺度表达进一步应用到制图综合领域。
图4 匹配最邻近顶点

Fig. 4 Match the nearest vertex

3.3 与D-P算法对单一线要素的对比实验

表6是本文算法与D-P算法在相同压缩率下对某单一等高线要素进行化简的特征指标对比。图5是二者化简结果的截选局部细节。在表6中压缩率控制了曲线的化简程度，几何相似度代表了化简结果与原曲线的贴合程度，保留长度在河流等线要素地物中具有重要意义。由实验结果可知，在比例尺变换较大的情况下，本文算法在几何相似度方面与D-P算法差异不明显，这是因为本文几何相似度主要以重合面积进行衡量，对于傅里叶方法和D-P算法，二者最大的差异在顶点的选取原则上。本文方法注重逐层保留线要素整体轮廓，D-P算法注重提取局部特征点，二者依循不同的原则所得结果视觉差异较大，但面积差异不一定明显，在保留长度方面不如D-P算法，这与算法的特点相关。如图5所示，相同的化简力度下在局部弯曲保留方面，本文算法更倾向于保留线要素主轮廓上的点，而D-P算法以阈值为参数，当垂距大于一定阈值则保留，即保留点的特征较为突出，变化幅度较大，因此D-P算法在特征点的保留上具有优势，这也使得D-P算法保留化简曲线的长度更长，但曲线局部特征更为尖锐。在尺度变化较小的综合中，由于曲线的局部特征更加重要，此时D-P算法更加适用，但在尺度变化较大的综合中，局部的细节程度相对于整体轮廓更应当被省略，同时视觉上的平滑性需求较为重要，不应在整体轮廓上产生较为突兀的尖锐，此时本文算法就更加适用。
表6 单个地物截断法与D-P算法对比

Tab. 6 Comparison between our method and Douglas-Peucker method in single line

压缩率α 截断法相似度 截断法长度/m D-P算法相似度 D-P算法长度/m
1 1 142 676 1 142 676
0.02 0.981 730 104 178 0.985 680 121 450
0.01 0.971 095 95 906 0.987 750 112 163
0.005 0.954 870 86 860 0.954 028 100 574
0.002 0.913 583 76 057 0.913 217 89 460
图5 2种方法的局部细节对比其中红色线条为原始线要素

Fig.5 Comparison of local details between the two methods The red line is the original line, the green line is the simplification result of paper method, and the blue line is the simplification result of D-P algorithm

3.4 与其他节点压缩算法对单一线要素整体特征保留能力的对比实验

图6是中国西北部某山区等高线用本文截断法与传统节点压缩方法的对比，采用Visvalingam算法和Douglas-Peucker算法的结果作为参照。其中，图6（b）、图6（c）为截断法在压缩率0.002及0.0085下的综合结果，图6（d）、图6（e）为Douglas-Peucker算法在压缩率0.002及0.0085下的综合结果，图6（f）、图6（g）为Visvalingam算法算法在压缩率0.002及0.0085下的综合结果。本实验不是为了提出完善的等高线综合方法，而是为了验证对曲线整体特征的保留能力。综合前后曲线的整体形态的相似，可以通过频域相似进行衡量，但本文方法是基于频域变换得到的，在频域的保留上具有天然优势。因此，需要从其他角度来证明保留曲线整体特征的能力。等高线作为特殊的线要素，在化简过程中，线要素之间的协调远比局部特征的保留更加重要，而等高线间的协调主要依赖于每条等高线全局特征的保留，一旦某条等高线的整体形态发生变化，极易产生错误的相交或自相交。直接对等高线群使用节点压缩算法，观察其结果的错误交点数，在一定程度上可以反映算法对单一线要素的整体特征保留能力，如产生的错误相交越少，说明算法对单一线要素的整体形态保留就越好。实验结果中产生的拓扑错误相交如表7所示，这反映了傅里叶变换法对曲线整体形态的兼顾。本文方法始终逐步删除高频细节，保留基本轮廓，相较于满足一定阈值条件便对点进行删减的传统节点压缩方法，对于曲线整体特征有着更好的保留。
图6 等高线在不同尺度下3种化简方法比较

Fig. 6 Comparison of three simplification methods for contour lines at different scales

表7 各方法错误相交数量

Tab. 7 Topology error number of each method

方法 α 错误交点数/个
截断法 0.0085 54
0.0020 43
DP 0.0085 184
0.0020 169
Visvalingam 0.0085 116
0.0020 124

4 结论与讨论

4.1 结论

本文提出一种基于傅里叶变换的节点压缩方法，针对矢量线要素的频域项进行基于期望点数的截断，对逆变换后还原的曲线进行最邻近点匹配，从而得到综合结果。并通过实验验证了本文方法的可行性。本方法的创新型在于将傅里叶变换法从多尺度表达进一步应用于地图综合领域，解决了传统傅里叶方法无法自动减少点数、无法保留原曲线顶点的缺陷。该方法适用于多数线要素的几何形态化简。其优势在于：① 相较于D-P算法等节点压缩方式，在尺度跨度较大的综合中所得结果的几何相似度与原曲线更高，说明在尺度跨度越大的转换中，该方法与原曲线越贴近，更符合视觉认知； ② 在等高线群化简的整体视觉效果实验中，该方法产生的错误相交数明显小于与之对比的D-P算法和Visvalingam算法，说明本文方法继承了傅里叶方法的特性，能够更好地保留曲线整体特征；③ 相较于现有的傅里叶方法，本文方法能够使综合结果保留原曲线顶点，同时自动减少顶点数，突破了现有傅里叶方法的局限性，扩展了傅里叶方法在地图综合领域中的应用。

4.2 不足与展望

该方法的不足在于：① 在与传统节点压缩方式的对比实验中，本文方法在尺度变换幅度较小优势并不明显，同时长度保留较少。这个缺陷是由傅里叶方法忽视特征点，注重整体形态的特性所导致，暂无改进办法；② 虽然采用了顶点数作为尺度参数相较于其它方法的参数在地图上更为直观可见，但线要素综合中比例尺与保留顶点数的关系尚未有研究给出定论，本文仅在针对实验情况做了经验拟合，在实际应用时仍需结合一定的制图经验；③ 适用范围有限，该方法适用范围与D-P算法等传统的节点压缩方法一致，对于不同的线要素进行综合需要结合相应条件约束的预处理。此外，该方法也不适用于较为特殊的线要素地物，如何能够更好地与不同地物的约束条件相结合，扩大该方法适用范围，有待于后续深入研究和不断完善。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Yan H W. Description approaches and automated generalization algorithms for groups of map objects[M]. Singapore: Springer Singapore, 2019.

[2]
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]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2):112-122.

DOI

[3]
Visvalingam M, Williamson P J. Simplification and generalization of large scale data for roads: A comparison of two filtering algorithms[J]. Cartography and Geographic Information Systems, 1995, 22(4):264-275.

[4]
武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10):1645-1664.

[ Wu F, Gong X Y, Du J W. Overview of the research progress in automated map generalization[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1645-1664. ] DOI:10.11947/j.AGCS.2017.20170287

DOI

[5]
Lawford G J. Fourier series and the cartographic line[J]. International Journal of Geographical Information Science, 2006, 20(1):31-52.

DOI

[6]
Boutoura C. Line generalization using spectral techniques[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1989, 26(3-4):33-48.

DOI

[7]
Fritsch E, Lagrange J P. Spectral representations of linear features for generalisation[C]//International Conference on Spatial Information Theory. Berlin: Springer, Heidelberg, 1995:157-171.

[8]
刘鹏程, 肖天元, 肖佳, 等. 曲线多尺度表达的Head-Tail信息量分割法[J]. 测绘学报, 2020, 49(7):921-933.

[ Liu P C, Xiao T Y, Xiao J, et al. A multi-scale representation method of polyline based on Head-Tail information break[J]. Acta Geodaeticaet Cartographica Sinica, 2020, 49(7):921-933. ] DOI:10.11947/j.AGCS.2020.20200004

DOI

[9]
刘鹏程, 艾廷华, 杨敏. 基于傅里叶级数的等高线网络渐进式传输模型[J]. 测绘学报, 2012, 41(2):284-290.

[ Liu P C, Ai T H, Yang M. The internet progressive transmission model for contour based on fourier series[J]. Acta Geodaeticaet Cartographica Sinica, 2012, 41(2):284-290. ] DOI:10.13203/j.whugis2013.02.017

DOI

[10]
肖天元, 刘鹏程, 艾廷华, 等. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报·信息科学版, 2020, 45(1):119-125.

[ Xiao T Y, Liu P C, Ai T H, et al. A fractal description and multiscale expression method of fourier information metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1):119125. ] DOI:10.13203/j.whugis20180336

DOI

[11]
刘鹏程, 艾廷华, 毕旭. 傅立叶级数支持下的等高线多尺度表达模型[J]. 武汉大学学报·信息科学版, 2013, 38(2):221-224.

[ Liu P C, Ai T H, Bi X. Multi-scale representation model for contour based on fourier serie[J]. Geomatics and Information Science of Wuhan University, 2013, 38(2):221-224. ] DOI:10.13203/j.whugis2013.02.017

DOI

[12]
刘鹏程, 罗静, 艾廷华, 李畅. 基于线要素综合的形状相似性评价模型[J]. 武汉大学学报·信息科学版, 2012, 37(1):114-117.

[ Liu P C, Luo J, Ai T H, LI C. Evaluation model for similarity based on curve generalizatio[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1):114-117. ] DOI:10.13203/j.whugis2012.01.025.

DOI

[13]
李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报·信息科学版, 2017, 42(8):1104-1109.

[ Li J Z, Zhang J M. 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

DOI

[14]
樊佳佳. 地图线要素自动综合并行计算方法研究[D]. 南京: 南京师范大学, 2011.

[ Fan J J. Study on parallel compytation methods of automated line feature generalization[D]. Nanjing: Nanjing Normal University, 2011. ]

[15]
Yan H W. Fundamental theories of spatial similarity relations in multi-scale map spaces[J]. Chinese Geographical Science, 2010, 20(1):18-22.

DOI

[16]
朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J]. 测绘学报, 2007(4):450-456.

[ Zhu K P, Wu F, W H L, et al. Improvement and assessment of Li-Openshaw algorithm[J]. Acta Geodaeticaet Cartographica Sinica, 2007(4):450-456. ] DOI:10.3321/j.issn:1001-1595.2007.04.015

DOI

[17]
王荣, 闫浩文, 禄小敏. Douglas-Peucker算法全自动化的多尺度空间相似关系方法[J]. 地球信息科学学报, 2021, 23(10):1767-1777.

DOI

[ Wang R, Yan H W, Lu X M. Automation of the Douglas-Peucker algorithm based on spatial similarity relations[J]. Journal of Geo-information Science, 2021, 23(10):1767-1777. ] DOI:10.12082/dqxxkx.2021.210016

DOI

Options
文章导航

/

〈 〉