CN102938008A - 一种人体建模中曲面拟合的进化算法 - Google Patents

Abstract

本发明公开了一种人体建模中曲面拟合的进化算法，属于计算机应用技术领域。本发明的原理及有益效果：进化算法是一种新兴的搜索寻优技术，提供了一种求解复杂系统的通用框架。本发明将基于进化算法的B样条曲面拟合应用到人体建模中，首先利用进化算法的B样条曲线拟合方法确定曲线边界线，从而得到基面，再按照曲面拟合的基本原理反求出曲面控制点，依据进化算法对控制点适应度大小的判断进行优化选择，最终实现人体建模中的曲面拟合。该方法利用进化算法的鲁棒性提高计算速度和效率，简化求取过程，降低拟合过程产生的误差，进而证明了该方法的优越性。

Description

一种人体建模中曲面拟合的进化算法

技术领域

本发明涉及一种人体建模中曲面拟合进化算法，属于计算机应用技术领域。

背景技术

曲面拟合是计算机图形学中的重要研究内容之一，在工程领域中有着广泛的应用。随着人们对计算机图形显示的真实性、实时性和交互性等方面要求的日益提高，曲面拟合的表示方法被不断地开拓创新。样条曲面是实体造型，样条曲面是在虚拟现实等CAD/CAM领域中普遍使用的几何造型工具。目前CAD系统中的曲面主要是B样条曲面和NURBS曲面，其中，B样条曲面是通过逼近一组控制点来生成，并具有两个最大的优点：（1）B样条多项式次数可独立于控制点数目；（2）B样条允许局部控制曲面。B样条曲面拟合方法中基于四边域曲面的几何重构方法是曲面重建中常用的方法。在CAD中，从点云中重建出被测物体表面的三角网格模型后，再将三角网格模型转换为用B样条表示的曲面。一般针对散乱点数据进行四边域曲面拟合，先根据散乱的数据构造一张基面，将数据点三角网格参数化，然后最小化测量数据到目标曲面的误差的平方和来判断所求目标曲面的精度，但一般的求取过程运算量较大，并且没有目的性。

发明内容

为了克服上述的不足，本发明提出一种人体建模中曲面拟合的进化算法。

本发明采用如下技术方案：

在计算过程中，曲面控制顶点的反求是通过两个阶段曲线反算得到的。

第一步：根据复杂曲面上的呈矩形阵列的数据点p_i，j，（i＝0,1，...,r;j＝0,1,...,s），反求出控制点d_i，j(i＝0,1，...,m;j＝0,1，...,s)，对控制顶点和数据点横、纵向进行平均规范积累弦长参数化从而得到节点矢量，这样就确定了一个B样条拟合曲面，该曲面逼近于已知的复杂曲面，但由于选取的数据点的数量、位置有可能存在噪声和摆动，所以计算出的拟合曲面在某些点处会过分偏离原有曲面。这时根据误差判断条件，实时调整偏离点处对应的控制顶点，便可修改拟合曲面的局部性状，达到更好的拟合效果。由于双三次B样条曲面具有良好的局部特性，工程实践中常常使用双三次B样条曲面来拟合复杂曲面，所以本发明采用双三次B样条曲面进行解释并运用四边域曲面拟合方法对其拟合。

四边界曲面拟合的具体步骤如下所示是：

1、边界预处理

2、空间散乱点的参数化

3、三角网格的建立

4、建立数学模型

第二步：为了得到散乱数据点的逼近曲面模型，散乱点的个数必须大于所求曲面的未知控制顶点数(l＞m×n)，这样才能保证未知数变量小于或等于方程数，目标函数为：

$I^r=\mathrm{\α}\underset{k=0}{\overset{j}{\mathrm{\Σ}}}{[S^r(u_k^{r-1},v_k^{r-1})-P_k]}^2+\mathrm{\β}[S_{\mathrm{uu}}^r{(u_k^{r-1},v_k^{r-1})}^2+S_{\mathrm{vv}}^r{(u_k^{r-1},v_k^{r-1})}^2+2S_{\mathrm{uv}}^r{(u_k^{r-1},v_k^{r-1})}^2]---\left(1.1\right)$

