平面散乱数据一种渐近正定径向基函数插值与拟插值研究

徐应祥,薛鹏翔

(1.中山大学 新华学院,广东 广州 510520；2.西安工业大学 理学院,陕西 西安 710021)

平面散乱数据一种渐近正定径向基函数插值与拟插值研究

徐应祥1,薛鹏翔2

(1.中山大学 新华学院,广东 广州 510520；2.西安工业大学 理学院,陕西 西安 710021)

结合一元B样条和已有径向基函数的优点,提出了一种渐近正定径向基函数,并将其应用于平面散乱数据逼近,得到了一种新的插值格式和拟插值方法。数值例子表明,这种插值格式与拟插值方法对平面散乱数据均具有良好的逼近效果。

散乱数据;渐近正定;插值;拟插值

0 引言

散乱数据点是指那些不能位于正规网格上的数据点。散乱数据拟合在汽车外形设计、船体放样、飞机机翼机身设计、服装设计、地质探矿、数据压缩、医学图形图像处理、模式识别等许多领域中都有广泛的应用[1-3]。将散乱数据拟合方法推向更高维空间乃至在点云数据三维曲面重建等方面也有了很多热烈的讨论[4-5]。从20世纪60年代以来,众多的科技工作者对散乱数据曲面拟合问题进行了一系列的研究[6-10]。近些年来,尽管Lai,吴宗敏等学者对散乱数据拟合方法有了一系列总结性的工作[11-16],但是对多元散乱数据与大规模散乱数据插值问题的解决仍不够理想。

为改进散乱数据插值方法,关履泰、徐应祥等人提出了带自然边界样条多元多项式样条插值方法[17-21],这种插值方法具有可以推广到任意维多元散乱数据插值,其基函数有紧凑的显示表示式,且是分片多项式的优点,但缺点是不具紧支性,这使得插值问题求解时因其系数矩阵不具有稀疏性而求解效率较低,并对大规模散乱数据插值时须进行分块插值。

另一种常用的散乱数据插值方法是径向基函数插值,其理论和方法已相当成熟。径向基函数插值的优点是可以构造局部基,插值矩阵较为稀疏,计算量相对较少。但也存在一些不足,主要表现在:具有紧支撑的局部基的构造依赖于一个整体截断多项式,为实现相应的连续性,一般要求截断多项式有较高的次数,如在2维空间中要求C2连续时,截断多项式的次数至少要是4次的。而容易满足连续性要求的径向基函数却一般不具有紧支撑性质,如薄板样条函数等,而且这样的径向基函数大多是非多项式型的。

由于一元B样条具有诸多良好的性质,如光滑性,紧支性,是分段多项式。能否将其优点与径向基函数结合,得到新的兼有样条与原有径向基函数共同优点的新插值基函数,在一定程度上弥补以前径向基函数的不足,也是值得研究的。尽管插值函数有经过插值点且误差一般较小的优点,但为得到插值函数往往需要解较高阶数的线性方程组,而拟插值函数的构造过程不需要解方程。相对于插值,拟插值不要求逼近函数经过插值点,在求解时也不需要解方程组,构造也相对容易一些。对于一元函数拟插值的研究已有相当丰富的成果,但是对于多元散乱数据拟插值的研究相对较少,其理论和方法相对还不完善[22-23]。因此,基于以上想法,本文提出了一种基于渐近正定径向基函数的新插值格式并构造了一种新的散乱数据拟插值函方法。

1 一类渐近正定径向基函数

设x3=Bk(x1)是三维空间直角坐标系O-x1x2x3中x1Ox3平面内的k次B样条,则满足如下性质:

(1)对称性与连续性:Bk(-x1)=Bk(x1),Bk∈Ck-1.

将x3=Bk(x1)绕x3轴旋转一周,可得二元函数

(1)

其中c>0为待选参数,则有

定理1φk,c具有如下的性质:

(2)连续性:φk,c(r)∈Ck-1.

其中ω=(ω1,ω2)∈R2.

证明(1)由一元B样条zk=Bk(x)的非负性与紧支性,显然。

进一步，由单调性可知当r=0时,φk,c(r)最大,最大值为

(4) 由φk,c(r)的构造可知

2 散乱数据渐近正定径向基插值与拟插值

给定平面区域Ω中包含N个两两不同的散乱数据点的集合X={x1,x2,…,xN}与相应每个散乱点处的值为fi(i=1,…,N),其中xi=(x1i,x2i)∈R2(i=1,2,…,N).

(Ⅰ)渐近正定径向基插值

再由定理1性质(1)-(3)可知,φ2m+1,c(r)具有优良的光滑性和紧支性,其可以作为基函数构造插值函数。下面是几个φ3,c(r)的图形:

Fig.1 Some figures of φ3,c(r)图1 几个φ3,c(r)的图形

由定理1,若选择了合适的c后φ2m+1,c(r)是正定的,则可以正定函数φ2m+1,c(r)为基函数构造如下的插值函数

