基于特征线分段技术的牙齿分割算法

肖 兵，魏 昕，胡 伟，夏鸿建

(广东工业大学 机电工程学院，广州 510006) (*通信作者电子邮箱1067197284@qq.com)

基于特征线分段技术的牙齿分割算法

肖 兵*，魏 昕，胡 伟，夏鸿建

(广东工业大学 机电工程学院，广州 510006) (*通信作者电子邮箱1067197284@qq.com)

牙齿分割是计算机口腔正畸的重要技术，针对三维牙颌模型直接进行牙齿分割而不对齿间融合区域进行处理会存在精确度较差、缺失侧面形状的问题,以及现有牙齿形状建模方法交互多、效率低的问题，提出一种基于特征线分段技术的牙齿分割算法。根据曲率信息筛选特征区域并采用形态学算法提取牙列特征线；结合特征线分段和分支点匹配算法以及形态学膨胀操作实现齿间融合区域的自动识别；利用匹配的分支点对齿间孔洞搭桥修补，实现牙齿形状的自动恢复；提取齿间龈缘线，然后以所有龈缘线作为牙齿分割线分离出单颗牙齿。实验结果表明，该算法不仅能准确分离出具有侧面形状的单颗牙齿，而且避免了牙齿形状建模时的交互操作，而且与手动识别并删除齿间粘连区域、采用曲面能量约束方式重建齿间缺失曲面的方法相比，提高了牙齿分割效率60%～90%。

三维牙颌模型；牙齿分割；牙齿形状建模；形态学；融合区域

0 引言

牙齿分割是计算机辅助口腔正畸[1]的重要技术。在口腔计算机辅助设计与制造(Computer Aided Design and Manufacturing, CAD/CAM)系统[2-3]中，为了测量牙齿参数，模拟牙齿的移动以及重新排列牙齿，都需要预先从三维牙颌模型中分离出单颗牙齿。然而，受扫描精度及三维重建精度等因素限制，数字化三维牙颌模型相邻的牙齿通常粘连在一起，没有清晰的牙缝，导致直接分割出的单颗牙齿局部形状缺失[4]。加之牙齿形态、排列的差异，使得自动且精确的牙齿分割较为困难。

近年来，牙齿分割领域有许多较为自动的方法[5-9]被提出，这些方法直接利用牙列特征线进行牙齿分割，虽在一定程度上分离出了单颗牙齿，但未对齿间融合区域进行处理，使得分割结果不够精确。为此，尹骏等[10]在牙齿分割时避开融合区域，该方法不仅交互少而且速度快，但所得牙齿侧面形态不完整，不便于口腔CAD/CAM系统中的使用。

为恢复牙齿侧面缺失形状，一些牙齿形状建模方法[4,11-12]被提出。文献[4]首先识别并删除齿间粘连区域，然后采用曲面能量约束的方式重建齿间缺失曲面，达到了较高的逼近度，但其粘连区域的识别需要手工框选，而且牙齿形状恢复环节的孔洞桥接也需要交互；文献[11]提出一种有效的孔洞修补算法精确地重建了牙齿侧面缺失形状，但该算法需要手工构造牙齿侧面孔洞；文献[12]利用控制曲线裁切分割区域，并通过建立参数化曲面重建了齿间缺失区域，但为了避免重建的邻牙侧面产生干涉，该方法需要手工调整参数曲面。总之，上述牙齿形状建模方法虽然较好地恢复了牙齿侧面形状，但都需要对多颗牙齿进行重复的交互操作，不仅费时费力、对操作人员要求高，还可能因操作失误而影响最终的分割结果。为此，本文在文献[4]的基础上提出一种准确的、少交互的牙齿分割算法。

1 技术路线

根据牙齿的形态学特征和口腔生物医学规律，要想从三维牙颌模型准确分离出单颗牙齿，有必要进行牙齿形状建模。为了避免牙齿形状建模中的交互、提升牙齿分割整个过程的自动化程度，本文提出一种基于特征线分段的牙齿分割算法。如图1，该算法主要步骤为：首先，对输入的三维牙颌模型以平均曲率作为特征点的度量，采用形态学算法提取牙列特征线；然后，根据特征线几何信息识别分支点并对特征线进行分段；接着，通过分支点匹配算法识别出融合区域特征线；进一步，对融合区域特征线采用形态膨胀操作，实现齿间融合区域的自动识别；在删除齿间融合区域后，将齿间缺失区域作为独立孔洞，利用匹配的分支点进行搭桥修补，实现单颗牙齿缺失形状的自动恢复；最后提取齿间龈缘线，并以全部龈缘线作为牙齿分割线分离出单颗牙齿。