其中：

S^r(u,0)＝p(u,0);S^r(u,1)＝p(u,1)

S^r(0,v)＝p(0,v);S^r(1,v)＝p(1,v)    （1.2）

S_v ^r(u,0)＝p_v(u,0);S_v ^r(u,1)＝p_v(u,1)

S_u ^r(0,v)＝p_u(0,v);S_u ^r(1,v)＝p_u(1,v)

r表示曲面的迭代次数；s^r(u,v)是经过r次迭代后得到的曲面，并且 $s^r(u,v)=\underset{i=0}{\overset{m}{\mathrm{\Σ}}}\underset{j=0}{\overset{n}{\mathrm{\Σ}}}{N}_{i,3}\left(u\right)N_{j,3}\left(v\right)V_{i,j}^r;$

是曲面S^r(u,v)的u,v两向量的二阶导数和混合偏导数；P_k(k＝0,1,...l)为散乱数据点；

是散乱点P_k在r-1次迭代曲面上的参数值；α为逼近权，β为光顺权，且α+β＝1。当α值越大时曲线越靠近逼近点，则β较小，曲线越不光顺；当β越大时，线越光顺，则α变小曲线到数据点的距离则越大，所以应调节好α和β平衡曲线光顺和精度的关系。

由以上叙述可知目标曲面的数学模型公式(1.1)是带有复杂约束条件的二次优化问题，我们的目的就是运用寻优手段使目标函数I^r既能满足约束，又能达到最小，由此就可求得第r次几何迭代目标曲面的控制顶点为

(i＝0,1,…,m;j＝0,1,…,n)。

第三步：数学模型的求解即目标函数I^r的求解

对于公式(1.1)的目标函数I^r的优化我们分为两步进行。由于约束条件只涉及到边界曲线和跨边界切矢曲线，而曲面的边界和跨边界切矢可以由曲面的边界和次边界控制顶点完全确定，因此我们可以先处理这些约束条件来得到目标曲面的边界和次边界控制顶点，根据公式(1.1)就可以得到我们所需要的拟合曲面。

曲面重建首先将离散点参数化，设计为三角网格进而初步拟合成第一层曲面（基面）所示。采用Delaunay三角化方法对散乱点进行三角网格拟合，以人体模型数据为例，优化整体曲面的边界线和基曲面。

然后利用公式（1.1）、（1.2）运用最小二乘法反求出曲面控制点，将控制点进行编码产生初始群体，通过适应度函数f＝1/|(F(x，y，z)-z)²+(y(x,y)-y)²+(x-x_i)²-ε|求得最大值，也就是最终的曲面控制点以便拟合出基面。

因为人体模型是复杂样件模型，并不能用一张曲面表达，因此将曲面细化，就是从粗糙到精细的B样条控制网格确定，最后使B样条曲面逐步逼近给定的散乱点云，而且由粗到细的过程仅在误差超过预定的区域进行，具体流程如图3所示。

首先对反求出的控制点进行编码，对控制点数据分块得到相互连接的矩形区域，为保证曲面的连续性，将每块曲面的左上角和右下角数值记录，以便确定细化曲面的范围，对分块后曲面内的数据建立初始群体，判断它的迭代次数是否超出给定范围（初次分块迭代次数为零），如果超出则进入到上层计算重复分块动作，如果没有则接着从初始群体（含有N个基因）中随机选取第0代群体（含有n个），对其拟合并求出适应度，如果适应度达到给出的标准则停止循环，直接得到拟合曲面，如果不符合适应度的要求则根据适应度的大小对数据进行遗传和变异操作，判断新生代基因个数，如果小于初始群体个数则从余下的数据中随机选取使新生代群体达到n个，从而得到第一代群体，再进入到循环中直到满足停机条件得到最优的拟合曲面。

