牙頜模型區(qū)域標(biāo)記分割算法

岳彥芳，楊 光，張永弟，吳松和

（河北科技大學(xué)機(jī)械工程學(xué)院，河北石家莊 050018）

牙頜模型一般都是通過三維掃描得到的整體STL數(shù)字模型［1-2］，牙齒矯治通常只對單顆或者幾顆牙齒進(jìn)行移動(dòng)或者轉(zhuǎn)動(dòng)。因此，將需要移動(dòng)的牙齒從整體STL牙頜數(shù)字模型中自動(dòng)分離出來便成為牙頜隱形矯治技術(shù)的關(guān)鍵。已有的自動(dòng)分割算法主要有以下幾種：邊界識別法［3］、矢量逼近法［4］、交互標(biāo)記控制法［5-6］等。邊界識別法算法簡單、效率較高，但分割邊界比較粗糙、不明顯，牙冠部分不完整，效果較差；矢量逼近法可以分割出較為理想的邊界，但每次都會(huì)將所有牙冠和牙齦分割開來，不能只分割所需要移動(dòng)的牙齒，效率較低，而且牙齦的部分邊緣也可能被錯(cuò)誤的分割到牙冠上；交互標(biāo)記控制法是一種相對理想的算法，通過手動(dòng)拾取面片作為標(biāo)記，自動(dòng)擴(kuò)展完成分割，分割出的邊界比較完整。但該算法的缺點(diǎn)是種子面片只是單個(gè)三角面片，如果一顆牙上有多個(gè)彎曲函數(shù)較小的局部表面，就會(huì)產(chǎn)生不完全分割的結(jié)果。

本文對交互標(biāo)記控制法進(jìn)行了改進(jìn)，提出一種區(qū)域選擇的分割算法。使用該算法可以高效的將單顆牙齒從牙頜模型中分割出來，完成牙齒的矯正。并在3DSMax平臺上利用MAX Script腳本語言進(jìn)行二次開發(fā)，實(shí)現(xiàn)了自動(dòng)分割牙齒。

1 STL牙頜模型特點(diǎn)

STL模型可以通過點(diǎn)云逆向處理獲得；也可以通過對已有的三維模型表面進(jìn)行三角化離散得到，即按照精度要求使用一定數(shù)量的三角面片來逼近模型表面形狀。在后一個(gè)方法中，每個(gè)三角面片用三角形的頂點(diǎn)坐標(biāo)（xi，yi，zi）（其中i=1，2，3）和一個(gè)法向量n（用來指明實(shí)體包含在面片的哪一邊）表示［7］。模型中每個(gè)面、邊、頂點(diǎn)都有唯一的序列號，牙頜的STL模型較其他模型主要有以下特點(diǎn)：

1）切牙的舌向是凹的，唇向是凸的，但牙冠上鄰接兩三角形的彎曲函數(shù)值較齦緣處的要大，這也是該分割算法實(shí)現(xiàn)的依據(jù)，在分割算法中會(huì)講到；

2）某些牙冠的表面可能凸凹不平的局部表面，由其在磨牙的頂部其鄰接兩三角形的彎曲函數(shù)值較齦緣處的要小，因此用閾值方法很難全部選擇；

3）不同患者的牙頜模型形狀不規(guī)則，大小不統(tǒng)一，不同人的牙頜模型基本沒有任何的聯(lián)系，因此很難對單個(gè)模型形狀進(jìn)行宏觀的研究而運(yùn)用到所有的模型。

2 分割算法

交互標(biāo)記控制法［8］是目前牙齒分割算法中較為理想的一種算法，以下是該法所需完成的工作。

2.1 交互標(biāo)記控制法

該算法是在分水嶺算法［9-10］的基礎(chǔ)上提出來的，將標(biāo)記作為種子，從種子點(diǎn)出發(fā)，完成分割過程。主要包括3個(gè)關(guān)鍵步驟。

1）選取單個(gè)面片作為標(biāo)記 本算法中，交互標(biāo)記輸入的是單個(gè)面片作為種子面片。缺點(diǎn)是在單顆牙上，有一些局部的彎曲函數(shù)值較齦緣處鄰接兩三角形的彎曲函數(shù)值?。?2-13］。如果閾值（通過交互方式輸入，與相鄰面片的彎曲函數(shù)值進(jìn)行對比的一個(gè)中間值）稍小，則這些局部部分無法選擇，反之則會(huì)把牙齦部分也錯(cuò)誤的選取，因此少數(shù)牙總是無法將牙冠完整的選擇。

2）計(jì)算相鄰面片彎曲函數(shù) 設(shè)2個(gè)三角面片f1和f2，其單位法向量分別為n1和n2，設(shè)AC為公共邊，AB為非公共邊，如圖1所示。則面片f1，f2的相對彎曲函數(shù)為

