一种基于Lipschitz估计的三维曲面拟合方法

一种基于Lipschitz估计的三维曲面拟合方法
【技术领域】
[0001] 本发明设及一种数学建模、计算机应用领域，尤其设及的是，一种基于Lipschitz 估计的=维曲面拟合方法。
【背景技术】
[0002] 科学和工程问题可W通过诸如采样、实验、测绘等方法获得若干离散的数据，根据 该些数据，我们往往希望得到一个连续的曲面与已知数据相吻合，此过程就叫做曲面拟合。 曲面拟合在计算机图形学、逆向工程、数值计算等方面有着广泛的应用。工程中的许多进展 都高度依赖于曲面拟合技术，因此，对曲面拟合方法的全面研究具有积极的现实意义。目 前，最常用的曲线拟合方法有最小二乘法、插值法和缩张算法等。
[0003] 最小二乘法是根据已知的数据（xk，yk)化二1，2, . . .，口（其中xk为测定量，yk为 其对应的函数值，K为数据点的数量规模大小）选取一个近似的函数f(x)，使得E2(f)(均 方根误差）最小；最小二乘法拟合最大优点是拟合精度可W调控，可W根据实际使用情况 选择不同的拟合精度，但在实际应用中，有些场合需要保留原数据点，该时使用最小二乘法 等常用方法就不合适了。插值法是根据插值原则构造n次多项式P"(x)，使得P"(x)在各测 试点的数据正好通过实测点；虽然插值法能够保留原数据点，但是，在一般情况下，为了尽 量反映实际情况而采集了很多样点，导致插值多项式P"(x)的次数很高，该不仅增大了计算 量，而且影响了拟合精度。缩张算法是一种W收缩、扩张捜索空间为基本特征的直接迭代算 法，缩张算法包含=个步骤；1)收缩步，缩小步长的捜索过程；2)扩张步，扩大步长的捜索 过程；3)调整步，中屯、点、临界值的重新调整。缩张算法无需提供适合的初始值，实现最优 拟合的能力较强，但是捜索效率不高，对多参数非线性问题难于实施。
[0004] 因此，现有的技术在曲线拟合方面存在着缺陷，需要改进。

【发明内容】

[0005] 为了克服已有方法不能保留原数据点、计算量大、拟合精度较低及效率不高的不 足，本发明提供一种能够保留原数据点、计算量小、拟合精度和效率较高的基于Lipschitz 估计的=维曲面拟合方法。
[0006] 本发明解决其技术问题所采用的技术方案是；
[0007] -种基于Lipschitz估计的=维曲面拟合方法，所述方法包括W下步骤：
[000引 1)参数初始化；设置常数M，输入初始数据点(成攻/)，k= 1，2，...，K，其中K 为数据点的规模大小；
[0009] 2)建立初始支撑矩阵，过程如下：
[0010] 2. 1)根据已有的数据点确定Xi的定义域[a。bi]，X2的定义域[3 2,b2]，其中ai、a2 分别为Xi、X2的下界，b1、b2为上界；
[0011] 2.。根据如下公式对点A(l，0)，B(0, 1)和C(0, 0)作转换；
[0012](1)
[0013] 其中x/，X2'，X3'为线性转换变量，并记转换后的点为A'、B'和C' ；
[0014] 2.如根据如下公式计算点A'、B'和C'的支撑向量：
[0015]
(2)
[0016] 其中，yk为点Xk函数值，M为足够大的常数，点A、B和C的函数值用初始数据点中 函数值最大的值代替，记作y。。,；
[0017] 2.4)把点A'，B'和C'的支撑向量组成支撑矩阵L，如公式做所示：
[00 化]
(3)
[0019] W支撑矩阵L为根建立树；
[0020] 3)计算每个已知数据点的支撑向量并更新树，对每个数据点作如下处理：
[002U3. 1)根据公式（4)对xk作线性转换为X' k
[0022]
(4)
[002引 3.。根据公式似计算出点（X'k，yk)的支撑向量Ik;
[0024] 3. 3)根据条件关系式（5)和（6)更新树：
[0027] 其中V表示任意，3表示存在；
[002引 3.3. 1)找出针对步骤3.2)构建的支撑向量Ik不满足条件化）的叶子节点，即
[0029] 3.3.2)依次用Ik替换步骤3. 3. 1)中找到的叶子节点矩阵中的每一行支撑向量 卢，从而形成=个新的叶子节点，即=个新的支撑矩阵；
[0030] 3. 3. 3)判断步骤3. 3. 2)中产生的新的叶子节点是否满足条件关系式巧），如果满 足，则保留，否则删除；
[0031] 4)计算下界估计值：
[0032] 4. 1)设置采样步长，并在各变量定义域范围内采样；
[003引 4.。对步骤4. 1)的每一个采样点（X。X2)作如下处理：
[0034] 4.2. 1)根据公式（4)作线性变换，得到新的向量X' = (X/，X2'，X3');
[0035] 4. 2. 2)根据公式（7)从步骤3. 3)建立的树中找到包含向量X'的叶子节点，如果 叶子节点满足式（7)则包含，否则不包含；
[0036]
(7)
[0037] 其中，产为所找的叶子节点矩阵中的元素；
[003引 4. 2. 3)根据公式（8)求出点X'所在的叶子节点对应区域的下界估计值另；
[0039]
巧）
[0040] 4. 2. 4)对步骤4. 2. 3)求得的下界估计值另乘WM得到实际下界估计值，即 而二？I乂M?，
[004U 4. 2. 5)输出下界估计值歹/及其对应的采样点（X。X2);
[0042]W计算上界估计值，过程如下：
[00创 5. 1)把数据点中的yk取负.
[0044] 5. 2)按步骤2)到4)计算下界估计值；
[0045] 5. 3)对步骤5. 2)所得的下界估计值取负，即为上界估计值九；
[0046] 5. 4)输出上界估计值方及其对应的采样点（X。X2);
[0047] 6)曲线拟合，过程如下：
[0048] 6. 1)连接每一个点对得到待拟合曲面的下界估计；
[0049] 6.。连接每一个点(Xi，A：2,灭,）得到待拟合曲面的上界估计；
[0050] 6. 3)对上界估计和下界估计取平均得到的曲面即为待拟合曲面。
[0化1] 本发明的技术构思为：基于Lipschitz估计理论，首先，对已知初始数据点构建 Lipschitz估计下界支撑面，并Wn叉树的形式来保存下界估计信息，从而建立待拟合曲面 的下界估计曲面，再W同样的方法建立待拟合曲面的上界估计曲面；然后，在各变量的定义 域范围内按一定的步长采样，获取各采样点的上界估计值和下界估计值，通过对上界估计 值和下界估计值取平均而得到该采样点估计值；最后，连接各采样点得到拟合曲面。
【附图说明】
[00巧图1是函数y=sin(Xi+X2)的下界估计示意图。
[0化引 图2是函数y=sin(Xi+X2)上界估计示意图。
[0054] 图3是函数y=sin(Xi+X2)的拟合曲面示意图。
【具体实施方式】
[0化5] 下面结合附图对本发明作进一步描述。
[0化6] 参照图1~图3, 一种基于Lipschitz估计的S维曲面拟合方法，包括W下步骤：
[0化7] 1)参数初始化；设置常数M，输入初始数据点扣-，.皆/)，k= 1，2，...，K，其中K 为数据点的规模大小；
[0化引 2)建立初始支撑矩阵，过程如下：
[0059] 2. 1)根据已有的数据点确定Xi的定义域[a。bi]，X2的定义域[3 2,b2]，其中ai、a2 分别为Xi、X2的下界，b1、b2为上界；
[0060] 2.。根据如下公式对点A(l，0)，BO), 1)和C(0, 0)作转换：
[0061]
(9)
[0062] 其中X/，X2'，X3'为线性转换变量，并记转换后的点为A'、B'和C' ；
[0063]2.如根据如下公式计算点A'、B'和C'的支撑向量：
[0064]
(10)
[00化]其中，yk为点Xk函数值，M为足够大的常数，点A、B和C的函数值用初始数据点中 函数值最大的值代替，记作y。。,；
[0066] 2. 4)把点A'，B'和C'的支撑向量组成支撑矩阵L，如公式做所示：
[0067]
(11)
[0068] W支撑矩阵L为根建立树；
[0069] 3)计算每个已知数据点的支撑向量并更新树，对每个数据点作如下处理：
[0070] 3. 1)根据公式（4)对xk作线性转换为X' k
[0071]
(12)
[007引 3.。根据公式似计算出点（X'k，yk)的支撑向量Ik;
[0073] 3. 3)根据条件关系式（5)和（6)更新树：
[0074] 方7，./巨{1，2,3!，/;^/.:/;' >// U3)
[007引 Wg{1，2，刊，击 ￡ 化2,3}: 4 =户 >/; y4)
[0076] 其中V表示任意，3表示存在；
[0077] 3.3. 1)找出针对步骤3. 2)构建的支撑向量Ik不满足条件化）的叶子节点，即 r;二!U
[007引 3.3.2)依次用Ik替换步骤3. 3. 1)中找到的叶子节点矩阵中的每一行支撑向量 /S从而形成=个新的叶子节点，即=个新的支撑矩阵；
[0079] 3. 3. 3)判断步骤3. 3. 2)中产生的新的叶子节点是否满足条件关系式巧），如果满 足，则保留，否则删除；
[0080] 4)计算下界估计值；
[0081] 4. 1)设置采样步长，并在各变量定义域范围内采样；
[008引 4.。对步骤4. 1)的每一个采样点（X。X2)作如下处理：
[0083] 4.2. 1)根据公式（4)作线性变换，得到新的向量X' = (X/，X2'，X3');
[0084] 4. 2. 2)根据公式（7)从步骤3. 3)建立的树中找到包含向量X'的叶子节点，如果 叶子节点满足式（7)则包含，否则不包含；
[0085]
(15)
[0086] 其中，X产，X,A为所找的叶子节点矩阵中的元素；[0087] 4. 2. 3)根据公式（8)求出点X'所在的叶子节点对应区域的下界估计值另；
[008引
06)
[0089] 4.2.4)对步骤4.2.扣求得的下界估计值另乘得到实际下界估计值，即 哀=方xM;
[0090] 4. 2.W输出下界估计值兩及其对应的采样点（X。X2);
[0091] 5)计算上界估计值，过程如下：
[009引 5.1)把数据点中的yk取负.
[0093] 5. 2)按步骤2)到4)计算下界估计值；
[0094] 5. 3)对步骤5. 2)所得的下界估计值取负，即为上界估计值及；
[00巧]5. 4)输出上界估计值记及其对应的采样点（Xi，X2);
[0096] 6)曲线拟合，过程如下：
[0097] 6. 1)连接每一个点知y;，对得到待拟合曲面的下界估计；
[009引 6.。连接每一个点知x;，哀,)得到待拟合曲面的上界估计；
[0099] 6. 3)对上界估计和下界估计取平均得到的曲面即为待拟合曲面。
[0100] 本实施例W函数y=sin(Xi+X2)为实施例，一种基于Lipschitz估计的S维曲面 拟合方法，其中包含W下步骤：
[0101] 1)参数初始化；设置常数M= 10,在各变量定义域范围（0, 2)内随机生成100个 点作为初始数据点(.rf，.冷/)，k= 1，2,. . .，100 ;
[0102] 2)建立初始支撑矩阵，过程如下：
[0103] 2. 1)根据已有的数据点确定Xi的定义域[a1,bi]，X2的定义域[32,b2]，其中ai、a2 分别为Xi、X2的下界，b1、b2为上界；
[0104] 2. 2)根据如下公式对点A(l，0)，B0)，1)和C(0, 0)作转换；
[0105]
(口）
[0106] 其中X/，X2'，X3'为线性转换变量，并记转换后的点为A'、B'和C' ；
[0107] 2. 3)根据如下公式计算点A'、B'和C'的支撑向量：
[010 引
（18)
[0109] 其中，yk为点xk函数值，M= 10,点A、B和C的函数值用初始数据点中函数值最大 的值代替，记作y。。,；
[0110] 2.4)把点A'，B'和C'的支撑向量组成支撑矩阵L如公式（3)所示：
[0111]
(19)
[0112] W支撑矩阵L为根建立树；
[0113] 3)计算每个已知数据点的支撑向量并更新树，对每个数据点作如下处理：
[0114] 3. 1)根据公式（4)对xk作线性转换为X'k
[0115]
口0)
[0116] 3.。根据公式似计算出点（X'k，yk)的支撑向量Ik;
[0117] 3. 3)根据条件关系式（5)和（6)更新树：
[0118] /1，]&\\,2巧，1丰.1:1^；' >li;' 口 1)
[0119] W€ 化 2,句，击E化 2,3}:王,',' =护 > /;' 口引
[0120] 其中V表示任意，3表示存在；
[0121] 3.3. 1)找出针对步骤3. 2)构建的支撑向量Ik不满足条件化）的叶子节点，即 二!
[0122] 3.3.2)依次用Ik替换步骤3. 3.1)中找到的叶子节点矩阵中的每一行支撑向量 卢，从而形成=个新的叶子节点，即=个新的支撑矩阵；
[0123] 3. 3. 3)判断步骤3. 3. 2)中产生的新的叶子节点是否满足条件关系式巧），如果满 足，则保留，否则删除；
[0124] 4)计算下界估计值：
[0125] 4. 1)设置采样步长，并在各变量定义域范围内采样；
[0126] 4. 2)对步骤4. 1)的每一个采样点（X。X2)作如下处理：
[0127] 4.2. 1)根据公式（4)作线性变换，得到新的向量X' = (X/，X2'，X3');
[012引 4. 2. 2)根据公式（7)从步骤3. 3)建立的树中找到包含向量X'的叶子节点，如果 叶子节点满足式（7)则包含，否则不包含；
[0129]
(23)
[0130] 其中，为所找的叶子节点矩阵中的元素；
[0131] 4. 2. 3)根据公式（8)求出点X'所在的叶子节点对应区域的下界估计值另，
[0132]
(24)
[0133] 4. 2. 4)对步骤4. 2. 3)求得的下界估计值另乘WM得到实际下界估计值，即 友二究xM;
[0134] 4. 2. 5)输出下界估计值巧及其对应的采样点（X。X2);
[01巧]5)计算上界估计值，过程如下：
[0136] 5. 1)把数据点中的yk取负.
[0137] 5. 2)按步骤2)到4)计算下界估计值；
[0138] 5. 3)对步骤5. 2)所得的下界估计值取负，即为上界估计值其；
[0139] 5.4)输出上界估计值及及其对应的采样点（Xi，X2);
[0140] 6)曲线拟合，过程如下；
[OW] 6. 1)连接每一个点知成，对得到待拟合曲面的下界估计，如图1所示；
[01创 6.。连接每一个点(.V与，及)得到待拟合曲面的上界估计，如图2所示；
[0143] 6. 3)对上界估计和下界估计取平均得到的曲面即为待拟合曲面，如图3所示。
[0144] W函数y=sin(X1+X2)为实施例，运用W上方法得到了其拟合曲面如图3所示，图 中，由于部分区域的已知初始数据较少，所W估计值较大。
[0145] W上阐述的是本发明给出的一个实施例表现出来的优良效果，显然本发明不仅适 合上述实施例，在不偏离本发明基本精神及不超出本发明实质内容所设及内容的前提下可 对其做种种变化加W实施。
【主权项】
1. 一种基于Lipschitz估计的三维曲面拟合方法，其特征在于：所述曲面拟合方法包 括以下步骤： 1) 参数初始化：设置常数M，输入初始数据点(<,￥,/)，k= 1，2，...，K，其中K为数 据点的规模大小； 2) 建立初始支撑矩阵，过程如下： 2. 1)根据已有的数据点确定定义域[a u bj ^2的定义域[a 2, b2]，其中Spa2分别 为X2的下界，b p b2为上界； 2. 2)根据如下公式对点A (1，0)，B (0, 1)和C (0, 0)作转换：其中X1'，x2'，x3'为线性转换变量，并记转换后的点为A'、B'和C'； 2. 3)根据如下公式计算点A'、B'和C'的支撑向量：其中，/为点X k函数值，M为足够大的常数，点A、B和C的函数值用初始数据点中函数 值最大的值代替，记作ymax; 2. 4)把点A'，B'和C'的支撑向量组成支撑矩阵L，如公式（3)所示：以支撑矩阵L为根建立树； 3) 计算每个已知数据点的支撑向量并更新树，对每个数据点作如下处理： 3. 1)根据公式（4)对Xk作线性转换为X' k3. 2)根据公式⑵计算出点（X' k，yk)的支撑向量Ik; 3. 3)根据条件关系式（5)和（6)更新树： V/，./e !l，2,3!.，/>./:/f.: >/产 〇) Vr ? {1,2,3}, 3/ e {1,2,3}: Lii = > /；' (6) 其中V表示任意，3表示存在； 3. 3. 1)找出针对步骤3. 2)构建的支撑向量Ik不满足条件（6)的叶子节点，即=/f; 3. 3. 2)依次用Ik替换步骤3. 3. 1)中找到的叶子节点矩阵中的每一行支撑向量产，从 而形成三个新的叶子节点，即三个新的支撑矩阵； 3. 3. 3)判断步骤3. 3. 2)中产生的新的叶子节点是否满足条件关系式（5)，如果满足， 则保留，否则删除； 4) 计算下界估计值： 4. 1)设置采样步长，并在各变量定义域范围内采样； 4. 2)对步骤4. 1)的每一个采样点（Xl，X2)作如下处理： 4.2. 1)根据公式⑷作线性变换，得到新的向量X' =Oc1'，X2'，X3'); 4. 2. 2)根据公式（7)从步骤3. 3)建立的树中找到包含向量V的叶子节点， 如果叶子节点满足式（7)则包含，否则不包含； -X1j > x'/'x'n Z,j'e!l,2,3}, ?φ] (7) 其中，为所找的叶子节点矩阵中的元素； 4. 2. 3)根据公式（8)求出点X'所在的叶子节点对应区域的下界估计值K; 只=min(- A/(.v" - λ*')） (8) i=l,2.3 ^ 4.2.4) 对步骤4. 2. 3)求得的下界估计值J；乘以M得到实际下界估计值，即 j,=歹;xM; 4. 2. 5)输出下界估计值另及其对应的采样点（Xl，x2); 5) 计算上界估计值，过程如下： 5. 1)把数据点中的yk取负； 5. 2)按步骤2)到4)计算下界估计值； 5. 3)对步骤5. 2)所得的下界估计值取负，即为上界估计值Λ ·， 5.4) 输出上界估计值叉及其对应的采样点（Xl，χ2); 6) 曲线拟合，过程如下： 6. 1)连接每一个点(.VaV歹/)得到待拟合曲面的下界估计； 6. 2)连接每一个点(??,又)得到待拟合曲面的上界估计； 6. 3)对上界估计和下界估计取平均得到的曲面即为待拟合曲面。
【专利摘要】一种基于Lipschitz估计的三维曲面拟合方法，包括以下步骤：首先，对已知初始数据点构建Lipschitz估计下界支撑面，并以n叉树的形式来保存下界估计信息，从而建立待拟合曲面的下界估计曲面，再以同样的方法建立待拟合曲面的上界估计曲面；然后，在各变量的定义域范围内按一定的步长采样，获取各采样点的上界估计值和下界估计值，通过对上界估计值和下界估计值取平均而得到该采样点估计值；最后，连接各采样点得到拟合曲面。
【IPC分类】G06F17/50
【公开号】CN104881525
【申请号】CN201510242319
【发明人】张贵军, 周晓根, 郝小虎, 陈凯, 俞旭锋, 徐东伟
【申请人】浙江工业大学
【公开日】2015年9月2日
【申请日】2015年5月12日