隱形矯治方案中的牙齒運(yùn)動(dòng)路徑規(guī)劃方法研究

李占利，劉童鑫，李洪安，孫志浩

隱形矯治方案中的牙齒運(yùn)動(dòng)路徑規(guī)劃方法研究

李占利，劉童鑫，李洪安，孫志浩

(西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710054)

針對(duì)隱形矯治方案制定過(guò)程中傳統(tǒng)牙齒運(yùn)動(dòng)路徑規(guī)劃方法準(zhǔn)確度及效率低下問(wèn)題，根據(jù)牙頜評(píng)價(jià)參數(shù)提出新的目標(biāo)函數(shù)，再以傳統(tǒng)的人工蜂群算法(ABC)為基礎(chǔ)，通過(guò)外部存儲(chǔ)存放Pareto解集，然后以改進(jìn)的Harmonic距離對(duì)Pareto解集進(jìn)行更新，從而提高種群的多樣性。隨后通過(guò)Slerp球面線性插值以及線性插值獲取牙齒運(yùn)動(dòng)路徑初始值，與人工蜂群算法中的初始食物源生成方式相結(jié)合，生成更好的食物源。通過(guò)改進(jìn)后的人工蜂群算法采用優(yōu)先級(jí)方案對(duì)新目標(biāo)函數(shù)進(jìn)行優(yōu)化，得到牙齒的無(wú)碰撞運(yùn)動(dòng)路徑。通過(guò)驗(yàn)證本文方法的矯治方案效果，并與傳統(tǒng)目標(biāo)函數(shù)進(jìn)行比較，結(jié)果表明目標(biāo)函數(shù)可以生成更符合臨床治療要求的矯治方案，改進(jìn)ABC算法相比基本ABC能夠獲得更優(yōu)的路徑，縮短了矯治階段數(shù)，具有實(shí)用價(jià)值。

隱形矯治；路徑規(guī)劃；人工蜂群算法；多目標(biāo)優(yōu)化

無(wú)托槽隱形矯治技術(shù)作為一種新型口腔正畸技術(shù)，相對(duì)于傳統(tǒng)矯治技術(shù)有著便于拆卸、透明美觀、干凈衛(wèi)生的優(yōu)勢(shì)，在正畸治療中很受歡迎[1]。隨著計(jì)算機(jī)輔助設(shè)計(jì)與口腔正畸學(xué)的不斷發(fā)展與融合，使得隱形矯治計(jì)算機(jī)輔助系統(tǒng)成為研究熱點(diǎn)[2]。在隱形矯治過(guò)程中，由牙醫(yī)根據(jù)病人的畸形類型以及病人的訴求進(jìn)行矯治方案的規(guī)劃，即牙齒運(yùn)動(dòng)路徑上關(guān)鍵中間位置的確定，然后將方案通過(guò)隱形矯治系統(tǒng)可視化，并將各階段方案的變化展示給病人，病人同意后進(jìn)行各階段矯治器母模的加工[3]。

目前，牙齒運(yùn)動(dòng)路徑規(guī)劃局限于交互式手動(dòng)排列，操作如下：

(1) 選定合適的牙弓曲線模型；

(2) 記錄牙齒的初始坐標(biāo)與理想位置坐標(biāo)；

(3) 依照牙弓曲線，采用虛擬正畸軟件對(duì)牙齒進(jìn)行手動(dòng)平移、旋轉(zhuǎn)等操作，設(shè)計(jì)牙齒的運(yùn)動(dòng)路徑。

交互式手動(dòng)規(guī)劃效率低、誤差大、精度不夠，而且會(huì)因?yàn)橐曈X(jué)誤差影響最終結(jié)果。

針對(duì)上述問(wèn)題，部分學(xué)者做出了自動(dòng)化牙齒路徑規(guī)劃方法。王先澤等[4]提出基于粒子群(particle swarm optimization，PSO)的自動(dòng)化規(guī)劃方法，其針對(duì)手動(dòng)交互效率不高的缺點(diǎn)，以每顆牙齒選取的特征點(diǎn)到標(biāo)準(zhǔn)牙弓曲線的距離和作為目標(biāo)函數(shù)，以牙齒間的間距作為約束條件，實(shí)現(xiàn)了對(duì)牙齒路徑的自動(dòng)規(guī)劃，但未考慮牙齒旋轉(zhuǎn)角度的因素；MOTOHASHI[5]以牙弓線牽引的方式實(shí)現(xiàn)了牙齒運(yùn)動(dòng)路徑規(guī)劃，但未考慮如病人牙列擁擠，可導(dǎo)致牙齒間發(fā)生碰撞，實(shí)際效果不好的特殊情況；楊光[6]以牙齒移動(dòng)量及旋轉(zhuǎn)量為目標(biāo)函數(shù)，通過(guò)約束條件，以A*算法進(jìn)行優(yōu)化求解牙齒運(yùn)動(dòng)中間位置，從而獲取牙齒運(yùn)動(dòng)路徑，目標(biāo)函數(shù)中的旋轉(zhuǎn)量只考慮了旋轉(zhuǎn)角，未考慮軸傾角及轉(zhuǎn)矩角；張?bào)鉡7]提出單顆牙齒分別規(guī)劃的方法，并在牙齒移動(dòng)規(guī)劃過(guò)程中加入了碰撞檢測(cè)，得到牙齒正畸路徑規(guī)劃方法的可視化結(jié)果，因牙齒運(yùn)動(dòng)是多個(gè)牙齒同時(shí)移動(dòng)的，可能會(huì)發(fā)生碰撞。