圖1 相鄰兩面彎曲程度函數(shù)Fig.1 Bending degree expression about adjacent surfaces

顯然C（f1，f2）∈［-1，1］，當(dāng)f1和f2的邊界為凹邊界時(shí)，C（f1，f2）為負(fù)，邊界為凸邊界時(shí)，C（f1，f2）為正，且兩相鄰面片之間的彎曲程度函數(shù)值只與它們之間的夾角有關(guān)［5］。

3）分割算法 將2.1中1）得到的種子面片的相鄰面壓入堆棧中，作為堆棧的初始化。計(jì)算出其與3個(gè)相鄰面片的3個(gè)相對彎曲函數(shù)值C（curvature），將C由大到小重新排列后壓入棧。這樣，當(dāng)前C值最大的元素位于棧頂，最先出棧；C值最小的元素位于棧底，最后出棧。重復(fù)以上的堆棧操作過程，從交互標(biāo)記的種子面片開始，對全部選擇合格且與標(biāo)記連通的面片進(jìn)行計(jì)算。該算法的面片進(jìn)棧排序操作算法時(shí)間復(fù)雜度較高。

2.2 算法的改進(jìn)——區(qū)域選擇算法

通過上述對交互標(biāo)記控制法的研究與描述，針對其的不足之處，區(qū)域選擇分割算法提出如下的改進(jìn)。

1）區(qū)域選擇標(biāo)記方式 針對該問題，本算法提出了區(qū)域選擇的標(biāo)記方式，將彎曲函數(shù)值較其他部分小的局部部分全部選擇，將其按照序列號的大小依次插入隊(duì)列，這些面片不需要計(jì)算其兩臨面間的相對彎曲函數(shù)值，直接作為合格的面片被選取，這樣就很好地避免了有些局部彎曲函數(shù)值很小不能被自動(dòng)選擇的問題，具體原理如2.2中2）分割算法所講，如圖2所示。圖2a）是以交互標(biāo)記控制法選取的單個(gè)面片作為種子面分割結(jié)果，圖2b）是通過區(qū)域選擇法選擇分割的結(jié)果。從分割結(jié)果也可以看出，區(qū)域選擇法優(yōu)勝于標(biāo)記控制法。

圖2 單面片和區(qū)域標(biāo)記的分割結(jié)果對比Fig.2 Comparison of segmentation results using single surface and area mark

2）分割算法 區(qū)域選擇法分割［13］的目標(biāo)是把與標(biāo)記連通且符合要求的面片選擇出來。由2.2中1）確定分割的部分后，用一個(gè)隊(duì)列S記錄擴(kuò)展的過程。以S［i］（i=0，1，2，3，…）為交互得到的種子面片，尋找其相鄰面片，符合要求且未被選擇的面片直接添加到隊(duì)尾，此過程直到將隊(duì)列中所有的面片按照隊(duì)列序列號作為種子面片依次訪問一遍，則S［i＋n］（n為后添加的面片）即為符合要求的面片集合，該算法的具體流程圖如圖3所示。

設(shè)R是需要分割的全部面片集合，R1（i=1，2，3，…，i-1）和R2（i，i＋1，i＋2，…）是交互得到的區(qū)域標(biāo)記，隊(duì)列S存儲(chǔ)全部種子面片，V是一個(gè)變量，如圖4所示。

第1步：將種子面片插入隊(duì)列。交互得到的種子面片根據(jù)ID號由小到大（假設(shè)ID（1）＜ID（2）＜ID（3）＜…）插入S中（S=R1∪R2）。第2步：尋找相鄰面片。取S第1個(gè)元素ID（1）放入V中，找出該面片公共邊的3個(gè)鄰面（ID（2），ID（4），ID（a）），由于面片ID（2），ID（4）已經(jīng)被訪問（2，4交互選入R2），則a是所需要的相鄰面片。第3步：判斷臨面是否符合要求。由2.1中2）算法得到面片1和a的相對彎曲函數(shù)值C，將其與交互輸入的T進(jìn)行對比，若C＞T且未被選擇，將a直接添加到S中（即插入隊(duì)尾），種子面片不刪除。若C＜T，直接進(jìn)入下一步。第4步：取下一個(gè)元素繼續(xù)分割。判斷是否是隊(duì)尾元素，是，結(jié)束，否則取下一個(gè)元素重復(fù)上述循環(huán)。在該算法的擴(kuò)展過程中，先按ID號從小到大把S中交互選擇的面片全部被作為種子面片訪問，再按照插入隊(duì)列的時(shí)間訪問新增加的面片，此過程直到S中的面片全部遍歷完為止，則S［i］即所需合格面片。