‖x-xk‖),

(2)

使其满足如下的插值条件

(3)

其中Ck是待定的插值系数,h是可选参数(关于这一点在后文总结中予以进一步说明)。

令A=(aij),F=(f1,f2,…,fN)T,C=(C1,C2,…,CN)T,其中aij=φ2m+1,c(h-1‖xi-xj‖),i,j=1,…,N,则(2)可改写为

AC=F

(4)

解(3)便可得插值系数C。

定理2 存在正数δ,使当c∈(0,δ)时,插值函数(2)是存在唯一的。

插值函数(2)的插值误差可仿文献[16]第11章中的误差估计方法进行估计,这里不再赘述。

(Ⅱ)一类新的拟插值

对任意的正整数k由定理1可知φk,c(r)≥0且是紧支撑的。于是构造如下的拟插值函数

(5)

其中α是一个正的可选参数,‖·‖为R2上的欧氏距离。

证明对常值函数f(x)=C有fi=C(i=1,2,…,N),因此由引理1有

定理3 对于选定α>0,设f(x)∈C(Ω),则对拟插值函数(5)有如下的估计式

证明由引理1及φk,c的非负性

3 插值与拟插值的数值例子

(Ⅰ)渐近正定径向基插值数值例子

例1 取测试函数为如下的Frank函数

Fig.2 Interpolated results for N=50图2 N=50时的插值结果

表1 N=50时的误差Table 1 Error for N=50

(Ⅱ)拟插值数值例子

例2 取测试函数为

f(x)=-0.5xcos(x+y2+1)-0.5(y+1)sin(2x2-y),

Fig.3 Quasi-interpolated results for N=50图3 N=50时的拟插值结果

表2 N=50时拟插值误差Table 2 Quasi-interpolated error for N=50

Fig.4 Quasi-interpolated results for N=500图4 N=500时的拟插值结果

表3 h=10时误差Table 3 Error for N=500

4 总结与进一步分析

本文构造了一类新的渐近正定径向基函数φk,c(r),并将其应用于构造平面散乱数据的一种插值与拟插值,定理1可知其优点在于:

(1)φk,c(r)是紧支撑的,且具有显式表达式;

(2)φk,c(r)具有k-1阶连续的导数,故在应用中容易满足连续性的要求;

(3)由紧支性可知,将φk,c(r)用作插值基时,插值系数矩阵的稀疏性较好,能够提高求解效率。

(4)由于φk,c(r)≥0具有非负性且是紧支撑的,故用其构造拟插值函数的基函数时能够保证基函数也是非负的,而且也是具有紧支撑性,这使得这样构造的拟插值可以较容易地推广到大规模散乱数据拟合。

(Ⅰ)插值结果的总结与进一步分析

从数值例1中的插值果可以看出:

(1)只要选定h,c就可使插值效果良好;

(2)当c变小时,插值结果会变得不好,这是因为当c变小时,基函数就像图1(c)中的所示,尽管基函数的支集不变,但其整个曲面变得又细又尖,从而使整个插值曲面呈现气泡效应。这种情况只要将h变大,便可使得插值结果得到改善。由此可知,h的选择会直接影响到插值结果,这也是前文中将h视为可选参数的原因。

如将h扩大,取h=10,则插值结果如图5,最大误差和平均误差如表4。显然较之前图2与表1中的插值结果已大为改善。通过多次数值实验验证,建议在选定c后,h的选择应使得插值函数中的每个基函数φ2m+1,c(h-1‖x-xk‖|)的支集中至少包含两个以上的插值点为好。

Fig.5 Interpolated results for h=10图5 h=10的插值结果

表4 h=10时误差Table 4 Error for N=50

(Ⅱ)拟插值结果总结与进一步分析

从数值例2中拟插值果可以看出:

(1)这种新的拟插值的构造仅依赖于散乱数据点的分布,而不依赖于区域Ω的形状,构造过程较为简单,而且拟插值效果良好;

(2)由表3中的误差也可以看出,当散乱数据点确定,并选定了α,则在选取不同的c时,拟插值的误差变化很小(这一点也从图4中(b)-(d)的拟插值曲面与误差曲面图形几乎一样也能证明),这使得拟插值基函数对c的依赖不明显,所以c的选取比较灵活。

再由定理3,若被插函数f(x)在Ω上连续时,增加散乱数据点的数量,会使插值结果会变得更好。下面就例2中的测试函数,给出了散乱数据点数增加到1 500,3 000及5 000时的几种拟插值结果。插值结果如图6,最大误差和平均误差如表5。显然图6与表5中的插值结果证明了当散乱数据点增加时,拟插值结果也会变得更好,这也说明这种新的拟插值格式可以向大规模散乱数据推广。

Fig.6 Quasi-interpolated results图6 拟插值结果

表5 误差表Table 5 Error table