牙齒運(yùn)動(dòng)是一個(gè)在三維空間中，涉及到平移、旋轉(zhuǎn)等多方面運(yùn)動(dòng)狀態(tài)的過(guò)程。在前人的研究中，由于運(yùn)動(dòng)過(guò)程中目標(biāo)函數(shù)的不足或是算法性能原因，使得規(guī)劃效果并不理想。針對(duì)傳統(tǒng)交互式牙齒路徑規(guī)劃方式以及目前自動(dòng)化牙齒路徑規(guī)劃方式中的缺陷，根據(jù)牙頜測(cè)量方法標(biāo)準(zhǔn)，提出更全面的參數(shù)目標(biāo)函數(shù)，然后以傳統(tǒng)人工蜂群算法為基礎(chǔ)，通過(guò)自適應(yīng)罰函數(shù)處理約束問(wèn)題，以外部存儲(chǔ)的方式存放Pareto解集，通過(guò)改進(jìn)的Harmonic距離對(duì)解集進(jìn)行更新，提高種群分布性。然后通過(guò)插值方法獲取牙齒運(yùn)動(dòng)理想路徑，結(jié)合人工蜂群算法的初始化過(guò)程，生成更好的初始食物源。最后以改進(jìn)后的人工蜂群算法對(duì)牙齒依照優(yōu)先級(jí)策略進(jìn)行路徑規(guī)劃。最后通過(guò)實(shí)驗(yàn)對(duì)本文改進(jìn)方法進(jìn)行驗(yàn)證及對(duì)比，結(jié)果表明，該方法規(guī)劃出的路徑更加精準(zhǔn)，牙齒運(yùn)動(dòng)代價(jià)更小。

1 數(shù)學(xué)模型

1.1 牙齒矯治方案定義

在牙齒矯治之前，醫(yī)生會(huì)根據(jù)患者的錯(cuò)頜類型、年齡以及個(gè)人訴求為患者規(guī)劃正畸方案，然后將整個(gè)矯治過(guò)程用計(jì)算機(jī)動(dòng)畫(huà)進(jìn)行模擬，記錄牙齒關(guān)鍵中間位置，也就是矯治過(guò)程中牙齒運(yùn)動(dòng)的路徑點(diǎn)，并將其展示給患者，記錄得到的關(guān)鍵中間位置，結(jié)合3D打印技術(shù)，制作每一階段的隱形矯治器。所以，在牙齒矯治方案中，關(guān)鍵的技術(shù)點(diǎn)在于規(guī)劃牙齒運(yùn)動(dòng)的路徑。對(duì)牙齒運(yùn)動(dòng)路徑規(guī)劃方案的評(píng)價(jià)是一個(gè)綜合了數(shù)學(xué)計(jì)算、計(jì)算機(jī)技術(shù)等多個(gè)方面的復(fù)合分析過(guò)程，其本質(zhì)就是綜合了牙科標(biāo)準(zhǔn)和生理限制對(duì)牙齒運(yùn)動(dòng)路徑的準(zhǔn)確性、時(shí)效性、經(jīng)濟(jì)性以及美觀程度等方面進(jìn)行評(píng)價(jià)。

1.2 矯治方案評(píng)價(jià)參數(shù)

1.2.1 Spee曲線和牙列擁擠度

Spee曲線[8](下頜牙列的縱頜曲線)是連接下頜切牙的切緣、尖牙的牙尖、前磨牙的頰尖以及磨牙的近遠(yuǎn)中頰尖的連線，可反映下頜平整度。文獻(xiàn)[9]指出，越是理想的牙頜形態(tài)，其Spee曲線就越平滑。在正畸學(xué)中，牙列擁擠度能直接決定是否需要進(jìn)行拔牙或擴(kuò)弓治療，如果患者牙列過(guò)于擁擠，則更易碰撞，與矯治器附件互相作用，導(dǎo)致牙齒無(wú)法到達(dá)理想位置，使矯治方案無(wú)法準(zhǔn)確實(shí)施，所以牙列擁擠度是矯治方案效果的評(píng)價(jià)依據(jù)。牙列擁擠度與Spee曲線有密切的關(guān)系，Spee曲線越平滑，牙列的擁擠度會(huì)變大，引起如牙齒向唇側(cè)突出的問(wèn)題。一般情況下，每平整1 mm的Spee曲線，需要縮小1 mm的牙弓間隙。所以Spee曲線深度和牙列擁擠度應(yīng)該控制在一個(gè)平衡的范圍內(nèi)，過(guò)度松散及擁擠均會(huì)給病人帶來(lái)不適。Spee曲線及咬合面關(guān)系如圖1所示。

圖1 Spee曲線

1.2.2 牙弓對(duì)稱性

牙弓對(duì)稱性[10]主要包含：①上下頜關(guān)于咬合面的對(duì)稱性；②同一牙列兩側(cè)牙齒關(guān)于牙弓中軸線的對(duì)稱性。牙弓對(duì)稱性如圖2所示。

圖2 牙弓對(duì)稱性

將上頜牙弓的中軸線投影到咬合面上，該投影與下頜中軸線方向向量之間的夾角越小則表明上下牙弓越對(duì)稱。

兩側(cè)牙齒之間的對(duì)稱性則分別在各自所在牙弓進(jìn)行，以上頜為例，將磨牙的近中舌側(cè)牙尖點(diǎn)、前磨牙的舌側(cè)牙尖點(diǎn)以及尖牙的牙尖點(diǎn)投影到咬合平面，向上頜牙弓中軸線作垂線，線段長(zhǎng)度代表牙齒到中軸線的距離，通過(guò)測(cè)量?jī)蓚?cè)牙齒到中軸線的距離，其差值越小則越對(duì)稱。

1.3 正畸參數(shù)計(jì)算

1.3.1 Spee曲線深度

口腔學(xué)將牙尖點(diǎn)中最低的點(diǎn)到第二磨牙遠(yuǎn)中頰尖與中切牙最高點(diǎn)所構(gòu)成的直線距離，稱為Spee曲線深度，即

其中，為咬合面的高度；為牙尖點(diǎn)高度，取最小值。為了使Spee曲線盡量平滑，式(1)需取極小值。

1.3.2 牙列擁擠度

牙列擁擠度，是指牙弓原本應(yīng)有的長(zhǎng)度與現(xiàn)有長(zhǎng)度之差。牙弓應(yīng)有長(zhǎng)度代表所有牙齒寬度之和。牙弓現(xiàn)有長(zhǎng)度是指當(dāng)前牙弓線長(zhǎng)度。

