基于遗传多层B样条插值算法的三维显示方法

摘要

本发明提出了一种基于遗传多层B样条插值算法的三维显示技术，通过引入遗传算法整定控制点网格密度以及B样条插值层数，获得控制点网格密度以及B样条插值层数的最优解，再代入插值曲面模型，利用Matlab生成三维图像。通过自适应调节适应度函数，保证了插值曲面的平滑度。生成的三维图像，近似精度高，曲面较为平滑。本发明技术内容适用于三维图像生成，以及三维实时显示。

说明书

技术领域

本发明涉及一种虚拟仿真领域的三维显示方法，特别涉及一种参数经遗传算法优化的多 层B样条插值算法三维显示方法。

背景技术

在虚拟仿真领域中，三维显示技术作为视景的重要组成部分，在过去的数十年中得到了 深入地研究与广泛地应用。其中通过数据插值处理离散点的三维显示方法，得到了极大的关 注。目前的三维插值显示方法均要通过求解联立方程组来获得插值曲面，这种方法必须保证 方程式的数目必须大于或等于散乱点的数目，对于散乱点的数目有着严格的限制，因此并不 适用于大规模散乱点的情况。

为了解决大规模散乱点的插值问题，基于B样条插值算法及层次B样条概念发展出了多 层B样条插值算法。但是仍然无法完全解决三维插值显示技术的核心问题，即解决插值后曲 面近似精度与曲面平滑度之间的矛盾。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局搜索算 法，通过模拟达尔文“优胜劣汰，适者生存”的原理筛选出最优的结构，通过模拟孟德尔遗 传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。因此，本发明提出一种参 数经遗传算法优化后的多层B样条插值算法的三维显示方法，绘制的三维图像近似精度高， 插值曲面更加平滑。

发明内容

本发明提出一种绘制三维图像更加精确，插值曲面更加平滑的遗传多层B样条插值算法 的三维显示方法。

本发明的实现包括如下步骤：

步骤一：测定目标地形每个点的三维坐标，并在计算机中存储为散乱点文件；

步骤二：读取步骤一中存储的散乱点文件，根据散乱点的分布和疏密程度，确定控制点网格 密度m的范围及B样条插值层数h的范围；

所涉及的网格密度的参数m范围为m∈[q,100q]，且m为正整数，其中q为已知离散数据 点形成的方形区域内某行及某列包含的数据个数的最大值，且有m≥q；所涉及的B样条插值 层数h的范围为[1,64]；

步骤三：将控制点网格密度m和B样条插值层数h转换为格雷码，并以m在高位h在低位的 次序，将该两个参数整合为单个新参数X；

所涉及的整合表达式为：

步骤四：利用遗传算法对由步骤三整合得到的参数X求解最优解，并调节适应度函数以保证 插值曲面的插值精度；

所涉及的遗传算法比例选择算子表达式为

$P_i=\frac{f\left(X_i\right)}{\underset{j=1}{\overset{u}{\Sigma }}f\left(X_j\right)}---\left(2\right)$

其中，P_i表示选中X_i的概率，u为群体中个体总数，f(X_i)为每个个体的适应度，为群体适应度；f(X)为适应度函数；

所涉及的遗传算法交叉算子表达式为

$\left(\begin{array}{c}{X_1}^{\prime }=\alpha X_1+(1-\alpha )X_2\\ {X_2}^{\prime }=\alpha X_2+(1-\alpha )X_1\end{array}\right)---\left(3\right)$

式中，X₁′、X₂′表示交叉后的子代个体，X₁、X₂表示交叉前的两个父代个体，α为随机变 量，且有α∈[0,1]；

所涉及的遗传算法变异算子表达式为

${x_k}^{\prime }=U_{\min }^k+\beta (U_{\max }^k-U_{\min }^k)---\left(4\right)$

其中，为父代个体变异点的取值范围，x_k′为新的基因值，β为随机变量，且有 β∈[0,1]；

所涉及的交叉概率及变异概率表达式为

$\left(\begin{array}{c}{P}_c=0.9-0.3\frac{t}{T}\\ P_m=0.2-0.19\frac{t}{T}\end{array}\right)---\left(5\right)$

其中，P_c为交叉概率，P_m为变异概率，t为当前进化代数，T为进化总代数；

步骤五：依据步骤四中得到的参数X的最优解，得到控制控制点网格密度m和B样条插值层 数h的最优解，并进行格雷码解码，得到十进制格式的控制点网格密度m和B样条插值层数h 的最优解；

