EN中文

Journal of Geo-information Science >

2022 , Vol. 24 >Issue 7: 1245 - 1253

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

A 3D Douglas-Peucker Terrain Simplification Algorithm Optimized Using Centroidal Voronoi Diagram

  • ZHANG Na ,
  • WANG Lei , * ,
  • YIN Nan
Expand
  • School of Surveying and Land Information Engineering, Henan Polytechnic University, Jiaozuo 454000, China
* WANG Lei, E-mail:

Received date: 2021-12-16

  Revised date: 2022-02-22

  Online published: 2022-09-25

Supported by

National Natural Science Foundation of China(41801318)

Key Research and Development Program of Henan Province(212102310432)

Young Backbone Teachers Funding Scheme of Henan Polytechnic University(2019XQG-03)

Doctoral Foundation of Henan Polytechnic University(B2017-14)

Fold

Abstract

The purpose of terrain simplification is to use the least effective terrain information to express multi-scale terrain, in order to solve the contradiction between massive terrain data and computer hardware and meet the needs of multi-scale terrain applications. Most of the existing terrain simplification algorithms can hardly take into account both the local detailed features and overall features of the terrain. In order to keep the main features of the terrain at different scales, it is necessary to select a suitable terrain simplification method to extract the structural feature information of the terrain. The traditional 3D Douglas-Peucker algorithm, which is a commonly used algorithm, simplifies terrain by setting distance threshold parameters. However, only main terrain features such as ridgelines and valley lines are retained, areas with obvious local terrain undulations have not been taken into consideration in the simplified terrain. The Centroidal Voronoi diagram, which is an important data structure, can use the terrain factor as the density function and drive the seed points to the areas with large terrain undulations through iteration, but it has deficiencies in the representation of major topographic features. To address these deficiencies, an optimized algorithm that combines the advantages of 3D Douglas-Peucker algorithm and centroidal Voronoi diagram is proposed in this paper. Firstly, overall terrain feature points, which form the main frame of the terrain, are extracted at different scale by changing the distance threshold parameters of traditional 3D Douglas-Peucker algorithm. Then, points with large local undulations that reflects local topographic undulations are acquired by setting terrain undulations as density function while generating centroidal Voronoi diagram using Lloyd’s algorithm. Also, different amount of seed points are set to satisfy the demand of different simplification level. Meanwhile, the proportion of the two types of feature points can be modified to fulfill different level of attention to the overall and local terrain information. Combining the overall terrain feature points obtained by the traditional 3D Douglas-Peucker algorithm with the points with large local undulations obtained by centroidal Voronoi diagram, the proposed algorithm simplifies terrain by considering both the main structural features and local undulations. Finally, comparison analysis is designed and conducted at different simplification levels. Results show that, compared with the traditional 3D Douglas-Peucker algorithm, the proposed algorithm that is optimized using centroidal Voronoi diagram approximates the original terrain better and has a higher accuracy of terrain representation. The optimized algorithm reduces the simplification error by more than 13.6% at each simplification level.

Key words： Douglas-Peucker algorithm; centroidal; Voronoi diagram; terrain simplification; feature point; multi-scale; degree of undulation; geographical features

Cite this article

ZHANG Na , WANG Lei , YIN Nan . A 3D Douglas-Peucker Terrain Simplification Algorithm Optimized Using Centroidal Voronoi Diagram[J]. Journal of Geo-information Science, 2022 , 24(7) : 1245 -1253 . DOI: 10.12082/dqxxkx.2020.210812

1 引言

地形简化的关键在于使用少量特征点,根据简化程度表达多尺度地形[1]。目前,国内外对于地形简化方面的研究有很多,使用的方法主要有3D Douglas-Peucker算法[2]、点舍弃法[3]、滤波法等[4],其中3D Douglas-Peucker算法应用较为广泛,该算法优势在于提取地形特征效率高、提取效果好,被广泛应用于矢量数据的压缩和等高线综合中[5⇓-7]。
Douglas-Peucker算法最初仅用在二维矢量的简化,如宗地界址点提取[8]、河网要素提取等[9-10],后由费立凡等在二维Douglas-Peucker算法原理实质的基础上,加入高程参与计算,拓展为三维Douglas-Peucker算法,利用基面替换基线,从点到线转换为点到面,实现了从二维到三维的地形简化,以山脊线、山谷线描述主要地形,通过对山脊线简化、山谷线简化、地形特征点的抽稀处理,得到多尺度 地形[11⇓⇓-14]。
然而,3D Douglas-Peucker算法仅考虑了地形整体特征,并没有考虑局部地形起伏[15-16],而质心Voronoi图能够提取位于地形起伏较大位置处的特征点,描述局部地形细节。因此,本文在原有3D Douglas-Peucker算法的基础上,利用质心Voronoi图的特点对算法进行优化,综合考虑整体特征及局部区域起伏对地形进行简化。

