基于啟發式搜索策略的牙齒生物特征線提取技術

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

1.南京航空航天大學，南京，210016 2.北京大學口腔醫學院，北京，100081

0 引言

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

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

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

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

1 技術路線

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

圖1 牙齒生物特征線提取技術路線圖

2 牙齒生物特征線提取

2.1 特征信息

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

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

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

將最小主曲率κmin沿其最小主方向tmin上的導數記作最小極值系數εmin，即

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

2.1.2 離散特征信息求解

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

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

圖2 局部曲面擬合

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

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

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

圖3 預備體模型特征線

2.2 預備體生物特征線提取

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

2.2.1 啟發式搜索策略

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

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

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

2.2.2 生物特征線初提取

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

則啟發函數f（n）可表示為

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

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

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

結合本算法進行測試分析，當權因子wa、wb、wc、wd分別取0.8、0.9、0.8、0.3時，能夠實現生物特征線的最優提取。

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

2.2.3 生物特征線形態優化

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

圖4 預備體模型初提取生物特征線

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

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

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

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

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

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

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

圖5 特征線路徑優化

3 提取實例與比較

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

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

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

4 結論

（1）針對現有的全局特征提取算法難以實現牙齒生物特征線提取的局限，本文提出了基于啟發式搜索策略的生物特征線提取算法，結合牙齒預備體三角網格模型的特征信息，采用啟發式的搜索策略自適應地提取生物特征線，并對提取結果進行形態優化以保證提取質量，實現對牙齒生物特征線的精確提取。

圖6 預備體生物特征線提取實例

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

（2）對100余例臨床預備體數據進行生物特征線提取實驗，結果表明本文算法具有良好的適應性，能夠實現對各類常見牙齒模型生物特征線的提取操作。與一些商業化的國外口腔修復CAD／CAM系統相比，本文算法已達到與其相當的提取水平，這為研發具有自主知識產權的口腔修復設備提供了一個參考解決方案。

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

［1］ 呂培軍.數學與計算機技術在口腔醫學中的應用［M］.北京：中國科學技術出版社，2001.

［2］ 呂培軍，李彥生，王勇，等.國產口腔修復CAD／CAM系統的研究與開發［J］.中華口腔醫學雜志，2002，37（5）：367－370

［3］ 馬軒祥，趙銥民.口腔修復學［M］.5版.北京：人民衛生出版社，2008.

［4］ 崔晨，石教英.三維模型中的特征提取技術綜述［J］.計算機輔助設計與圖形學學報，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］ 戴寧.口腔修復體造型關鍵技術研究及其應用［D］.南京：南京航空航天大學，2006.

［11］ 戴寧，周永耀，袁天然，等.口腔預備體頸緣線的快速提取［J］.華南理工大學學報（自然科學版），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］.長春理工大學學報（自然科學版），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.