肖 兵，魏 昕，胡 偉，夏鴻建

(廣東工業(yè)大學 機電工程學院，廣州 510006) (*通信作者電子郵箱1067197284@qq.com)

基于特征線分段技術(shù)的牙齒分割算法

肖 兵*，魏 昕，胡 偉，夏鴻建

(廣東工業(yè)大學 機電工程學院，廣州 510006) (*通信作者電子郵箱1067197284@qq.com)

牙齒分割是計算機口腔正畸的重要技術(shù)，針對三維牙頜模型直接進行牙齒分割而不對齒間融合區(qū)域進行處理會存在精確度較差、缺失側(cè)面形狀的問題,以及現(xiàn)有牙齒形狀建模方法交互多、效率低的問題，提出一種基于特征線分段技術(shù)的牙齒分割算法。根據(jù)曲率信息篩選特征區(qū)域并采用形態(tài)學算法提取牙列特征線；結(jié)合特征線分段和分支點匹配算法以及形態(tài)學膨脹操作實現(xiàn)齒間融合區(qū)域的自動識別；利用匹配的分支點對齒間孔洞搭橋修補，實現(xiàn)牙齒形狀的自動恢復；提取齒間齦緣線，然后以所有齦緣線作為牙齒分割線分離出單顆牙齒。實驗結(jié)果表明，該算法不僅能準確分離出具有側(cè)面形狀的單顆牙齒，而且避免了牙齒形狀建模時的交互操作，而且與手動識別并刪除齒間粘連區(qū)域、采用曲面能量約束方式重建齒間缺失曲面的方法相比，提高了牙齒分割效率60%～90%。

三維牙頜模型；牙齒分割；牙齒形狀建模；形態(tài)學；融合區(qū)域

0 引言

牙齒分割是計算機輔助口腔正畸[1]的重要技術(shù)。在口腔計算機輔助設(shè)計與制造(Computer Aided Design and Manufacturing, CAD/CAM)系統(tǒng)[2-3]中，為了測量牙齒參數(shù)，模擬牙齒的移動以及重新排列牙齒，都需要預(yù)先從三維牙頜模型中分離出單顆牙齒。然而，受掃描精度及三維重建精度等因素限制，數(shù)字化三維牙頜模型相鄰的牙齒通常粘連在一起，沒有清晰的牙縫，導致直接分割出的單顆牙齒局部形狀缺失[4]。加之牙齒形態(tài)、排列的差異，使得自動且精確的牙齒分割較為困難。

近年來，牙齒分割領(lǐng)域有許多較為自動的方法[5-9]被提出，這些方法直接利用牙列特征線進行牙齒分割，雖在一定程度上分離出了單顆牙齒，但未對齒間融合區(qū)域進行處理，使得分割結(jié)果不夠精確。為此，尹駿等[10]在牙齒分割時避開融合區(qū)域，該方法不僅交互少而且速度快，但所得牙齒側(cè)面形態(tài)不完整，不便于口腔CAD/CAM系統(tǒng)中的使用。

為恢復牙齒側(cè)面缺失形狀，一些牙齒形狀建模方法[4,11-12]被提出。文獻[4]首先識別并刪除齒間粘連區(qū)域，然后采用曲面能量約束的方式重建齒間缺失曲面，達到了較高的逼近度，但其粘連區(qū)域的識別需要手工框選，而且牙齒形狀恢復環(huán)節(jié)的孔洞橋接也需要交互；文獻[11]提出一種有效的孔洞修補算法精確地重建了牙齒側(cè)面缺失形狀，但該算法需要手工構(gòu)造牙齒側(cè)面孔洞；文獻[12]利用控制曲線裁切分割區(qū)域，并通過建立參數(shù)化曲面重建了齒間缺失區(qū)域，但為了避免重建的鄰牙側(cè)面產(chǎn)生干涉，該方法需要手工調(diào)整參數(shù)曲面?？傊?，上述牙齒形狀建模方法雖然較好地恢復了牙齒側(cè)面形狀，但都需要對多顆牙齒進行重復的交互操作，不僅費時費力、對操作人員要求高，還可能因操作失誤而影響最終的分割結(jié)果。為此，本文在文獻[4]的基礎(chǔ)上提出一種準確的、少交互的牙齒分割算法。

