基于啟發(fā)式搜索策略的牙齒生物特征線提取技術(shù)

張長東 戴 寧 廖文和 閆國棟 孫玉春 王 勇 呂培軍

1.南京航空航天大學(xué)，南京，210016 2.北京大學(xué)口腔醫(yī)學(xué)院，北京，100081

0 引言

CAD／CAM技術(shù)在口腔修復(fù)中的應(yīng)用取得了飛速的發(fā)展，相比于傳統(tǒng)的手工修復(fù)方式，口腔CAD／CAM技術(shù)不僅極大地提高了修復(fù)效率，而且具備更加優(yōu)良的修復(fù)質(zhì)量［1－2］。牙齒生物特征線包括單冠預(yù)備體模型的頸緣線和嵌體預(yù)備體模型的洞緣線，是全冠修復(fù)以及嵌體修復(fù)的基準線［3］。牙齒預(yù)備體生物特征線的提取是數(shù)字化口腔修復(fù)體造型設(shè)計的關(guān)鍵環(huán)節(jié)，生物特征線的提取質(zhì)量直接影響修復(fù)體的建模精度，關(guān)系到患者佩戴修復(fù)體的舒適度，對于牙齦健康也有重要影響。

牙齒生物特征線屬于網(wǎng)格模型的特征線范疇，在網(wǎng)格分片、網(wǎng)格簡化以及模型匹配等領(lǐng)域中被廣泛應(yīng)用。許多學(xué)者對特征線提取算法進行了研究［4－9］，文獻［5］采用局部緊支撐的徑向基函數(shù)全局擬合三角網(wǎng)格模型，并結(jié)合牛頓迭代法求解網(wǎng)格模型的特征信息，最后設(shè)定閾值過濾準則篩選出網(wǎng)格模型的特征線；文獻［6］利用局部多項式擬合方法計算并提取出網(wǎng)格模型的特征線；文獻［7］提出了基于離散微分幾何算子的特征計算方法，有效地結(jié)合三角網(wǎng)格模型固有的離散特性計算其特征區(qū)域，并利用Laplace光順算法得到優(yōu)化特征線。

預(yù)備體生物特征線是一條準確表現(xiàn)頸緣特征或洞緣特征的封閉光滑的曲線，上述特征線提取算法均是對模型數(shù)據(jù)全局特征的提取，提取出的特征線，不僅數(shù)量多，而且排列沒有規(guī)律，無法按照生物特征線提取的特定要求提取出預(yù)備體頸緣區(qū)域的特征線，因此，上述算法不適用于牙齒生物特征線的提取操作。戴寧等［10－11］提出了一種基于方向追蹤的半自動頸緣線提取操作方法，并結(jié)合曲率吸引策略優(yōu)化生物特征線形態(tài)，取得了較為理想的提取效果，但提取精度有待提高。目前，商業(yè)化的口腔修復(fù)CAD／CAM系統(tǒng)中，大都不同程度地采用了交互式的生物特征線提取方法。CEREC口腔修復(fù)系統(tǒng)通過在頸緣區(qū)域交互拾取一系列特征點，拾取的同時將已提取的特征點優(yōu)化連接成生物特征線；3Shape口腔修復(fù)系統(tǒng)首先在頸緣附近定位8個標志點，通過8個標志點粗略定位頸緣特征點，隨后優(yōu)化提取出光滑的頸緣特征線；DentalWings口腔修復(fù)系統(tǒng)將預(yù)備體三維曲面展開到平面中，通過在二維預(yù)備體曲面的頸緣區(qū)域拾取初始點計算出二維頸緣線，隨后映射回三維曲面得到最優(yōu)的生物特征線。三種修復(fù)系統(tǒng)均能夠?qū)崿F(xiàn)預(yù)備體生物特征線的提取操作，但算法均未知。

通過分析上述特征計算算法的優(yōu)劣，結(jié)合國外三種商業(yè)化的口腔修復(fù)CAD／CAM系統(tǒng)提取生物特征線的操作方式，本文提出了基于啟發(fā)式搜索策略的牙齒預(yù)備體生物特征線提取技術(shù)，首先分析牙齒預(yù)備體三角網(wǎng)格模型的特征信息，其次采用啟發(fā)式的搜索策略自適應(yīng)地提取生物特征線，最后對提取結(jié)果進行形態(tài)優(yōu)化以保證提取質(zhì)量。

1 技術(shù)路線

