蔡占川,陳 偉

(澳門科技大學(xué)資訊科技學(xué)院,澳門)

散亂數(shù)據(jù)是指在二維平面上或三維空間中，無規(guī)則的、隨機(jī)分布的抽樣數(shù)據(jù)點(diǎn)[1]。自然界中的很多觀測信號都是散亂的，諸如衛(wèi)星的觀測數(shù)據(jù)、海平面船載測量數(shù)據(jù)等。在對這些數(shù)據(jù)進(jìn)行分析時，除了抽樣的數(shù)值之外，也需要知道任意位置的數(shù)值，在這種情況下，就需要對所得到的觀測數(shù)據(jù)進(jìn)行插值或逼近(工程上通常稱為擬合)[2-4]。正如Roussell 所言“描述自然的問題最后一般都?xì)w結(jié)為逼近問題?！?事實(shí)上，求解逼近問題的指導(dǎo)思想有二：其一，要選擇簡單的函數(shù)空間作為描述對象的逼近空間；其二，這個空間要有好的逼近度。為了得到好的逼近效果，通常選擇最佳平方逼近。接下來的問題是，選擇什么樣的函數(shù)空間？對于散亂數(shù)據(jù)而言，傳統(tǒng)的散亂數(shù)據(jù)的曲面造型插值方法是Shepard方法，它是一個與距離成反比的加權(quán)方法，有在插值點(diǎn)附近會出現(xiàn)平臺、精度較差、函數(shù)重建質(zhì)量較差和計算量大等缺點(diǎn)。后來陸續(xù)又有了各種各樣的對多元散亂數(shù)據(jù)的插值方法，都有一定的效果，如薄板樣條、光滑余因子方法、Box樣條[5]、Bézier曲面[6]、頂點(diǎn)樣條[7]、多項式自然樣條和三角網(wǎng)最優(yōu)插值[8]．這些方法具有能量極小的性質(zhì)，避免插值點(diǎn)附近出現(xiàn)平臺現(xiàn)象，重建質(zhì)量較好；近年來，細(xì)分算法成為一個熱點(diǎn)，還有層次B樣條方法[9]、徑向基函數(shù)方法，但是它們都沒有選擇正交基函數(shù)。本文試圖選擇一類正交基函數(shù)對散亂數(shù)據(jù)做逼近。利用正交基逼近后，可以對散亂數(shù)據(jù)進(jìn)行更加深入的分析和挖掘，諸如頻譜分析等。

最近，文獻(xiàn)[10]提出了一類新的正交樣條函數(shù)系——GF系統(tǒng)，作為樣條函數(shù)空間的一組標(biāo)準(zhǔn)正交基，它能較為精確表達(dá)連續(xù)樣條函數(shù)。GF系統(tǒng)是通過對一組線性無關(guān)的函數(shù)組施行正交化過程得到,零次GF系統(tǒng)恰是Haar函數(shù)。

本文首先簡要介紹GF系統(tǒng)的構(gòu)造過程，然后詳細(xì)介紹了基于GF系統(tǒng)的散亂數(shù)據(jù)的最佳逼近算法，接著是實(shí)驗結(jié)果,最后是結(jié)論與展望。

1 k次GF系統(tǒng)簡介

M

其中，第1組表達(dá)式為：

圖與正交化后函數(shù)組(k次GF系統(tǒng))部分函數(shù)圖形 their orthogonalization function group system of degree k) graphics

2 基于GF系統(tǒng)的散亂數(shù)據(jù)的最佳平方逼近

2.1 基本思想

rT=(g(x1)-f1,…,g(xn)-fn)

所謂的散亂數(shù)據(jù)最佳平方逼近就是在F中，尋找函數(shù)g(x)，使得這個誤差向量的平方和取最小，也就是通常意義下的最小二乘逼近。

2.2 算法描述

本文處理的散亂數(shù)據(jù)集限于雙自變量的數(shù)據(jù)集：P={(x,y,z)|z=f(x,y)}，算法可以用如下過程描述：已知二維平面域上散亂數(shù)據(jù)點(diǎn)集P={(xk,yk,zk)|zk=f(xk,yk),k=1,2,…,N}，如圖2所示，W為包含點(diǎn)集P的最小矩形域，xk∈[Xmin,Xmax],yk∈[Ymin,Ymax]。

圖2 二維平面域上散亂數(shù)據(jù)點(diǎn)集P示意圖Fig.2 Scattered data point set P in two-dimensional plane domain

各采樣點(diǎn)殘差表達(dá)式為

殘差平方和

依據(jù)最小二乘算法，問題歸結(jié)為確定m×n個系數(shù)Cij使殘差平方和最小。對F(Cij)求偏導(dǎo)數(shù)并令其為零，即得到一個m×n階線性方程組，求解此線性方程組就可以得到擬合系數(shù)Cij。

2.3 能量模型

3 實(shí) 驗

下面通過幾個實(shí)驗來測試GF系統(tǒng)對散亂數(shù)據(jù)的逼近效果，并利用得到的能量模型進(jìn)行了散亂數(shù)據(jù)的分析。

圖3 原始數(shù)據(jù)模型Fig.3 The original model