1 技術(shù)路線

根據(jù)牙齒的形態(tài)學特征和口腔生物醫(yī)學規(guī)律，要想從三維牙頜模型準確分離出單顆牙齒，有必要進行牙齒形狀建模。為了避免牙齒形狀建模中的交互、提升牙齒分割整個過程的自動化程度，本文提出一種基于特征線分段的牙齒分割算法。如圖1，該算法主要步驟為：首先，對輸入的三維牙頜模型以平均曲率作為特征點的度量，采用形態(tài)學算法提取牙列特征線；然后，根據(jù)特征線幾何信息識別分支點并對特征線進行分段；接著，通過分支點匹配算法識別出融合區(qū)域特征線；進一步，對融合區(qū)域特征線采用形態(tài)膨脹操作，實現(xiàn)齒間融合區(qū)域的自動識別；在刪除齒間融合區(qū)域后，將齒間缺失區(qū)域作為獨立孔洞，利用匹配的分支點進行搭橋修補，實現(xiàn)單顆牙齒缺失形狀的自動恢復；最后提取齒間齦緣線，并以全部齦緣線作為牙齒分割線分離出單顆牙齒。

圖1 本文牙齒分割算法流程

2 牙齒自動分割

2.1 牙列特征線提取

牙列特征線提取是牙齒分割必不可少的步驟。雖然三維牙頜模型表面是極其不規(guī)則的復雜曲面，但其齦緣區(qū)域和齒間融合區(qū)域有著明顯的特征，通常呈“谷底”狀分布，因而可以根據(jù)其對應(yīng)的曲率變化進行分析和劃分。本文采用文獻[5]的方法，以平均曲率作為特征點的度量，通過基于形態(tài)學的特征線提取方法提取牙列特征線。對于大多數(shù)特征明顯的牙頜模型，該方法都能較好地提取牙列特征線(如圖2所示)。

圖2 牙列特征線

2.2 特征線分段

由于齒間融合區(qū)域的存在，直接用2.1節(jié)提取的牙列特征線進行牙齒分割得到的結(jié)果并不精確。牙齒形狀建模雖能解決這一問題，但齒間融合區(qū)域的自動識別仍是一個技術(shù)難題。為解決該問題，本文提出一種特征線分段技術(shù)。首先，將圖2所示的牙列特征線分為齦緣線和融合區(qū)域特征線兩部分。由于理想的牙列特征線不存在開環(huán)特征線且僅在齦緣線與融合區(qū)域相交處出現(xiàn)分支，因而可通過分支點將特征線分段并結(jié)合牙齒特征信息區(qū)分出融合區(qū)域特征線。

1)識別分支點。觀察已提取的牙列特征線發(fā)現(xiàn)，非分支處的特征點首尾相連，有且僅有兩個特征點與之相鄰；而分支點的1-鄰域特征點多于兩個(其數(shù)目通常為3)。根據(jù)這一規(guī)律，即可識別出所有分支點，如圖3(a)所示。然而，由于部分分支點可能與兩個1-鄰域特征點同屬一個三角片，所以可能在同一分支處識別出三個分支點，即有兩個冗余分支點。實際上，這樣的三個點中具體選擇哪一個作為分支點并不重要，所以可任意剔除其中兩個點，如圖3(b)所示，因此，識別分支點的具體步驟為：

步驟1 遍歷所有特征點，若特征點p(i)的1-鄰域特征點數(shù)大于2，則將p(i)加入分支點集合Jets中。

步驟2 檢查Jets中分支點，若存在3個分支點互為1-鄰域點，則將其中任意兩個從Jets中剔除。

圖3 識別分支點

2)特征線分段。利用識別的分支點對牙列特征線分段，每段特征線都以分支點作為首末端點；若存在孤立閉環(huán)也將其視為一段。將各段特征線依次存入集合FLines中。

3)編輯特征線。由于數(shù)字化三維牙頜曲面的復雜性及模型質(zhì)量的差異，采用2.1節(jié)的自動方法提取的牙列特征線難免存在一些瑕疵：存在少量多余分支或缺少某段特征線。為滿足牙齒分割要求，在這種情況下對提取的特征線進行少量的編輯是必要的。本文提出兩個簡單的特征線編輯操作：剔除特征線和增添特征線。由于特征線已分段存儲，對于特征線上的多余分支，可直接選中加以刪除，如圖4(a)所示；對于由牙頜模型局部特征不明顯導致某段特征線缺失的情形，可交互指定2～3個點，即可添加特征線，如圖4(b)所示。

