2015 , Vol. 17 >Issue 3: 260 - 267

Orginal Article

A Hierarchical RBF Interpolation Method Based on Local Optimal Shape Parameters

• LV Haiyang , 1 ,
• SHENG Yehua , 1, * ,
• DUAN Ping 1 ,
• ZHANG Siyang 1 ,
• LI Jia 2
Expand
• 1. Key Laboratory of Virtual Geographical Environment, Ministry of Education, Nanjing Normal University, Nanjing 210023, China
• 2. College of Tourism and Geographical Sciences, Yunnan Normal University, Kunming 650500, China
*Corresponding author: SHENG Yehua, E-mail:

Request revised date: 2014-05-20

Online published: 2015-03-10

《地球信息科学学报》编辑部 所有

### Abstract

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.

LV Haiyang , SHENG Yehua , DUAN Ping , ZHANG Siyang , LI Jia . A Hierarchical RBF Interpolation Method Based on Local Optimal Shape Parameters[J]. Journal of Geo-information Science, 2015 , 17(3) : 260 -267 .

### 2 自适应分块插值与RBF最优形态参数

#### 2.1 自适应分块插值

2.1.1 自适应分块

l层至第l+1层点集分块规则如下：
（1）计算区域内点集外包矩形RecΩ信息,如果矩形沿着x轴方向的边长大于沿着y轴方向的边长,则将点集依x坐标进行排序,反之亦然;
（2）计算l+1层叶子节点的重叠点数为 $n q l + 1 = q n 1$ ,得到子区域 $Ω 1 l + 1$ 中最后1个点序号为 $n 1 l + 1 = n l + n q l + 1 2$ ,子区域 $Ω 2 l + 1$ 中第1个点序号为 $n 2 l + 1 = n l - n q l + 1 2$ ;
（3）将第1个点至第nl+1个点作为点集 $P 1 l + 1$ ,第nl+1+1个点至第nl个点作为点集 $P 2 l + 1$

IF区域点数小于阈值nmin

END

2.1.2 区域插值

$V ( d ) = 2 d 3 - 3 d 2 + 1$ （1）

$ν p = VoD ( p )$ （3）

##### Fig. 1 Weight change in leaf area

$f P 2 = λ l f P l + λ r f P r$ （4）
##### Fig. 2 Interpolation process for the unknown point

IF Node为叶子节点区域

ELSE
（插值结果 $f P l$ ,相邻子节点权重 $ν l$ ）= Interpolation（X0,相邻子节点Nodel）;
（插值结果 $f P r$ ,相邻子节点权重 $ν r$ ）= Interpolation（X0,相邻子节点Noder）;

END

#### 2.2 RBF最优形态参数求解

RBF插值模型十分简洁,设多维空间中包含n个已知点,使用向量xi表示第i个已知点,则径向基函数插值模型[9,20]可以表示为：
$F ( x ) = ∑ i = 1 n c i φ ( x - x i 2 )$ （5）

###### Tab. 1 Some RBF basis functions

Gaussians $φ(r)=e-r22α2$
Multiquadric $φ(r)=α2+r2$
Inverse Multiquadric $φ(r)=1α2+r2$
Thin Plate Spline $φ(r)=αr2lnαr$
 注：α为形态参数,控制基函数的平滑程度,r为待插值点与已知点之间的径向距（2-范数）

$f ˜ ( x i ( i ) ) - y i = c i Φ ii - 1$ （6）
ci为使用全部已知点进行RBF插值模型求解,得到第i个已知点处的基函数线性组合系数; $Φ ii - 1$ 为使用全部点集进行RBF模型求解,得到插值矩阵的逆矩阵第i个对角线元素值。因此,最优形态参数求解过程的伪代码表示如下：

FOR $α i ∈ p , q$

END
αoptimal=min(LOOCV(α));

### 3 RBF插值实验分析

#### 3.1 实验数据与插值

##### Fig. 3 The study area

###### Tab.2 Topographic factors statistics in study area

1245 2585 2010 252 24.5

#### 3.2 实验结果与分析

##### Fig. 6 The local enlarged view of the original DEM and interpolation results

###### Tab. 3 Error statistic of different interpolation methods (m)

IDW 137.4158 7.2966×10-4 19.0169 25.4318
CSRBF 302.3613 1.6825×10-4 9.7419 16.5656
Pouderoux方法 139.1777 3.9567×10-5 9.7295 13.6998

### 4 结论

RBF插值方法作为一种精确的插值方法,能适用于任意维度的空间插值,但随着已知点的增加,RBF全局插值方法插值矩阵求逆困难,限制了该方法的适用范围。本文基于单元分解原理,采用二叉树分块的方式对研究区域进行自适应分块,LOOCV方法求解子区域局部最优形态参数,构建RBF局部插值模型,对研究区域进行DEM递归插值重建。与IDW、CSRBF、Pouderoux方法进行比较和分析表明,本文方法精度高,插值结果可靠,是一种有效可行的空间插值方法。

The authors have declared that no competing interests exist.

 [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] 汤国安,杨昕. ArcGIS 地理信息系统空间分析实验教程[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 multiquadric-biharmonic method 20 years of discovery 1968-1988[J]. Computers & Mathematics with Applications, 1990,19(8):163-208.
Options
Outlines

/

 〈 〉