實(shí)驗一選定一個原始模型,如圖3所示。然后分別在模型上隨機(jī)采樣600～2 600個不等的散亂點(diǎn)，應(yīng)用上述算法分別對各個散亂點(diǎn)集進(jìn)行擬合，得到擬合曲面，并計算各擬合曲面與原始曲面的均方誤差MSE。如表1所示。圖4表明了采樣點(diǎn)數(shù)與均方誤差的變化關(guān)系,表明了本文方法對散亂數(shù)據(jù)擬合具有較高的擬合度。

4）采用計算機(jī)機(jī)房的多媒體廣播教學(xué)方式指導(dǎo)同學(xué)采用寫字板對表達(dá)譜數(shù)據(jù)進(jìn)行預(yù)處理：將臨床數(shù)據(jù)和基因表達(dá)數(shù)據(jù)拆分出兩個文件。

圖4 采樣點(diǎn)與均方誤差示意圖Fig.4 Sampling points and the mean square error diagram

實(shí)驗二選擇采用一個球面參數(shù)曲面模型，分別在曲面上采樣128×128個點(diǎn)，并加入隨機(jī)噪聲擾動以模擬真實(shí)的數(shù)據(jù)。將基于GF系統(tǒng)的擬合結(jié)果與其他幾種擬合方法的結(jié)果進(jìn)行比較。

注：擬合曲面與理想標(biāo)準(zhǔn)曲面的差別用相對中誤差RRMSE評價，設(shè)i點(diǎn)的真值為256×256，擬合值為zi，誤差εi=|Zi-zi|，計算公式如下

PRMSE值越小說明擬合效果越好。擬合對象是一個標(biāo)準(zhǔn)球體，其參數(shù)方程為

實(shí)驗三本例選取三組散亂數(shù)據(jù)，每組散亂數(shù)據(jù)又分別含有1 000、1 200、1 500、2 000個不同的采樣點(diǎn)，如表3所示。

對上述散亂點(diǎn)采用本文算法進(jìn)行擬合，并根據(jù)得到的擬合系數(shù)計算擬合曲面的能量。擬合曲面及其能量(E)如表4所示。

從表4可以看出，同一組內(nèi)曲面的“能量”比較接近甚至相同，不同組間的曲面的“能量”差別較大。因此，利用GF系統(tǒng)進(jìn)行散亂數(shù)據(jù)擬合，能夠擬合出光滑的曲面，亦可以進(jìn)行頻譜分析。

表1 采樣本文方法擬合的曲面與原曲面的均方誤差

表2 球體點(diǎn)云數(shù)據(jù)擬合Table 2 Fitting of sphere point cloud data

4 結(jié)論與展望

本文利用GF系統(tǒng)對給定的散亂數(shù)據(jù)點(diǎn)進(jìn)行最佳平方逼近，得到擬合曲面。實(shí)驗結(jié)果表明，該方法不僅可以擬合出光滑的曲面，而且因GF系統(tǒng)是正交樣條函數(shù)系，還可以引入頻譜分析手段進(jìn)行后續(xù)分析工作。本文利用擬合系數(shù)(即頻譜)，計算了擬合曲面的能量，從而給出了散亂數(shù)據(jù)的一種新度量。下一步我們將研究快速算法，從而能應(yīng)用于更大規(guī)模的散亂數(shù)據(jù)擬合。利用散亂數(shù)據(jù)的能量模型可以深度挖掘散亂數(shù)據(jù)所隱藏的內(nèi)部信息。

參考文獻(xiàn)：

[1] FRANKE R. Scattered data interpolation: tests of some methods[J]. Mathematics of Computation, 1982, 38:181-200.

[2] BAJAJ C L, IHM I. Algebraic surface design using Hermite interpolation[J]. ACM Transactions on Graphics, 1992, 11(1):61-91.

表3 幾組模型的不同采樣點(diǎn)圖示

表4 擬合曲面及其能量

[4] FRANKE R, NIELSON G M. Scattered data interpolation of large sets of scattered data[J]. Intl J Numerical Methods in Eng, 1980,15: 1691-1704.

[5] WANG R H,SHI X Q, LUO Z X, et al. Multivariate spline and its applications[M]. Beijing: Science Press, 1994.

[6] WANG N, MENG F Z, LI M. Interpolation of large scale scattered data base on Bezier surface[J]. Journal of Tianjin University of Technology, 2005, 21(2):40-43.

[7] WANG G F, SUN Y, ZHANG H X, et al. Large_scale interpolation of discrete data based on nodal point interpolation principle[J]. Journal of Harbin Engineering University, 2001, 22(1):45-48.

[8] CHUI CHARLES K, LAI M J. Filling polygonal holes using C1 cubic triangular spline patches[J]. Computer Aided Geometric Design, 2000, 17(4):297-307.

[9] ZHANG W Q, TANG Z S, LI J. Adaptive hierarchical b-spline surface approximation of large-scale scattered data[C]∥ Pacific Graphics’98, 1998.

[10] CAI Z C, CHEN W, QI D X, et al. A class of general Franklin functions and its application[J]. Chinese J Computers, 2009, 32(10): 2004-2013.