2.3 牙齒形狀建模

三維牙頜模型上牙齒形狀建模的目的是重建牙齒側(cè)面缺失形狀，其步驟一般包括齒間融合區(qū)域的檢測、提取刪除和牙齒形狀恢復。文獻[4，11]均將齒間缺失區(qū)域視為孔洞，并采用孔洞填充、網(wǎng)格細分優(yōu)化和拓撲調(diào)整的策略精確恢復了牙齒側(cè)面形狀，但文獻[11]的方法需要為每顆牙齒構(gòu)造封閉的孔洞邊界，交互量大，效率低，因此本文對文獻[4]的方法加以改進，根據(jù)牙頜形態(tài)特征自動識別齒間融合區(qū)域并利用匹配的分支點對齒間孔洞橋接，既保留原方法的精確度，又避免繁瑣的人工操作。

圖4 編輯特征線

2.3.1 齒間融合區(qū)域的識別與刪除

1)融合區(qū)域特征線的識別。通過對大量的三維牙頜模型進行觀察分析表明，同一融合區(qū)域特征線的兩分支點間距離總小于牙齒同側(cè)(同為頰(唇)側(cè)或同為舌側(cè))兩鄰近分支點間的距離，如圖5(a)，總存在a

2)齒間融合區(qū)域識別。設(shè)M={v1,v2,…,vi,…,vn}表示三維牙頜模型對應(yīng)的三角網(wǎng)格曲面，M上任意點vi及其所有鄰接點構(gòu)成的1環(huán)鄰域定義為：

nhd1{vi}:={vi}∪{vj|?edge{vi,vj}}

依此類推，vi的n環(huán)鄰域嵌套定義為：

nhdn{vi}:=nhd(nhdn-1{vi})；n>1

設(shè)F表示三角網(wǎng)格上的特征區(qū)域，在形態(tài)學[13]中，膨脹操作(dilaten(F) )表示對F中每個點，令其n環(huán)鄰域點都成為特征點，其數(shù)學定義為：

dilaten(F):{vj|vi∈F:vj∈nhdn{vi}}

對識別的融合區(qū)域特征線(如圖6(a))執(zhí)行m次形態(tài)學膨脹操作，直至覆蓋齒間融合區(qū)域，即實現(xiàn)齒間融合區(qū)域的自動識別。實驗分析表明，m的值一般在2～4，其大小取決于融合區(qū)域網(wǎng)格密度，當網(wǎng)格較密時m值適當增加。本文取m=3，對大多數(shù)牙頜模型都能取得較好的結(jié)果，識別的齒間融合區(qū)域效果如圖6(b)所示。

3)齒間融合區(qū)域的刪除。對齒間融合區(qū)域進行刪除，得到齒間孔洞如圖6(c)所示。為了在后續(xù)牙齒形狀修復階段實現(xiàn)孔洞修補的自動搭橋，需在刪除齒間融合區(qū)域過程中保留已匹配的分支點。

圖5 融合區(qū)域特征線的識別

圖6 齒間融合區(qū)域的識別與刪除

2.3.2 牙齒形狀恢復

健康牙齒的側(cè)面形狀具有近似一階連續(xù)的屬性，并且側(cè)面開口對應(yīng)的曲面是規(guī)則的。文獻[4]根據(jù)齒間孔洞邊界的頂點信息，采用曲面能量約束的方式構(gòu)建缺失部分對應(yīng)的曲面，所得結(jié)果與原始牙齒有較高的逼近度，因此，本文采用該方法進行牙齒形狀建模并進行適當?shù)母倪M。

然后，對初始恢復曲面Pmin進行局部細分優(yōu)化，得到與原始牙頜模型網(wǎng)格密度相近且近似符合Delaunay劃分準則的中間恢復曲面(如圖7(b)所示)，記作Prefine。

最后，根據(jù)牙齒的個性特征，以齒間孔洞邊界點及其外側(cè)1-鄰域點作為約束變形點，對優(yōu)化細分曲面Prefine進行二階Laplacian變形，得到在邊界和內(nèi)部滿足C1連續(xù)的最終恢復曲面Pdeform，其效果如圖7(c)所示。

