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

隱形矯治方案中的牙齒運動路徑規(guī)劃方法研究

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

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

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

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

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

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

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

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

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

交互式手動規(guī)劃效率低、誤差大、精度不夠，而且會因為視覺誤差影響最終結(jié)果。

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

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

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

1.1 牙齒矯治方案定義

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

1.2 矯治方案評價參數(shù)

1.2.1 Spee曲線和牙列擁擠度

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

圖1 Spee曲線

1.2.2 牙弓對稱性

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

圖2 牙弓對稱性

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

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

1.3 正畸參數(shù)計算

1.3.1 Spee曲線深度

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

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

1.3.2 牙列擁擠度

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

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

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

牙列擁擠度為

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

1.3.3 牙弓對稱度

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

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

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

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

最終顆牙齒的正畸方案為

設(shè)第顆牙齒的運動函數(shù)為

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

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

其中

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

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

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

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

1.5 約束條件

1.5.1 碰撞檢測

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

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

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

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

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

1.5.3 牙齒間距

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

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

由上文可知，牙齒運動路徑規(guī)劃問題的最終求解為

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

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

2.1 基本人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法優(yōu)化

2.2.1 動態(tài)罰函數(shù)處理約束問題

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

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

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

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

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

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

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

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

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

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

3 牙齒運動路徑規(guī)劃

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

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

3.1.1 旋轉(zhuǎn)量插值

圖3 線性插值

圖4 球面插值

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

3.1.2 平移量線性插值

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

圖5 平移量插值

3.1.3 初始食物源生成

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

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

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

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

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

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

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

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

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

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

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

情況3：2顆牙齒朝著相反方向運動，此時主要考慮避免牙冠的碰撞情況；

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

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

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

3.2.1 優(yōu)先級算法

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

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

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

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

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

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

步驟1. 依次遍歷牙齒；

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

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

3.3 牙齒運動路徑規(guī)劃

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

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

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

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

3.3.2 牙齒運動路徑規(guī)劃步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.3 算法流程圖

算法流程如圖9所示。

圖9 牙齒運動路徑規(guī)劃流程圖

4 實驗結(jié)果及分析

4.1 牙齒運動路徑規(guī)劃結(jié)果

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

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

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

4.2 不同目標(biāo)函數(shù)實驗結(jié)果對比

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

圖11 牙齒移動前后對比

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

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

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

5 結(jié)束語

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

[1] 盧海麗, 康娜. 無托槽隱形矯治器與固定矯治器對正畸患者牙周健康影響的研究現(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] 范然, 鈕葉新, 金小剛，等. 計算機輔助牙齒隱形正畸系統(tǒng)[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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的自動化排牙方法[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] 楊光. 牙齒矯正中牙齒移動的仿真和優(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] 張筱. 牙齒正畸路徑規(guī)劃方法研究及可視化開發(fā)[D]. 濟南: 山東大學(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] 龔誠, 聞娟, 李佳嶺, 等. Spee曲線和擁擠度對口腔正畸模型2D與3D測量法的影響[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各類錯(牙合)及正常(牙合)牙弓對稱性分析與比較[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]. 計算機研究與發(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] 馬勇. 多移動機器人路徑規(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ǔ)研究計劃項目(2019JM-162；2019JM-348)；西安科技大學(xué)博士啟動金項目(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)師。主要研究方向為計算機圖形圖像處理。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)師。主要研究方向為計算機圖形圖像處理。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