2 研究方法

2.1 Douglas-Peucker算法

Douglas-Peucker算法主要应用于二维、三维空间中线面矢量要素的简化处理。对于二维Douglas-Peucker算法,只涉及平面坐标,取2D道格拉斯曲线（图1）两端点作基线,计算曲线上其余特征点到基线的距离,设定阈值,保留能够代表曲线弯曲程度的点,不断增加新的基点生成新基线参与计算,通过递归,对位于基线两侧的点抽稀处理,达到简化的目的,如道路简化、河网简化等[17]。
图1 2D Douglas-Peucker曲线

Fig. 1 2D Douglas-Peucker curve

3D Douglas-Peucker曲线（图2）在三维空间内表达主要地形特征的主要思想是将山脊线、山谷线抽稀处理,根据阈值保留特征点。关键步骤为计算特征线上的点到基面OAB的距离,设定阈值,对特征点取舍,递归计算,通过添加新的基点和基面进行简化,从而得到多尺度DEM。
图2 3D Douglas-Peucker曲线

Fig. 2 3D Douglas-Peucker curve

2.2 质心Voronoi图

Voronoi图因其具有自然邻近、结构稳定等优点,被广泛运用到气象建模[18]、区域搜索等领域[19]。质心Voronoi是一种重要的几何结构,它相对于普通的Voronoi图具有更多优良特性,广泛应用于GIS、网格生成与优化、可视化等领域,质心 Voronoi图的生成算法主要有Lloyd算法[20]、MacQueen算法等[21]。
质心是几何图形的一个重要特征点,标准质心（匀质质心）的x和y坐标仅通过几何图形内所有点横纵坐标即可获得,如式（1）所示。
x - = ∑ i = 1 N x i N
式中：N为几何图形包含的栅格总数;i为栅格的编号; x ¯为质心横坐标。纵坐标y计算方法与横坐标相同,匀质质心Voronoi图如图3所示。
图3 普通Voronoi图与质心Voronoi图

注：图a圆圈为种子点,图b圆圈既是种子点又是质心。

Fig. 3 General Voronoi diagram and centroidal Voronoi diagram

非均质质心（加权质心）S可由式（2）计算。
S = ∑ i = 1 N y ρ ( y ) ∑ i = 1 N ρ ( y )
式中： ρ(y)为研究区域的密度函数,可根据实际问题进行选取,对于地形方面的研究权重可选用地形因子,如地形起伏度、坡度、曲率等。
根据质心Voronoi图的特点,在非均质的区域中,质心Voronoi图的种子点会向密度较大区域聚集[22⇓-24]。如选取地形起伏度作为密度函数,跟踪迭代过程中质心Voronoi图种子点的运动轨迹,结果表明种子点会向地形起伏较大区域聚集（图4）。因此利用这种方法,可以使种子点分布到地形起伏较大的区域。
图4 密度函数与加权质心Voronoi图

Fig. 4 Density function with weighted centroidal Voronoi diagram

2.3 基于质心Voronoi图的3D Douglas-Peucker 算法优化

地形简化的目的是简化后保留一定的必要地形特征,保证地形轮廓接近真实地形。本文在利用3D Douglas-Peucker算法提取地形特征点同时,利用质心Voronoi图获取地形起伏较大区域的特征点,综合考虑整体特征及局部起伏特征简化地形。

2.3.1 基于3D Douglas-Peucker算法的地形特征提取

利用3D Douglas-Peucker算法提取地形的特征点,并将其与原始地形的山脊线、山谷线叠加,结果表明简化得到的点主要分布在山脊线、山谷线上（图5）,这与该算法的特点相符。
图5 3D Douglas-Peucker算法简化后的点位分布