本发明的原理及有益效果：进化算法是一种新兴的搜索寻优技术，进化算法和传统方法的最大不同，就是它不要求所研究的问题连续或可导，能够很快地得到所求的最优解，适用于处理传统搜索方法难以解决的复杂和非线性问题。进化算法的整体搜索策略和优化搜索方法在计算工程中不依赖于梯度信息或是其他辅助知识，而只需要对搜索反应有影响的目标函数和相应的适应度函数，所以进化算法提供了一种求解复杂体统的通用框架。本发明将基于进化算法的B样条曲面拟合应用到人体建模中，首先利用进化算法的B样条曲线拟合方法确定曲线边界线，从而得到基面，再按照曲面拟合的基本原理反求出曲面控制点，依据进化算法对控制点适应度大小的判断进行优化选择，最终实现人体建模中的曲面拟合。该方法利用进化算法的鲁棒性提高计算速度和效率，简化求取过程，降低拟合过程产生的误差，进而证明了该方法的优越性。

附图说明

图1三角网格化。

图2基面。

图3具体流程图。

图4.人体模型的曲面拟合。

具体实施方式

下面结合附图对本发明做进一步说明，本发明的一个实施例：

在计算过程中，曲面控制顶点的反求是通过两个阶段曲线反算得到的。

第一步：根据复杂曲面上的呈矩形阵列的数据点p_i，j，（i＝0,1，...,r;j＝0,1，...,s），反求出控制点d_i，j(i＝0,1，...,m;j＝0,1，...,s)，对控制顶点和数据点横、纵向进行平均规范积累弦长参数化从而得到节点矢量，这样就确定了一个B样条拟合曲面，该曲面逼近于已知的复杂曲面，但由于选取的数据点的数量、位置有可能存在噪声和摆动，所以计算出的拟合曲面在某些点处会过分偏离原有曲面。这时根据误差判断条件，实时调整偏离点处对应的控制顶点，便可修改拟合曲面的局部性状，达到更好的拟合效果。由于双三次B样条曲面具有良好的局部特性，工程实践中常常使用双三次B样条曲面来拟合复杂曲面，所以本发明采用双三次B样条曲面进行解释并运用四边域曲面拟合方法对其拟合。

四边界曲面拟合的具体步骤如下所示是：

1、边界预处理

2、空间散乱点的参数化

3、三角网格的建立

4、建立数学模型

第二步：为了得到散乱数据点的逼近曲面模型，散乱点的个数必须大于所求曲面的未知控制顶点数(l＞m×n)，这样才能保证未知数变量小于或等于方程数，目标函数为：

$I^r=\mathrm{\α}\underset{k=0}{\overset{j}{\mathrm{\Σ}}}{[S^r(u_k^{r-1},v_k^{r-1})-P_k]}^2+\mathrm{\β}[S_{\mathrm{uu}}^r{(u_k^{r-1},v_k^{r-1})}^2+S_{\mathrm{vv}}^r{(u_k^{r-1},v_k^{r-1})}^2+2S_{\mathrm{uv}}^r{(u_k^{r-1},v_k^{r-1})}^2]---\left(1.1\right)$

其中：

S^r(u,0)＝p(u,0);S^r(u,1)＝p(u,1)

S^r(0,v)＝p(0,v);S^r(1,v)＝p(1,v)    （1.2）

S_v ^r(u,0)＝p_v(u,0);S_v ^r(u,1)＝p_v(u,1)

S_u ^r(0,v)＝p_u(0,v);S_u ^r(1，v)＝p_u(1，v)

r表示曲面的迭代次数；s^r(u,v)是经过r次迭代后得到的曲面，并且 $s^r(u,v)=\underset{i=0}{\overset{m}{\mathrm{\Σ}}}\underset{j=0}{\overset{n}{\mathrm{\Σ}}}{N}_{i,3}\left(u\right)N_{j,3}\left(v\right)V_{i,j}^r;$

是曲面S^r(u,v)的u,v两向量的二阶导数和混合偏导数；P_k(k＝0,1,..l)为散乱数据点；