图1 本文牙齿分割算法流程

2 牙齿自动分割

2.1 牙列特征线提取

牙列特征线提取是牙齿分割必不可少的步骤。虽然三维牙颌模型表面是极其不规则的复杂曲面，但其龈缘区域和齿间融合区域有着明显的特征，通常呈“谷底”状分布，因而可以根据其对应的曲率变化进行分析和划分。本文采用文献[5]的方法，以平均曲率作为特征点的度量，通过基于形态学的特征线提取方法提取牙列特征线。对于大多数特征明显的牙颌模型，该方法都能较好地提取牙列特征线(如图2所示)。

图2 牙列特征线

2.2 特征线分段

由于齿间融合区域的存在，直接用2.1节提取的牙列特征线进行牙齿分割得到的结果并不精确。牙齿形状建模虽能解决这一问题，但齿间融合区域的自动识别仍是一个技术难题。为解决该问题，本文提出一种特征线分段技术。首先，将图2所示的牙列特征线分为龈缘线和融合区域特征线两部分。由于理想的牙列特征线不存在开环特征线且仅在龈缘线与融合区域相交处出现分支，因而可通过分支点将特征线分段并结合牙齿特征信息区分出融合区域特征线。

1)识别分支点。观察已提取的牙列特征线发现，非分支处的特征点首尾相连，有且仅有两个特征点与之相邻；而分支点的1-邻域特征点多于两个(其数目通常为3)。根据这一规律，即可识别出所有分支点，如图3(a)所示。然而，由于部分分支点可能与两个1-邻域特征点同属一个三角片，所以可能在同一分支处识别出三个分支点，即有两个冗余分支点。实际上，这样的三个点中具体选择哪一个作为分支点并不重要，所以可任意剔除其中两个点，如图3(b)所示，因此，识别分支点的具体步骤为：

步骤1 遍历所有特征点，若特征点p(i)的1-邻域特征点数大于2，则将p(i)加入分支点集合Jets中。

步骤2 检查Jets中分支点，若存在3个分支点互为1-邻域点，则将其中任意两个从Jets中剔除。

图3 识别分支点

2)特征线分段。利用识别的分支点对牙列特征线分段，每段特征线都以分支点作为首末端点；若存在孤立闭环也将其视为一段。将各段特征线依次存入集合FLines中。

3)编辑特征线。由于数字化三维牙颌曲面的复杂性及模型质量的差异，采用2.1节的自动方法提取的牙列特征线难免存在一些瑕疵：存在少量多余分支或缺少某段特征线。为满足牙齿分割要求，在这种情况下对提取的特征线进行少量的编辑是必要的。本文提出两个简单的特征线编辑操作：剔除特征线和增添特征线。由于特征线已分段存储，对于特征线上的多余分支，可直接选中加以删除，如图4(a)所示；对于由牙颌模型局部特征不明显导致某段特征线缺失的情形，可交互指定2～3个点，即可添加特征线，如图4(b)所示。

2.3 牙齿形状建模

三维牙颌模型上牙齿形状建模的目的是重建牙齿侧面缺失形状，其步骤一般包括齿间融合区域的检测、提取删除和牙齿形状恢复。文献[4，11]均将齿间缺失区域视为孔洞，并采用孔洞填充、网格细分优化和拓扑调整的策略精确恢复了牙齿侧面形状，但文献[11]的方法需要为每颗牙齿构造封闭的孔洞边界，交互量大，效率低，因此本文对文献[4]的方法加以改进，根据牙颌形态特征自动识别齿间融合区域并利用匹配的分支点对齿间孔洞桥接，既保留原方法的精确度，又避免繁琐的人工操作。

图4 编辑特征线

2.3.1 齿间融合区域的识别与删除

