基于KD树的规则格网DEM插值技术

Grid DEM Interpolation Technology Based on KD Tree

插值是规则格网DEM生产的重要环节。通常插值算法首先需要获取待插值点的若干邻域采样点，然后由邻域采样点通过某种内插算法获取待插值点的高程值。邻域采样点的快速获取和高精度的内插算法是点云插值的关键。本文针对当前密集匹配并滤波后生成的点云数据，围绕邻域点的快速获取，在分析传统栅格法索引的基础上，引入KD树实现了邻域点的快速获取，并通过反距离加权插值算法完成了DEM插值。试验结果表明，在保证邻域点检索正确率的前提下，基于KD树的索引效率更优。

Interpolation is an important part of grid DEM production. Usually the interpolation algorithm requires several neighboring sampling points of interpolation points at first, and then the elevation values of interpolated points are acquired through interpolation of neighborhood sampling points. Therefore, the rapid acquisition of neighboring sampling points and high- precision interpolation algorithm are the key factors of point cloud interpolation. To acquire neighbouring points rapidly, point cloud data obtained by dense matching and filtering are used, KD tree is introduced on the basis of traditional grid index analysis, and DEM interpolation is completed using the inverse distance weighted interpolation algorithm. The test results show that the in- dex efficiency based on KD tree is better on condition that the accuracy of neighborhood point retrieval is ensured.