步骤六：将步骤五中得到的十进制格式的控制点网格密度m和B样条插值层数h的最优解， 代入插值曲面模型中，利用Matlab生成三维图像，实现基于遗传多层B样条插值算法的三维 显示方法；

所涉及的插值曲面模型为：

$F(m,h,x,y)=\underset{i=0}{\overset{h}{\Sigma }}{f}_i(x,y,m)---\left(6\right)$

其中，F(m,h,x,y)为插值曲面，f_i(x,y,m)为第i层数据插值结果，x、y为待插点坐标。

技术方案二：本发明针对曲面平滑度这一特性进行适应度函数的调节。在遗传算法中，使用 适应度函数来衡量在进化过程中每个个体的适应情况，适应情况较好的个体为较理想的结果。 当控制点网格上相邻的某控制点数值相差较大时，即

$\max \left\{\right|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{(i+1)j}}{{\Phi }_{\mathrm{ij}}}|,|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{i(j+1)}}{{\Phi }_{\mathrm{ij}}}|,|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{(i+1)(j+1)}}{{\Phi }_{\mathrm{ij}}}\left|\right\}>50\%---\left(7\right)$

系统则对其处以一个罚函数，以降低这类解的适应度；

当Φ_ij不满足式（7）时，

f′(X)=f(X)    (8) 当Φ_ij满足式（7）时，

f′(X)=f(X)-p(X)    (9)

其中，f′(X)为处以罚函数后的适应度函数，p(X)为罚函数。

本发明具有以下优点及有益效果：

利用多层B样条插值算法有效解决了具有大规模散乱点的插值问题；通过引入遗传算法 优化了参数控制点网格密度m和B样条插值层数h的选取，获取了上述两个参数的最优解， 有效提升了三维图像的曲面近似精度；通过调节适应度函数提升了曲面平滑度。

附图说明

图1本发明方法的工作流程图；

图2多层B样条插值原理图；

图3本发明方法涉及的参数编码示意图；

图4本发明方法涉及的遗传算法确定最优解流程图。

具体实施方式

本发明选取控制点网格密度和B样条插值层数作为研究对象并利用遗传算法整定这两个 影响插值曲面的重要参数，以此保证插值曲面在逼近度及平滑度方面均具有良好效果。结合 图1，图1所示为基于遗传多层B样条插值算法的三维显示方法工作流程图。具体步骤如下：

步骤一：本方法首先读入散乱点文件（每个点在空间的三维坐标必须已知），根据散乱点 的分布及疏密程度确定控制点网格密度的范围及B样条插值层数的范围；

本发明选择B样条插值方法对散乱点进行插值，根据多次仿真结果确定了已知点为散乱 点情况下的B样条插值基函数，并确定了控制点网格密度的范围及B样条插值层数的范围。

图2为多层B样条插值算法原理图。先确定底层控制点网格并计算待插点数据，然后将 其与真实值作差比较得到单层的插值误差，同时，将底层网格间距减为一半得到第一层控制 点网格，在得到待插点数据后作差计算插值误差，以此类推，每一层的网格间距均为上一层 的一半，最终得到多层B样条插值算法表达式及插值误差。其中，Φ_i(i=0,1,...,k)为第i层控 制点网格，f_i(x_c,y_c)为根据Φ_i得到的待插点数据，Δⁱz_c为i层B样条插值误差，其表达形式 为：

${\Delta }^i{z}_c=z_c-\underset{j=0}{\overset{i}{\Sigma }}{f}_j(x_c,y_c)---(1-1)$

易知，Δⁱz_c随着i的增大而减小，即近似精度随层数的增加而增高，平滑性虽较单层B样条 插值方法得到的曲面有所提高，但仍随层数的增加而降低。

步骤二：选取表征网格密度的参数m及B样条插值层数h作为参数进行遗传算法的整定；

本发明采用可以表征网格密度的参数m和B样条插值层数h作为遗传算法的参数。由于 二者数值的增大均可带来曲面近似精度增加、平滑度降低的效果，所以将两参数整合为一个 参数考虑。设q为已知离散数据点形成的方形区域内某行及某列包含的数据个数的最大值。 结合图3，图3所示为基于遗传多层B样条插值算法的参数编码示意图（以q=8为例），其中 max对应的编码情况为参数取最大值时的编码情况，min对应的编码情况为参数取最小值时 的编码情况，参数编码的前部分为表征网格密度的参数m的编码，后部分为表征B样条插值 层数h的编码，将两参数整合在一起进行编码，整合后的参数记作X。由于常见的二进制编 码方式在某两个邻近数之间会发生多位数字跳变的情况，如由7（二进制编码为0111）到8 （二进制编码为1000）四位数字均发生跳变，这将引起遗传过程的不稳定，所以本发明的基 因编码采用格雷码的形式，其相邻数字间只有一位数字变化。