當(dāng)前牙弓線長(zhǎng)度可以用四次二維曲線來(lái)表示，將牙齒特征點(diǎn)投影到咬合面，然后用最小二乘法擬合出該曲線，即

則可得到牙弓線現(xiàn)有長(zhǎng)度為

牙列擁擠度為

其中，W為第顆牙齒的寬度。

1.3.3 牙弓對(duì)稱度

分析上下頜兩側(cè)同名牙齒之間的對(duì)稱度，將兩側(cè)牙尖到中軸線的距離差值的絕對(duì)值進(jìn)行累加，再除以牙齒的對(duì)數(shù)，即可求出牙弓對(duì)稱度[11]，即

其中，D為觀察者左側(cè)的牙齒到中軸線的距離；D為觀察者右側(cè)的牙齒到中軸線的距離；為牙齒數(shù)量，/2則是牙齒的總對(duì)數(shù)；當(dāng)越小，則兩側(cè)牙齒的對(duì)稱度越高。

1.3.4 牙齒移動(dòng)量與旋轉(zhuǎn)量

假設(shè)分割后的牙齒數(shù)量為，則顆牙齒中的每一顆從初始位姿到最終位姿都會(huì)構(gòu)成一系列的離散點(diǎn)，這一系列的離散點(diǎn)即為路徑點(diǎn)。其中每個(gè)路徑點(diǎn)就是每一矯治階段中該牙齒所在的位置，路徑點(diǎn)的總數(shù)需要在路徑規(guī)劃前確定，在每一階段中，牙齒的運(yùn)動(dòng)狀態(tài)又可分為平移與旋轉(zhuǎn)。

最終顆牙齒的正畸方案為

設(shè)第顆牙齒的運(yùn)動(dòng)函數(shù)為

其中，，，分別為第顆牙齒在局部坐標(biāo)系中沿3個(gè)方向的移動(dòng)量；，，分別為牙齒的轉(zhuǎn)矩角、軸傾角、旋轉(zhuǎn)角。

最終的目標(biāo)轉(zhuǎn)化為對(duì)下列的問(wèn)題求解

其中

其中，d為牙齒在第階段的移動(dòng)量，即

且，為牙齒在第階段的旋轉(zhuǎn)量。

1.4 目標(biāo)函數(shù)

經(jīng)過(guò)上述評(píng)價(jià)參數(shù)的建立，得到需要最優(yōu)化的目標(biāo)函數(shù)集合

1.5 約束條件

1.5.1 碰撞檢測(cè)

在牙齒移動(dòng)過(guò)程中，為避免同步移動(dòng)時(shí)的干涉問(wèn)題，故要在規(guī)劃過(guò)程中對(duì)牙齒進(jìn)行碰撞檢測(cè)，即

其中，c為當(dāng)前第顆牙齒是否在第階段與相鄰牙齒發(fā)生碰撞，默認(rèn)值為0，發(fā)生碰撞則為1；為判斷當(dāng)前路徑是否發(fā)生碰撞，當(dāng)=1為發(fā)生碰撞。

1.5.2 移動(dòng)量和旋轉(zhuǎn)量

在矯治過(guò)程中，牙齒一次平移量與旋轉(zhuǎn)量不能過(guò)大，有

其中，0取0.5 mm；0取3°。

1.5.3 牙齒間距

牙齒在沿正畸路徑移動(dòng)時(shí)需要考慮到牙齒間距，相鄰牙齒的間距不大于0.5 mm，即

其中，d()為第與第+1顆牙間距。

由上文可知，牙齒運(yùn)動(dòng)路徑規(guī)劃問(wèn)題的最終求解為

其中，()為需要最優(yōu)化的目標(biāo)函數(shù)集合；()為約束函數(shù)集合，式(18)要在滿足約束條件的情況下取得目標(biāo)函數(shù)最小值，因此牙齒運(yùn)動(dòng)路徑規(guī)劃問(wèn)題實(shí)際上是一個(gè)帶約束條件的多目標(biāo)優(yōu)化問(wèn)題。

2 基于人工蜂群算法的約束多目標(biāo)優(yōu)化

2.1 基本人工蜂群算法

為了解決全局優(yōu)化問(wèn)題，KARABOGA[12]提出了人工蜂群(artificial bee colony，ABC)算法。其是根據(jù)蜜蜂采蜜行為提出的一種優(yōu)化方法，可通過(guò)直接比較參數(shù)的優(yōu)劣來(lái)實(shí)現(xiàn)局部尋優(yōu)，快速收斂，從而迅速找出全局最優(yōu)值。

ABC算法將蜂種按分工分為雇傭蜂、觀察蜂和偵察蜂，其中雇傭蜂與食物源對(duì)應(yīng)，一個(gè)食物源為一個(gè)可能的解決方案，花蜜量代表該解決方案對(duì)應(yīng)的目標(biāo)函數(shù)值。觀察蜂以適應(yīng)度選擇食物源，經(jīng)過(guò)一定數(shù)量的選擇(控制參數(shù))，若食物源得不到更新，則棄之，該雇傭蜂變?yōu)閭刹榉洌俅嗡褜な澄镌?，且此偵查蜂又變回雇傭蜂。許多研究者利用人工蜂群算法易用、高效的特點(diǎn)，將其應(yīng)用于路徑規(guī)劃領(lǐng)域。初始人工蜂群算法的步驟如下：

步驟1.初始化。在初始化階段，假設(shè)蜂群規(guī)模為，則偵察蜂與觀察蜂的數(shù)量均為=/2，首先由偵察蜂隨機(jī)生成個(gè)食物源，即

其中，x為第個(gè)食物源的位置，=1,2,...,，=1,2,...,，為優(yōu)化問(wèn)題的維數(shù)；ub和lb分別為該食物源第維變量可取的上界和下界。