圖7 牙齒形狀恢復

2.4 獲取牙齒分割線

經(jīng)過2.3節(jié)的牙齒形狀建模，相鄰牙齒之間重現(xiàn)清晰的牙縫，牙縫的“谷底”為齒間齦緣且與頰(唇)舌側(cè)齦緣自然過渡。依照牙齒分割經(jīng)驗，此時的齦緣線即可作為牙齒分割線，但牙頜模型的數(shù)據(jù)量通常都較大，重新提取完整的齦緣線需要不小的時間消耗?？紤]到前面提取的牙齒特征線已包含大部分齦緣線——除去融合區(qū)域的部分均為頰(唇)舌側(cè)齦緣線，為提升牙齒分割整體效率，避免大量特征線的重復提取，本文在牙齒形狀恢復后保留這部分齦緣線(如圖8(a)所示)，而本環(huán)節(jié)只需再提取齒間的一小部分即可獲得完整的齦緣線。

圖8 獲取牙齒分割線效果

根據(jù)牙體形態(tài)，齒間齦緣線可視為已匹配的分支點間的特征路徑。張長東等[14]將牙齒生物特征線提取問題轉(zhuǎn)化為兩點間的最優(yōu)特征路徑搜索問題，提出基于啟發(fā)式搜索策略的半自動提取方法。本文采用該方法提取齒間齦緣線：對于每對匹配的分支點，以其中一點作為起點、另一點作為終點進行啟發(fā)式搜索，相應(yīng)的啟發(fā)函數(shù)為：

f(n)=fdir1+fD+fdir2+fC

其中：fdir1表示當前搜索方向與上一搜索方向的夾角關(guān)系；fD表示下一搜索點到起點的歐氏距離；fdir2表示下一搜索方向與始末端點方向的夾角關(guān)系；fC表示前后搜索點平均曲率的差值。與文獻[14]不同，上述搜索起點、終點是自動獲得的，因而本文齒間齦緣線的提取也是自動的，提取效果如圖8(b)所示。

將齒間齦緣線與頰(唇)舌側(cè)齦緣線一起作為牙齒分割線，以之分離出單顆牙齒，即完成牙齒分割。

3 實驗結(jié)果分析

為驗證本文方法的有效性和適應(yīng)性，對多副三維牙頜模型進行測試，所有測試均在處理器為Corei5-4460 3.20GHz，內(nèi)存4GB，64位Windows7系統(tǒng)的平臺上進行。圖9、10所示為兩種具有典型代表性的三維牙頜模型及對應(yīng)的牙齒分割結(jié)果。

圖9所示為完整的牙頜模型。其中，圖9(a)中對應(yīng)的初始三維牙頜模型包含103 541個頂點/205 325個三角片，圖9(b)～(e)為牙齒分割幾個關(guān)鍵步驟的結(jié)果，圖9(f)為最終牙齒分割結(jié)果，圖9(g)為文獻[10]避開融合區(qū)域分離的單顆牙齒對應(yīng)的放大顯示，圖9(h)為本文算法分離的單顆牙齒對應(yīng)的放大顯示。

圖9 完整的三維牙頜模型牙齒分割結(jié)果

圖10所示為不完整的牙頜模型(包含基臺)，其中圖10(a)對應(yīng)的初始三維牙頜模型包含68 425個頂點/135 119個三角片。

圖10 不完整的三維牙頜模型牙齒分割結(jié)果

由圖9(c)、10(c)可以看出，該方法對齒間融合區(qū)域有較好的識別效果。對比圖9(g)與圖9(h)、圖10(g)與圖10(h)，可以看出本文牙齒分割方法能達到與文獻[4]算法同等的效果，重建的牙齒側(cè)面形狀達C1連續(xù)，精確地分割出了單顆牙齒。相比文獻[10]的牙齒分割算法，本文算法得到的牙齒具有更高的精確度且形態(tài)更加完整，而相比文獻[4,11-12]的牙齒形狀建模算法，本文算法避免了人工交互，具有更高的自動化程度。圖9、10共同說明了本文算法可對完整和不完整的三維牙頜模型均能得到理想的分割結(jié)果，具有較好的適用性。