圖3 牙齒分割算法流程Fig.3 Procedure of segmentation algorithm

圖4 種子面片的臨面尋找Fig.4 Seeking the adjacent surface of seed surface

如果按初始閾值分割模型不能獲得滿意的結(jié)果，通過交互輸入方式調(diào)節(jié)閾值的大小，重新進(jìn)行分割。一般情況下，分割出的都是封閉的區(qū)域，可以達(dá)到需求。如果牙齒邊界上存在一些局部只調(diào)節(jié)閾值則無法達(dá)用戶所需要的結(jié)果，可以通過交互方式添加到已選擇的區(qū)域，從而分割出所需要的部分。

3 分割算法比較與分析

從算法中堆棧的操作次數(shù)和整個(gè)分割過程所需時(shí)間來分析［7］，交互標(biāo)記控制法進(jìn)入堆棧的是彎曲函數(shù)值，棧次數(shù)與所選擇區(qū)域模型三角面片的邊數(shù)相等，區(qū)域選擇法進(jìn)入隊(duì)列的是面片ID。其進(jìn)入隊(duì)列的次數(shù)與所選擇區(qū)域模型三角面片的面數(shù)相等，在STL模型中，三角面片的邊數(shù)目大約是面的1.5倍，因此區(qū)域選擇法在操作次數(shù)節(jié)省了大量的時(shí)間，排序運(yùn)算上，原算法在每次進(jìn)棧都需要進(jìn)行大小排序，因此時(shí)間復(fù)雜度是平方階。而本算法根據(jù)閾值判斷三角面片的鄰面片是否符合要求，不用排序直接插入隊(duì)列，算法時(shí)間復(fù)雜度是一個(gè)常數(shù)階，程序運(yùn)行速度得到了明顯的提高。2種算法的對比如表1所示。

表1 2種算法的對比分析Tab.1 Analysis and comparison of two algorithms

從表1中可以得到如下結(jié)論：改進(jìn)的算法——區(qū)域選擇法的算法復(fù)雜度明顯優(yōu)于傳統(tǒng)的交互標(biāo)記法。

4 基于3DSMax平臺對牙齒分割的完成

在3DSMax平臺［14-15］上創(chuàng)建浮動(dòng)窗口，其包含標(biāo)記選取、閾值微調(diào)器以及牙齒分割按鈕。標(biāo)記按鈕作用是區(qū)域選擇種子面片，閾值微調(diào)器按鈕的作用是交互輸入閾值，牙齒分割按鈕作用是通過點(diǎn)擊該按鈕在3DSMax中自動(dòng)完成牙齒的分割。

在牙齒的矯治中，有時(shí)需要將多顆牙同時(shí)移動(dòng)，前面所講算法中牙每顆之間是分割開的，不能將多顆牙齒同時(shí)移動(dòng)或轉(zhuǎn)動(dòng)。本算法先在不同的牙齒上同時(shí)標(biāo)記，再進(jìn)行分割，多顆牙齒合為一組被分割到指定的區(qū)域，因此區(qū)域選擇法很好地解決了該問題，分割結(jié)果如圖5所示。圖5a）是將牙頜模型的兩切牙同時(shí)選取且向舌向移動(dòng)，圖5b）是將牙頜模型一顆側(cè)切牙選取且向唇向移動(dòng)。在3DSMAX中以該算法為依據(jù)完成牙齒的分割及移動(dòng)，由表1的比較可以得到分割速度和精度完全的達(dá)到了用戶的要求。

圖5 多顆或單顆牙齒的移動(dòng)Fig.5 Movements of multiple teeth or single tooth

5 結(jié) 論

提出一種快速的區(qū)域選擇分割算法，算法利用相鄰兩面之間的彎曲程度作為對應(yīng)的高度場函數(shù)，由用戶輸入的標(biāo)記出發(fā)，選取全部合格面片，完成STL模型的分割。實(shí)驗(yàn)結(jié)果表明，算法不影響交互的實(shí)時(shí)性。用戶通過標(biāo)記和閾值確定分割的區(qū)域，能夠使同種標(biāo)記被分割到同一區(qū)域，因此該算法滿足實(shí)際應(yīng)用的需要。利用該算法，在3DSMax中成功的實(shí)現(xiàn)了牙齒的分割。除了牙頜模型，本算法還適用于其他有類似特征的STL模型邊界查找與分割。該算法的不足之處在于，用戶難以一次給出合適的閾值分割出想要的結(jié)果，另外，許多復(fù)雜的模型中還是需要一些必要的用戶交互才能得到需要的結(jié)果。