對(duì)每個(gè)初始食物源計(jì)算適應(yīng)度，并記錄其適應(yīng)度值設(shè)置為，并將最優(yōu)食物源記為best，初始化當(dāng)前食物源開(kāi)采次數(shù)變量()=0，適應(yīng)度為

步驟2.循環(huán)以下4步，直至到達(dá)終止條件。

(1) 雇傭蜂搜索。雇傭蜂在當(dāng)前食物源周圍搜索新的食物源，搜索策略為

其中，x為當(dāng)前食物源的一個(gè)相鄰食物源，通過(guò)計(jì)算新食物源的適應(yīng)度并與當(dāng)前食物源適應(yīng)度進(jìn)行比較，選擇適應(yīng)度較高的食物源，即

若成功更新了當(dāng)前食物源，則將新食物源()置零，否則()自增一次。

(2) 觀察蜂評(píng)價(jià)。觀察蜂可根據(jù)食物源的適應(yīng)度計(jì)算食物源的跟隨概率p

獲得p后，利用輪盤賭機(jī)制決定當(dāng)前食物源是否更新，若更新則按照雇傭蜂策略局部搜索新食物源。

(3) 偵察蜂搜索。對(duì)當(dāng)前食物源的()進(jìn)行判斷，當(dāng)超過(guò)搜索次數(shù)上限時(shí)，則按照式(19)全局搜索新的食物源來(lái)代替當(dāng)前的枯竭食物源。

(4) 記錄最好食物源。通過(guò)變量記錄當(dāng)前蜂群中的最大適應(yīng)度，并與進(jìn)行比較，且更新

若最好食物源得到更新，則同步更新種群中的最好食物源記錄best。

步驟3.當(dāng)?shù)螖?shù)超過(guò)，輸出最終解best。

2.2 算法優(yōu)化

2.2.1 動(dòng)態(tài)罰函數(shù)處理約束問(wèn)題

KARABOGA和BASTURK[13]通過(guò)Deb準(zhǔn)則解決了約束問(wèn)題，但也破壞了種群的多樣性，不利于算法收斂。本文提出使用罰函數(shù)將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，根據(jù)牙齒運(yùn)動(dòng)約束量，罰函數(shù)為

其中，g()為小于號(hào)約束條件；h()為等號(hào)約束條件；H(g())和H(h())為指示函數(shù)，分別為

其中，為懲罰系數(shù)，其值通過(guò)自適應(yīng)方法來(lái)選取，即

2.2.2 改進(jìn)的Harmonic距離排序構(gòu)造Pareto解集

本文通過(guò)外部存儲(chǔ)來(lái)存放Pareto解集，其計(jì)算及更新方式基于擁擠距離排序方法進(jìn)行優(yōu)化。擁擠距離排序方法在NSGA-Ⅱ[14]算法中被提出，用于描述某一最優(yōu)解周圍分布其他解的密度，便于排除冗余度大的解，保留其他具有多樣性的解，從而確保全局尋優(yōu)能力。文獻(xiàn)[15]指出，與擁擠距離相比，Harmonic距離用來(lái)反映個(gè)體間的擁擠程度效果更好，其表達(dá)式為

其中，為種群規(guī)模；d,j為個(gè)體x與x在目標(biāo)空間上的歐氏距離。

擁擠密度改進(jìn)方法一方面減少了計(jì)算量，提高了算法效率，另一方面計(jì)算擁擠距離時(shí)也考慮到了距離較遠(yuǎn)的個(gè)體，不影響解集的分布性，還考慮了當(dāng)前精英個(gè)體的影響，降低了較差個(gè)體帶來(lái)的影響。因此，改進(jìn)的Harmonic擁擠距離計(jì)算在提高效率的同時(shí)減少了不良影響，能準(zhǔn)確反映個(gè)體的分布情況，兼顧了種群多樣性。

綜上，本文Pareto解集更新方式為：設(shè)外部存儲(chǔ)Pareto解集的容量為。

步驟1. 在每個(gè)優(yōu)化目標(biāo)上，按目標(biāo)函數(shù)值對(duì)當(dāng)前所有個(gè)體進(jìn)行升序排列，選擇Pareto等級(jí)較優(yōu)的個(gè)體放入中，若容量超出限制，則跳至步驟2，否則繼續(xù)計(jì)算直至遍歷結(jié)束；

步驟2.利用式(29)計(jì)算目前解集中最劣Pareto等級(jí)個(gè)體的擁擠距離并降序排列，刪除擁擠距離較小的個(gè)體，如果有2個(gè)或更多最小解，隨機(jī)移除一個(gè)。

3 牙齒運(yùn)動(dòng)路徑規(guī)劃

3.1 結(jié)合牙齒運(yùn)動(dòng)路徑規(guī)劃的初始食物源生成

在人工蜂群算法中，初始化階段是由偵察蜂全局生成初始食物源。對(duì)于牙齒運(yùn)動(dòng)路徑規(guī)劃而言，最優(yōu)路徑實(shí)際上是直接從起始位姿平移旋轉(zhuǎn)到目標(biāo)位姿，是理想無(wú)碰撞情況下的路徑，而實(shí)際正畸過(guò)程中，會(huì)出現(xiàn)牙齒間的碰撞、約束及運(yùn)動(dòng)量約束等問(wèn)題，因此需要在理想路徑的基礎(chǔ)上優(yōu)化出無(wú)碰撞、滿足約束的路徑?；诖耍枋紫全@取理想狀態(tài)下的牙齒路徑，并以此作為初始食物源，然后結(jié)合人工蜂群算法對(duì)路徑進(jìn)行優(yōu)化。

3.1.1 旋轉(zhuǎn)量插值

圖3 線性插值

圖4 球面插值

在牙齒運(yùn)動(dòng)路徑規(guī)劃過(guò)程中，由于正畸力不便于控制，所以假設(shè)牙齒的角速度恒定，本文采用球面線性插值(spherical linear interpolation，Slerp) 來(lái)進(jìn)行牙齒旋轉(zhuǎn)量插值，即

3.1.2 平移量線性插值