是散乱点P_k在r-1次迭代曲面上的参数值；α为逼近权，β为光顺权，且α+β＝1。当α值越大时曲线越靠近逼近点，则β较小，曲线越不光顺；当β越大时，线越光顺，则α变小曲线到数据点的距离则越大，所以应调节好α和β平衡曲线光顺和精度的关系。

由以上叙述可知目标曲面的数学模型公式(1.1)是带有复杂约束条件的二次优化问题，我们的目的就是运用寻优手段使目标函数I^r既能满足约束，又能达到最小，由此就可求得第r次几何迭代目标曲面的控制顶点为

(i＝0,1,…,m;j＝0,1,…,n)。

第三步：数学模型的求解

对于公式(1.1)的目标函数I^r的优化我们分为两步进行。由于约束条件只涉及到边界曲线和跨边界切矢曲线，而曲面的边界和跨边界切矢可以由曲面的边界和次边界控制顶点完全确定，因此我们可以先处理这些约束条件来得到目标曲面的边界和次边界控制顶点，根据公式(1.1)就可以得到我们所需要的拟合曲面。

曲面重建首先将离散点参数化，设计为三角网格进而初步拟合成第一层曲面（基面）如图1所示。采用Delaunay三角化方法对散乱点进行三角网格拟合，以人体模型数据为例，优化整体曲面的边界线和基曲面。

然后利用公式（1.1）、（1.2）运用最小二乘法反求出曲面控制点，将控制点进行编码产生初始群体，通过适应度函数f＝1/|(F(x，y，z)-z)²+(y(x,y)-y)²+(x-x_i)²-ε|求得最大值，也就是最终的曲面控制点以便拟合出基面，如图2所示。

因为人体模型是复杂样件模型，并不能用一张曲面表达，因此将曲面细化，就是从粗糙到精细的B样条控制网格确定，最后使B样条曲面逐步逼近给定的散乱点云，而且由粗到细的过程仅在误差超过预定的区域进行，具体流程如图3所示。

首先对反求出的控制点进行编码，对控制点数据分块得到相互连接的矩形区域，为保证曲面的连续性，将每块曲面的左上角和右下角数值记录，以便确定细化曲面的范围，对分块后曲面内的数据建立初始群体，判断它的迭代次数是否超出给定范围（初次分块迭代次数为零），如果超出则进入到上层计算重复分块动作，如果没有则接着从初始群体（含有N个基因）中随机选取第0代群体（含有n个），对其拟合并求出适应度，如果适应度达到给出的标准则停止循环，直接得到拟合曲面，如果不符合适应度的要求则根据适应度的大小对数据进行遗传和变异操作，判断新生代基因个数，如果小于初始群体个数则从余下的数据中随机选取使新生代群体达到n个，从而得到第一代群体，再进入到循环中直到满足停机条件得到最优的拟合曲面。

以双三次B样条曲面为例，方程为：

$p(u,v)=\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}{d}_{i,j}{N}_{i,3}\left(u\right)N_{j,3}\left(v\right)---\left(1.3\right)$

其中节点向量U和V，边界的控制点

由第三章内容得出，曲面数据点

及将其参数化为

为解方程要求控制点d_i，j(i＝2,3,…,m-1;j＝2,3,…,n-1)在最小二乘意义下逼近

即：

$f=\underset{k}{\overset{L}{\mathrm{\Σ}}}{[Q_k-p(u_k,v_k)]}^2=\underset{k}{\overset{L}{\mathrm{\Σ}}}{[Q_k-\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}{d}_{i,j}{N}_{i,3}\left(u_k\right)N_{j,3}\left(v_k\right)]}^2=\min ---\left(1.4\right)$

$f=\underset{k}{\overset{L}{\mathrm{\Σ}}}[Q_k-\underset{i=1}{\overset{m}{\mathrm{\Σ}}}{d}_{i,1}{N}_{i,3}\left(u_k\right)N_{\mathrm{1,3}}\left(v_k\right)-\underset{i}{\overset{m}{\mathrm{\Σ}}}{d}_{i,n}{N}_{i,3}\left(u_k\right)N_{n,3}\left(v_k\right)-\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,n}{N}_{i,3}\left(u_k\right)N_{j,3}\left(v_k\right)$