數(shù)字化口腔修復(fù)過程中，對于牙齒預(yù)備體模型生物特征線的提取，首先需要準確、可靠地計算預(yù)備體模型的特征信息，其次通過在預(yù)備體特征區(qū)域識別關(guān)鍵特征點，結(jié)合啟發(fā)式的搜索策略搜索最優(yōu)的生物特征線。生物特征線的提取結(jié)果應(yīng)是一條光順閉合的曲線，能夠精確表達牙齒預(yù)備體模型的頸緣、洞緣特征信息。牙齒生物特征線提取技術(shù)路線如圖1所示。

圖1 牙齒生物特征線提取技術(shù)路線圖

2 牙齒生物特征線提取

2.1 特征信息

特征信息是指能夠表現(xiàn)模型顯著形狀的信息，主要包括脊線、谷線、拐點和邊界線等要素。在微分幾何中，一般通過主曲率、主方向以及主曲率極值等微分量計算曲面的特征信息。

2.1.1 特征信息的微分幾何表示

對于連續(xù)曲面S上的一點p，κn表示過點p的任意法截面的曲率，定義κn的極大值κmax和極小值κmin為曲面S在點p處的最大（最小）主曲率，使κn取得極大值和極小值的方向為曲面S在點p處的最大（最小）主方向，分別記為tmax和tmin（tmax⊥tmin）。用極值系數(shù)ε表示p點的主曲率沿其對應(yīng)的主方向上的偏導(dǎo)數(shù)，其中，將最大主曲率κmax沿其最大主方向上的偏導(dǎo)數(shù)記作最大極值系數(shù)εmax，即

將最小主曲率κmin沿其最小主方向tmin上的導(dǎo)數(shù)記作最小極值系數(shù)εmin，即

極值系數(shù)ε反映了主曲率沿其對應(yīng)的主方向上的變化率，若極值系數(shù)為0，則定義p點為曲面S的特征點，根據(jù)極值系數(shù)是否為0計算出曲面上所有的特征點，所有特征點的集合即為曲面的特征信息集。

2.1.2 離散特征信息求解

由于三角網(wǎng)格曲面是離散的分片線性曲面，故無法用參數(shù)方程或隱式方程精確表示，一般可通過曲面擬合方法進行逼近，用擬合曲面的微分幾何特征近似表示三角網(wǎng)格的特征信息，本文采用基于局部曲面擬合的方法計算預(yù)備體三角網(wǎng)格模型的離散微分量。

局部擬合方法需在每個頂點建立局部坐標系puvw，在局部坐標系中用多項式方程擬合當(dāng)前點p及其鄰域點，利用多項式曲面f（u，v）計算離散網(wǎng)格頂點的微分量，如圖2所示。

圖2 局部曲面擬合

McIvor等［12］利用二次多項式曲面擬合求解離散網(wǎng)格點的曲率值，由于曲面只具有C2次可微，因而無法應(yīng)用于特征信息求解；Goldfeather等［13］對離散三角網(wǎng)格的主方向場的逼近誤差作了理論和實驗分析，提出了基于局部三次多項式擬合曲面的三角網(wǎng)格離散微分信息的求解方法，采用的局部三次多項式f（u，v）為

其中，A、B、C、D、E、F、G 表 示 多 項 式 的 系 數(shù)。根據(jù)式（3）計算預(yù)備體網(wǎng)格模型的離散微分量，結(jié)合文獻［5］的特征點判定準則在網(wǎng)格邊vivj上插值出所有的特征點pv，即

將模型上具有相鄰關(guān)系的特征點依次連接成模型的特征線，如圖3所示。

圖3 預(yù)備體模型特征線

2.2 預(yù)備體生物特征線提取

2.1節(jié)計算出的預(yù)備體模型的特征信息，不僅數(shù)量多，而且排列雜亂，包含大量的非頸緣區(qū)域以及非洞緣區(qū)域的特征線，并且所有的特征線均分段分布，如圖3所示。數(shù)字化口腔修復(fù)過程中，上述特征線求解算法難以實現(xiàn)對預(yù)備體模型生物特征線的自動提取，難以按照牙齒生物特征線提取的特定要求計算出一條光滑閉合的曲線。

2.2.1 啟發(fā)式搜索策略