在歐氏空間中，任意2點(diǎn)間的最短距離為 2點(diǎn)的直線距離，因?yàn)檠例X的平移量只需根據(jù)上文中移動(dòng)量約束進(jìn)行均勻插值，可分為若干正畸階段，如圖5所示，其中0i為牙齒初始位置；C為牙齒目標(biāo)位置。

圖5 平移量插值

3.1.3 初始食物源生成

在獲取了牙齒旋轉(zhuǎn)量及平移量插值后，也就獲得了牙齒在理想情況下的運(yùn)動(dòng)路徑，圖6為側(cè)切牙插值結(jié)果。此時(shí)結(jié)合人工蜂群算法中的偵察蜂搜索策略，以插值路徑作為初始值，生成初始食物源，步驟如下：

步驟1.設(shè)定牙齒平移步長(zhǎng)約束0和旋轉(zhuǎn)步長(zhǎng)限制0；

步驟2.根據(jù)0和0計(jì)算初步正畸階段數(shù)；

步驟3.根據(jù)正畸階段數(shù)對(duì)旋轉(zhuǎn)量進(jìn)行Slerp球面插值，對(duì)平移量進(jìn)行線性插值，獲取初始值；

步驟4. 由偵察蜂算法根據(jù)初始值生成個(gè)初始食物源。

圖6 側(cè)切牙插值結(jié)果

將人工蜂群算法的初始化方法與牙齒運(yùn)動(dòng)理想路徑相結(jié)合，對(duì)搜索方向加以引導(dǎo)，加快收斂速率的同時(shí)并未改變偵察蜂算法的初衷，確保了食物源的多樣性。

3.2 基于優(yōu)先級(jí)策略的牙齒碰撞避免

在正畸過(guò)程中，由于牙齒的畸形情況各不相同，且運(yùn)動(dòng)狀態(tài)各異，根據(jù)牙齒不同運(yùn)動(dòng)狀態(tài)以及不同的錯(cuò)位情況，將牙齒可能發(fā)生碰撞的情況分為圖7中的4類情況。

情況1：2顆牙齒相向運(yùn)動(dòng)，其牙根交錯(cuò)，此類情況在正畸過(guò)程中應(yīng)該避免牙根的碰撞，主要靠牙冠粘貼附件選擇合適的施力方式避免碰撞；

情況2：牙齒朝著同一方向運(yùn)動(dòng)，此時(shí)為一顆牙齒擋在另一顆前面，且占據(jù)了另一顆要去的位置，由于在正畸過(guò)程中牙齒是同步移動(dòng)的，可以優(yōu)先規(guī)劃前一顆，再規(guī)劃后一顆牙齒；

情況3：2顆牙齒朝著相反方向運(yùn)動(dòng)，此時(shí)主要考慮避免牙冠的碰撞情況；

情況4：已經(jīng)運(yùn)動(dòng)到最終位姿的牙齒占據(jù)了其他牙齒的路徑，此時(shí)被占據(jù)路徑的牙齒只能繞路以避免碰撞。

通過(guò)分析牙齒碰撞情況可以發(fā)現(xiàn)，牙齒運(yùn)動(dòng)過(guò)程的碰撞只發(fā)生于相鄰牙齒之間，不會(huì)與其他的牙齒發(fā)生碰撞，因此，可以根據(jù)各個(gè)牙齒與相鄰牙齒的不同情況，制定優(yōu)先級(jí)方案，實(shí)現(xiàn)無(wú)碰撞的牙齒運(yùn)動(dòng)路徑規(guī)劃。

優(yōu)先級(jí)方案在多機(jī)器人路徑規(guī)劃的研究中被廣泛使用[17]，通過(guò)為多個(gè)運(yùn)動(dòng)過(guò)程中可能存在沖突的機(jī)器人分配運(yùn)動(dòng)順序使其避免沖突，即：首先為每個(gè)機(jī)器人分配一個(gè)優(yōu)先級(jí)，然后按照優(yōu)先級(jí)對(duì)機(jī)器人遍歷，依次為機(jī)器人規(guī)劃路徑，避免與工作環(huán)境中的靜態(tài)障礙物和其他機(jī)器人發(fā)生碰撞。本文參考文獻(xiàn)[18]，在牙齒運(yùn)動(dòng)路徑規(guī)劃策略中引入優(yōu)先級(jí)方案，從而實(shí)現(xiàn)無(wú)碰撞正畸路徑。

3.2.1 優(yōu)先級(jí)算法

牙齒的碰撞只會(huì)發(fā)生在相鄰牙齒之間，因此只需考慮相鄰牙齒間的優(yōu)先級(jí)關(guān)系，本文采用的牙齒正畸優(yōu)先級(jí)判定算法是通過(guò)相鄰牙齒的位姿距離來(lái)判定牙齒間的優(yōu)先級(jí)，即

其中，L0i_0j中的0為牙齒初始位姿序號(hào)，m為牙齒理想位姿序號(hào)，i為牙齒序號(hào)，j為與i相鄰的牙齒；w1，w2為權(quán)值，取0.5；為牙齒間的歐氏距離；為牙齒姿態(tài)間的四元數(shù)距離，越大，表示其角旋轉(zhuǎn)越相似，同理可計(jì)算得到2顆牙齒的目標(biāo)位姿距離Lmi_mj。以2顆牙齒初始位姿距離與目標(biāo)位姿距離的差值進(jìn)行判斷，當(dāng)時(shí)，牙齒間碰撞會(huì)出現(xiàn)情況1或情況3，這2種情況說(shuō)明2顆牙齒優(yōu)先級(jí)相同，即PMi=PMj；當(dāng)時(shí)，此時(shí)為情況2，2顆牙齒運(yùn)動(dòng)方向相同，需要判斷其位姿前后順序，分別計(jì)算牙齒i的初始位姿到牙齒j的目標(biāo)位姿距離L0i_mj，以及牙齒j的初始位姿到牙齒i的目標(biāo)位姿距離L0j_mi，若，則PMi>PMj，否則PMi

