基于遗传算法的二次曲面提取技术研究

王长明， 聂建军

(1．新乡巴山航空材料有限公司 河南新乡453001;2．中原工学院 机电学院 河南郑州450001)

0 引言

据Mills统计，在传统机械零件中，85%的机械零件都可用平面、圆锥面、球面和圆柱面描述，其中圆柱面出现的频率就达到了73．5%［1］．由此看出，一般工业零件表面存在大量的平面和二次曲面．这些规则曲面可用少量几何参数精确表示，容易实现参数化设计与修改．如果统一使用NURBS曲面或三角Bezier曲面构造零件表面上的这些规则曲面，从精确建模的角度看，显然不合理．由于没有考虑到曲面的特殊性质，导致可用少量参数就能精确表示的曲面不得不用很多数据才能表示出来，甚至不能反映原来产品的设计信息和设计者的设计意图，而且纯NURBS曲面或三角Bezier曲面模型不利于转换到现有实体和特征造型系统中进行再设计，进而影响到产品的创新．因此，将零件中的规则曲面从测量数据中提取出来，并判断曲面类型，计算其几何参数，可以减少计算量，对提高重建模型的精度和速度具有十分重要的意义．

目前对二次曲面的提取，大多以三角化的测量数据为基础，但是，对海量点云数据进行三角化运算不仅效率低下，而且提取精度往往难以满足实际需要．本文针对离散点云数据直接进行二次曲面提取，首先对单一类型的点云数据块进行曲面识别，然后针对不同类型的二次曲面，利用其几何参数方程，实现基于实数编码遗传算法的二次曲面提取．

1 基于实数编码遗传算法的二次曲面提取

遗传算法(genetic algorithm，GA)［2］是由美国Michigan大学的Holland教授首先提出的一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与种群内部染色体的随机信息交换机制相结合的随机化搜索算法．遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态．

遗传算法大致包含7个基本步骤［3］:(1)对所求问题确定编码方案;(2)确定适应度函数;(3)初始化一个种群;(4)选择策略的确定;(5)选取遗传过程中合适的控制参数;(6)对整个种群反复进行选择、交叉、变异等遗传操作，使得整个种群不断趋向于最优值;(7)满足终止规则时，结束第(6)步的遗传操作．

空间离散点云提取二次曲面实际上是寻找这些离散点的最佳拟合二次曲面，属优化问题，理论上可用遗传算法求解．与传统优化方法相比，遗传算法采用交叉、变异等操作产生新个体，扩大了搜索范围，使优化结果为全局最优解，而非局部最优解．多数传统优化算法，当目标函数仅具有单极点时，通常表现出较高的效率，但当目标函数有多个极点时，往往会陷入局部最优解，而不能得到真正的全局最优解［4］．因此，本文提出采用遗传算法实现基于离散点云的二次曲面提取技术．

1．1 确定编码方案

遗传算法首先对实际问题的可行解进行编码，用字符串表达问题的解．字符串相当于遗传学中的染色体，其中的每个字符相当于一个基因．通常编码有二进制编码和实数编码两种方案．

二进制编码、解码操作简单易行，交叉、变异操作便于实现，但对于像二次曲面这样的多参寻优问题，若采用二进制编码，将导致编码过长，搜索效率降低．而实数编码具有搜索空间大、全局搜索能力强、搜索速度快等优点，同时可避免数制的转换，在数值优化方面具有更高的精度和效率，适合多参寻优问题［4］．因此，本文采用实数编码．

设变量x(j)为第j个优化变量，［L(j)，R(j)］为x(j)的变化区间，利用线性变换

将初始变化区间为［L(j)，R(j)］的第j个优化变量x(j)映射到［0，1］区间上的实数y(j)，y(j)为基因．实数编码直接把每个变量作为基因处理，也是一种没有编码的编码方式．经过这种实数编码，所有优化变量的取值范围都统一在［0，1］区间．

1．2 确定适应度函数

f(xi，yi，zi)反映点(xi，yi，zi)到二次曲面的代数距离，理想情况下，代数距离应该为0．因此，目标函数可

1．3 选择策略

为将已有群体变为下一代群体，遗传算法仿效进化论中“自然选择，适者生存”的原则，从当前群体中选择优良个体进行复制．选择依据是适应度的大小，适应度大的个体接受复制，使之繁衍;适应度小的个体予以删除，使之死亡．常见的选择策略有转盘式选择、规则化几何分布选择、锦标赛选择等，其中转盘式选择策略使用的最多［5］．