［1］ 王邦康.口腔正畸矯治方法的新進(jìn)展——無托槽隱形矯治器的研究與展望［J］.北京口腔醫(yī)學(xué)，2005，13（1）：2-5.

WANG Bangkang.New progress of orthodontics treatment method：The research and prospect of without braces stealth rectification device［J］.Beijing Journal of Stomatology，2005，13（1）：2-5.

［2］ 張征宇，丁玉成，洪 軍.STL模型分割截面的三角剖分算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（6）：1240-1245.

ZHANG Zhengyu，DING Yucheng，HONG Jun.A triangulating algorithm for cutting cross-section of STL model［J］.Journal of Computer-aided Design &Computer Graphics，2005，17（6）：1240-1245.

［3］ 陳有蘭，李占利，師玉璞.一種三角網(wǎng)格模型的邊界提取快速算法［J］.計(jì)算機(jī)工程，2012，38（13）：208-211.

CHEN Youlan，LI Zhanli，SHI Yupu.Fast algorithm for boundary extraction of triangular mesh model［J］.Computer Engineering，2012，38（13）：208-211.

［4］ 紀(jì) 峰.虛擬牙齒矯正中的組織分割研究［J］.北華大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，9（2）：189-192.

JI Feng.On tissue segmentation in virtual orthodontic treatment［J］.Journal of Beihua University（Natural Science），2008，9（2）：189-192.

［5］ 劉 瑜.計(jì)算機(jī)輔助口腔正畸算法研究［D］.重慶：重慶大學(xué)，2012.

LIU Yu.Research on Algorithms in Computer Aided Orthodontic［D］.Chongqing：Chongqing University，2012.

［6］ 李成軍，張 弛，汪國平.交互標(biāo)記控制的快速網(wǎng)格分割［J］.北京大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，42（5）：662-667.

LI Chengjun，ZHANG Chi，WANG Guoping.Fast marker-controlled interactive mesh segmentation［J］.Acta Scientiarum Naturalium Universitatis Pekinensis，2006，42（5）：662-667.

［7］ 寧小娟.牙齒數(shù)字模型的分割方法研究［D］.西安：西安科技大學(xué)，2007.

NING Xiaojuan.Research on Segmentation Methods of Dental Digital Model［D］.Xi′an：Xi′an University of Science and Technology，2007.

［8］ ZHANG C，ZHANG Ning，LI Chengjun.Marker-controlled perception-based mesh segmentation［J］.Proceedings of the Third International Conference on Image and Graphics，2004，4：18-20.

［9］ 管慧娟.基于區(qū)域的圖像分割方法［D］.大連：大連理工大學(xué)，2006.

GUAN Huijuan.Study on Region based Image Segmentation Methods［D］.Dalian：Dalian University of Technology，2006.

［10］ MANGAN A P，WHITAKER R T.Partitioning 3Dsurface meshes using watershed segmentation［J］.IEEE Transactions on Visualization and Computer Graphics，1999，5（4）：308-321.

［11］ 李海濱，杜益福，劉 彬.基于圖割和分水嶺變換的圖像分割算法［J］.燕山大學(xué)學(xué)報(bào)，2013，37（2）：143-148.

LI Haibin，DU Yifu，LIU Bin.Image segmentation method based on graph cut and watershed transformation［J］.Journal of Yanshan University，2013，37（2）：143-148.

［12］ 熊福松.基于閾值選取的圖像分割方法研究［D］.無錫：江南大學(xué)，2007.

XIONG Fusong.The Research of Image Segmentation Method Based on Threshold Selection［D］.Wuxi：Jiangnan University，2007.

［13］ 全紅艷，張?zhí)镂?基于區(qū)域生長的網(wǎng)格模型分割技術(shù)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（7）：1011-1016.

QUAN Hongyan，ZHANG Tianwen.Region growth approach for mesh model segmentation［J］.Journal of Computer-Aided Design and Computer Graphics，2006，18（7）：1011-1016.

［14］ 耿建璞，崔洪斌，劉慶華，等.盆式橡膠支座計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)［J］.河北工業(yè)科技，2013，30（1）：50-53.

GENG Jianpu，CUI Hongbin，LIU Qinghua，et al.CAD system for design of pot rubber bearing［J］.Hebei Journal of Industrial Science and Technology，2013，30（1）：50-53.

［15］ 原建偉，李愛國，李文宇.GPU編程模型中存儲(chǔ)體沖突的研究［J］.河北工業(yè)科技，2013，30（1）：39-41.

YUAN Jianwei，LI Aiguo，LI Wenyu.Study of bank conflict in GPU programming model［J］.Hebei Journal of Industrial Science and Technology，2013，30（1）：39-41.