注：分辨率为5 m,数据像素大小为800×800。

Fig. 5 Simplified point distribution of 3D Douglas-Peucker algorithm

2.3.2 基于质心Voronoi图的局部地形细节提取

将地形因子作为密度生成质心Voronoi图,可以使种子点分布到相应因子较大的区域,提取局部地形细节特征。可作为密度函数的地形因子有很多,如坡度、地形起伏度、高程变异系数等。起伏度是地形描述中最常用的参数之一,能快速、直观地反映地势起伏特征。地形起伏度可将地形进一步划分为台地、丘陵、小起伏山地、中起伏山地和大起伏山地等类型,基本地貌类型就是由海拔和起伏度2个指标确定的形态类型,它是遥感解译划分更详细地貌类型的基础[25]。为保证良好的地形模拟效果,本文通过实验对比,选取地形起伏度（图6）作为密度函数来生成质心Voronoi图。
图6 地形起伏度

注：分辨率为5 m,数据像素大小为800×800。

Fig. 6 Topographic Relief

某点的地形起伏度由其邻近格网间的最大高差决定,计算公式如式（3）所示。
h x = m a x h 1 , h 2 , ⋯ , h n - m i n h 1 , h 2 , ⋯ , h n
式中：n代表邻域格网数量; h x为该点处的地形起伏度。
以地形起伏度作为密度函数,利用式（2）计算区域质心,通过Lloyd算法迭代计算,直至迭代达到指定次数或者种子点与新生成的质心坐标之间距离在一定阈值范围内,即可生成基于地形起伏度的质心Voronoi图。将Voronoi区域种子点与河网叠加,可以发现种子点大多分布在地形起伏较大的区域,平坦区域点数较少,避免了数据冗余（图7）。利用质心Voronoi图提取的地形特征点分布于地形起伏较大的区域,却未体现山脊线、山谷线、鞍部等重要地形特征。
图7 质心Voronoi图及种子点与河网叠加

Fig. 7 Centroidal Voronoi diagram and overlay of seed points and river network

2.3.3 两类特征点组合优化

为使简化后的地形能够兼顾地形主要特征及局部地形起伏,本文对利用3D Douglas-Peucker算法提取的地形特征点及利用质心Voronoi图提取的地形起伏较大区域的点进行组合,综合考虑整体及局部两类因素对地形进行简化,如图8所示。
图8 本文优化算法流程

Fig. 8 Optimize the algorithm process

3 实验与分析

本文选取的实验数据如图9所示,DEM数据的分辨率为5 m,数据像素大小为800×800[26]。
图9 原始DEM

Fig. 9 Original DEM

3.1 简化效果定性对比

实验通过控制特征点的数量达到多尺度地形简化的目的。总的地形特征点由3D Douglas-Peucker算法和质心Voronoi图提取的相同数量的地形特征点组合得到,将得到的特征点与提取的河网、山脊线叠加（图10）,可以看出优化后的算法提取的地形特征点兼顾整体特征与局部地形起伏,在主要地形特征线及地形起伏较大区域均保留了较多的地形特征点。
图10 本文优化算法地形特征点与河网、山脊线叠加

注：分辨率为5 m,数据像素大小为800×800。

Fig. 10 Optimization algorithm terrain feature points overlaid with river network and ridgelines

将DEM简化前后提取的山脊线及河网进行叠加,可以看出简化后地形提取的山脊线及河网虽与简化前有一定差别,但能够保留地形的基本骨架信息（图11）;相对于传统3D Douglas-Peucker算法,本文优化算法得到的地形提取的河网除保留地形基本骨架信息外,在细节的表达上也更具优势。如图12所示,传统算法仅保留了主干河流,而本文优化算法在相同的简化级别下保留主干河流的同时,也保留了部分支流,与原始DEM提取的河网具有更高的重叠度,说明本文优化算法可以兼顾地形总体特征及局部细节特征。
图11 DEM简化前后提取的山脊线叠加

注：分辨率为5 m,数据像素大小为800×800。

Fig. 11 Overlay of ridgelines extracted before and after DEM simplification

图12 DEM简化前后提取的河网叠加

注：分辨率为5 m,数据像素大小为800×800。

