局部最优形态参数的RBF分块地形插值方法与实验
|
摘要
径向基函数(Radial Basis Function,RBF)是一种不需对数据做任何假设,能准确逼近任意维度数据的空间插值方法。其特别适合于复杂地形的数字高程模型(Digital Elevation Model,DEM)插值重建,但随着已知点数量的增加会导致插值模型求解困难或缓慢。针对这个问题,本文基于二叉树自适应递归分块原理,采用局部最优形态参数的RBF分块插值方法进行DEM插值重建。首先,设定子区域最小点数阈值和相邻子区域的重叠率,自顶向下,对研究区域进行递归分块,构建区域分块二叉树,对二叉树叶子节点区域,采用逐点交叉验证(Leave One Out Cross Validation,LOOCV)方法求解其最优形态参数,建立局部RBF最优插值模型;然后,根据单元分解原理,采用加权平均方法对相应叶子节点区域内的待插值点高程进行加权求和,自底向上递归求解,得到待插值点最终高程值。以云南某地区DEM进行插值实验表明,采用本文方法进行DEM插值重建,稳定性较好,插值精度高。
As an accurate spatial interpolation method for data in arbitrary dimensions, Radial Basis Function(referred RBF), was particularly suitable for Digital Elevation Model(referred DEM) interpolation with respect to complex terrain that no assumption is needed for the experiment data. But the interpolation model would become difficult to solve when the number of points, whose elevation is already known, used to construct RBF interpolation model is too large. This is due to the reason that the inversed RBF interpolation matrix would become too huge or too slow to be solved. To address this issue, the hierarchical RBF interpolation method based on local optimal shape parameters, was proposed in this paper and the DEM was interpolated and reconstructed in the experiment. The interpolation procedure was described as follows: first, set the minimum point number in the tree node sub- regions of the study area and define the overlap rate between the adjacent child node sub- regions.Then, construct the regional binary tree recursively from top to bottom, that means the study area was firstly divided from a complete area into two small overlapped regions, and each region could be taken as the child nodes of the binary tree. Second, use the Leave One Out Cross Validation(referred LOOCV) method to calculate the optimal shape parameters in the leaf node regions of the binary tree. As the point distributions in each sub-region are different from each other, as well as the elevation properties, it would lead to different optimal shape parameters. Next, establish the optimal RBF interpolation model, i.e. calculate the linear combination coefficients for each RBF node in the interpolation model with the optimal shape parameter. Third, calculate the elevations of the unknown points in the leaf node regions and get the elevation values using the weighted average method according to the principle of Partition of Unity. The weight of the unknown point in the child node sub- region is calculated using the distance to the center point of the sub-region. Solve the interpolation problem from the bottom to the top recursively to get the final elevation values of the unknown points. Experiments was carried out by using the DEM in some area of Yunnan Province, and the results showed that RBF hierarchical interpolation method with local optimal shape parameters had good stability and high accuracy when DEM was reconstructed from random distributed spatial elevation points, thus it can be taken as an reliable interpolation method.
As an accurate spatial interpolation method for data in arbitrary dimensions, Radial Basis Function(referred RBF), was particularly suitable for Digital Elevation Model(referred DEM) interpolation with respect to complex terrain that no assumption is needed for the experiment data. But the interpolation model would become difficult to solve when the number of points, whose elevation is already known, used to construct RBF interpolation model is too large. This is due to the reason that the inversed RBF interpolation matrix would become too huge or too slow to be solved. To address this issue, the hierarchical RBF interpolation method based on local optimal shape parameters, was proposed in this paper and the DEM was interpolated and reconstructed in the experiment. The interpolation procedure was described as follows: first, set the minimum point number in the tree node sub- regions of the study area and define the overlap rate between the adjacent child node sub- regions.Then, construct the regional binary tree recursively from top to bottom, that means the study area was firstly divided from a complete area into two small overlapped regions, and each region could be taken as the child nodes of the binary tree. Second, use the Leave One Out Cross Validation(referred LOOCV) method to calculate the optimal shape parameters in the leaf node regions of the binary tree. As the point distributions in each sub-region are different from each other, as well as the elevation properties, it would lead to different optimal shape parameters. Next, establish the optimal RBF interpolation model, i.e. calculate the linear combination coefficients for each RBF node in the interpolation model with the optimal shape parameter. Third, calculate the elevations of the unknown points in the leaf node regions and get the elevation values using the weighted average method according to the principle of Partition of Unity. The weight of the unknown point in the child node sub- region is calculated using the distance to the center point of the sub-region. Solve the interpolation problem from the bottom to the top recursively to get the final elevation values of the unknown points. Experiments was carried out by using the DEM in some area of Yunnan Province, and the results showed that RBF hierarchical interpolation method with local optimal shape parameters had good stability and high accuracy when DEM was reconstructed from random distributed spatial elevation points, thus it can be taken as an reliable interpolation method.
引文
[1]李志林,朱庆.数字高程模型[M].武汉:武汉大学出版社,2001:125-139.
[2]汤国安,刘学军,闾国年.数字高程模型及地学分析的原理与方法[M].北京:科学出版社,2005:80-85.
[3]李新,程国栋,卢玲.空间内插方法比较[J].地球科学进展,2000,15(3):260-265.
[4]Li J,Heap A D.A Review of Spatial Interpolation Methods for Environmental Scientists[M].Canberra:Geoscience Australia,2008:10-13.
[5]汤国安,杨昕.Arc GIS地理信息系统空间分析实验教程[M].北京:科学出版社,2006:294-295.
[6]Franke R.Scattered data interpolation:tests of some methods[J].Mathematics of computation,1982,38(157):181-200.
[7]Wendland H.Scattered data approximation[M].Cambridge:Cambridge University Press,2005:119-120.
[8]Fasshauer G E.Meshfree approximation methods with MATLAB[M].Singapore:World Scientific,2007:17-19.
[9]Buhmann M D.Radial basis functions:theory and implementations[M].Cambridge:Cambridge University press,2003:11-29.
[10]Wendland H.Piecewise polynomial,positive definite and compactly supported radial functions of minimal degree[J].Advances in computational Mathematics,1995,4(1):389-396.
[11]Wu Z.Compactly supported positive definite radial functions[J].Advances in Computational Mathematics,1995,4(1):283-292.
[12]Wendland H.Fast evaluation of radial basis functions:Methods based on partition of unity[C].Approximation Theory X:Wavelets,Splines,and Applications,2002:473-483.
[13]Ohtake Y,Belyaev A,Alexa M,et al.Multi-level partition of unity implicits[C].ACM SIGGRAPH 2005 Courses.ACM,2005:173.
[14]Pouderoux J,Gonzato J C,Tobor I,et al.Adaptive hierarchical RBF interpolation for creating smooth digital elevation models[C].Proceedings of the 12th annual ACM international workshop on Geographic information systems.ACM,2004:232-240.
[15]Kansa E J,Carlson R E.Improved accuracy of multiquadric interpolation using variable shape parameters[J].Computers&Mathematics with Applications,1992,24(12):99-120.
[16]Fornberg B,Zuev J.The Runge phenomenon and spatially variable shape parameters in RBF interpolation[J].Computers&Mathematics with Applications,2007,54(3):379-398.
[17]Rippa S.An algorithm for selecting a good value for the parameter c in radial basis function interpolation[J].Advances in Computational Mathematics,1999,11(2-3):193-210.
[18]Fasshauer G E,Zhang J G.On choosing“optimal”shape parameters for RBF approximation[J].Numerical Algorithms,2007,45(1-4):345-368.
[19]Scheuerer M.An alternative procedure for selecting a good value for the parameter c in RBF-interpolation[J].Advances in Computational Mathematics,2011,34(1):105-126.
[20]吴宗敏.散乱数据拟合的模型、方法和理论[M].北京:科学出版社,2007:81-86.
[21]Hardy R L.Theory and applications of the multiquadricbiharmonic method 20 years of discovery 1968-1988[J].Computers&Mathematics with Applications,1990,19(8):163-208.
[2]汤国安,刘学军,闾国年.数字高程模型及地学分析的原理与方法[M].北京:科学出版社,2005:80-85.
[3]李新,程国栋,卢玲.空间内插方法比较[J].地球科学进展,2000,15(3):260-265.
[4]Li J,Heap A D.A Review of Spatial Interpolation Methods for Environmental Scientists[M].Canberra:Geoscience Australia,2008:10-13.
[5]汤国安,杨昕.Arc GIS地理信息系统空间分析实验教程[M].北京:科学出版社,2006:294-295.
[6]Franke R.Scattered data interpolation:tests of some methods[J].Mathematics of computation,1982,38(157):181-200.
[7]Wendland H.Scattered data approximation[M].Cambridge:Cambridge University Press,2005:119-120.
[8]Fasshauer G E.Meshfree approximation methods with MATLAB[M].Singapore:World Scientific,2007:17-19.
[9]Buhmann M D.Radial basis functions:theory and implementations[M].Cambridge:Cambridge University press,2003:11-29.
[10]Wendland H.Piecewise polynomial,positive definite and compactly supported radial functions of minimal degree[J].Advances in computational Mathematics,1995,4(1):389-396.
[11]Wu Z.Compactly supported positive definite radial functions[J].Advances in Computational Mathematics,1995,4(1):283-292.
[12]Wendland H.Fast evaluation of radial basis functions:Methods based on partition of unity[C].Approximation Theory X:Wavelets,Splines,and Applications,2002:473-483.
[13]Ohtake Y,Belyaev A,Alexa M,et al.Multi-level partition of unity implicits[C].ACM SIGGRAPH 2005 Courses.ACM,2005:173.
[14]Pouderoux J,Gonzato J C,Tobor I,et al.Adaptive hierarchical RBF interpolation for creating smooth digital elevation models[C].Proceedings of the 12th annual ACM international workshop on Geographic information systems.ACM,2004:232-240.
[15]Kansa E J,Carlson R E.Improved accuracy of multiquadric interpolation using variable shape parameters[J].Computers&Mathematics with Applications,1992,24(12):99-120.
[16]Fornberg B,Zuev J.The Runge phenomenon and spatially variable shape parameters in RBF interpolation[J].Computers&Mathematics with Applications,2007,54(3):379-398.
[17]Rippa S.An algorithm for selecting a good value for the parameter c in radial basis function interpolation[J].Advances in Computational Mathematics,1999,11(2-3):193-210.
[18]Fasshauer G E,Zhang J G.On choosing“optimal”shape parameters for RBF approximation[J].Numerical Algorithms,2007,45(1-4):345-368.
[19]Scheuerer M.An alternative procedure for selecting a good value for the parameter c in RBF-interpolation[J].Advances in Computational Mathematics,2011,34(1):105-126.
[20]吴宗敏.散乱数据拟合的模型、方法和理论[M].北京:科学出版社,2007:81-86.
[21]Hardy R L.Theory and applications of the multiquadricbiharmonic method 20 years of discovery 1968-1988[J].Computers&Mathematics with Applications,1990,19(8):163-208.