平面散亂數(shù)據(jù)一種漸近正定徑向基函數(shù)插值與擬插值研究

徐應(yīng)祥,薛鵬翔

(1.中山大學(xué) 新華學(xué)院,廣東 廣州 510520；2.西安工業(yè)大學(xué) 理學(xué)院,陜西 西安 710021)

平面散亂數(shù)據(jù)一種漸近正定徑向基函數(shù)插值與擬插值研究

徐應(yīng)祥1,薛鵬翔2

(1.中山大學(xué) 新華學(xué)院,廣東 廣州 510520；2.西安工業(yè)大學(xué) 理學(xué)院,陜西 西安 710021)

結(jié)合一元B樣條和已有徑向基函數(shù)的優(yōu)點,提出了一種漸近正定徑向基函數(shù),并將其應(yīng)用于平面散亂數(shù)據(jù)逼近,得到了一種新的插值格式和擬插值方法。數(shù)值例子表明,這種插值格式與擬插值方法對平面散亂數(shù)據(jù)均具有良好的逼近效果。

散亂數(shù)據(jù);漸近正定;插值;擬插值

0 引言

散亂數(shù)據(jù)點是指那些不能位于正規(guī)網(wǎng)格上的數(shù)據(jù)點。散亂數(shù)據(jù)擬合在汽車外形設(shè)計、船體放樣、飛機機翼機身設(shè)計、服裝設(shè)計、地質(zhì)探礦、數(shù)據(jù)壓縮、醫(yī)學(xué)圖形圖像處理、模式識別等許多領(lǐng)域中都有廣泛的應(yīng)用[1-3]。將散亂數(shù)據(jù)擬合方法推向更高維空間乃至在點云數(shù)據(jù)三維曲面重建等方面也有了很多熱烈的討論[4-5]。從20世紀60年代以來,眾多的科技工作者對散亂數(shù)據(jù)曲面擬合問題進行了一系列的研究[6-10]。近些年來,盡管Lai,吳宗敏等學(xué)者對散亂數(shù)據(jù)擬合方法有了一系列總結(jié)性的工作[11-16],但是對多元散亂數(shù)據(jù)與大規(guī)模散亂數(shù)據(jù)插值問題的解決仍不夠理想。

為改進散亂數(shù)據(jù)插值方法,關(guān)履泰、徐應(yīng)祥等人提出了帶自然邊界樣條多元多項式樣條插值方法[17-21],這種插值方法具有可以推廣到任意維多元散亂數(shù)據(jù)插值,其基函數(shù)有緊湊的顯示表示式,且是分片多項式的優(yōu)點,但缺點是不具緊支性,這使得插值問題求解時因其系數(shù)矩陣不具有稀疏性而求解效率較低,并對大規(guī)模散亂數(shù)據(jù)插值時須進行分塊插值。

另一種常用的散亂數(shù)據(jù)插值方法是徑向基函數(shù)插值,其理論和方法已相當(dāng)成熟。徑向基函數(shù)插值的優(yōu)點是可以構(gòu)造局部基,插值矩陣較為稀疏,計算量相對較少。但也存在一些不足,主要表現(xiàn)在:具有緊支撐的局部基的構(gòu)造依賴于一個整體截斷多項式,為實現(xiàn)相應(yīng)的連續(xù)性,一般要求截斷多項式有較高的次數(shù),如在2維空間中要求C2連續(xù)時,截斷多項式的次數(shù)至少要是4次的。而容易滿足連續(xù)性要求的徑向基函數(shù)卻一般不具有緊支撐性質(zhì),如薄板樣條函數(shù)等,而且這樣的徑向基函數(shù)大多是非多項式型的。

由于一元B樣條具有諸多良好的性質(zhì),如光滑性,緊支性,是分段多項式。能否將其優(yōu)點與徑向基函數(shù)結(jié)合,得到新的兼有樣條與原有徑向基函數(shù)共同優(yōu)點的新插值基函數(shù),在一定程度上彌補以前徑向基函數(shù)的不足,也是值得研究的。盡管插值函數(shù)有經(jīng)過插值點且誤差一般較小的優(yōu)點,但為得到插值函數(shù)往往需要解較高階數(shù)的線性方程組,而擬插值函數(shù)的構(gòu)造過程不需要解方程。相對于插值,擬插值不要求逼近函數(shù)經(jīng)過插值點,在求解時也不需要解方程組,構(gòu)造也相對容易一些。對于一元函數(shù)擬插值的研究已有相當(dāng)豐富的成果,但是對于多元散亂數(shù)據(jù)擬插值的研究相對較少,其理論和方法相對還不完善[22-23]。因此,基于以上想法,本文提出了一種基于漸近正定徑向基函數(shù)的新插值格式并構(gòu)造了一種新的散亂數(shù)據(jù)擬插值函方法。

1 一類漸近正定徑向基函數(shù)

設(shè)x3=Bk(x1)是三維空間直角坐標(biāo)系O-x1x2x3中x1Ox3平面內(nèi)的k次B樣條,則滿足如下性質(zhì):