1)融合区域特征线的识别。通过对大量的三维牙颌模型进行观察分析表明，同一融合区域特征线的两分支点间距离总小于牙齿同侧(同为颊(唇)侧或同为舌侧)两邻近分支点间的距离，如图5(a)，总存在a

2)齿间融合区域识别。设M={v1,v2,…,vi,…,vn}表示三维牙颌模型对应的三角网格曲面，M上任意点vi及其所有邻接点构成的1环邻域定义为：

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

依此类推，vi的n环邻域嵌套定义为：

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

设F表示三角网格上的特征区域，在形态学[13]中，膨胀操作(dilaten(F) )表示对F中每个点，令其n环邻域点都成为特征点，其数学定义为：

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

对识别的融合区域特征线(如图6(a))执行m次形态学膨胀操作，直至覆盖齿间融合区域，即实现齿间融合区域的自动识别。实验分析表明，m的值一般在2～4，其大小取决于融合区域网格密度，当网格较密时m值适当增加。本文取m=3，对大多数牙颌模型都能取得较好的结果，识别的齿间融合区域效果如图6(b)所示。

3)齿间融合区域的删除。对齿间融合区域进行删除，得到齿间孔洞如图6(c)所示。为了在后续牙齿形状修复阶段实现孔洞修补的自动搭桥，需在删除齿间融合区域过程中保留已匹配的分支点。

图5 融合区域特征线的识别

图6 齿间融合区域的识别与删除

2.3.2 牙齿形状恢复

健康牙齿的侧面形状具有近似一阶连续的属性，并且侧面开口对应的曲面是规则的。文献[4]根据齿间孔洞边界的顶点信息，采用曲面能量约束的方式构建缺失部分对应的曲面，所得结果与原始牙齿有较高的逼近度，因此，本文采用该方法进行牙齿形状建模并进行适当的改进。

然后，对初始恢复曲面Pmin进行局部细分优化，得到与原始牙颌模型网格密度相近且近似符合Delaunay划分准则的中间恢复曲面(如图7(b)所示)，记作Prefine。

最后，根据牙齿的个性特征，以齿间孔洞边界点及其外侧1-邻域点作为约束变形点，对优化细分曲面Prefine进行二阶Laplacian变形，得到在边界和内部满足C1连续的最终恢复曲面Pdeform，其效果如图7(c)所示。

图7 牙齿形状恢复

2.4 获取牙齿分割线

经过2.3节的牙齿形状建模，相邻牙齿之间重现清晰的牙缝，牙缝的“谷底”为齿间龈缘且与颊(唇)舌侧龈缘自然过渡。依照牙齿分割经验，此时的龈缘线即可作为牙齿分割线，但牙颌模型的数据量通常都较大，重新提取完整的龈缘线需要不小的时间消耗。考虑到前面提取的牙齿特征线已包含大部分龈缘线——除去融合区域的部分均为颊(唇)舌侧龈缘线，为提升牙齿分割整体效率，避免大量特征线的重复提取，本文在牙齿形状恢复后保留这部分龈缘线(如图8(a)所示)，而本环节只需再提取齿间的一小部分即可获得完整的龈缘线。

图8 获取牙齿分割线效果

根据牙体形态，齿间龈缘线可视为已匹配的分支点间的特征路径。张长东等[14]将牙齿生物特征线提取问题转化为两点间的最优特征路径搜索问题，提出基于启发式搜索策略的半自动提取方法。本文采用该方法提取齿间龈缘线：对于每对匹配的分支点，以其中一点作为起点、另一点作为终点进行启发式搜索，相应的启发函数为：

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

其中：fdir1表示当前搜索方向与上一搜索方向的夹角关系；fD表示下一搜索点到起点的欧氏距离；fdir2表示下一搜索方向与始末端点方向的夹角关系；fC表示前后搜索点平均曲率的差值。与文献[14]不同，上述搜索起点、终点是自动获得的，因而本文齿间龈缘线的提取也是自动的，提取效果如图8(b)所示。

将齿间龈缘线与颊(唇)舌侧龈缘线一起作为牙齿分割线，以之分离出单颗牙齿，即完成牙齿分割。

3 实验结果分析

为验证本文方法的有效性和适应性，对多副三维牙颌模型进行测试，所有测试均在处理器为Corei5-4460 3.20GHz，内存4GB，64位Windows7系统的平台上进行。图9、10所示为两种具有典型代表性的三维牙颌模型及对应的牙齿分割结果。