为方便计算机编程，对转盘式选择策略作部分改进．首先按照适应度值从大到小进行排序，将序号在前的m个个体复制两份，淘汰序号在后的m个个体，序号在中间的(N－2m)个个体复制一份．该做法能够保证群体尺寸不变，且编程非常容易．

1．4 遗传算法的实现

为加快向最优解收敛的速度，提高算法的执行效率，编程时对标准遗传算法引入以下策略［6］:

1)迭代初期使用大的交叉概率pc，小的变异概率pm，随后动态减小pc，增大pm．

2)分阶段判断终止条件．对父代种群进行交叉操作后，已初步实现父代解朝最优方向的改进．因此，交叉操作完成后，满足终止条件的最优解可能已存在，如再次进行下一步变异操作，可能会暂时破坏最优解，增加迭代次数，延长搜索最优解的时间．因此，在交叉操作完成后、变异操作执行前增加一次终止条件的判断，能够一定程度上提高执行效率．

3)变异操作时，总希望优秀个体被选中的机会大，较差个体被选中的机会小．因此，可用交叉操作产生的种群中的优秀个体替换最差个体，从而使参加变异的种群中优秀个体数量增加，被选中的机会也增大，使搜索更快的朝着有利于最优解的方向发展，该操作过程称为择优操作．

2 应用实例分析

本文采用大量模拟数据进行验证．假设点云数据已完成前期分割，对指定的单一曲面采用遗传算法进行提取实验．

2．1 遗传算法提取二次曲面

采用3组模拟数据进行实验，用计算机生成常用二次曲面离散数据(精确到小数点后5位)作为一组，然后分别在生成数据的基础上加入两种不同程度的高斯噪声(≤0．02和≤0．2)作为另外两组，如图1所示．

图1 实验用点云数据Fig．1 Experimental data of point cloud

遗传迭代时，取表面上100个数据点，遗传控制参数设为:群体规模N为100，交叉概率pc初始值为0．85，变异概率pm初始值为0．12，算法终止条件为误差平方和小于0．01或进化代数大于10 000代．

2．2 遗传算法提取二次曲面结果分析

遗传算法提取结果分析如表1所示．在正常数据情况下，遗传算法的迭代次数为362次，执行时间为14．95 s，当加入0．02噪声时，遗传算法的迭代次数为586次，执行时间为18．14 s;当加入0．2噪声时，遗传算法的迭代次数为726次，执行时间为26．84 s．

表1 遗传算法提取结果分析表Tab．1 Analysis table of extraction results using genetic algorithm

从表1可以看出，对正常数据或较少噪音的数据来讲，遗传算法计算精度非常高，随着噪音数据的增多增大，遗传算法仍具有很强的抗噪音能力，甚至在加入大量0．2噪音数据的情况下，依然能得到精度很高的提取结果，但效率稍低．

3 结论

本文详细介绍了基于实数编码遗传算法的二次曲面提取技术，并通过实例，针对不同类型的二次曲面，验证了实数编码遗传算法提取二次曲面的有效性，分析了实数编码遗传算法在曲面提取中的优缺点，对实际工程中应用实数编码遗传算法提取二次曲面具有一定的指导意义．结果表明:对正常数据或较少噪音的数据来讲，遗传算法计算精度非常高，随着噪音数据的增多增大，遗传算法仍具有很强的抗噪音能力，甚至在加入大量0．2噪音数据的情况下，依然能得到精度很高的提取结果，但效率稍低．本文研究结果建立在点云数据已前期分割为单一二次曲面的假定基础之上，对由多个二次曲面拼接而成的复杂曲面及二次曲面的判定方法有待进一步研究．

［1］ Yang M，Lee E．Segmentation of measured point data using a parametric quatric surface approximation［J］．Computer Aided Design，1999，31:449 －457．

［2］ Pottmann H，Hofer M，Odehnal B，et al．Line geomettry for 3D shape understanding and reconstruction［C］//Proceedings of the 8th European Conference on Computer Vision．Prague，2004:297 －309．

［3］ Marshall D，Lukacs G，Martin R．Robust segmentation of primitives from range data in the presence of geometric degeneracy［J］．IEEE Transaction on Pattern Analysis and Machine Intelligence，2001，23(3):304－314．

［4］ Sablatning R，Kampel M．Model-based registration of front and backviews of rotationally symmetric objects［J］．Computer Vision and Image Understanding，2002，87(1/2/3):90 －103．

［5］ Pottmann H，Peternell M，Ravani B．An instruction to line geometry with applications［J］．Computer Aided Design，1999，31(1):3－16．

［6］ Benko P，Varady T．Best fit translational and rotational surfaces for reverse engineering shapes［C］//9th IMA Conference on the Mathematics of Surface．London，2000:70－81．