版权信息
主管单位:北京电子控股有限责任公司
主办单位:北京电子控股有限责任公司
出版地区:北京
国际刊号:1003-9767
国内刊号:11-2697/TP
出版周期:半月刊
期刊开本:A4
审稿周期:1-2天
所在栏目:电信技术
综合影响因子:0.125
复合影响因子:0.05
期刊级别: 省级期刊
杂志社地址:北京市东城区北河沿大街79号万科·北河沿甲77号

《信息与电脑》录用通知

您的当前位置:首页 >> 录用通知

基于遗传算法的虚拟牙齿矫正路径规划
 

基于遗传算法的虚拟牙齿矫正路径规划

王增波[1],向海兰,贺丹,熊湘林

(衡阳师范学院 数学与统计学院,湖南衡阳 421002

  :在隐形牙齿矫正仿真系统中,通过前期完成工作的基础上采用遗传算法对分割出来的牙齿实现了多颗牙齿同时移动的路径规划。通过反复实验确定了算法中的各种遗传参数和操作,特别是适应度函数中加入了牙齿间的碰撞检测,更符合真实的治疗场景。最后,通过反复实验验证了该方法的有效性。

关键词: 遗传算法;牙齿矫正;移动路径规划;适应度函数;碰撞检测

中图法分类号: TP301

Path Planning for Virtual Orthodontics Treatment Process Based on Genetic Algorithm

WANG Zeng-bo, XIANG Hai-lan, HE Dan, XIONG Xiang-lin

(College of Mathematics and Statistics Hengyang Normal University Hengyang Hunan 421002 China)

Abstract: In the virtual orthodontic treatment process simulation system, the genetic algorithm is used to realize the path planning of multiple teeth moving simultaneously on the basis of the preliminary work. Through repeated experiments, various genetic parameters and operations in the algorithm were determined. In particular, the collision detection was added to the fitness function, which is more in line with the real treatment scene. Finally, the effectiveness of the method is verified by repeated experiments.

Key words: genetic algorithmorthodontics treatmentpath planningfitness functioncollision detection

1  引言

现在很多医院采用隐形牙齿矫正手术患者进行牙齿矫正,为了在牙齿矫正手术前能够让医生规划牙齿的矫正路径和让用户体验未来的矫正过程,最终可利用仿真系统计算出来的过程数据为患者量身定制一系列近乎无法察觉的透明牙托来完成整个矫正疗程,因此开发一套虚拟矫正仿真系统就具有非常重要的现实意义。整个虚拟仿真过程要经历三维牙齿模型数字化扫描、三维拓扑重构[1]、牙颌组织分割、牙齿交互重排、牙齿移动路径规划等诸多过程。其中,牙齿移动路径规划是一项非常重要的工作,要根据牙齿的初态和终态通过算法自动生成中间的位置信息,初态为患者术前的牙齿位置,终态是医生根据患者的牙颌情况确定的矫正后的理想位置。很多情况下,会存在需要对几颗牙齿同时进行矫正,这就是一个并行的过程,要实现多颗牙齿同时移动传统优化方法在这类问题中缺乏优势,很多智能算法却能快速求得优化解。

这里所研究的问题属于虚拟移动路径规划问题,它是指在虚拟环境中,存在障碍物的工作环境中寻找一条在给定起点到终点位置前提下的最优运动路径,并使物体在运动过程中能避免碰撞所有的障碍物。在这里我们可以主要借鉴现有的移动机器人的路径规划方法来实现牙齿移动的路径规划,障碍物被认为是其它的牙齿,为了牙齿间避免碰撞,这就需要在移动过程中进行碰撞检测,碰撞检测方法见文献[2]

在动态环境或未知环境中的移动路径规划,需要解决的主要问题是移动对象与运动障碍物的避碰问题。国内外有许多的专家学者从人工势场法[3]、栅格法[4] 、自由空间法等传统方法进行过路径规划的研究,也有采用各种智能算法如模糊逻辑[5]、神经网络[6]和遗传算法[7]对问题进行求解。其中Woong- Cie Han[8]采用了遗传算法,算法中采用安全和距离作为算法的适应度函数评估系数实现了实时路径规划。J ianping Tu[9]在用遗传算法求解时,编码方式采用变长和相对位置的方法,有效减少了算法中的个体长度。国内的袁曾任等[10]提出了一种基于改进的栅格法和回归预测相结合的方法,对移动对象进行路径规划并实现避撞和导航任务。

牙齿矫正的过程是多颗牙齿同时矫正的过程,虚拟牙齿矫正仿真系统需支持多颗牙齿同时移动,遗传算法存在内在的并行性,因此本文将采用遗传算法对牙齿移动的路径进行规划。

2 问题的定义

本论文研究牙齿的移动环境为三维空间,必须确定单颗牙齿矫正过程中的起止位置,初始位置是对患者治疗前的牙齿进行三维重建得来的数据,终止位置是由专业牙科医生根据对患者的临床诊断确定需要矫正的牙齿。从医学角度来看,我们要通过牙齿的矫正得到一副整齐漂亮的牙列,必须建立一条理想牙弓形态曲线,并以该曲线为参照来调整牙齿的位置和姿态,牙弓线的绘制方法可参考文献[11]。医生可参照牙弓形态曲线并综合考虑整个牙颌组织的情况在虚拟矫正仿真系统中通过交互式操作确定矫正后的位置。

由于在牙齿移动过程中单颗牙齿之间可能会发生相互之间的碰撞,仿真系统中可能出现牙齿间的干涉问题,因此在仿真过程中的碰撞检测将是遗传算法中适应度函数的重要因素。我们的目标是要设计一条路径使得牙齿之间不发生干涉,并使得所有牙齿在符合患者牙颌组织可接受强度(由专业牙齿医生根据临床经验确定矫正周期实现)的前提下尽快地从初始位置到达终止位置。我们建立牙齿移动路径规划的数学模型,具体定义为:

(1)牙齿的移动是一个连续的过程,仿真过程中我们利用基于slerp运算的四元数插值方法[31]实现移动过程的离散化,这样能够减少计算量并得到一个平滑移动的路径。

(2)按照前面的方法,我们就可以把每颗牙齿的移动路径简化成起止位置状态间的一系列的散离点状态,散离点间的距离和角度根据路径长度和牙列的整体情况进行确定,这些散离点我们把它称为路径点。

(3)每颗牙齿都有从起始位置到终止位置的若干个路径点,我们可以利用前面讲到的碰撞检测算法,计算出相邻牙齿路径点间的干涉情况,得到一个碰撞检测表作用适应度函数的其中的一个参数,这样才能避免在仿真过程中出现牙齿间的干涉问题。

3 遗传算法实现牙齿移动的路径规划

3.1 编码

染色体的表示和编码是运用遗传算法的关键步骤。对于牙齿移动路径规划这个具体问题来说,很自然地考虑到可由路径中的点的序列来构成。我们用二进制的01表示牙齿是否移动到下一个路径点,如:0110表示在整个移动时间序列中,时间序列10表示走了0步停止在原处,时间序列21走了1步进入了第一个路径点,时间序列31表示走到了第二个路径点,时间序列40表示停止在第二个路径点了。因此,把染色体用一个只存储01的数组来表示,图1表示了染色体的基因存储结构,一个染色体把所有需移动牙齿的路径移动信息都整合在了一起,不需要移动的牙齿自然就不被编入到基因组中。在这里每颗牙齿的基因个数(二进制位数)要根据的实际情况计算得到,并不固定在一个确定的长度。

1 牙齿移动的染色体表示

3.2 路径评估的适应度函数计算

遗传算法根据适者生存原则,从当前群体中选择出比较适应环境的下一代个体,这些被选中的个体用于繁殖下一代。在选择时,以适应度函数为选择原则。

对路径优劣程度的评估就可以作为遗传算法中染色体的适应度。因此要将我们规划路径时所作的要求包含进去,并用数值的形式体现出来,以便进行比较和衡量。对于可行路径的适应度我们要综合考虑碰撞强度、路径长度、距离长度这几个因素。这样看来该问题是一个典型的多目标优化问题,多目标进化算法已用于求解该类问题,但通常的算法过程复杂或者需要人工干预。为了减少运算量,我们在这里采用“加权和”形式求得综合反映各子目标要求的单一适应度函数,将多目标问题转化为可利用单目标遗传算法求解的等效问题:

式中为个体X关于子目标的归一化适应度。在此基础上,借鉴人工神经网络中的后向传播(Back-propagation)学习算法,令权值系数跟随的优化程度动态地更新:

.

式中01,可统一选取为0.8为第t代种群关于的平均适应度。这样优化程序较高的子目标的优化压力将逐渐减小,优化程序较低的子目标则相反,从而使遗传搜索能够兼顾各个子目标;但仍可利用的初始值来表达对子目标的重视程序。

这里的碰撞强度就是参照前面提到的碰撞检测表,在这个表里保存任两个相邻牙齿的路径点间的碰撞检测情况,通过它计算出路径点间发生碰撞的次数。所谓路径长度即牙齿从初始位置到终止位置间的路径点的数目,路径的长度是决定到达终点快慢程度的首要因素,在适应度函数里所占的权重也最大,在这里设置所有的路径长度一样,即取所有牙齿所需路径点的最大值。所谓距离长度即指牙齿当前位置距离终点位置的步长。

我们令(t)= d(t),(t)= c(t),则一条可行路径P(n颗牙齿,路径长度为m),其适应度函数定义如下:

这里分别表示距离长度、碰撞强度在适应度函数中的权重。其它参数分别定义如下:

d(t)表示归一化的距离长度,计算如下:

其中表示牙齿i的距离长度。

c(t)表示归一化的碰撞强度,计算如下:

其中表示牙齿ki当前所处路径点与邻接牙齿ki+1当前所处路径点的碰撞函数,当牙齿kiki+1发生碰撞时函数值为1,否则为0

3.3 路径规划的遗传操作

根据牙齿移动路径规划问题的特点,本文使用选择、交叉和变异三种遗传操作算子。

(1)选择操作

选择(Selection),就是从群体中挑选出一些个体,将其作为创建下一代个体的基因库(gene base)

我们在规划过程中采用赌轮选择方法,该方法使个体被选中的几率和它们的适应度函数值成比例,适应度函数值越大的染色体,被选中的概率也越大。这并不能保证适应度函数值最高的个体一定能选入下一代,仅仅说明它有最大的概率被选中。

(2)交叉操作

在生物的自然进化过程中,两个同源染色体通过交配而重组,形成新的染色体,从而产生出新的个体或物种。

常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉、均匀两点交叉[37,38]等。上面的例子就是使用了单点交叉算子进行交叉操作。

交叉算子通过对所选择的两个父代染色体的基因片断互换形成子代个体,交叉操作的方式很多,但对于由路径点序列构成的染色体来说,只有单点交叉和多点交叉具有实际意义,而多点交叉与单点交叉相比并无本质差别,因此本文中采用单点交叉的方法。

(3)变异操作

交叉算子最后不可避免的使群体失去多样性,从而造成程序陷入局部,达不到全局最优解的现象。变异算子在遗传算法中起着相当重要的作用,它不仅被视为找回因交叉操作而遗失的优良基因的手段,而且还是优化性能的有力工具。

我们实现变异操作的方法是沿着一个染色体的长度,一位一位地进行考察,并按一定的几率下将其中某些位进行翻转。

3.4 路径规划终止条件

作为一种算法不能无限地执行下去,要在合理的时间内终止。

在这里我们对遗传算法的终止采用最大遗传代数和设定收敛条件的复合准则。当遗传算法满足设定的收敛判断条件时,遗传算法终止;若进化了指定的代数仍然没有满足设定的收敛判断条件,也令遗传算法终止。

本文将判断算法收敛的条件设为:若连续进化5代,最优解均未发生变化,且种群的平均适应值提高不足1%,或算法进化代数已达到了设定的最大值。

4 实验结果与分析

从前面对遗传算法的分析我们可以看到,组成算法的每个部分都有许多参数,如变异概率、交叉概率、群体大小等,不同的参数取值使遗传算法体现不同的行为。

我们通过反复实验,群体规模选择140,交叉概率选择0.7,变异概率选择0.001,能够得到良好的规划效果。

另一个系统参数是个体的长度,它对算法的性能也有影响。由于GA是一个概率过程,所以每次迭代的情况是不一样的,系统参数不同,迭代情况也不同,也直接影响了牙齿的矫正过程。

我们通过实验分析遗传算法中各参数对算法性能的影响,以便为的实际应用选择参数提供依据。同其它启发式搜索技术一样,遗传算法也是一种随机性的技术,因此我们不能根据一次运行的结果来判断参数的好坏。在下面的试验过程中,我们对于每一种环境都运行10次,并记录下每次实验的基因长度、染色体长度和遗传代数,表1和表1中列出了在不同的基因长度和染色体长度情况下得到可行解的时间效率,在这里每遗传100代耗时5.729秒。

为了分析算法,在这里我们针对矫正16颗牙的情况下进行统计。如下表1所示,基因长度与染色体长度要相互配合才能得到良好的规划效果,表格里的数据都可以应用到矫正过程中作为参考。

矫正16颗牙齿时,基因长度取6时染色体长度取144,基因长度取7时染色体长度取160,基因长度取8时染色体长度取176,规划效果良好,效果参见图2-5

1 规划16颗牙齿的情况

基因长度

染色体长度

最小遗传代数

最大遗传代数

平均遗传代数

6

112

85

184

133.6

6

144

51

204

107.6

6

192

132

457

310.7

7

160

130

500

189.9

7

168

159

1497

516.7

8

176

100

1497

543.9

8

192

112

2064

1033.8

2 调整单颗牙齿

3矫正过程图一

4 矫正过程图二

5 矫正后的效果图

5 结论

本文研究了利用基于遗传算法实现虚拟牙齿矫正仿真的路径规划方法,在完成的三维牙齿数字模型拓扑重构、牙颌组织分割等基础工作完成的前提下,实现了多颗牙齿的同时移动路径的规划工作,仿真系统的运行效果较理想。当然这个系统还必须通过一段时间的临床实验才能真正投入使用,后期可以根据实际临床情况对一些参数进行调整就能适应牙科医生的要求,未来还要考虑增加牙齿移动过程中牙龈组织的变形仿真,这样该系统将是更加的完善。

参考文献:

[1] 王增波.STL格式文件的快速拓扑重建算法[J].计算机应用,2014,34(09):2720-2724.

[2] 刘涛,王增波,李占利.碰撞检测过程中的包围盒技术及应用研究[J].西安科技大学学报,2006(03):395-399.

[3] KHATB O. Real-time obstacle avoidance for manipulators and mobile robots[A]. IEEE International Conference on Robotics and Automation[C], St Louis,  1985.500-505

[4] 马浩浩,郑紫微.基于栅格模型下机器人路径规划的改进遗传算法[J].无线通信技术,2019,28(02):55-57+61.

[5] MARTIVEZA,'IUNSTEL E, JARNSH D IM. Fuzzy logic based collision avoidance for a mobile robot[A]. Third International Conference on Industrial Fuzzy Control and Intelligent Systems[C]. Houston, 1993, 66-69.

[6] AHMED F, CHIN CLP  An efficient obstacle avoidance scheme in mobile robot path planning using polynomial neural networks[A].Aerospace and Electronics Conference[C].1993,2, 848-850.

[7] 王功亮,王好臣,李振雨,李家鹏.基于优化遗传算法的移动机器人路径规划[J].机床与液压,2019,47(03):37-40+100.

[8] HAN W-G, BAEK S-M, KUC T-Y Genetic algorithm based path planning and dynamic  obstacle avoidance of mobile robots[A]. 1997 IEEE International Conference on SMC[C]. Fbrida, 1997,3, 2747-2751.

[9] TU JP, YANG 3M. Genetic algorithm based path planning for a mobile robot[A]. ICRA'03[C]. Taipei, 2003, 3. 1221-1226.

[10] 哀曾任,高明.在动态环境中移动机器人导航和避碰的一种新方法[J].机器人.2000, 22 (2): 81-88.

[11] 王增波.虚拟牙齿矫正过程中的牙弓绘制方法研究[J].贵州大学学报(自然科学版),2011,28(06):62-65.

 



[1]基金项目湖南省教育厅项目15C0201湖南省大学生研究性学习和创新性实验计划项目CX1704,教育部产学合作协同育人项目201702030029

作者简介王增波(1975-),男,湖南衡阳人,讲师,硕士学位,主要研究方向为数学建模、智能算法、计算机图形学。

推荐资讯