${-\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,n}{N}_{m,3}\left(u_k\right)N_{j,3}\left(v_k\right)-\underset{i=2}{\overset{m-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,j}{N}_{i,3}\left(u_k\right)N_{j,3}\left(v_k\right)]}^2---\left(1.5\right)$

令：

$r_k=Q_k-\underset{i=1}{\overset{m}{\mathrm{\Σ}}}{d}_{i,1}{N}_{i,3}\left(u_k\right)N_{\mathrm{1,3}}\left(v_k\right)-\underset{i=1}{\overset{m}{\mathrm{\Σ}}}{d}_{i,n}{N}_{i,3}\left(u_k\right)N_{n,3}\left(v_k\right)$

$-\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,n}{N}_{\mathrm{1,3}}\left(u_k\right)N_{j,3}\left(v_k\right)-\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,n}{N}_{m,3}\left(u_k\right)N_{j,3}\left(v_k\right)---\left(1.6\right)$

d_{(i-2)×(n-2)+j}＝d_i,j,t_{(i-2)×(n-2)+j}(w_k)＝N_i,3(u_k)N_j,3(v_k)

(i＝2，3，...，m-1；j＝2，3，...，n-1)    （1.7）

可得：

$f=\underset{k=1}{\overset{L}{\mathrm{\Σ}}}{[r_k-\underset{i=2}{\overset{m-1}{\mathrm{\Σ}}}\underset{j=2}{\overset{n-1}{\mathrm{\Σ}}}{d}_{i,j}{N}_{i,3}\left(u_k\right)N_{j,3}\left(v_k\right)]}^2=\underset{k=1}{\overset{L}{\mathrm{\Σ}}}{[r_k-\underset{s=1}{\overset{(m-2)\×(n-2)}{\mathrm{\Σ}}}{d}_s{t}_s\left(w_k\right)]}^2---\left(1.8\right)$

式中：

$D={\left[\begin{array}{c}{d}_1\\ .\\ .\\ .\\ d_{(m-2)\×(n-2)}\end{array}\right]}_{(m-2)\×(n-2)\×s}$ $R={\left[\begin{array}{c}{r}_1\\ .\\ .\\ .\\ r_L\end{array}\right]}_{L\×s}$

公式1.4则可改写成f＝(R-FD)^T(R-FD)＝min欲使目标函数f最小，应使它关于控制顶点D的导数为零，则可解得。

D＝F-R    （1.9）

假设f的值为α，对每一块曲面重新拟合分别得到f₁,f₂,f₃,f₄，使他们分别与α比较，以f_n-a＝min,(n＝1,2,3,4)为适应度进行判断，对该曲面内的控制点进行遗传、变异操作，从而选取最优的控制点拟合第n块曲面，当迭代次数超过30时或f_n-a＞0,(n＝1,2,3,4)则将第n块曲面平分为4块，在平分曲面时，应将该区面的左上坐标和右下坐标记录，并以这两点作为面片的边界点之一，这样在拟合结束时较容易拼接曲面片并保持拟合后的整体曲面的连续性，重复以上步骤直到得到最优曲面，如图4所示。

基于进化算法B样条曲面拟合是一种自适应细化B样条曲面拟合法，提高了拟合精度，并且具有目的性，一旦达到早期设定的精度则立即停止迭代输出曲面结果，减少了数据的计算量，本发明将其应用在人体建模，并证明了它的优越性。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。

Claims (1)

1.一种人体建模中曲面拟合的进化算法，其特征在于：包括以下几个步骤