通過(guò)以上策略，遍歷所有牙齒，即可得到牙齒間的優(yōu)先級(jí)關(guān)系，其中為牙齒不同的情形分類閾值，為牙齒移動(dòng)距離閾值，當(dāng)牙齒移動(dòng)距離小于時(shí)，最后考慮其運(yùn)動(dòng)路徑。

3.2.2 優(yōu)先級(jí)判定步驟

判定牙齒之間優(yōu)先級(jí)的具體步驟如下：

輸入：牙齒初始位姿及目標(biāo)位姿序列，空的牙齒正畸優(yōu)先級(jí)列表；

步驟1. 依次遍歷牙齒；

步驟2. 根據(jù)當(dāng)前牙齒的初始位姿和目標(biāo)位姿計(jì)算其位姿距離0i_mi，若0i_mi≤，則可定義為極小優(yōu)先級(jí)，跳轉(zhuǎn)至步驟1，否則，繼續(xù)步驟3；

步驟5. 遍歷結(jié)束，輸出。

3.3 牙齒運(yùn)動(dòng)路徑規(guī)劃

3.3.1 實(shí)際正畸階段數(shù)獲取

在生成初始食物源的過(guò)程中所獲取的正畸階段數(shù)是通過(guò)插值所得，考慮的是無(wú)碰撞的理想環(huán)境。但實(shí)際中，牙齒運(yùn)動(dòng)很可能會(huì)發(fā)生碰撞，所以，相較于理想情況，實(shí)際規(guī)劃過(guò)程中的牙齒路徑點(diǎn)數(shù)會(huì)發(fā)生變化，實(shí)際的正畸階段數(shù)也會(huì)大于無(wú)碰撞情況下的階段數(shù)。

為解決此問(wèn)題，在雇傭蜂計(jì)算適應(yīng)度函數(shù)時(shí)，不考慮牙齒移動(dòng)量和旋轉(zhuǎn)量約束，在整體規(guī)劃完成后，再對(duì)每一階段的路徑點(diǎn)按照平移量和旋轉(zhuǎn)量的約束進(jìn)行若干個(gè)路徑點(diǎn)的劃分，獲取真實(shí)情況下的正畸階段數(shù)。如圖8所示，點(diǎn)與是2個(gè)初始食物源，′和′分別是點(diǎn)和點(diǎn)鄰域內(nèi)的最佳食物源，由于牙齒運(yùn)動(dòng)量約束，會(huì)判斷′與′距離超過(guò)約束而放棄這2個(gè)食物源，那么就會(huì)錯(cuò)過(guò)最優(yōu)值，所以在對(duì)食物源進(jìn)行評(píng)價(jià)時(shí)，不對(duì)移動(dòng)量與旋轉(zhuǎn)量進(jìn)行約束，而是在規(guī)劃完成后，按照約束對(duì)路徑進(jìn)行劃分，如將′′劃分為′和′ 2個(gè)階段。

圖8 路徑點(diǎn)規(guī)劃示意圖

3.3.2 牙齒運(yùn)動(dòng)路徑規(guī)劃步驟

根據(jù)本文算法，結(jié)合正畸優(yōu)先級(jí)、牙齒運(yùn)動(dòng)路徑規(guī)劃實(shí)際情況，建立牙齒運(yùn)動(dòng)路徑規(guī)劃步驟：

輸入：待正畸牙齒T初始位姿0i、目標(biāo)位姿P序列；

輸出：各顆牙齒運(yùn)動(dòng)路徑關(guān)鍵中間位姿解集PA。

步驟1. 通過(guò)Slerp球面及平移量插值對(duì)每顆牙齒生成平移量插值1i~(m–1)i、旋轉(zhuǎn)姿態(tài)插值1i~δ(m–1)i；

步驟2.遍歷牙齒，根據(jù)優(yōu)先級(jí)方案為牙齒設(shè)置優(yōu)先級(jí)，獲取牙齒優(yōu)先級(jí)列表；

步驟3. 根據(jù)優(yōu)先級(jí)列表，按照優(yōu)先級(jí)順序?qū)ρ例X依次進(jìn)行路徑規(guī)劃；

步驟4. 初始化參數(shù)，主要包括路徑點(diǎn)數(shù)量、每個(gè)食物源搜索最大限制參數(shù)、當(dāng)前迭代次數(shù)=0，偵察蜂最大搜索次數(shù)，初始種群數(shù)量、偵察蜂和觀察蜂分別為=/2，外部存儲(chǔ)PA；

步驟5. 偵察蜂算法生成初始個(gè)食物源，然后轉(zhuǎn)變?yōu)楣蛡蚍洌?/p>

步驟6. 初始化當(dāng)前食物源搜索次數(shù)()=0，根據(jù)目標(biāo)函數(shù)值計(jì)算食物源適應(yīng)度，將非支配解放入PA中并計(jì)算擁擠距離，進(jìn)行排序；

步驟7. 雇傭蜂局部尋找新的食物源并計(jì)算適應(yīng)度，若優(yōu)于當(dāng)前食物源，則更新食物源位置，令次數(shù)()=0，更新外部存儲(chǔ)PA，否則次數(shù)()自增1；

步驟8. 觀察蜂計(jì)算跟隨概率，根據(jù)其尋找新食物源，然后轉(zhuǎn)變?yōu)楣蛡蚍溥M(jìn)行局部搜索，計(jì)算適應(yīng)度，判斷是否更新，并更新開(kāi)采次數(shù)()，更新外部存儲(chǔ)，若()>，則繼續(xù)步驟9，否則跳至步驟10；

步驟9. 放棄當(dāng)前食物源并轉(zhuǎn)化為偵察蜂，在決策空間隨機(jī)產(chǎn)生新的食物源，計(jì)算適應(yīng)度，更新()；

步驟10. 記錄食物源，并更新外部存儲(chǔ)解集，迭代次數(shù)自增1，若>，則輸出解集PA，否則跳轉(zhuǎn)至步驟8。

3.3.3 算法流程圖

算法流程如圖9所示。