Fig. 12 Overlay of river network extracted before and after DEM simplification

3.2 简化误差定量分析

为进一步验证本文优化算法的精度,分别使用3D Douglas-Peucker算法和本文优化算法对地形进行简化,并利用简化后的点重构DEM,将2种算法重构得到的DEM与原始DEM数据进行比较,由式（4）计算高程中误差 σ。
σ = ∑ i = 1 N H i - h i 2 N × N
式中： H为原始DEM高程值; h为简化后DEM的高程值。N为几何图形包含的栅格总数;i为栅格的编号。
首先设定不同的简化级别（保留点数）,然后利用式（4）分别计算原始算法和本文优化算法的高程中误差,结果如表1和图13所示。可以看出,随点数的增加,2种算法的精度均呈上升趋势,且本文优化算法相对于原始算法具有更高的精度。
表1 本文优化算法与3D Douglas-Peucker算法高程中误差对比

Tab. 1 Comparison of the optimization algorithm with the 3D Douglas-Peucker algorithm for elevation mid-error

点数/个
300 600 900 1200 1500 1800 2100 2400
高程中误差/m 本文优化算法 23.95 20.91 17.73 17.19 14.98 14.57 13.80 13.08
3D-DP算法 27.71 25.12 22.36 21.82 19.57 18.12 16.82 16.18
误差降低/% 13.60 16.80 20.70 21.20 23.50 19.60 18.00 19.20
图13 本文优化算法与3D Douglas-Peucker算法高程中误差对比

Fig. 13 Comparison of the error in elevation between the algorithm in this paper and the 3D Douglas-Peucker algorithm

4 结论与展望

本文针对传统3D Douglas-Peucker算法在地形简化时只保留主要特征线、局部细节缺失的问题,利用质心Voronoi图获取局部起伏较大的特征点,综合考虑整体与局部特征简化地形,弥补了原算法在地形细节表达方面的不足,实验结果表明：
（1）优化后的算法能够保留山脊线、山谷线地形整体特征及局部地形细节特征。
（2）在相同的简化级别下,优化算法相对于传统3D Douglas-Peucker算法具有更高的地形简化精度。
为兼顾整体与局部特征,本文将传统3D Douglas-Peucker算法获取的整体地形特征点与通过质心Voronoi图获取的局部起伏较大的点进行组合,两类特征点的比例也会对简化结果产生一定的影响,需根据地形的复杂度及对地形细节的关注程度来确定两类特征点的数量比例,本文按1：1的比例取两类特征点,后续研究将进一步考虑两类特征点的比例对简化效果的影响。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Xie X, Xu W P, Zhu Q, et al. Integration method of TINs and Grids for multi-resolution surface modeling[J]. Geo-spatial information science, 2013, 16(1):61-68. DOI: 10.1080/10095020.2013.774109

DOI

[2]
徐勇, 马燕, 康建成. 基于轮廓草图的三维地形建模方法研究[J]. 计算机应用与软件, 2016, 33(3):126-128.

[ Xu Y, Ma Y, Kang J C, et al. Research on contour sketch-based 3D terrain modelling method[J]. Computer Applications and Software, 2016, 33(3):126-128. ] DOI: 10.3969/j.issn.1000-386x.2016.03.028

DOI

[3]
张倩宁. 基于地形复杂度的LiDAR点云简化方法研究[D]. 成都: 西南交通大学, 2016.

[ Zhang Q N. A new simplification method based on terrain complexity for LiDAR point cloud[D]. Cheng du: Southwest Jiaotong University, 2016. ]

[4]
丁少鹏, 刘如飞, 蔡永宁, 等. 一种顾及地形的点云自适应坡度滤波方法[J]. 遥感信息, 2019, 34(4):108-113.

[ Ding S P, Liu R F, Cai Y N, et al. A point cloud adaptive slope filtering method considering terrain[J]. Remote Sensing Information, 2019, 34(4):108-113. ] DOI: CNKI:SUN:Y GXX.0.2019-04-017

DOI

[5]
高远. 基于Douglas-Peucker算法的等高线自动综合研究[D]. 福州: 福州大学, 2011.

[ Gao Y. Study of contour generalization based on Douglas-Peucker algorithm[D]. Fuzhou: Fuzhou University, 2011. ]