图9所示为完整的牙颌模型。其中，图9(a)中对应的初始三维牙颌模型包含103 541个顶点/205 325个三角片，图9(b)～(e)为牙齿分割几个关键步骤的结果，图9(f)为最终牙齿分割结果，图9(g)为文献[10]避开融合区域分离的单颗牙齿对应的放大显示，图9(h)为本文算法分离的单颗牙齿对应的放大显示。

图9 完整的三维牙颌模型牙齿分割结果

图10所示为不完整的牙颌模型(包含基台)，其中图10(a)对应的初始三维牙颌模型包含68 425个顶点/135 119个三角片。

图10 不完整的三维牙颌模型牙齿分割结果

由图9(c)、10(c)可以看出，该方法对齿间融合区域有较好的识别效果。对比图9(g)与图9(h)、图10(g)与图10(h)，可以看出本文牙齿分割方法能达到与文献[4]算法同等的效果，重建的牙齿侧面形状达C1连续，精确地分割出了单颗牙齿。相比文献[10]的牙齿分割算法，本文算法得到的牙齿具有更高的精确度且形态更加完整，而相比文献[4,11-12]的牙齿形状建模算法，本文算法避免了人工交互，具有更高的自动化程度。图9、10共同说明了本文算法可对完整和不完整的三维牙颌模型均能得到理想的分割结果，具有较好的适用性。

表1列出了几组牙颌模型从开始到牙齿分割完成的分步运行时间和总时间，其中，Model1、Model3为完整牙列(14颗牙)，Model2为不完整牙列。对于Model1、Model3，采用本文算法自动识别融合区域并删除分别需要0.111s、0.068s；若采用文献[4]手工框选的方式，在操作熟练的情况下，拾取每个齿间融合区域也平均需要2～5s，识别所有融合区域则需26～65s。对于常规的牙颌模型，本文算法均能在30s以内完成牙齿分割。粗略估计，本文算法相比文献[4]算法对牙齿分割总时间减少60%～90%，相比操作更加复杂的文献[11-12]则提升效率更多。由此可见，本文算法在包含牙齿形状建模并去除大部分交互的情况下仍具有快速性。

表1 算法运行时间 s

4 结语

针对牙齿分割需要恢复牙齿侧面形状和牙齿形状建模需要较多交互的问题，本文提出一种基于特征线分段的牙齿分割算法。经实验表明，该算法具有以下优点：1)智能化程度高。整个牙齿分割过程交互极少，实现了全自动的牙齿形状建模。2)分割精度高。避免了交互操作产生的误差，牙齿侧面恢复曲面达C1连续，与原始牙齿相比具有较高的逼近度。3)适应性强。对不完整的牙颌模型也能准确地分割。4)运行速度快。常规的牙颌模型均能在30s以内完成牙齿分割。当然，本文算法也有一定的局限性，当牙颌模型特征不明显或网格质量较差时，需要在提取牙列特征线之前对模型进行一定的预处理操作。

)

[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] 郝国栋，程筱胜，戴宁，等.基于形态学的牙齿模型交互分割[J].中国制造业信息化,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] 尹骏,刘森.避开融合区域的牙齿分割算法[J].计算机工程与设计,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] 范然,钮叶新,金小刚,等.计算机辅助牙齿隐形正畸系统[J].计算机辅助设计与图形学学报,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] 张长东,戴宁,廖文和,等.基于启发式搜索策略的牙齿生物特征线提取技术[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—)，男，湖北十堰人，硕士研究生，主要研究方向：计算机图形学、计算机辅助生物医学工程； 魏昕(1964—)，女，江西南昌人，教授，博士，主要研究方向：精密与超精密加工、计算机辅助设计与制造； 胡伟(1978—)，男，湖北黄冈人，讲师，博士，主要研究方向：精密与超精密加工、计算机辅助设计与制造； 夏鸿建(1978—)，男，江西上饶人，讲师，博士，主要研究方向：参数化设计、智能计算机辅助设计。

1001- 9081(2017)03- 0844- 05

10.11772/j.issn.1001- 9081.2017.03.844

TP391.41

A