表1列出了幾組牙頜模型從開始到牙齒分割完成的分步運行時間和總時間，其中，Model1、Model3為完整牙列(14顆牙)，Model2為不完整牙列。對于Model1、Model3，采用本文算法自動識別融合區(qū)域并刪除分別需要0.111s、0.068s；若采用文獻[4]手工框選的方式，在操作熟練的情況下，拾取每個齒間融合區(qū)域也平均需要2～5s，識別所有融合區(qū)域則需26～65s。對于常規(guī)的牙頜模型，本文算法均能在30s以內(nèi)完成牙齒分割。粗略估計，本文算法相比文獻[4]算法對牙齒分割總時間減少60%～90%，相比操作更加復雜的文獻[11-12]則提升效率更多。由此可見，本文算法在包含牙齒形狀建模并去除大部分交互的情況下仍具有快速性。

表1 算法運行時間 s

4 結(jié)語

針對牙齒分割需要恢復牙齒側(cè)面形狀和牙齒形狀建模需要較多交互的問題，本文提出一種基于特征線分段的牙齒分割算法。經(jīng)實驗表明，該算法具有以下優(yōu)點：1)智能化程度高。整個牙齒分割過程交互極少，實現(xiàn)了全自動的牙齒形狀建模。2)分割精度高。避免了交互操作產(chǎn)生的誤差，牙齒側(cè)面恢復曲面達C1連續(xù)，與原始牙齒相比具有較高的逼近度。3)適應(yīng)性強。對不完整的牙頜模型也能準確地分割。4)運行速度快。常規(guī)的牙頜模型均能在30s以內(nèi)完成牙齒分割。當然，本文算法也有一定的局限性，當牙頜模型特征不明顯或網(wǎng)格質(zhì)量較差時，需要在提取牙列特征線之前對模型進行一定的預(yù)處理操作。

)

[1]MOTOHASHIN,KURODAT.A3Dcomputer-aideddesignsystemappliedtodiagnosisandtreatmentplanninginorthodonticsandorthognathicsurgery[J].EuropeanJournalofOrthodontics, 1999, 21(3): 263-274.

[2]LIUP-R.ApanoramaofdentalCAD/CAMrestorativesystems[J].CompendiumofContinuingEducationinDentistry, 2008, 26(7): 507-508.

[3]MIYAZAKIT,HOTTAY,KUNIIJ,etal.AreviewofdentalCAD/CAM:currentstatusandfutureperspectivesfrom20yearsofexperience[J].DentalMaterialsJournal, 2009, 28(1): 44-56.

[4]YUANT,LIAOW,DAIN,etal.Single-toothmodelingfor3Ddentalmodel[J].InternationalJournalofBiomedicalImaging, 2010, 2010:ArticleNo. 9.

[5] 郝國棟，程筱勝，戴寧，等.基于形態(tài)學的牙齒模型交互分割[J].中國制造業(yè)信息化,2008,37(1):36-39. (HAOGD,CHENGXS,DAIN,etal.Themorphology-basedinteractivesegmentationofdentalmodels[J].ManufacturingInformationEngineeringofChina. 2008, 37(1): 36-39. )

[6]WONGWAENN,SINTHANAYOTHINC.Computerizedalgorithmfor3Dteethsegmentation[C]//ICEIE2010:Proceedingsofthe2010InternationalConferenceonElectronicsandInformationEngineering.Piscataway,NJ:IEEE, 2010， 1: 277-280.

[7]KRONFELDT,BRUNNERD,BRUNNETTG.Snake-basedsegmentationofteethfromvirtualdentalcasts[J].Computer-AidedDesignandApplications, 2010, 7(2): 221-233.

[8]KUMARY,JANARDANR,LARSONB,etal.Improvedsegmentationofteethindentalmodels[J].Computer-AidedDesign&Applications, 2011, 8(2): 211-224.

[9]WUK,CHENL,LIJ,etal.Toothsegmentationondentalmeshesusingmorphologicskeleton[J].Computers&Graphics, 2014, 38: 199-211.

[10] 尹駿,劉森.避開融合區(qū)域的牙齒分割算法[J].計算機工程與設(shè)計,2016,37(1):180-184. (YINJ,LIUS.Toothsegmentationalgorithmbasedonfusionregionavoidance[J].ComputerEngineeringandDesign, 2016, 37(1): 180-184. )

