《计算机专业毕业论文4.doc》由会员分享，可在线阅读，更多相关《计算机专业毕业论文4.doc（18页珍藏版）》请在三一办公上搜索。
1、B样条曲线曲面插值问题中参数化的智能算法数学与计算机科学学院 计算机科学与技术【摘 要】本文用遗传算法代替传统的方法解决B样条曲线曲面的插值问题，该遗传算法的思想是：对参数值进行编码，并用光顺度做为适应度，通过遗传搜索对参数值求优解。实验表明，用遗传算法代替传统的方法可以使曲线曲面具有更良好的形状。【关键词】B样条曲线；插值；参数化；智能算法1引言 样条函数是近代数学的新发展。60年代以来，它被广泛应用于数据拟合、函数逼近、数值积分与微分，并在理论上逐步完善，成为逼近论中的一个新分支和计算机辅助几何设计（CAGD）工作中主要数学工具，在航空、造船、汽车等部门发挥着日益重要的作用。目前，在CAG
2、D中使用较多的是多项式样条函数，即整体具有一定连续性而分段为多项式的样条函数，如二次样条函数、三次样条函数和B样条函数等。由于B样条函数具有许多样条函数所没有的优点。如可以灵活地构成随意形状的曲线。包括直线、封闭曲线和含有尖点的曲线在内。具有直观性和凸包性；与特征多边形的外形较接近；移动某个节点只会影响临近的几段曲线，因而便于对生成的曲线进行局部修改；可以采用较低次的多项式而又保证一定阶数的连续性等，因而成为目前CAGD中最常用的方法1。B样条曲线曲面插值问题是计算机辅助几何设计、计算机图形学以及现实工业等领域的关键技术。具有很强的实际应用意义。传统的曲线插值方法是一般地强制使曲线的首末端点分
3、别与给定的一组数据点中的首末数据点一致2，3，使曲线的分段连接点分别依次与B样条曲线定义域内的节点一一对应，即使数据点对应的节点值分别与参数值一一对应。确定数据点(i=0,1, ,m)相应的节点值的方法有：里森费尔德（Riesenfeld,1975）方法、哈特利(Hartley)贾德(Judd,1978)方法、均匀参数化(uniform parameterization)、累加弦长法(cumulative chord length parameterization)、向心参数化法(centripetal model parameterization)、Forley 参数化法、梯度法(Gauss
4、-Newton approach)等4。取其中一种方法即可得出节点值。相应可确定定义域内参数值为。再通过插值条件及自由端点条件，便可以求出控制顶点。从而可以得通过这些数据点的B样条曲线。这种方法具有简单快速的优点，对一般的曲线也能得到良好光顺的形状，但是对一些复杂、给定的数据点很不均匀的曲线时，这种方法就不能得到良好光顺的形状。同样在曲面的插值中，这种方法既有它简单快速的优点，也有不好的不能适用于所有类型的曲面的一面。遗传算法能克服传统方法中存在的这些缺点，它在传统方法的基础上对参数值在一定的范围和误差内进行搜索求出最优解，从而使曲线曲面具有良好光顺的形状。遗传算法是一种新型的全局优化搜索算法
5、5，其主要特点是从多个点出发进行群体搜索，同时充分利用群体中个体之间的信息交换。算法计算过程简单，对搜索空间有广泛的适应性，其对函数本身没有任何依赖性，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。遗传算法自提出以来，得到了广泛的应用，已有越来越多的人在这领域进行研究。遗传算法在插值计算、曲线曲面设计和拟合方面也有多人研究。Yoshimoto等对节点向量进行二进制编码和实数编码，用遗传算法获得拟合B样条曲线。Markus等则先对参数用累加弦长法产生一条三次B样条曲线，再以此B样条曲线为中心产生宽为的一个带状区域，然后在此带状区域中，以曲率平方的积分为目标函数，应用遗传算法求出较佳的插值
6、B样条曲线6。鉴于已有的这方面的研究结果，本文应用遗传算法替代传统优化算法来对B样条进行优化处理以达到更佳的效果是可行的。2B样条曲线基本知识 B样条曲线的参数方程可表示为2,3： (2-1)其中，为控制顶点，又称德布尔点。顺序连成的折线称为B样条控制多边形，又常简称为控制多边形。称为次规范样条基函数，其中每一个称为规范样条，简称样条。它是由一个称为节点矢量的非递减的参数的序列所决定的次分段多项式，也即是次多项式样条。样条具有局部支承性质。样条基是多项式样条空间具有最小支承的一组基，故被称为基本样条，简称样条。曲线方程中相应n+1个控制顶点，要用到n+1个k次B样条基函数 。其中，k次B样条基
7、函数按德布尔-考克斯递推公式计算： （2-2）的双下标中第二下标表示次数，第一个下标表示序号。该递推公式表明，欲确定第个次B样条，需要用到共+2个节点。称区间为的支承区间。次B样条的支承区间包含k+1个节点区间，因此在参数t轴上任一点处，就至多只有+1个非零的次B样条，其他次B样条在该处均为零。因此可将B样条曲线方程改写成为分段表示： （2-3）该式表明了B样条曲线的局部性质，在曲线定义域内，定义在非零节点区间上那一次B样条曲线段，由+1个控制顶点及相应的B样条基函数决定，与其他顶点无关。3. B样条曲线的插值问题 B样条的插值问题是一个从给定数据点和阶数来确定参数值、节点矢量与控制顶点的反算
8、问题。其中，在给定阶数下决定B样条曲线的因素有四个：数据点、参数值、节点矢量、控制顶点。这四个之间满足的关系为： （3-1）其中为数据点；为参数值；为控制顶点；为节点。在这四个因素中，数据点是已给定的，不能对它进行更改，剩余的三个因素中，控制顶点是由上述的关系方程求出，即由插值方程求出，由其它的三个因素决定，所以也不能对它进行优化。而余下的两个因素中，它们之间的关联很复杂，且又是不唯一的，所以用遗传算法并以更光顺良好形状为最优化目标对它们两个中的一个或同时两个（本文是对其中的参数值求最优解）求最优解是可行的。3.1确定节点矢量对于给定的一条k次B样条曲线上的一组数据点(i=0,1,m)（即型值
9、点）,首先对其进行节点矢量的确定，节点确定的方法有很多，可以直接求，也可以间接求。直接求的主要方法有（1）里森费尔德（Riesenfeld,1975）方法和（2）哈特利(Hartley)贾德(Judd,1978)方法。间接求的原理是先让节点值与传统方法求到的参数值相应相等，再将首末节点变为重节点，即有 ，其中，。从而可得到整个节点。对于数据点的参数化，这方面的主要方法有均匀参数化(uniform parameterization)、累加弦长法(cumulative chord length parameterization)、向心参数化法(centripetal model parameter
10、ization)、Forley 参数化法、梯度法(Gauss-Newton approach)4。其中，累加弦长法（Gro71)如实反应了数据点按弦长分布情况，一致被认为是较佳参数化方法。它克服了数据点按弦长不均匀时采用均匀参数化所出现的问题，在多数情况下能得到较满意的结果。拟合曲线有较好的光顺性。基于累加弦长法的这些优点，本文用累加弦长法间接求出节点矢量。3.2确定参数值 这是本文的核心，用遗传算法代替传统的方法来求各个参数值。由遗传算法搜索出相应m+1个参数值。这部分的知识放在第4节中介绍，这里就不再重复。3.3确定控制顶点当三个因素数据点、节点矢量、参数值确定后就可以由插值条件给出以n+
11、1个控制顶点为未知矢量的m+1个线性方程组成的方程组： （3-2） 这里方程数m+1少于未知顶点数n+1，还必须补充k-1个合适的边界条件。如本文中k取3，即还必须补充2个边界条件，本文用自由端点条件。在添加了边界条件之后方程数与未知顶点数都是n+1，从而才可以联立求出唯一解。同时，为了该组方程可同时用于开曲线和闭曲线，直接使首末节点分别与首末的控制顶点重合。于是上述的n+1个线性方程组可改写成如下矩阵形式：其中，、为自由端点系数（可随机取）： 值得注意下的是，为了方程有解，方程对应的系数矩阵必须是非奇异矩阵，即每个参数值对应的n+1个基函数不能全为零（矩阵不能有零行），并且每个基函数的支承区
12、间中必须要有参数值使该区间的基函数不全为零（矩阵不能有零列）。并且各个参数的值不能相等，否则矩阵中会出现相等的行而使得矩阵是奇异的。4. 遗传算法 遗传算法(GA)是一种随机的全局多点搜索算法。具有隐含并行性的特点 ，特别适合于求解优化问题。本文基于遗传算法对B样条曲线中的参数值进行优化处理以得到良好光顺的形状。遗传算法包含四个部分：编码方案，适应度函数，遗传算子，控制参数。4.1 编码方案采用实数编码，将一组参数值中的内部参数值映射成一个实数串，并称这个实数串为染色体，其中每个参数值对应的实数 为整数，且取值范围为0，9称为基因。m-1称为染色体长度。在迭代过程中，表示对应的参数值在相应的两
13、个节点值中的位置（将两节点值间十等分）。例如，为0则表示该参数值等于这两个相应节点值中的前一个的值；为5则表示该参数值处在这两个节点值的第5个等分点，即参数值=前一个节点值+这两个节点值的距离长*5/10。这里需要说明的一点是：底数取10而不取9是为了使参数值不等后一个节点值，使得每个节点区间内都含有一个参数值，从而在控制方程中避免奇异矩阵的出现。对于初始种群，设其种群规模为30。在初始化种群过程中，为了使染色体中的每个基因都能取遍它自己的取值范围（即0至9），种群的前10个染色体人为的为它们分别赋值为全0、全1、全9。其余的20个染色体中的每个基因则是随机的赋值为0到9之间的任何数。另外一点
14、值得说明的是：根据参数值的定义域，首末两个端点一定分别为0和1，直接给出而不用参加优解的搜索。4.2 适应度函数本文应用遗传的方法代替传统的方法求B样条曲线的插值问题的目的就是为了使B样条有更良好光顺的形状。这里的“更良好光顺的形状”可有两层含义：一是指曲线光顺、光滑；二是指曲线不能失真太大，即曲线与数据点所连成的折线多边形的差值不能太大。所以，在这里，以曲线的光顺度以及失真度的加权和为该算法的适应度函数。4.2.1 光顺度自定义根据控制顶点阵列定义的曲线的离散能量7。具体为：给定n+1个控制顶点阵列，定义l 为相邻两控制顶点连线的单位折线向量，为相邻两控制顶点连线的折线长度，表示相邻两控制多
15、边形折线和 方向的变化量。则： （4-1）称为曲线X的光顺度(离散能量)，而： （4-2）称为离散曲率变化总和。从定义1可以看出对于曲线上任一控制多边形，如果值较大， 表明所对应的曲线段的法向曲率变化较大，则曲线在该处的光顺性就差；反之，法向曲率变化较平缓，曲线在该处的光顺性就好。据此，光顺准则可定义为：如果Ex max b=i; max=f(c,i); endend% 选择算子 %function codec=select(code,c,f,m) s=0;for i=1:30 s=s+f(c,i);endj=0;for i=1:30 g(i)=f(c,i)/s; b=round(g(i)*1
16、00); r(j+1):(j+b)=i; j=j+b;endfor i=1:29 a(1:j)=randperm(j); r(a(1); codec(i,1:(m-1)=code(c,r(a(1),1:(m-1);endb=Maxf(f,c); codec(30,1:(m-1)=code(c,b,1:(m-1);% 交叉算子(两点交叉) %function codec=crossover(code,c,Pc,m) codec(1:30,1:(m-1)=code(c,1:30,1:(m-1);a(1:30)=randperm(30); s=round(Pc*100);for i=1:2:30 d
17、(1:100)=randperm(100); if d(1) O(2) j=O(1); O(1)=O(2); O(2)=j; end h(O(1):O(2)=code(c,a(i),O(1):O(2); codec(a(i),O(1):O(2)=code(c,a(i+1),O(1):O(2); codec(a(i+1),O(1):O(2)=h(O(1):O(2); endend% 变异算子 %function codec=Mutation(code,c,Pm,m) codec(1:30,1:(m-1)=code(c,1:30,1:(m-1);for i=1:30 s=round(Pm*100)
18、; a(1:100)=randperm(100); if a(1) =U(j+1) j=j+1; end for j1=(j-k):(j) A(i,j1)=Nb(j1,k,t(i),U); B(i,:)=Q(i,:); endendA(1,1)=1;A(m+1,m+k)=1;B(1,:)=Q(1,:);B(m+1,:)=Q(m+1,:);for i=1:k A(m+2,i)=Nb(i,(k-1),t(1),U); A(m+3,i+m)=Nb(i+1),(k-1),t(m+1),U);endA(m+2,2)=A(m+2,2)-k/(U(k+2)-U(2); A(m+2,1)=A(m+2,1)+k
19、/(U(k+2)-U(2);A(m+3,m+k)=A(m+3,m+k)-k/(U(m+k+k)-U(m+k)+1; A(m+3,m+k-1)=A(m+3,m+k-1)+k/(U(m+k+k)-U(m+k);B(m+2,:)=0,0;B(m+3,:)=0,0;%d(:,1)=AB(:,1); %d(:,2)=AB(:,2);d(:,1)=pinv(A)*B(:,1);d(:,2)=pinv(A)*B(:,2);%求B样条基函数,Ni,j(u) %5function N=Nb(i,j,u,U)if j=0 if u=U(i) & uU(i+1) N=1.0; else N=0.0; endelse
20、 a=Nb(i,j-1,u,U); b=Nb(i+1,j-1,u,U); if (U(i+j)-U(i)=0.0 if (U(i+j+1)-U(i+1)=0.0 N=0.0; else N=(U(i+j+1)-u)/(U(i+j+1)-U(i+1)*b; end else if (U(i+j+1)-U(i+1)=0.0 %2(U(i+j+1)-u)=0.0 & N=(u-U(i)/(U(i+j)-U(i)*a; else N=(u-U(i)/(U(i+j)-U(i)*a+(U(i+j+1)-u)/(U(i+j+1)-U(i+1)*b; end endend% 适应度函数 %function f
21、ci=Fitness(k,m,code,c,i,Q,U,s)t(1:(m+1)=jiema(code,c,i,m,k,U);d=control(Q,t,U,m,k);待添加的隐藏文字内容2s0=diffs(Q,m,k,U,t,d);if s0pi ee(j)=2*pi-ee(j); end ee(j)=ee(j)2; Ex=Ex+ee(j)*(l(j)+l(j+1); end fci=1/(Ex/(m+k-2)/ss)*0.9+s0*0.1); else fci=0;end % 求方向量 %555 function a=eatan(e,j) if e(j,1)=0 a=atan(1/1)*2;
22、 else a=atan(e(j,2)/e(j,1); end if e(j,1)0 & e(j,2)0 a=a+pi; end if e(j,1)=0 a=a+pi; end if e(j,1)0 & e(j,2)=U(j+1) j=j+1; end p(1:2)=0,0; for w=j-k:j N=Nb(w,k,i,U); p(1:2)=p(1:2)+d(w,1:2)*N; end pp(1:2)=Q(j-k,1:2)+(Q(j+1-k,1:2)-Q(j-k,1:2)*(i-U(j)/(U(j+1)-U(j); s=s+sqrt(p(1)-pp(1)2+(p(2)-pp(2)2); en
23、d s=s/20; 6 实例例1给定一组数据点，其中各个数据点的坐标分别如下：、；为6。则用改进前的适应度函数与改进后的适应度函数求的插值B样条的曲线分别如下(为了更好的比较改进前后，这里的适应度就是光顺度而没有加进失真度)： 图 6-1 光顺度改进前图 6-2 光顺度改进后图表中，虚线表示相应的数据点所连成的多边形；实线表示相应的B样条插值曲线(以下例子类似)。从这两幅图中可以清楚的看到，改进前的曲线不是理想的，而改进后的曲线比改进前的更光顺良好。例2给定一组数据点，其中各个数据点的坐标分别如下：、；为7。则适应度中不用失真度与用失真度下求的插值B样条的曲线分别如下：图 6-3 适应度中不用
24、失真度图 6-4 适应度中有用失真度从这两幅图中可以清楚的看到，适应度中不用失真度时得到的曲线失真较大。有用失真度可以很好的避免了曲线失真过大。例 3 给定一组数据点，其中各个数据点的坐标分别如下：、；为10。则用传统方法与用遗传算法求的插值B样条的曲线分别如下： 图 6-5 传统方法求的曲线图 6-6 遗传算法求的曲线 用传统方法求的B样条曲线的适应度为0.2760；而用遗传算法求的B样条曲线的适应度为0.3789。例4给定一组数据点，其中各个数据点的坐标分别如下：、；为6。则用传统方法与用遗传算法求的插值B样条的曲线分别如下： 图 6-7 传统方法求的曲线图 6-8 遗传算法求的曲线用传统
25、方法求的B样条曲线的适应度为0.2580；而用遗传算法求的B样条曲线的适应度为0.2931。例 5给定一组数据点，其中各个数据点的坐标分别如下：、；为7。则用传统方法与用遗传算法求的插值B样条的曲线分别如下： 图 6-9 传统方法求的曲线图 6-10 遗传算法求的曲线用传统方法求的B样条曲线的适应度为0.5230；而用遗传算法求的B样条曲线的适应度为0.5554。 从以上后三个例子中可知用遗传算法求的B样条曲线比用传统方法更有效的避免了“尖角”的出现，同时也降低了失真程度。比用传统方法求的B样条曲线有着更良好的形状。7 结论 平面有序数据点的拟合插值有很多方法，本文应用遗传算法变化参数值来拟合
26、平面有序数据点，着重与传统插值方法进行比较，并在遗传算法中，用改进后的光顺度代替一般的光顺度以及再加上自定义的失真度一起作为适应度。实验的结果表明遗传算法是可以求出比传统具有更良好的B样条曲线的。并且改进后的适应度比改进前一般的适应度更理想、更符合本文要求的优化目标。遗传算法具有稳定性好、精度高、不依赖于初值，全局最优、可以处理较复杂的非线性问题等许多优点，但在计算时间上处于劣势。同样，因为B样条曲面是张量积曲面，可利用B样条曲线的结果研究B样条曲面，所以，本文关于B样条曲线插值的有关结果可推广到B样条曲面的插值方面。它较之曲线只是在维数方面有所增加，其它的都是相同的原理的，因此，遗传算法在曲
27、面中也是可以求出具有更良好的形状的。本文中，遗传算法只是用来搜索参数值而固定节点矢量求良好光顺形状，在这里遗传算法可进一步改进为同时搜索节点矢量和参数值。参考文献1 宋松.B样条插值曲线的快速算法J.系统工程与电子技术，1995，12，44-45.2 施法中.计算机辅助几何设计与非均匀有理B样条M.北京：高等教育出版社，2001，211-267. 3 朱心雄.自由曲线曲面造型技术M.北京：科学出版社，2000，88-137.4 周明华.近代算法在工程领域中的应用研究D.浙江大学学报,2005，10-14.5 张文修，梁怡.遗传算法的数学基础M,西安：西安交通大学出版社，2000，1-20.6 周明华，汪国昭.基于遗传算法的B样条曲线和Bezier曲线的最小二乘拟合J.计算机研究与发展，2005，42（1），134-143.7 郑康平，姜虹，吴坚,等.一种光顺B-Spline曲线的实用方法J.计算机工程与应用，2