(1)對稱性與連續(xù)性:Bk(-x1)=Bk(x1),Bk∈Ck-1.

將x3=Bk(x1)繞x3軸旋轉(zhuǎn)一周,可得二元函數(shù)

(1)

其中c>0為待選參數(shù),則有

定理1φk,c具有如下的性質(zhì):

(2)連續(xù)性:φk,c(r)∈Ck-1.

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

證明(1)由一元B樣條zk=Bk(x)的非負性與緊支性,顯然。

進一步，由單調(diào)性可知當(dāng)r=0時,φk,c(r)最大,最大值為

(4) 由φk,c(r)的構(gòu)造可知

2 散亂數(shù)據(jù)漸近正定徑向基插值與擬插值

給定平面區(qū)域Ω中包含N個兩兩不同的散亂數(shù)據(jù)點的集合X={x1,x2,…,xN}與相應(yīng)每個散亂點處的值為fi(i=1,…,N),其中xi=(x1i,x2i)∈R2(i=1,2,…,N).

(Ⅰ)漸近正定徑向基插值

再由定理1性質(zhì)(1)-(3)可知,φ2m+1,c(r)具有優(yōu)良的光滑性和緊支性,其可以作為基函數(shù)構(gòu)造插值函數(shù)。下面是幾個φ3,c(r)的圖形:

Fig.1 Some figures of φ3,c(r)圖1 幾個φ3,c(r)的圖形

由定理1,若選擇了合適的c后φ2m+1,c(r)是正定的,則可以正定函數(shù)φ2m+1,c(r)為基函數(shù)構(gòu)造如下的插值函數(shù)

‖x-xk‖),

(2)

使其滿足如下的插值條件

(3)

其中Ck是待定的插值系數(shù),h是可選參數(shù)(關(guān)于這一點在后文總結(jié)中予以進一步說明)。

令A(yù)=(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)便可得插值系數(shù)C。

定理2 存在正數(shù)δ,使當(dāng)c∈(0,δ)時,插值函數(shù)(2)是存在唯一的。

插值函數(shù)(2)的插值誤差可仿文獻[16]第11章中的誤差估計方法進行估計,這里不再贅述。

(Ⅱ)一類新的擬插值

對任意的正整數(shù)k由定理1可知φk,c(r)≥0且是緊支撐的。于是構(gòu)造如下的擬插值函數(shù)

(5)

其中α是一個正的可選參數(shù),‖·‖為R2上的歐氏距離。

證明對常值函數(shù)f(x)=C有fi=C(i=1,2,…,N),因此由引理1有

定理3 對于選定α>0,設(shè)f(x)∈C(Ω),則對擬插值函數(shù)(5)有如下的估計式

證明由引理1及φk,c的非負性

3 插值與擬插值的數(shù)值例子

(Ⅰ)漸近正定徑向基插值數(shù)值例子

例1 取測試函數(shù)為如下的Frank函數(shù)

Fig.2 Interpolated results for N=50圖2 N=50時的插值結(jié)果

表1 N=50時的誤差Table 1 Error for N=50

(Ⅱ)擬插值數(shù)值例子

例2 取測試函數(shù)為

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時的擬插值結(jié)果

表2 N=50時擬插值誤差Table 2 Quasi-interpolated error for N=50

Fig.4 Quasi-interpolated results for N=500圖4 N=500時的擬插值結(jié)果

表3 h=10時誤差Table 3 Error for N=500

4 總結(jié)與進一步分析

本文構(gòu)造了一類新的漸近正定徑向基函數(shù)φk,c(r),并將其應(yīng)用于構(gòu)造平面散亂數(shù)據(jù)的一種插值與擬插值,定理1可知其優(yōu)點在于:

(1)φk,c(r)是緊支撐的,且具有顯式表達式;

(2)φk,c(r)具有k-1階連續(xù)的導(dǎo)數(shù),故在應(yīng)用中容易滿足連續(xù)性的要求;

(3)由緊支性可知,將φk,c(r)用作插值基時,插值系數(shù)矩陣的稀疏性較好,能夠提高求解效率。

(4)由于φk,c(r)≥0具有非負性且是緊支撐的,故用其構(gòu)造擬插值函數(shù)的基函數(shù)時能夠保證基函數(shù)也是非負的,而且也是具有緊支撐性,這使得這樣構(gòu)造的擬插值可以較容易地推廣到大規(guī)模散亂數(shù)據(jù)擬合。

(Ⅰ)插值結(jié)果的總結(jié)與進一步分析

從數(shù)值例1中的插值果可以看出:

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

(2)當(dāng)c變小時,插值結(jié)果會變得不好,這是因為當(dāng)c變小時,基函數(shù)就像圖1(c)中的所示,盡管基函數(shù)的支集不變,但其整個曲面變得又細又尖,從而使整個插值曲面呈現(xiàn)氣泡效應(yīng)。這種情況只要將h變大,便可使得插值結(jié)果得到改善。由此可知,h的選擇會直接影響到插值結(jié)果,這也是前文中將h視為可選參數(shù)的原因。

