張長(zhǎng)東 戴 寧 廖文和 閆國(guó)棟 孫玉春 王 勇 呂培軍

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ù)的基準(zhǔn)線［3］。牙齒預(yù)備體生物特征線的提取是數(shù)字化口腔修復(fù)體造型設(shè)計(jì)的關(guān)鍵環(huán)節(jié)，生物特征線的提取質(zhì)量直接影響修復(fù)體的建模精度，關(guān)系到患者佩戴修復(fù)體的舒適度，對(duì)于牙齦健康也有重要影響。

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

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

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

1 技術(shù)路線

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

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

2 牙齒生物特征線提取

2.1 特征信息

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

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

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

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

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

2.1.2 離散特征信息求解

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

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

圖2 局部曲面擬合

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

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

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

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

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

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

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

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

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

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

2.2.2 生物特征線初提取

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

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

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

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

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

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

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

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

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

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

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

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

其中，fD1為三角片的重心點(diǎn)Vcenter到目標(biāo)點(diǎn)C的距離代價(jià)，距離越小，fD1代價(jià)越小；fdir3表示路徑點(diǎn)B到重心點(diǎn)Vcenter的方向與重心點(diǎn)Vcenter到目標(biāo)點(diǎn)C 的方向之間的夾角，夾角越小，fdir3代價(jià)越小。

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

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

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

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

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

3 提取實(shí)例與比較

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

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

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

4 結(jié)論

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

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

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

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

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

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

［2］ 呂培軍，李彥生，王勇，等.國(guó)產(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］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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ù)備體頸緣線的快速提?。跩］.華南理工大學(xué)學(xué)報(bào)（自然科學(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］ 張國(guó)英.人工智能圖搜索策略的研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)（自然科學(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.