啟發(fā)式搜索在人工智能領(lǐng)域中應(yīng)用廣泛［14-15］，通過評估每一個待搜索目標的代價，得到最優(yōu)的搜索位置，再從這個位置進行搜索直到最終目標，因此可以省略大量無謂的搜索路徑，提高搜索效率。啟發(fā)搜索過程中，借助于估值函數(shù)f（n）估算當(dāng)前搜索點到目標點的代價，并由此決定搜索方向，如下式所示：

式中，g（n）為從路徑起始點到當(dāng)前搜索點的代價；h（n）為當(dāng)前搜索點到路徑末端點即目標點的代價。

g（n）、h（n）用啟發(fā)函數(shù)表示，啟發(fā)函數(shù)的選取直接決定搜索效率。f（n）值越小，表示當(dāng)前可能路徑點越接近最優(yōu)路徑點，將最先搜索到的最優(yōu)路徑點作為新的起始搜索點，迭代搜索，直至搜索到目標點，每次迭代搜索到的最優(yōu)路徑點的集合構(gòu)成最優(yōu)路徑。

2.2.2 生物特征線初提取

牙齒生物特征線提取的策略基于2.1節(jié)中模型的特征點信息，從特征點集中搜索最能表現(xiàn)預(yù)備體頸緣或洞緣區(qū)域特征的特征點。通過在特征區(qū)域識別有限個關(guān)鍵點，根據(jù)啟發(fā)函數(shù)計算代價最小的路徑點，提取出牙齒預(yù)備體模型的初始生物特征線。啟發(fā)式搜索的目標是根據(jù)當(dāng)前搜索點vcur搜索代價最小的目標點vnext，代價函數(shù)的選取直接決定搜索效率和搜索準確度。結(jié)合各個特征點與識別的關(guān)鍵點之間的方向、距離以及曲率關(guān)系，設(shè)計方向函數(shù)fdir1和距離函數(shù)fD表示代價函數(shù)g（n），設(shè)計方向函數(shù)fdir2和曲率函數(shù)fC表示代價函數(shù)h（n），具體定義如下：

則啟發(fā)函數(shù)f（n）可表示為

其中，fdir1表示當(dāng)前搜索方向與前一步搜索方向之間的夾角關(guān)系，夾角越小，對應(yīng)的函數(shù)值fdir1越小；fD表示下一個搜索點vnext與起始搜索點vstart之間的距離關(guān)系，兩點間的距離越大，fD越小；fdir2表示下一步搜索方向與始末端點方向之間的夾角關(guān)系，夾角越小，fdir2越小；函數(shù)fC描述了前后搜索點曲率的差異曲率差異越小，fC越小。其中，特征點的曲率大小用平均曲率Cv表示，根據(jù)特征點所在邊的兩個網(wǎng)格頂點的曲率大小插值計算平均曲率Cv，即

式中，Ci、Cj分別為特征點vi、vj的平均曲率。

方向函數(shù)fdir1確保生物特征線具有良好的光順效果，方向函數(shù)fdir2和距離函數(shù)fD保證搜索能夠沿著特征線方向進行并能夠最終搜索到生物特征線末端點。曲率函數(shù)fC用于確保搜索到的路徑點能夠最大程度地描述頸緣區(qū)域的特征，相較于方向函數(shù)和距離函數(shù)，曲率函數(shù)fC更能夠影響搜索結(jié)果的準確度［13］。因此，為了表現(xiàn)不同代價函數(shù)對搜索結(jié)果的影響程度，對各代價函數(shù)賦以權(quán)因子wa、wb、wc、wd，式（8）可表示為

結(jié)合本算法進行測試分析，當(dāng)權(quán)因子wa、wb、wc、wd分別取0.8、0.9、0.8、0.3時，能夠?qū)崿F(xiàn)生物特征線的最優(yōu)提取。

算法執(zhí)行步驟如下：①在預(yù)備體頸緣特征區(qū)域拾取關(guān)鍵點vstart作為起始搜索點；②將vstart作為當(dāng)前搜索點vcur，結(jié)合啟發(fā)函數(shù)f（n）從vcur的k個鄰近點中計算出具有最小代價的特征點vnext，k值一般取8～10；③如果vnext是目標點，結(jié)束搜索，執(zhí)行步驟④，反之，將vnext作為新的vcur，執(zhí)行步驟②；④順次連接搜索到的路徑點，構(gòu)建初始生物特征線，如圖4所示。

2.2.3 生物特征線形態(tài)優(yōu)化