圖9 牙齒運(yùn)動(dòng)路徑規(guī)劃流程圖

4 實(shí)驗(yàn)結(jié)果及分析

4.1 牙齒運(yùn)動(dòng)路徑規(guī)劃結(jié)果

實(shí)驗(yàn)中共用20口患者牙齒數(shù)據(jù)進(jìn)行了路徑規(guī)劃，其中選取患者為18歲男性為樣例，展示執(zhí)行優(yōu)化人工蜂群算法后所形成的牙齒矯治方案以及牙齒運(yùn)動(dòng)前后位置對(duì)比。

如圖10所示，以上頜為例，總共分為39個(gè)階段，算法中設(shè)置為200次，設(shè)置為 4 000次，種群大小為28。篩選出解集中的非支配解形成牙齒運(yùn)動(dòng)路徑，展示其中9個(gè)中間階段。圖中牙齒上的線段為每顆牙齒的特征線段，可以看出，經(jīng)過(guò)39個(gè)階段的平移與旋轉(zhuǎn)，各顆牙齒逐漸移動(dòng)至理想牙弓線上，牙齒特征線段也逐漸平滑(圖中被橢圓及矩形標(biāo)注的牙齒)。圖11展示了各顆牙齒的位姿變化?？梢钥闯?，上頜左側(cè)中切牙(牙號(hào)11)的旋轉(zhuǎn)量最大，旋轉(zhuǎn)角為順時(shí)針31.3°，兩側(cè)側(cè)切牙(牙號(hào)12，22)移動(dòng)量較大，分別為2.393 mm與2.418 mm。此例主要移動(dòng)量集中在前牙、尖牙及前磨牙，而兩側(cè)后磨牙移動(dòng)較少，在實(shí)際正畸治療中對(duì)后磨牙的矯正難度較大。

圖10 牙齒關(guān)鍵中間位置

4.2 不同目標(biāo)函數(shù)實(shí)驗(yàn)結(jié)果對(duì)比

牙齒移動(dòng)前后對(duì)比如圖11所示，僅以牙齒偏移量為目標(biāo)函數(shù)的規(guī)劃結(jié)果參數(shù)對(duì)比見(jiàn)表1，在優(yōu)化ABC算法中，由于對(duì)解集的更新方式進(jìn)行了改進(jìn)，提高了種群的分布性，可以獲得更好的解，與基本ABC算法相比，能夠以更小的牙齒移動(dòng)代價(jià)實(shí)現(xiàn)牙齒運(yùn)動(dòng)路徑規(guī)劃，到達(dá)理想位姿所需的矯治階段數(shù)也更少，從而縮短矯治周期，減輕患者負(fù)擔(dān)。從表2中可以看出，在目標(biāo)函數(shù)中加入了正畸參數(shù)之后，由于優(yōu)化目標(biāo)變多，會(huì)略微增加牙齒的偏移量，也會(huì)稍微增加矯治階段數(shù)。但從表3的牙頜參數(shù)中可以看出，牙弓對(duì)稱度、牙列擁擠度以及Spee曲線深度都有了很好的改善，正畸方案可取得更好的效果，可以說(shuō)明在目標(biāo)函數(shù)中加入正畸評(píng)價(jià)參數(shù)有利于提高矯治方案的準(zhǔn)確性和實(shí)用性。與此同時(shí)，優(yōu)化ABC算法的結(jié)果優(yōu)于基本ABC算法，證明本文在提升了ABC算法的種群多樣性之后，能夠獲得更好的優(yōu)化結(jié)果。

圖11 牙齒移動(dòng)前后對(duì)比

表1 僅考慮偏移量的規(guī)劃結(jié)果

表2 考慮正畸評(píng)價(jià)參數(shù)的規(guī)劃結(jié)果

表3 牙頜參數(shù)對(duì)比

5 結(jié)束語(yǔ)

本文基于傳統(tǒng)的隱形矯治方案生成方法，提出了新的目標(biāo)函數(shù)，以Spee曲線深度、牙列擁擠度、牙弓對(duì)稱度以及牙齒的偏移量為參數(shù)，減少了牙齒偏移量，在人工蜂群算法的基礎(chǔ)上加入搜索系數(shù)，提高了算法的效率，再對(duì)牙齒運(yùn)動(dòng)路徑進(jìn)行規(guī)劃。最后在仿真軟件進(jìn)行測(cè)試，并與其他方法進(jìn)行對(duì)比，結(jié)果顯示本文方法能較快生成較高準(zhǔn)確度的運(yùn)動(dòng)路徑，減少牙齒總的偏移量，生成的方案結(jié)果更接近理想牙頜，有效縮短矯治周期，具有實(shí)用意義。

[1] 盧海麗, 康娜. 無(wú)托槽隱形矯治器與固定矯治器對(duì)正畸患者牙周健康影響的研究現(xiàn)狀和進(jìn)展[J]. 口腔醫(yī)學(xué)研究, 2019, 35(7): 625-628. LU H L, KANG N. Research progress and current situation of influence of Invisalign system and fixed appliances on periodontal health[J]. Journal of Oral Science Research, 2019, 35(7): 625-628 (in Chinese).

[2] 范然, 鈕葉新, 金小剛，等. 計(jì)算機(jī)輔助牙齒隱形正畸系統(tǒng)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(1): 81-92. FAN R, NIU Y X, JIN X G, et al. Computer aided invisible orthodontic treatment system[J]. Journal of Computer-Aided Design ＆Computer Graphics, 2013, 25(1): 81-92 (in Chinese).

[3] GERARD BRADLEY T, TESKE L, ELIADES G, et al. Do the mechanical and chemical properties of InvisalignTMappliances change after use? A retrieval analysis[J]. The European Journal of Orthodontics, 2016, 38(1): 27-31.

[4] 王先澤, 李忠科, 馬亞奇, 等. 一種基于PSO的自動(dòng)化排牙方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(5): 211-212, 238. WANG X Z, LI Z K, MA Y Q, et al. Method of arranging teeth automatically based on PSO[J]. Computer Engineering and Applications, 2012, 48(5): 211-212, 238 (in Chinese).