[11]QIUN,FANR,YOUL,etal.Anefficientandcollision-freehole-fillingalgorithmfororthodontics[J].TheVisualComputer, 2013, 29(6):577-586.

[12] 范然,鈕葉新,金小剛,等.計算機輔助牙齒隱形正畸系統(tǒng)[J].計算機輔助設(shè)計與圖形學學報,2013,25(1):81-92. (FANR,NIUYX,JINXG,etal.Computeraidedinvisibleorthodontictreatmentsystem[J].JournalofComputer-AidedDesign&ComputerGraphics, 2013, 25(1): 81-92.)

[13]ROESSLC,KOBBELTL,SEIDELH-P.Extractionoffeaturelinesontriangulatedsurfacesusingmorphologicaloperators[C]//Proceedingsofthe2000AAAISymposiumonSmartGraphics.MenloPark,CA:AAAIPress, 2000: 71-75.

[14] 張長東,戴寧,廖文和,等.基于啟發(fā)式搜索策略的牙齒生物特征線提取技術(shù)[J].中國機械工程,2012,23(13):1567-1571. (ZHANGCD,DAIN,LIAOWH,etal.Extractionofdentalbiologicalfeaturelinebasedonheuristicsearchstrategy[J].ChinaMechanicalEngineering, 2012, 23(13): 1567-1571. )

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(51175092),theNaturalScienceFoundationofGuangdongProvince(10151009001000036).

XIAO Bing, born in 1991, M. S. candidate. His research interests include computer graphics, computer-aided biomedical engineering.

WEI Xin, born in 1964, Ph. D., professor. Her research interests include precision and ultra-precision machining, computer aided design and manufacturing.

HU Wei, born in 1978, Ph. D., lecturer. His research interests include precision and ultra-precision machining, computer aided design and manufacturing.

XIA Hongjian, born in 1978, Ph. D., lecturer. His research interests include parametric design, intelligent computer aided design.

Tooth segmentation algorithm based on segmentation of feature line

XIAO Bing*, WEI Xin, HU Wei, XIA Hongjian

(SchoolofElectro-mechanicalEngineering,GuangdongUniversityofTechnology,GuangzhouGuangdong510006,China)

Tooth segmentation plays an important role in computer-aided orthodontics. However, many published approaches directly separate teeth from dental mesh without dealing with the region fusion, which leads to inaccurate results and incomplete segmented teeth with side shape lacked. Meanwhile, existing tooth shape modeling schemes are interaction-intensive and inefficient. To resolve this problem, a new tooth segmentation approach based on segmentation of feature line was proposed. Feature region was selected according to mean curvature, and morphologic algorithm was used to extract dentition line. The fusion region was automatically recognized by the feature line segmenting and branch points matching algorithm as well as morphologic dilation. The restoration result was automatically obtained by repairing holes with matched branch points. After the gingival margin lines between adjacent teeth were extracted, the teeth were segmented by all the gingival margin lines. Experimental results demonstrate that the poposed approach is accurate, the segmented teeth have complete side feature. In addition, the approach avoids user interactions in the stage of tooth shape modeling, thus improving the whole efficience by 60%—90% compared with the method which manually identifies and removes the interdental adhesion area and reconstructs the missing tooth surface by surface energy constraint.

three-dimensional dental model; tooth segmentation; tooth shape modeling; morphology; fusion area

2016- 07- 18;

2016- 08- 20。

國家自然科學基金資助項目(51175092)；廣東省自然科學基金資助項目(10151009001000036)。

肖兵(1991—)，男，湖北十堰人，碩士研究生，主要研究方向：計算機圖形學、計算機輔助生物醫(yī)學工程； 魏昕(1964—)，女，江西南昌人，教授，博士，主要研究方向：精密與超精密加工、計算機輔助設(shè)計與制造； 胡偉(1978—)，男，湖北黃岡人，講師，博士，主要研究方向：精密與超精密加工、計算機輔助設(shè)計與制造； 夏鴻建(1978—)，男，江西上饒人，講師，博士，主要研究方向：參數(shù)化設(shè)計、智能計算機輔助設(shè)計。

1001- 9081(2017)03- 0844- 05

10.11772/j.issn.1001- 9081.2017.03.844

TP391.41

A