啟發(fā)式搜索的搜索對象是基于2.1節(jié)提取的特征點信息，由于預(yù)備體模型的形態(tài)復(fù)雜多樣，故在曲率變化不明顯的頸緣區(qū)域無法計算其特征點，若特征點不連續(xù)，提取的生物特征線與預(yù)備體模型之間容易產(chǎn)生穿越，生物特征線不能夠完全貼合在模型表面，如圖4所示。存在穿越的生物特征線不僅顯示效果差，而且影響后續(xù)設(shè)計的精度。解決上述缺陷有兩種方案：一是計算前后不連續(xù)的兩個特征點之間的測地路徑，用測地線替代穿越處的特征線［16-17］；二是自定義路徑優(yōu)化原則。由于測地線無法捕捉局部特征信息，為了保證提取精度，采用方案二設(shè)計能夠反映局部特征信息的生物特征線優(yōu)化算法。基于啟發(fā)式搜索算法的執(zhí)行思想，對初提取的生物特征線進行如下優(yōu)化。

圖4 預(yù)備體模型初提取生物特征線

如圖5a所示，點A、B、C 為利用2.2.2節(jié)所述算法依次搜索到的特征點，其中，A、B點同屬于一個三角片區(qū)域，無需進行優(yōu)化；而B、C點不屬于同一個三角片，執(zhí)行生物特征線優(yōu)化算法。算法步驟如下：

（1）以高亮三角片T0作為起始搜索位置，查找到其共邊的兩個三角片Ti和Tj，設(shè)計代價函數(shù)fT，計算與目標點C在B、C兩點連線方向VBC上具有最小代價的三角片。代價函數(shù)fT用距離函數(shù)fD1和方向函數(shù)fdir3表示，即

其中，fD1為三角片的重心點Vcenter到目標點C的距離代價，距離越小，fD1代價越小；fdir3表示路徑點B到重心點Vcenter的方向與重心點Vcenter到目標點C 的方向之間的夾角，夾角越小，fdir3代價越小。

（2）若三角片Tj的代價函數(shù)fT最小，則將三角片Tj作為新的起始搜索位置，執(zhí)行步驟（1），直至搜索到與目標點C共面的邊為止，如圖5b所示。

（3）利用式（4），在每條邊上插值得到路徑點，如圖5c所示。

（4）將路徑點按次序加入初始搜索點A、B、C之間，構(gòu)造最優(yōu)路徑，如圖5d所示。

優(yōu)化前后的牙齒生物特征線如圖5e、圖5f所示。

圖5 特征線路徑優(yōu)化

3 提取實例與比較

應(yīng)用本文算法，對100余例臨床牙齒預(yù)備體模型數(shù)據(jù)進行了生物特征線提取操作，其中代表性的提取結(jié)果如圖6a～圖6d所示，圖6e～圖6h所示為利用提取的生物特征線執(zhí)行組織面裁剪后的效果。

本文算法不僅能夠?qū)崿F(xiàn)對前牙、磨牙、尖牙等預(yù)備體模型數(shù)據(jù)的頸緣線提取操作，而且對嵌體洞緣線的提取亦有良好的效果，所提取的生物特征線光順自然，均能夠緊密貼合在預(yù)備體模型曲面上，裁剪后的預(yù)備體組織面邊緣無鋸齒，保證了后續(xù)設(shè)計所需的曲面精度，如圖6所示。

表1所示是本文算法與三種商業(yè)化的口腔修復(fù)CAD／CAM系統(tǒng)之間的比較，在保證提取質(zhì)量的前提下，本文算法具有以下特點：①提取操作簡單易用，只需在預(yù)備體頸緣區(qū)域或洞緣區(qū)域交互識別關(guān)鍵特征點即可自適應(yīng)地提取生物特征線；②提取對象不受預(yù)備體倒凹區(qū)域形態(tài)的影響，能夠提取任意預(yù)備體模型的生物特征線；③簡單易用的提取方式確保本文算法具有較高的執(zhí)行效率，只需6～11s即可完成生物特征線的最優(yōu)提取。

4 結(jié)論

（1）針對現(xiàn)有的全局特征提取算法難以實現(xiàn)牙齒生物特征線提取的局限，本文提出了基于啟發(fā)式搜索策略的生物特征線提取算法，結(jié)合牙齒預(yù)備體三角網(wǎng)格模型的特征信息，采用啟發(fā)式的搜索策略自適應(yīng)地提取生物特征線，并對提取結(jié)果進行形態(tài)優(yōu)化以保證提取質(zhì)量，實現(xiàn)對牙齒生物特征線的精確提取。