[1] Andrew R Webb.统计模式识别[M].王萍,杨培龙,罗颖昕,译.2版.北京:电子工业出版社,2004.

[2] Chen T F,Shen J.图像处理与分析:变分,PDE,小波及随机方法[M].北京:科学出版社,2009.

[3] 唐泽圣.三维数据场可视化[M].北京:清华大学出版社,1999.

[4] 钱归平,童若锋,彭文,等.保持特征区域的点云自适应网格重建[J].中国图象图形学报,2009(1):148-154.DOI:10.1 1834/jig.20090126.

[5] Kazhdan M,Bolitho M,Hoppe H.Poisson Surface Reconstruction[C]∥Association Eurogrouphics Synposium on Geometry Processing.Eurographics Association,2006:61-70.

[6] 王仁宏.多元样条及其应用[M].北京:科学出版社,1992.

[7] 崔锦泰著,程正兴译.多元样条理论用其应用[M].西安：西安交通大学出版社,1991.

[8] Guan L T,Liu Bin.Surface Design by Natural Splines Over Refined Grid Points[J].JournalofComputationalandAppliedMathematics,2004,163(1):107-115.DOI:10.1016/j.cam.2003.08.057.

[9] 关履泰,罗笑南,黎罗罗.计算机辅助几何图形设计[M].北京:高等教育出版社,海德尔堡:施普林格出版社,1999.

[10] 关履泰,覃廉,张健.用参数样条插值挖补方法进行大规模散乱数据曲面造型[J].计算机辅助设计与图形学学报,2006,18(3):372-377.DOI:10.3321/j.issn:1003-9775.2006.03.008.

[11] Lai M J,Schumaker L L.Spline Functions Over Triangulations[M].London:Cambridge University Press,2007.

[12] Lai M J.Multivarariate Splines for Data Fitting and Approximation,Approximation Theory XII, San Antonio[M].2007,edited by M.Neamtu and L.L.Schumaker,Nashboro Press,Brentwood,2008:210-228.

[13] Zhou T H,Han D F,Lai M J.Energy Minimization Method for Scattered Data Hermit Interpolation[J].AppliedNumericalMathematics,2008,58:646-659.

[14] 王仁宏.计算几何教程[M].北京:科学出版社,2008.

[15] 吴宗敏.散乱数据拟合的模型、方法和理论[M].北京:科学出版社, 2007.

[16] Wendland H.Scattered Data Approximation[M].New York:Cambridge University Press,2005.

[17] Chui C K,Guan L T.Multivariate Polynomial Natural Spline for Interpolation of Scattered Data and Other Applications[C]∥Workship on Computational Geometry, eds. A. Conte et al. World Scientific,1993:77-98.

[18] Guan L T.Bivariate Polynomial Natural Spline Interpolation Algorithms With Local Basis for Scattered Data[J].JCompAnalandAppl,2003,1:77-101.DOI:10.1023/A:1021478106002.

[19] 关履泰,许伟志,朱庆勇.一种双三次散乱数据多项式自然样条插值[J].中山大学学报(自然科学版),2008,47(5):1-4.

[20] 徐应祥,关履泰.散乱数据带自然边界条件二元样条光顺及数值微分[J].计算数学,2013,35(3):253-270.DOI:10.3969/j.issn.0254-7791.2013.03.003.

[21] 马利敏,吴宗敏.Multiquadric拟插值对高阶导数逼近的稳定性分析[J].中国科学,2010,40(12):1197-1204.DOI:10.1007/s11425-010-0068-9.

[22] 高文武.基于导数信息的Multiquadric拟插值[J].复旦学报(自然科学版),2016(3):298-303.

[23] 袁晖坪.关于复正定矩阵的判定[J].数学的实践与认识,2004(2):133-138.DOI:10.3969/j.issn.1000-0984. 2004.02.024.

[24] 包学游.特征值的实部为正或为非负的矩阵类[J].哈尔滨工业大学学报,1994(2):1-5.

AnApproximatedDefiniteRadialBasisInterpolationandQuasi-interpolationforScatteredDataInPlane

XU Yingxiang1，XUE Pengxiang2

(1.XinhuaCollegeofSunYat-senUniversity,GuangdongProvince, 510520,China;2.CollegeofScienceofXi’anTechnologicalUniversity,ShaanxiProvince710021,China)

Merging the advantages of B-spline and radial basis, a kind of approximated definite radial basis function was proposed and used for scattered data approximating in plane. A new interpolated form and a new quasi-interpolation were constructed.The numerical experiments show that the new interpolation and quasi-interpolation are all very efficient for approximating of scattered data in plane.

scattered data;approximated definite;interpolation;quasi-interpolation

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.012

2017-04-12；

2017-04-26

国家自然科学基金(10871160)

徐应祥(1978-),男,博士,副教授,研究方向为数值逼近。E-mail:xuyx-78@126.com

O241.5,TP391.7

A

0253-2395(2017)04-0702-10