基于离散傅里叶变换的线要素节点压缩方法
何山(1998— ),男,甘肃兰州人,硕士生,主要从事地图综合研究。E-mail: 413940043@qq.com |
收稿日期: 2021-12-10
修回日期: 2022-03-02
网络出版日期: 2023-02-25
基金资助
国家自然科学基金项目(41930101)
青年科学基金项目(41801395)
Polyline Generalization Method based on Discrete Fourier Transform
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)
相较于传统删减顶点的线要素综合方法,基于傅里叶变换的线要素综合更能保留曲线的全局特征,但现有的傅里叶综合方法无法自动减少和控制点数,更多适用于曲线的平滑及多尺度表达。因此本文提出一种利用离散傅里叶变换进行线要素综合的方法。对曲线进行离散傅里叶变换,获得有限项傅里叶描述子;根据期望的压缩比对傅里叶描述子进行截断;根据截断后的描述子项进行离散傅里叶逆变换获得化简曲线。本文提出的这种傅里叶方法能够减少化简后曲线顶点数,适用于地图综合领域。本文通过四组实验验证了算法的可行性,展示其如下优点:① 能够在相应尺度上对线性地物进行平滑、渐进的化简和表达② 在现有傅里叶变换法的基础上能够保留曲线原顶点;③ 以顶点数作为综合过程参数,能够自动减少曲线顶点数;④ 相较于传统节点压缩方法,更注重整体形态的化简,在综合过程中能更好地保留曲线的整体特征;⑤ 在转换尺度较大的综合过程中,相较于传统节点压缩方法所保留的几何精度更高。
何山 , 闫浩文 , 李蓬勃 . 基于离散傅里叶变换的线要素节点压缩方法[J]. 地球信息科学学报, 2022 , 24(12) : 2309 -2321 . DOI: 10.12082/dqxxkx.2022.210795
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.
表1 截断法中傅里叶系数对应关系Tab. 1 correspondence of Fourier coefficients in paper method |
原曲线点集 | … | … | … | |||||||
---|---|---|---|---|---|---|---|---|---|---|
傅里叶系数 | … | … | … | |||||||
是否保留 | 保留 | 保留 | 保留 | 保留 | 保留 | 删除 | 保留 | 保留 | 保留 | 保留 |
还原后点集 | … | - | … |
表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 |
表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 | - |
表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 |
表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 |
表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 |
[1] |
|
[2] |
|
[3] |
|
[4] |
武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10):1645-1664.
[
|
[5] |
|
[6] |
|
[7] |
|
[8] |
刘鹏程, 肖天元, 肖佳, 等. 曲线多尺度表达的Head-Tail信息量分割法[J]. 测绘学报, 2020, 49(7):921-933.
[
|
[9] |
刘鹏程, 艾廷华, 杨敏. 基于傅里叶级数的等高线网络渐进式传输模型[J]. 测绘学报, 2012, 41(2):284-290.
[
|
[10] |
肖天元, 刘鹏程, 艾廷华, 等. 一种傅里叶信息度量的曲线分形描述与多尺度表达方法[J]. 武汉大学学报·信息科学版, 2020, 45(1):119-125.
[
|
[11] |
刘鹏程, 艾廷华, 毕旭. 傅立叶级数支持下的等高线多尺度表达模型[J]. 武汉大学学报·信息科学版, 2013, 38(2):221-224.
[
|
[12] |
刘鹏程, 罗静, 艾廷华, 李畅. 基于线要素综合的形状相似性评价模型[J]. 武汉大学学报·信息科学版, 2012, 37(1):114-117.
[
|
[13] |
李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报·信息科学版, 2017, 42(8):1104-1109.
[
|
[14] |
樊佳佳. 地图线要素自动综合并行计算方法研究[D]. 南京: 南京师范大学, 2011.
[
|
[15] |
|
[16] |
朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J]. 测绘学报, 2007(4):450-456.
[
|
[17] |
王荣, 闫浩文, 禄小敏. Douglas-Peucker算法全自动化的多尺度空间相似关系方法[J]. 地球信息科学学报, 2021, 23(10):1767-1777.
[
|
/
〈 |
|
〉 |