圖6 預(yù)備體生物特征線提取實例

表1 生物特征線提取操作比較

（2）對100余例臨床預(yù)備體數(shù)據(jù)進行生物特征線提取實驗，結(jié)果表明本文算法具有良好的適應(yīng)性，能夠?qū)崿F(xiàn)對各類常見牙齒模型生物特征線的提取操作。與一些商業(yè)化的國外口腔修復(fù)CAD／CAM系統(tǒng)相比，本文算法已達到與其相當(dāng)?shù)奶崛∷剑@為研發(fā)具有自主知識產(chǎn)權(quán)的口腔修復(fù)設(shè)備提供了一個參考解決方案。

（3）為了保證牙齒生物特征線的提取質(zhì)量，本文采用半自動的交互提取方式，使得提取結(jié)果易受操作熟練程度的影響。因此，如何在保證提取質(zhì)量的同時減少交互拾取過程、全自動地提取出牙齒生物特征線是下一步研究需要解決的問題。

［1］ 呂培軍.數(shù)學(xué)與計算機技術(shù)在口腔醫(yī)學(xué)中的應(yīng)用［M］.北京：中國科學(xué)技術(shù)出版社，2001.

［2］ 呂培軍，李彥生，王勇，等.國產(chǎn)口腔修復(fù)CAD／CAM系統(tǒng)的研究與開發(fā)［J］.中華口腔醫(yī)學(xué)雜志，2002，37（5）：367－370

［3］ 馬軒祥，趙銥民.口腔修復(fù)學(xué)［M］.5版.北京：人民衛(wèi)生出版社，2008.

［4］ 崔晨，石教英.三維模型中的特征提取技術(shù)綜述［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004，16（7）：882－889.

［5］ Yutake O，Alexander B，Hanspeter S.Ridge－valley Lines on Meshes via Implicit Surface Fitting［J］.ACM Trans.Graph，2004，23（3）：609－612.

［6］ Shin Y，Alexander B，Hideo Y，et al.Fast，Robust，and Faithful Methods for Detecting Crest Lines on Meshes［J］.Computer Aided Geometric Design，2008，25（8）：545－560.

［7］ Klaus H，Konrad P，Max W.Smooth Feature Lines on Surface Meshes［C］／／Proceedings of Eurographics Symposium on Geometry Processing.Vienna，Austria：Eurographics Association，2005：85－90.

［8］ Shenghan H，Jiingyih L.Extraction of Geodesic and Feature Lines on Triangular Meshes［J］.Int.J.Adv.Manuf.Technol.，2009，42（9）：940－954.

［9］ Hyunsoo K，Hankyun C，Kwanh L.Feature Detection of Triangular Meshes Based on Tensor Voting Theory［J］.Computer Aided Design，2009，41（1）：47－58.

［10］ 戴寧.口腔修復(fù)體造型關(guān)鍵技術(shù)研究及其應(yīng)用［D］.南京：南京航空航天大學(xué)，2006.

［11］ 戴寧，周永耀，袁天然，等.口腔預(yù)備體頸緣線的快速提取［J］.華南理工大學(xué)學(xué)報（自然科學(xué)版），2008，36（5）：128－134.

［12］ McIvor M，Robert J.A Comparison of Local Surface Geometry Estimation Methods［J］.Machine Vision and Applications，1997，10（1）：17－26.

［13］ Goldfeather J，Victoria I.A Novel Cubic－order Algorithm for Approximating Principal Direction Vectors［J］.ACM Transactions on Graphics，2004，23（1）：45－63.

［14］ 張國英.人工智能圖搜索策略的研究［J］.長春理工大學(xué)學(xué)報（自然科學(xué)版），2010，33（1）：170－173.

［15］ Koenig S，Likhachev M，Liu Y，et al.Incremental Heuristic Search in AI［J］.AI Magazine，2004，25（2）：99－112.

［16］ Guo Yanwen，Peng Qunsheng，Hu Guofei，et al.Smooth Feature Line Detection for Meshes［J］.Journal of Zhejiang University Science，2005，6（5）：460－468.

［17］ Shi Qingxin，Wang Guojin.Applying the Improved Chen and Han’s Algorithm to Different Versions of Shortest Path Problems on a Polyhedral Surface［J］.CAD Computer Aided Design，2010，42（10）：942－951.