第一步：根据复杂曲面上的呈矩形阵列的数据点p_i，j，（i＝0,1,...,r;j＝0,1,...,s），反求出控制点d_i，j(i＝0,1，...,m;j＝0,1，...,s)，对控制顶点和数据点横、纵向进行平均规范积累弦长参数化从而得到节点矢量，这样就确定了一个B样条拟合曲面，该曲面逼近于已知的复杂曲面，但由于选取的数据点的数量、位置有可能存在噪声和摆动，所以计算出的拟合曲面在某些点处会过分偏离原有曲面；这时根据误差判断条件，实时调整偏离点处对应的控制顶点，便可修改拟合曲面的局部性状，达到更好的拟合效果，由于双三次B样条曲面具有良好的局部特性，工程实践中常常使用双三次B样条曲面来拟合复杂曲面；采用双三次B样条曲面进行解释并运用四边域曲面拟合方法对其拟合；

所述四边域曲面拟合方法步骤如下：

1、边界预处理，

2、空间散乱点的参数化，

3、三角网格的建立，

4、建立数学模型；

第二步：建立目标函数为：

$I^r=\mathrm{\α}\underset{k=0}{\overset{j}{\mathrm{\Σ}}}{[S^r(u_k^{r-1},v_k^{r-1})-P_k]}^2+\mathrm{\β}[S_{\mathrm{uu}}^r{(u_k^{r-1},v_k^{r-1})}^2+S_{\mathrm{vv}}^r{(u_k^{r-1},v_k^{r-1})}^2+2S_{\mathrm{uv}}^r{(u_k^{r-1},v_k^{r-1})}^2]---\left(1.1\right)$

所述：

S^r(u,0)＝p(u,0);S^r(u,1)＝p(u,1)

S^r(0,v)＝p(0,v);S^r(1,v)＝p(1,v)

S_v ^r(u,0)＝p_v(u,0);S_v ^r(u,1)＝p_v(u,1)

S_u ^r(0,v)＝p_u(0,v);S_u ^r(1,v)＝p_u(1,v)

散乱点的个数必须大于所求曲面的未知控制顶点数(l＞m×n)，r表示曲面的迭代次数；s^r(u,v)是经过r次迭代后得到的曲面，并且

是曲面S^r(u,v)的u,v两向量的二阶导数和混合偏导数；P_k(k＝0,1,...l)为散乱数据点；是散乱点Pk在r-1次迭代曲面上的参数值；α为逼近权，β为光顺权，且α+β＝1；当α值越大时曲线越靠近逼近点，则β较小，曲线越不光顺；当β越大时，线越光顺，则α变小曲线到数据点的距离则越大，所以应调节好α和β平衡曲线光顺和精度的关系；所述可知目标曲面的目标函数是带有复杂约束条件的二次优化问题使目标函数I^r既能满足约束，又能达到最小，由此就可求得第r次几何迭代目标曲面的控制顶点为

(i＝0,1,…,m;j＝0,1,…,n)；

第三步：目标函数I^r的求解

目标函数I^r的优化分为两步；

1.采用Delaunay三角化方法对散乱点进行三角网格拟合，以人体模型数据为例，优化整体曲面的边界线和基曲面；

2.利用公目标函数运用最小二乘法反求出曲面控制点，将控制点进行编码产生初始群体，通过适应度函数f＝1/|(F(x，y，z)-z)²+(y(x,y)-y)²+(x-x_i)²-ε|求得最大值，即最终的曲面控制点，以便拟合出基面；

所述拟合出基面的过程：首先对反求出的控制点进行编码，对控制点数据分块得到相互连接的矩形区域，为保证曲面的连续性，将每块曲面的左上角和右下角数值记录，以便确定细化曲面的范围，对分块后曲面内的数据建立初始群体，判断它的迭代次数是否超出给定范围，即初次分块迭代次数为零；如果超出则进入到上层计算重复分块动作，如果没有则接着从初始群体中随机选取第0代群体，所述第0代群体含有n个，所述初始群体含有N个基因，第0代群体含有n个；对其拟合并求出适应度，如果适应度达到给出的标准则停止循环，直接得到拟合曲面，如果不符合适应度的要求则根据适应度的大小对数据进行遗传和变异操作，判断新生代基因个数，如果小于初始群体个数则从余下的数据中随机选取使新生代群体达到n个，从而得到第一代群体，再进入到循环中直到满足停机条件得到最优的拟合曲面。

Images