参数m的范围为m∈[q,100q]且m为正整数，其中q为已知离散数据点形成的方形区域内 某行及某列包含的数据个数的最大值，要保证已知离散数据点均落在控制点网格的整数点上， 所以m≥q，由经验数据，当m>100q时网格密度过大导致平滑度严重受损，故取m∈[q,100q]。 由经验数据得，参数h的范围为[1,64]。

步骤三：经过遗传算法整定过程，即基因编码、适应度函数选择、遗传优化算子设计等 过程，对整定后的结果进行基因解码得到控制点网格密度和B样条插值层数的准确值；

本发明采用遗传算法确定m和h的最优解，并设计了适应度函数以保证插值曲面的插值 精度，结合图4，图4所示为遗传算法确定最优解流程图。具体流程有如下步骤：

（1）参数选取与基因编码。

本发明选取X（m和h整合后的参数）作为参数，基因编码详见附图3。

（2）适应度函数的选择。

在遗传算法中，使用适应度函数来衡量在进化过程中每个个体的适应情况，适应情况较 好的个体为较理想的结果。本发明就曲面平滑度这一特性进行适应度函数的设计。当控制点 网格上相邻的某控制点数值相差较大时，即

$\max \left\{\right|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{(i+1)j}}{{\Phi }_{\mathrm{ij}}}|,|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{i(j+1)}}{{\Phi }_{\mathrm{ij}}}|,|\frac{{\Phi }_{\mathrm{ij}}-{\Phi }_{(i+1)(j+1)}}{{\Phi }_{\mathrm{ij}}}\left|\right\}>50\%---(1-2)$

系统则对其处以一个罚函数，以降低这类解的适应度。

当Φ_ij不满足式(1-2)时，有

f′(X)=f(X)    (1-3) 当Φ_ij满足式(1-2)时，有

f′(X)=f(X)-p(X)    (1-4)

其中，f(X)为原适应度函数，f′(X)为处以罚函数后的适应度函数，p(X)为罚函数。

（2）遗传优化算子的设计。

1）选择算子

在选择算子的设计中，本发明使用比例选择算子来确定每个个体被选中的概率，其具体 方式为计算每个个体的适应度在群体适应度中占有比例的大小，即

$P_i=\frac{f\left(X_i\right)}{\underset{j=1}{\overset{u}{\Sigma }}f\left(X_j\right)}---(1-5)$

其中，P_i表示选中X_i的概率，u为群体中个体总数。

2）交叉算子

在交叉算子的设计中，交叉后的子代个体X₁′及X₂′是由交叉前的两个父代个体X₁及X₂ 进行线性组合得到的。本发明采用一随机变量α∈[0,1]作为比例系数，即

$\left(\begin{array}{c}{X_1}^{\prime }=\alpha X_1+(1-\alpha )X_2\\ {X_2}^{\prime }=\alpha X_2+(1-\alpha )X_1\end{array}\right)---(1-6)$

3）变异算子

在变异算子的设计中，本发明根据变异点的取值范围随机赋给变异点新的数值，具体设 计为

${x_k}^{\prime }=U_{\min }^k+\beta (U_{\max }^k-U_{\min }^k)---(1-7)$

其中，为父代个体变异点的取值范围，x_k′为新的基因值，β为一随机变量， β∈[0,1]。

4）交叉概率及变异概率的选取

由于交叉概率、变异概率过小会导致算法收敛太慢，过大会导致算法成为随机算法，失 去意义，所以本发明采用自适应的方法使交叉概率及变异概率随着进化代数根据公式（2）而 进行调整。

$\left(\begin{array}{c}{P}_c=0.9-0.3\frac{t}{T}\\ P_m=0.2-0.19\frac{t}{T}\end{array}\right)---(1-8)$

其中，t为当前进化代数，T为进化总代数。

步骤四：最后将这两个参数代入预先设计的插值曲面模型中，得到散乱点数据形成的三 维地形。

本发明选用Matlab作为生成三维图像的仿真工具，在利用遗传算法确定最优解后，将其 解码并将解码后结果带入插值曲面模型中，具体方法为：将m与h最优解的基因模型进行格 雷码的解码，得到十进制的最优解，再带入插值曲面模型：

$F(m,h,x,y)=\underset{i=0}{\overset{h}{\Sigma }}{f}_i(x,y,m)---(1-9)$

其中，F(m,h,x,y)为插值曲面，f_i(x,y,m)为第i层数据插值结果。