[6]
何津, 费立凡, 黄丽娜, 等. 三维Douglas-Peucker算法的等高线间接综合方法研究[J]. 测绘学报, 2013, 42(3):467-473.

[ He J, Fei L F, Huang L N, et al. Study on the method of indirect generalization for contour lines based on the 3D Douglas-Peucker algorithm[J]. Acta Gcodaetica et Cartographica Sinica, 2013, 42(3):467-473.] DOI: CNKI:SUN:CHXB.0.2013-03-024

DOI

[7]
Wang P, Liu X, Fei L. The integration of water and soil based on three-in-one 3D D-P algorithm[J]. IOP conference series. Materials Science and Engineering, 2019, 490(6):62008. DOI: 10.1088/1757-899X/490/6/062008

DOI

[8]
李磊, 李正品, 李曦凌. 宗地界址点自动化提取算法研究[J]. 测绘地理信息, 2018, 43(2):90-92, 96.

[ Lei L I, Zhengpin L I, Xiling L I. Automatic extraction algorithm of cadastral parcel boundary points[J]. Journal of Geomatics, 2018, 43(2):90-92, 96. ] DOI: 10.14188/j.2095-6045.2016139

DOI

[9]
窦世卿, 赵学胜, 刘成军, 等. 河网线要素与DEM综合的三维Douglas-Peucker算法[J]. 测绘学报, 2016, 45(4):450-457.

[ Dou S Q, Zhao X S, Liu C J, et al. The three dimensional Douglas-Peucker algorithm for generalization between river network line element and DEM[J]. Acta Gcodaetica et Cartographica Sinica, 2016, 45(4):450-457. ] DOI: 10.11947/j.AGCS.2016.20140584

DOI

[10]
于靖, 陈刚, 张笑, 等. 面向自然岸线抽稀的改进道格拉斯—普克算法[J]. 测绘科学, 2015, 40(4):23-27.

[ Yu J, Chen G, Zhang X, et al. An improved Douglas-Peucker algorithm oriented to natural shoreline simplification[J]. Science of Surveying and Mapping, 2015, 40(4):23-27. ] DOI: 10.16251/j.cnki.1009-2307.2015.04.006

DOI

[11]
费立凡, 何津, 马晨燕, 等. 3维Douglas-Peucker算法及其在DEM自动综合中的应用研究[J]. 测绘学报, 2006, 35(3):278-284.

[ He J, Ma C Y, et al. Three Dimensional Douglas-Peucker Algorithm and the Study of Its Application to Automated Generalization of DEM[J]. Acta Geodatica et Cartographica Sinica, 2006, 35(3):278-284. ] DOI: 10.3321/j.issn:1001-1595.2006.03.016

DOI

[12]
何津, 费立凡. 再论三维Douglas-Peucker算法及其在DEM综合中的应用[J]. 武汉大学学报·信息科学版, 2008, 33(2):160-163.

[ He J, Fei L F. Further study on three dimensional Douglas-Peucker algorithm and its application to generalization of DEM[J]. Geomatics and Information Science of Wuhan University, 2008, 33(2):160-163. ] DOI: CNKI:SUN:WHCH.0.2008-02-014

DOI

[13]
黄丽娜, 费立凡. 采用3D D-P算法的等高线三维综合实验研究[J]. 武汉大学学报·信息科学版, 2010, 35(1):55-58.

[ Huang L N, Fei L F. Experimental investigation on the three dimension generalization of contour lines using 3D D-P algorithm[J]. Geomatics and Information Science of Wuhan University, 2010, 35(1):55-58. ] DOI: 10.13203/j.whugis2010.01.012

DOI

[14]
张俊峰, 费立凡, 黄丽娜, 等. 利用3D_DP和Quad_TIN的地形实时动态显示算法研究[J]. 武汉大学学报·信息科学版, 2011, 36(3):346-350.

[ Zhang J F, Fei L F, Huang L N, et al. Real time dynamic rendering algorithm of terrain using 3D_DP method and Quad_TIN model[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3):346-350. ] DOI: 10.13203/j.whugis2011.03.024

DOI

[15]
王维. 基于Douglas-Peucker的全局性地形综合简化算法研究[D]. 武汉: 湖北大学, 2014.