[5] MOTOHASHI N. A 3D computer-aided design system applied to diagnosis and treatment planning in orthodontics and orthognathic surgery[J]. The European Journal of Orthodontics, 1999, 21(3): 263-274.

[6] 楊光. 牙齒矯正中牙齒移動(dòng)的仿真和優(yōu)化方法研究[D].西安: 西安科技大學(xué), 2011. YANG G. Research on simulation and optimization method for tooth movement in virtual orthodontics[D]. Xi’an: Xi’an University of Science and Technology, 2011 (in Chinese).

[7] 張?bào)? 牙齒正畸路徑規(guī)劃方法研究及可視化開(kāi)發(fā)[D]. 濟(jì)南: 山東大學(xué), 2016. ZHANG X. Research on teeth orthodontic movement path planning and visual development[D]. Jinan: Shan Dong University, 2016 (in Chinese).

[8] REKOW E D, ERDMAN A G, RILEY D R, et al. CAD/CAM for dental restorations-some of the curious challenges[J]. IEEE Transactions on Biomedical Engineering, 1991, 38(4): 314-318.

[9] 龔誠(chéng), 聞娟, 李佳嶺, 等. Spee曲線和擁擠度對(duì)口腔正畸模型2D與3D測(cè)量法的影響[J]. 口腔醫(yī)學(xué)研究, 2018, 34(6): 657-661.GONG C, WEN J, LI J L, et al. Influence of Spee’s curve and crowding on 2D and 3D measurement of orthodontic model[J]. Jouranal Oral Science Research, 2018, 34(6): 657-661 (in Chinese).

[10] STANLEY B, WILLAM P, DANA E, et al. The form of the human dental arch[J]. Angle Orthod, 1998, 68: 29-36.

[11] 聶瓊, 林久祥. Angle各類錯(cuò)(牙合)及正常(牙合)牙弓對(duì)稱性分析與比較[J]. 中華口腔醫(yī)學(xué)雜志, 2000, 35(2): 105-107. NIE Q, LIN J X. Analysis and comparison of dental arch symmetry between different Angle’s malocclusion categories and normal occlusion[J]. China Jouranal Stomatol, 2000, 35(2): 105-107 (in Chinese).

[12] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Erciyes University, 2005.

[13] KARABOGA D, BASTURK B. Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems[C]//Lecture Notes in Computer Science. Heidelberg: Springer, 2007: 789-798.

[14] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]//International Conference on Parallel Problem Solving From Nature. Heidelberg: Springer, 2000: 849-858.

[15] HUANG V L, SUGANTHAN P N, QIN A K. Multi-objective differential evolution with external archive and harmonic distance-based diversity measure[R]. Singapore: Nanyang Technological University, 2005．

[16] 畢曉君, 張磊, 肖婧. 基于雙種群的約束多目標(biāo)優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(12): 2813-2823. BI X J, ZHANG L, XIAO J. Constrained multi-objective optimization algorithm based on dual populations[J]. Journal of Computer Reasearch and Development, 2015, 52(12): 2813-2823 (in Chinese).

[17] 馬勇. 多移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 武漢: 華中科技大學(xué), 2012. MA Y. Research on path planning of multi-mobile robots[D]. Wuhan: Huazhong University of Science and Technology, 2012 (in Chinese).

[18] 付敬鼎. 隱形矯治技術(shù)中的正疇路徑規(guī)劃研究[D]. 西安: 西安科技大學(xué), 2018. FU J D, Research on the path planning for orthodontics in invisalign technique[D]. Xi’an:Xi’an University of Science and Technology, 2018 (in Chinese).

Research on path planning of teeth movement in invisible orthodontic

LI Zhan-li, LIU Tong-xin, LI Hong-an, SUN Zhi-hao

(College of Computer Science and Technology, Xi’an University of Science and Technology, Xi’an Shaanxi 710054, China)

Aimed at solving low efficiency and accuracy of path planning of teeth movement in invisible orthodontic schedule, a new method was proposed. First, a new objective function was proposed based on the evaluation parameters of teeth and jaws. Based on the traditional artificial bee colony algorithm (ABC), Pareto solution sets were stored through external storage, and then the Pareto solution set was updated by the improved Harmonic distance, thus diversifying the population. Then, the Slerp spherical linear interpolation and linear interpolation were used to obtain the initial value of the tooth movement path, which was combined with the initial food source generation method in the artificial colony algorithm to generate a better food source. Finally, the new objective function was optimized by the priority scheme of the optimized ABC, leading to the collision-free path for the teeth movement. The experiment showed the effect of the proposed method and compared it with the traditional objective function. The results show that the proposed objective function can generate a more suitable schedule for clinical orthodontic. The improved algorithm can result in a better path and reduce the number of orthodontic stages, and is of practical value.

invisible orthodontic; path planning; artificial bee colony algorithm; multi-objective optimization

TP 391

10.11996/JG.j.2095-302X.2020040556

A

2095-302X(2020)04-0556-11

2019-12-30；

2020-04-14

14 April, 2020

30 December, 2019;

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2019JM-162；2019JM-348)；西安科技大學(xué)博士啟動(dòng)金項(xiàng)目(2019QDJ007)

Natural Science Basic Research Plan in Shaanxi Province (2019JM-162; 2019JM-348); Ph.D Research Startup Foundation of Xi’an University of Science and Technology (2019QDJ007)

李占利(1964–)，男，陜西周至人，教授，博士，博士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理。E-mail：lizl@xust.edu.cn

LI Zhan-li (1964–), male, professor, Ph.D. His main research interests cover computer graphics, image processing. E-mail: lizl@xust.edu.cn

李洪安(1978–)，男，山東武城人，副教授，博士，碩士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)圖形圖像處理。E-mail：an6860@126.com

LI Hong-an (1978–), male, associate professor, Ph.D. His main research interests cover computer graphics, image processing. E-mail: an6860@126.com