如將h擴大,取h=10,則插值結(jié)果如圖5,最大誤差和平均誤差如表4。顯然較之前圖2與表1中的插值結(jié)果已大為改善。通過多次數(shù)值實驗驗證,建議在選定c后,h的選擇應(yīng)使得插值函數(shù)中的每個基函數(shù)φ2m+1,c(h-1‖x-xk‖|)的支集中至少包含兩個以上的插值點為好。

Fig.5 Interpolated results for h=10圖5 h=10的插值結(jié)果

表4 h=10時誤差Table 4 Error for N=50

(Ⅱ)擬插值結(jié)果總結(jié)與進一步分析

從數(shù)值例2中擬插值果可以看出:

(1)這種新的擬插值的構(gòu)造僅依賴于散亂數(shù)據(jù)點的分布,而不依賴于區(qū)域Ω的形狀,構(gòu)造過程較為簡單,而且擬插值效果良好;

(2)由表3中的誤差也可以看出,當(dāng)散亂數(shù)據(jù)點確定,并選定了α,則在選取不同的c時,擬插值的誤差變化很小(這一點也從圖4中(b)-(d)的擬插值曲面與誤差曲面圖形幾乎一樣也能證明),這使得擬插值基函數(shù)對c的依賴不明顯,所以c的選取比較靈活。

再由定理3,若被插函數(shù)f(x)在Ω上連續(xù)時,增加散亂數(shù)據(jù)點的數(shù)量,會使插值結(jié)果會變得更好。下面就例2中的測試函數(shù),給出了散亂數(shù)據(jù)點數(shù)增加到1 500,3 000及5 000時的幾種擬插值結(jié)果。插值結(jié)果如圖6,最大誤差和平均誤差如表5。顯然圖6與表5中的插值結(jié)果證明了當(dāng)散亂數(shù)據(jù)點增加時,擬插值結(jié)果也會變得更好,這也說明這種新的擬插值格式可以向大規(guī)模散亂數(shù)據(jù)推廣。

Fig.6 Quasi-interpolated results圖6 擬插值結(jié)果

表5 誤差表Table 5 Error table

[1] Andrew R Webb.統(tǒng)計模式識別[M].王萍,楊培龍,羅穎昕,譯.2版.北京:電子工業(yè)出版社,2004.

[2] Chen T F,Shen J.圖像處理與分析:變分,PDE,小波及隨機方法[M].北京:科學(xué)出版社,2009.

[3] 唐澤圣.三維數(shù)據(jù)場可視化[M].北京:清華大學(xué)出版社,1999.

[4] 錢歸平,童若鋒,彭文,等.保持特征區(qū)域的點云自適應(yīng)網(wǎng)格重建[J].中國圖象圖形學(xué)報,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] 王仁宏.多元樣條及其應(yīng)用[M].北京:科學(xué)出版社,1992.

[7] 崔錦泰著,程正興譯.多元樣條理論用其應(yīng)用[M].西安：西安交通大學(xué)出版社,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] 關(guān)履泰,羅笑南,黎羅羅.計算機輔助幾何圖形設(shè)計[M].北京:高等教育出版社,海德爾堡:施普林格出版社,1999.

[10] 關(guān)履泰,覃廉,張健.用參數(shù)樣條插值挖補方法進行大規(guī)模散亂數(shù)據(jù)曲面造型[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,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].北京:科學(xué)出版社,2008.

[15] 吳宗敏.散亂數(shù)據(jù)擬合的模型、方法和理論[M].北京:科學(xué)出版社, 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] 關(guān)履泰,許偉志,朱慶勇.一種雙三次散亂數(shù)據(jù)多項式自然樣條插值[J].中山大學(xué)學(xué)報(自然科學(xué)版),2008,47(5):1-4.

[20] 徐應(yīng)祥,關(guān)履泰.散亂數(shù)據(jù)帶自然邊界條件二元樣條光順及數(shù)值微分[J].計算數(shù)學(xué),2013,35(3):253-270.DOI:10.3969/j.issn.0254-7791.2013.03.003.

[21] 馬利敏,吳宗敏.Multiquadric擬插值對高階導(dǎo)數(shù)逼近的穩(wěn)定性分析[J].中國科學(xué),2010,40(12):1197-1204.DOI:10.1007/s11425-010-0068-9.

[22] 高文武.基于導(dǎo)數(shù)信息的Multiquadric擬插值[J].復(fù)旦學(xué)報(自然科學(xué)版),2016(3):298-303.

[23] 袁暉坪.關(guān)于復(fù)正定矩陣的判定[J].數(shù)學(xué)的實踐與認識,2004(2):133-138.DOI:10.3969/j.issn.1000-0984. 2004.02.024.

[24] 包學(xué)游.特征值的實部為正或為非負的矩陣類[J].哈爾濱工業(yè)大學(xué)學(xué)報,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

國家自然科學(xué)基金(10871160)

徐應(yīng)祥(1978-),男,博士,副教授,研究方向為數(shù)值逼近。E-mail:xuyx-78@126.com

O241.5,TP391.7

A

0253-2395(2017)04-0702-10