[ Wang W. Study on comprehensive simplified algorithm of global terrain based on Douglas-Peucker[D]. Wuhan: Hubei University, 2014. ]

[16]
朱雪坚, 叶远智, 汤国安. 运用三维Douglas-Peucker算法提取DEM地形特征[J]. 测绘通报, 2014(3):118-121.

[ Zhu X J, Ye Y Z, Tang G A. Three dimensional Douglas-Peucker algorithm based extraction of topographical features from DEM[J]. Bulletin of Surveying and Mapping, 2014(3):118-121.]DOI: 10.13474/j.cnki.11-2246.2014.0105

DOI

[17]
郑先伟. 顾及地形特征的全球多尺度TIN自动构建及快速可视化[D]. 武汉: 武汉大学, 2015.

[ Zheng X W. Multi-scale morphology-preserved TIN surface modeling and visualization for virtual globe[D]. Wuhan: Wuhan University, 2015. ]

[18]
Ringler T, Ju L, Gunzburger M. A multiresolution method for climate system modeling: Application of spherical centroidal Voronoi tessellations[J]. Ocean Dynamics, 2008, 58(5-6):475-498. DOI: 10.1007/s10236-008-0157-2

DOI

[19]
陈桂珍, 季鹏磊, 龚声蓉. 基于质心化的Voronoi划分图像分割算法在交通视频中的车辆检测研究[J]. 机械设计与制造, 2016(9):269-272.

[ Chen G R, Ji P L, Gong S R. Vehicle detection research in traffic video based on centroid Voronoi tessellation image segmentation algorithm[J]. Machinery Design and Manufacture, 2016,(9):269-272. ] DOI: 10.19356/j.cnki.1001-3997.2016.09.070

DOI

[20]
Lloyd S. Least squares quantization in PCM[J]. IEEE transactions on information theory, 1982, 28(2):129-137. DOI: 10.1109/TIT.1982.1056489

DOI

[21]
J. M. Some methods for classification and analysis of multivariate observations[J]. Berkeley Symposium on Mathematical Statistics and Probability, 1967.

[22]
宋占杰, 张美, 何改云, 等. 基于质心Voronoi结构的自由曲面布点策略[J]. 吉林大学学报(工学版), 2013, 43(1):34-38.

[ Song Z J, Zhang M, He G Y, et al. Sculptured surface point distribution strategy based on centroidal Voronoi tesssellation[J]. Journal of Jilin University(Engineering and Technology Edition), 43(1):34-38. ] DOI: 10.13229/j.cnki.jdxbgxb2013.01.034

DOI

[23]
冀翠莲, 周慎杰, 田蕴, 等. 基于质心Voronoi结构的布点算法及应用[J]. 机械工程学报, 2008(1):168-172.

[ Ji C L, Zhou S J, Tian Y, et al. Node placement algorithm and application based on the centroidal Voronoi tessellation[J]. Chinese Journal of Mechanical Engineering, 2008,(1):168-172. ] DOI: 10.3321/j.issn:0577-6686.2008.01.029

DOI

[24]
刘盛恩, 陈向宁, 王得成. 基于质心Voronoi图重构的UDSM边折叠简化[J]. 应用光学, 2020, 41(1):127-133.

[ Liu S N, Chen X N, Wang D Z. Edge collapse of UDSM based on centroidal Voronoi diagram reconstruction[J]. Journal of Applied Optics, 2020, 41(1):127-133. ] DOI: CNKI:SUN:YYGX.0.2020-01-022

DOI

[25]
郎玲玲, 程维明, 朱启疆, 等. 多尺度DEM提取地势起伏度的对比分析——以福建低山丘陵区为例[J]. 地球信息科学, 2007, 9(6):1-6.

[ Lang L L, Cheng W M, Zhu Q J, et al. A comparative a-nalysis of the multi-criteria DEM extracted relief: Taking Fujian low mountainous region as an example[J]. Geo-information Science, 2007, 9(6):1-6,135-136. ] DOI: 10.3969/j.issn.1560-8999.2007.06.001

DOI

[26]
中科图新_全国5米地形OEM[EB/OL]. 2022. http://www.tuxingis.com/resource/dem_5_down-load.html.

Options
Outlines

/

〈 〉