(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 CN 111738397 A(43)申请公布日 2020.10.02
(21)申请号 202010554815.X(22)申请日 2020.06.17
(71)申请人 江苏师范大学
地址 221000 江苏省徐州市铜山区上海路
101号(72)发明人 李轩宇 张兆军 许钊雄 (51)Int.Cl.
G06N 3/00(2006.01)G06F 17/16(2006.01)G06F 17/10(2006.01)G06F 16/904(2019.01)
权利要求书3页 说明书7页 附图3页
CN 111738397 A(54)发明名称
一种基于遗传粒子群算法的NURBS曲线拟合方法
(57)摘要
本发明提供了一种基于遗传粒子群算法的NURBS曲线拟合方法，包括步骤：(1)将带有法向约束的非线性最优化问题以惩罚函数的方法转化为无约束的最优化问题，建立一个与数据点和法向同时相关且比较合适的适应度函数。(2)将NURBS曲线中的节点向量自由化，使用遗传粒子群算法自适应的调节节点向量，并使用最小二乘法求解在该节点向量下的最优拟合曲线。(3)通过判断适应度函数值的优劣循环迭代，直到产生满足误差要求的拟合曲线。本发明的方法在逼近数据点的同时，亦能够满足数据点处的法向约束条件，并通过对节点向量的自适应调整，实现了数据点的精确拟合，提高了NURBS曲线拟合的准确性和可靠性。
CN 111738397 A
权 利 要 求 书
1/3页
1.一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，包括步骤：S1：输入待拟合数据di及其对应法向；S2：数据点参数化，以及建立有效的适应度函数；S3：设置遗传粒子群算法的相关参数，包括种群规模pop，终止条件，终止条件即最大迭代次数maxgen；
S4：初始化粒子位置及速度，这里每一个粒子代表一个节点向量；S5：根据粒子的位置，通过最小二乘法计算控制顶点，计算每个粒子的适应度值；S6：对每个粒子，比较其当前位置和它经历过的最好位置pbest，如果当前位置更好，则更新个体极值pbest；
S7：对每个粒子，比较其当前位置和群体中所有粒子所经历过的最好位置gbest，如果这个粒子的位置更好，则更新全局极值gbest；
S8：更新粒子的位置和速度；S9：对子代中的优秀个体进行交叉和变异操作，得到新的子代个体；
S10:判断迭代终止的条件,如果满足条件,则输出最优节点向量和控制顶点并计算重构曲线,否则转到步骤S5。
2.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S1中，数据拟合的数学模型如下：
一条p次B样条曲线可以表示为：
其中，p表示B样条次数，{Pi},i＝0,1,K,n是曲线的控制顶点，Ni,p(u)表示p次B样条在节点向量U上的基函数，其定义由de Boor-Cox递推公式给出：
由于公式(3)中可能出现分子、分母同时为0的情况，因此规定ui为节点向量U
{ui},i＝0,1,K,n+p+1中的元素，u的取值范围除非另外说明，通常取[0,1]；
给定m+1个数据点Q0,Q1,L,Qm，在p≥1的前提下，让逼近曲线经过首末两点需要满足的条件是：
Q0＝C(0),Qm＝C(1) (4)
对其余m-1个离散数据点Qk,k＝1,K,m-1进行最小二乘拟合，确保曲线误差最小即公式(5)最小：
该公式是最小二乘法近似拟合曲线的数学模型，这条曲线并不是精确地通过所有数据点，为了求解这条近似曲线，令
2
CN 111738397 A
权 利 要 求 书
2/3页
构造函数并推导如下：
函数f是一个关于变量P1,K,Pn-1的标量函数，为了得到f的最小值，需要对其求偏导：
令偏导数为0，可得：
当l＝1,2,K,n-1时，上式成立，可得线性方程组：NTR＝(NTN)P (10)
为了保证方程有且仅有唯一的最小二乘解，对矩阵N求Moore-Penrose广义逆；对于带法向约束的问题，只需在原有模型的基础上添加法向约束条件如下：
其中di表示数据点对应的参数值，法向约束的几何意义为参数化后的数据点在曲线上的切线矢量与对应的法向约束矢量li垂直。
3.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S2中，数据点的参数化方式为向心参数化。
4.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S4中，粒子的初始化方式为随机初始化。
5.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S6中，粒子通过跟踪两个信息来更新自己：一个是粒子本身所找到的最优解，叫做个体极值点；个体极值点即pbest；另一个是整个种群目前找到的最优解，称为全局极值点，全局极值点gbest表示；粒子i的信息可以用D维向量表示，位置表示为xi＝(xi1,xi2,L,xiD)T，速度为vi＝(vi1,vi2,L,viD)T。
6.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S8中，粒子的位置和速度更新方式为：
其中，ω是惯性权重；是粒子i在第k次迭代中的速度；是粒子i在第k次迭代中的当前位置；r1、r2是[0,1]上的随机数；c1、c2是加速系数。
3
CN 111738397 A
权 利 要 求 书
3/3页
7.根据权利要求1所述的一种基于遗传粒子群算法的NURBS曲线拟合方法，其特征在于，所述步骤S9中，交叉方式为均匀交叉，变异方式为高斯变异。
4
CN 111738397 A
说 明 书
一种基于遗传粒子群算法的NURBS曲线拟合方法
1/7页
技术领域
[0001]本发明涉及NURBS曲线拟合，具体涉及一种基于遗传粒子群算法的NURBS曲线拟合方法。
背景技术
[0002]现代工程设计中经常需要从测量的数据点中获取最合适的曲线或曲面表达，但是这些数据点往往由于各种因素的影响存在误差，所以待求的曲线或曲面不必严格的经过每一个数据点，可以用拟合的方法逼近数据点。由于NURBS曲线具有较好的逼近能力以及局部修改、投影不变等优秀的数学性质，可以非常灵活地表示各类曲线的形状。因此，在测试数据处理、逆向工程和图像处理等工程领域中，NURBS曲线拟合技术得到了广泛的应用。[0003]NURBS曲线描述自由曲线面时相比于NC代码，节省了存储空间；能够最大限度的减小轮廓误差，有效保证刀路的长度和连续性，尽可能地恢复到设计时的理想形状，因此拥有NURBS曲线解析或拟合的数控系统可以满足更多样化的加工需求。目前国外很多先进的数控公司如FANUC、SIEMENS等都有成熟规范的NURBS曲线拟合、规划与插补方法但这些技术处于保密状态，并不对用户开放。[0004]我国是一个制造业大国，为了贯彻落实中国“制造强国”的战略，需要对当前发展现状有基本的认识，也需要有突破当前困境的决心。现阶段我国高端数控系统大多仍然依赖进口，国产数控系统在样条曲线解析、生成以及规划和插补方面仍多有欠缺。为了从根本上解决这些问题，需要开发具有完整NURBS曲线轨
迹生成和规划功能的技术。发明内容
[0005]本发明的目的在于克服现有技术的不足，提供一种基于遗传粒子群算法的NURBS曲线拟合方法，将数据点带有法向约束的NURBS曲线拟合问题转化为基于遗传粒子群算法的无约束最优化问题，将节点向量自由化，自适应寻找最优节点向量，最终产生满足法向约束条件的最优逼近曲线。
[0006]为实现上述发明目的，本发明的技术方案具体如下：[0007]一种基于遗传粒子群算法的NURBS曲线拟合方法，包括以下步骤：[0008]S1：输入待拟合数据di及其对应法向；[0009]S2：数据点参数化，以及建立有效的适应度函数；[0010]S3：设置遗传粒子群算法的相关参数，包括种群规模pop，终止条件(最大迭代次数maxgen)；[0011]S4：初始化粒子位置及速度，这里每一个粒子代表一个节点向量；[0012]S5：根据粒子的位置，通过最小二乘法计算控制顶点，计算每个粒子的适应度值；[0013]S6：对每个粒子，比较其当前位置和它经历过的最好位置pbest，如果当前位置更好，则更新个体极值pbest；
5
CN 111738397 A[0014]
说 明 书
2/7页
S7：对每个粒子，比较其当前位置和群体中所有粒子所经历过的最好位置gbest，
如果这个粒子的位置更好，则更新全局极值gbest；[0015]S8：更新粒子的位置和速度；[0016]S9：对子代中的优秀个体进行交叉和变异操作，得到新的子代个体；
[0017]S10:判断迭代终止的条件,如果满足条件,则输出最优节点向量和控制顶点并计算重构曲线,否则转到步骤S5。[0018]进一步地，所述步骤S1中，数据拟合的数学模型如下：[0019]一条p次B样条曲线可以表示为：
[0020][0021]
其中，p表示B样条次数，{Pi},i＝0,1,...,n是曲线的控制顶点，Ni,p(u)表示p次B
样条在节点向量U上的基函数，其定义由de Boor-Cox递推公式给出：
[0022]
[0023]
[0024]由于上式中可能出现分子、分母同时为0的情况，因此规定ui为节点向量U
{ui},i＝0,1,...,n+p+1中的元素，u的取值范围除非另外说明，通常取[0,1]；[0025]给定m+1个数据点Q0,Q1,…,Qm，在p≥1的前提下，让逼近曲线经过首末两点需要满足的条件是：
[0026]Q0＝C(0),Qm＝C (1)
[0027]对其余m-1个离散数据点Qk,k＝1,...,m-1进行最小二乘拟合，确保曲线误差最小即下式最小：
[0028][0029]
该公式是最小二乘法近似拟合曲线的数学模型，这条曲线并不是精确地通过所有
数据点，为了求解这条近似曲线，令
[0030][0031]
构造函数并推导如下：
[0032]
[0033]
函数f是一个关于变量P1,...,Pn-1的标量函数，为了得到f的最小值，需要对其求
偏导：
6
CN 111738397 A[0034][0035][0036][0037]
说 明 书
3/7页
令偏导数为0，可得：
当l＝1,2,...,n-1时，上式成立，可得线性方程组：
[0038]NTR＝(NTN)P
[0039]为了保证方程有且仅有唯一的最小二乘解，对矩阵N求Moore-Penrose广义逆；对于带法向约束的问题，只需在原有模型的基础上添加法向约束条件如下：
[0040]
[0041]
其中di表示数据点对应的参数值，法向约束的几何意义为参数化后的数据点在曲线上的切线矢量与对应的法向约束矢量li垂直。[0042]进一步地，所述步骤S2中，数据点的参数化方式为向心参数化。[0043]进一步地，所述步骤S4中，粒子的初始化方式为随机初始化。[0044]进一步地，所述步骤S6中，粒子通过跟踪两个信息来更新自己：一个是粒子本身所找到的最优解，叫做个体极值点(用pbest表示)；另一个是整个种群目前找到的最优解，称为全局极值点(用gbest表示)；粒子i的信息可以用D维向量表示，位置表示为xi＝(xi1,xi2,…,xiD)T，速度为vi＝(vi1,vi2,…,viD)T。[0045]进一步地，所述步骤S8中，粒子的位置和速度更新方式为：
[0046][0047][0048]
其中，ω是惯性权重；是粒子i在第k次迭代中的速度；是粒子i在第k次迭代
中的当前位置；r1、r2是[0,1]上的随机数；c1、c2是加速系数(或称学习因子)。[0049]进一步地，所述步骤S9中，交叉方式为均匀交叉，变异方式为高斯变异。[0050]与现有技术相比，本发明的有益效果：[0051]1、本发明提供的基于遗传粒子群算法的NURBS曲线拟合方法通过罚函数的方法将带法向约束的非线性优化问题转化为无约束最优化问题，建立了一个与数据点和法向同时相关的适应度函数，然后利用遗传粒子群算法自适应的调节节点向量，迭代进化直至找到最优的节点向量。[0052]2、本发明的方法生成的拟合曲线在逼近数据点的同时，亦能够满足数据点处的法向约束条件。[0053]3、本发明通过对节点向量的自适应调整，实现了数据点的精确拟合，提高了NURBS曲线拟合的准确性和可靠性。
7
CN 111738397 A
说 明 书
4/7页
附图说明
[0054]下面结合附图和具体实施方式对本发明做更进一步的具体说明。[0055]图1是本发明实施例中的NURBS曲线拟合方法的流程图；
[0056]图2是本发明实施例中的基于遗传粒子群算法的NURBS曲线拟合方法对未知曲面的测量数据点进行曲线拟合的效果图。
[0057]图3是本发明实施例中的基于遗传粒子群算法的NURBS曲线拟合方法对未知曲面的测量数据点进行曲线拟合的效果图。
[0058]图4是本发明实施例中的基于遗传粒子群算法的NURBS曲线拟合方法对未知曲面的测量数据点进行曲线拟合的效果图。
[0059]图5是本发明实施例中的基于遗传粒子群算法的NURBS曲线拟合方法对未知曲面的测量数据点进行曲线拟合的效果图。
具体实施方式
[0060]下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0061]本发明提供了一种基于遗传粒子群算法的NURBS曲线拟合方法，该方法流程图如图1所示，包括以下步骤：[0062]步骤1：输入待拟合数据di及其对应法向。[0063]步骤2：数据点参数化，以及建立有效的适应度函数；[00]步骤3：设置遗传粒子群算法的相关参数，包括种群规模pop，终止条件(最大迭代次数maxgen)；[0065]步骤4：初始化粒子位置及速度，这里每一个粒子代表一个节点向量；[0066]步骤5：根据粒子的位置，通过最小二乘法计算控制顶点，计算每个粒子的适应度值；
[0067]步骤6：对每个粒子，比较其当前位置和它经历过的最好位置pbest，如果当前位置更好，则更新个体极值pbest；[0068]步骤7：对每个粒子，比较其当前位置和群体中所有粒子所经历过的最好位置gbest，如果这个粒子的位置更好，则更新全局极值gbest；[0069]步骤8：更新粒子的位置和速度；[0070]步骤9：对子代中的优秀个体进行交叉和变异操作，得到新的子代个体；[0071]步骤10：判断迭代终止的条件,如果满足条件,则输出最优节点向量和控制顶点并计算重构曲线,否则转到步骤S5。[0072]进一步，所述步骤1中，数据拟合的数学模型如下：[0073]一条p次B样条曲线可以表示为：
[0074][0075]
其中，p表示B样条次数，{Pi},i＝0,1,...,n是曲线的控制顶点，Ni,p(u)表示p次B
8
CN 111738397 A
说 明 书
5/7页
样条在节点向量U上的基函数，其定义由de Boor-Cox递推公式给出：
[0076]
[0077]
[0078]由于公式中可能出现分子、分母同时为0的情况，因此规定ui为节点向量U
{ui},i＝0,1,...,n+p+1中的元素，u的取值范围除非另外说明，通常取[0,1]；[0079]给定m+1个数据点Q0,Q1,…,Qm，在p≥1的前提下，让逼近曲线经过首末两点需要满足的条件是：
[0080]Q0＝C(0),Qm＝C(1)
[0081]对其余m-1个离散数据点Qk,k＝1,...,m-1进行最小二乘拟合，确保曲线误差最小即下式最小：
[0082][0083]
该公式是最小二乘法近似拟合曲线的数学模型，这条曲线并不是精确地通过所有
数据点，为了求解这条近似曲线，令
[0084][0085]
构造函数并推导如下：
[0086]
[0087]
函数f是一个关于变量P1,...,Pn-1的标量函数，为了得到f的最小值，需要对其求
偏导：
[0088][00][0090][0091]
令偏导数为0，可得：
当l＝1,2,...,n-1时，上式成立，可得线性方程组：[0092]NTR＝(NTN)P
[0093]为了保证方程有且仅有唯一的最小二乘解，对矩阵N求Moore-Penrose广义逆；对于带法向约束的问题，只需在原有模型的基础上添加法向约束条件如下：
9
CN 111738397 A
说 明 书
6/7页
[0094]
[0095]
其中di表示数据点对应的参数值，法向约束的几何意义为参数化后的数据点在曲
线上的切线矢量与对应的法向约束矢量li垂直。[0096]进一步，所述步骤2中，数据点的参数化方式为向心参数化。[0097]进一步，所述步骤4中，粒子的初始化方式为随机初始化。[0098]进一步，所述步骤6中，粒子通过跟踪两个信息来更新自己：一个是粒子本身所找到的最优解，叫做个体极值点(用pbest表示)；另一个是整个种群目前找到的最优解，称为全局极值点(用gbest表示)；粒子i的信息可以用D维向量表示，位置表示为xi＝(xi1,xi2,…,xiD)T，速度为vi＝(vi1,vi2,…,viD)T。[0099]进一步，所述步骤8中，粒子的位置和速度更新方式为：
[0100][0101][0102]
其中，ω是惯性权重；是粒子i在第k次迭代中的速度；是粒子i在第k次迭代
中的当前位置；r1、r2是[0,1]上的随机数；c1、c2是加速系数(或称学习因子)。[0103]进一步，所述步骤9中，交叉方式为均匀交叉，变异方式为高斯变异。[0104]实施例1：
[0105]
以参数曲线作为采样函数，在区间[-2,2]上以0.05为间隔均
匀取点和相应法向,取点个数为80，NURBS曲线次数为3。则，根据本发明的方法步骤，进行仿
真，其中图2是其拟合效果图。[0106]实施例2：
[0107]
以参数曲线作为采样函数，在区间[0,2π]上以0.05为间
隔均匀取点和相应法向,取点个数为126，NURBS曲线次数为3。则，根据本发明的方法步骤，
进行仿真，其中图3是其拟合效果图。[0108]实施例3：
[0109]
以参数曲线作为采样函数，在区间[0,2π]上以0.05为间隔
均匀取点和相应法向,取点个数为126，NURBS曲线次数为3。则，根据本发明的方法步骤，进
行仿真，其中图4是其拟合效果图。[0110]实施例4：
[0111]以参数曲线作为采样函数，其中，a＝2,
10
CN 111738397 A
说 明 书
7/7页
在区间[-π,π]上以0.05为间隔均匀取点和相应法向,取点个数为126，NURBS曲
线次数为3。则，根据本发明的方法步骤，进行仿真，其中图5是其拟合效果图。
[0112]最后所应说明的是，以上具体实施方式仅用以说明本发明的技术方案而非，尽管参照实例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。
11
CN 111738397 A
说 明 书 附 图
1/3页
图1
12
CN 111738397 A
说 明 书 附 图
2/3页
图2
图3
13
CN 111738397 A
说 明 书 附 图
3/3页
图4
图5
14
