基于正交GF系统的散乱数据拟合及分析*

蔡占川,陈 伟

(澳门科技大学资讯科技学院,澳门)

散乱数据是指在二维平面上或三维空间中，无规则的、随机分布的抽样数据点[1]。自然界中的很多观测信号都是散乱的，诸如卫星的观测数据、海平面船载测量数据等。在对这些数据进行分析时，除了抽样的数值之外，也需要知道任意位置的数值，在这种情况下，就需要对所得到的观测数据进行插值或逼近(工程上通常称为拟合)[2-4]。正如Roussell 所言“描述自然的问题最后一般都归结为逼近问题。” 事实上，求解逼近问题的指导思想有二：其一，要选择简单的函数空间作为描述对象的逼近空间；其二，这个空间要有好的逼近度。为了得到好的逼近效果，通常选择最佳平方逼近。接下来的问题是，选择什么样的函数空间？对于散乱数据而言，传统的散乱数据的曲面造型插值方法是Shepard方法，它是一个与距离成反比的加权方法，有在插值点附近会出现平台、精度较差、函数重建质量较差和计算量大等缺点。后来陆续又有了各种各样的对多元散乱数据的插值方法，都有一定的效果，如薄板样条、光滑余因子方法、Box样条[5]、Bézier曲面[6]、顶点样条[7]、多项式自然样条和三角网最优插值[8]．这些方法具有能量极小的性质，避免插值点附近出现平台现象，重建质量较好；近年来，细分算法成为一个热点，还有层次B样条方法[9]、径向基函数方法，但是它们都没有选择正交基函数。本文试图选择一类正交基函数对散乱数据做逼近。利用正交基逼近后，可以对散乱数据进行更加深入的分析和挖掘，诸如频谱分析等。

最近，文献[10]提出了一类新的正交样条函数系——GF系统，作为样条函数空间的一组标准正交基，它能较为精确表达连续样条函数。GF系统是通过对一组线性无关的函数组施行正交化过程得到,零次GF系统恰是Haar函数。

本文首先简要介绍GF系统的构造过程，然后详细介绍了基于GF系统的散乱数据的最佳逼近算法，接着是实验结果,最后是结论与展望。

1 k次GF系统简介

M

其中，第1组表达式为：

图与正交化后函数组(k次GF系统)部分函数图形 their orthogonalization function group system of degree k) graphics

2 基于GF系统的散乱数据的最佳平方逼近

2.1 基本思想

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

所谓的散乱数据最佳平方逼近就是在F中，寻找函数g(x)，使得这个误差向量的平方和取最小，也就是通常意义下的最小二乘逼近。

2.2 算法描述

本文处理的散乱数据集限于双自变量的数据集：P={(x,y,z)|z=f(x,y)}，算法可以用如下过程描述：已知二维平面域上散乱数据点集P={(xk,yk,zk)|zk=f(xk,yk),k=1,2,…,N}，如图2所示，W为包含点集P的最小矩形域，xk∈[Xmin,Xmax],yk∈[Ymin,Ymax]。

图2 二维平面域上散乱数据点集P示意图Fig.2 Scattered data point set P in two-dimensional plane domain

各采样点残差表达式为

残差平方和

依据最小二乘算法，问题归结为确定m×n个系数Cij使残差平方和最小。对F(Cij)求偏导数并令其为零，即得到一个m×n阶线性方程组，求解此线性方程组就可以得到拟合系数Cij。

2.3 能量模型

3 实 验

下面通过几个实验来测试GF系统对散乱数据的逼近效果，并利用得到的能量模型进行了散乱数据的分析。

图3 原始数据模型Fig.3 The original model

实验一选定一个原始模型,如图3所示。然后分别在模型上随机采样600～2 600个不等的散乱点，应用上述算法分别对各个散乱点集进行拟合，得到拟合曲面，并计算各拟合曲面与原始曲面的均方误差MSE。如表1所示。图4表明了采样点数与均方误差的变化关系,表明了本文方法对散乱数据拟合具有较高的拟合度。

4）采用计算机机房的多媒体广播教学方式指导同学采用写字板对表达谱数据进行预处理：将临床数据和基因表达数据拆分出两个文件。

图4 采样点与均方误差示意图Fig.4 Sampling points and the mean square error diagram

实验二选择采用一个球面参数曲面模型，分别在曲面上采样128×128个点，并加入随机噪声扰动以模拟真实的数据。将基于GF系统的拟合结果与其他几种拟合方法的结果进行比较。

注：拟合曲面与理想标准曲面的差别用相对中误差RRMSE评价，设i点的真值为256×256，拟合值为zi，误差εi=|Zi-zi|，计算公式如下

PRMSE值越小说明拟合效果越好。拟合对象是一个标准球体，其参数方程为

实验三本例选取三组散乱数据，每组散乱数据又分别含有1 000、1 200、1 500、2 000个不同的采样点，如表3所示。

对上述散乱点采用本文算法进行拟合，并根据得到的拟合系数计算拟合曲面的能量。拟合曲面及其能量(E)如表4所示。

从表4可以看出，同一组内曲面的“能量”比较接近甚至相同，不同组间的曲面的“能量”差别较大。因此，利用GF系统进行散乱数据拟合，能够拟合出光滑的曲面，亦可以进行频谱分析。

表1 采样本文方法拟合的曲面与原曲面的均方误差

表2 球体点云数据拟合Table 2 Fitting of sphere point cloud data

4 结论与展望

本文利用GF系统对给定的散乱数据点进行最佳平方逼近，得到拟合曲面。实验结果表明，该方法不仅可以拟合出光滑的曲面，而且因GF系统是正交样条函数系，还可以引入频谱分析手段进行后续分析工作。本文利用拟合系数(即频谱)，计算了拟合曲面的能量，从而给出了散乱数据的一种新度量。下一步我们将研究快速算法，从而能应用于更大规模的散乱数据拟合。利用散乱数据的能量模型可以深度挖掘散乱数据所隐藏的内部信息。

参考文献：

[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 几组模型的不同采样点图示

表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.