牙齿分割是计算机辅助口腔正畸[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,该算法主要步骤为:首先,对输入的三维牙颌模型以平均曲率作为特征点的度量,采用形态学算法提取牙列特征线;然后,根据特征线几何信息识别分支点并对特征线进行分段;接着,通过分支点匹配算法识别出融合区域特征线;进一步,对融合区域特征线采用形态膨胀操作,实现齿间融合区域的自动识别;在删除齿间融合区域后,将齿间缺失区域作为独立孔洞,利用匹配的分支点进行搭桥修补,实现单颗牙齿缺失形状的自动恢复;最后提取齿间龈缘线,并以全部龈缘线作为牙齿分割线分离出单颗牙齿。
牙列特征线提取是牙齿分割必不可少的步骤。虽然三维牙颌模型表面是极其不规则的复杂曲面,但其龈缘区域和齿间融合区域有着明显的特征,通常呈“谷底”状分布,因而可以根据其对应的曲率变化进行分析和划分。本文采用文献[5]的方法,以平均曲率作为特征点的度量,通过基于形态学的特征线提取方法提取牙列特征线。对于大多数特征明显的牙颌模型,该方法都能较好地提取牙列特征线(如图 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中剔除。
2) 特征线分段。利用识别的分支点对牙列特征线分段,每段特征线都以分支点作为首末端点;若存在孤立闭环也将其视为一段。将各段特征线依次存入集合FLines中。
3) 编辑特征线。由于数字化三维牙颌曲面的复杂性及模型质量的差异,采用2.1节的自动方法提取的牙列特征线难免存在一些瑕疵:存在少量多余分支或缺少某段特征线。为满足牙齿分割要求,在这种情况下对提取的特征线进行少量的编辑是必要的。本文提出两个简单的特征线编辑操作:剔除特征线和增添特征线。由于特征线已分段存储,对于特征线上的多余分支,可直接选中加以删除,如图 4(a)所示;对于由牙颌模型局部特征不明显导致某段特征线缺失的情形,可交互指定2~3个点,即可添加特征线,如图 4(b)所示。
2.3 牙齿形状建模三维牙颌模型上牙齿形状建模的目的是重建牙齿侧面缺失形状,其步骤一般包括齿间融合区域的检测、提取删除和牙齿形状恢复。文献[4, 11]均将齿间缺失区域视为孔洞,并采用孔洞填充、网格细分优化和拓扑调整的策略精确恢复了牙齿侧面形状,但文献[11]的方法需要为每颗牙齿构造封闭的孔洞边界,交互量大,效率低,因此本文对文献[4]的方法加以改进,根据牙颌形态特征自动识别齿间融合区域并利用匹配的分支点对齿间孔洞桥接,既保留原方法的精确度,又避免繁琐的人工操作。
1) 融合区域特征线的识别。通过对大量的三维牙颌模型进行观察分析表明,同一融合区域特征线的两分支点间距离总小于牙齿同侧(同为颊(唇)侧或同为舌侧)两邻近分支点间的距离,如图 5(a),总存在a<b1, a<b2。根据这一规律,通过匹配分支点实现融合区域特征线的自动识别:对于分支点集合Jets中任意一个分支点Jets(i),根据距离最短原则从以Jets(i)为端点的分段特征线中选出另一端点Jets(j)作为匹配点,相应的分段特征线即为融合区域特征线。例如,在图 5(b)中,对于分支点A,以之为端点的分段特征线共有3条,分别为特征线a、特征线b和特征线c,这3条特征线的另一端点分别为分支点B、分支点C和分支点D。比较这3个分支点到分支点A的距离,其中分支点B到分支点A的距离最短,则B为A的匹配点;相应地,特征线a为融合区域特征线。通过这样的方式,匹配所有分支点,同时识别所有的融合区域特征线。
2) 齿间融合区域识别。设M={v1, v2, …, vi, …, vn}表示三维牙颌模型对应的三角网格曲面,M上任意点vi及其所有邻接点构成的1环邻域定义为:
$nh{d^1}\{ {v_i}\} : = \{ {v_i}\} \cup \{ {v_j}|\exists edge\{ {v_i},{v_j}\} \} $ |
依此类推,vi的n环邻域嵌套定义为:
$nh{{d}^{n}}\{{{v}_{i}}\}:=nhd(nh{{d}^{n-1}}\{{{v}_{i}}\});\text{ }n>1$ |
设F表示三角网格上的特征区域,在形态学[13]中,膨胀操作(dilaten(F) )表示对F中每个点,令其n环邻域点都成为特征点,其数学定义为:
$dilat{{e}^{n}}(F):\{{{v}_{j}}|{{v}_{i}}\in F:{{v}_{j}}\in nh{{d}^{n}}\{{{v}_{i}}\}\}$ |
对识别的融合区域特征线(如图 6(a))执行m次形态学膨胀操作,直至覆盖齿间融合区域,即实现齿间融合区域的自动识别。实验分析表明,m的值一般在2~4,其大小取决于融合区域网格密度,当网格较密时m值适当增加。本文取m=3,对大多数牙颌模型都能取得较好的结果,识别的齿间融合区域效果如图 6(b)所示。
3) 齿间融合区域的删除。对齿间融合区域进行删除,得到齿间孔洞如图 6(c)所示。为了在后续牙齿形状修复阶段实现孔洞修补的自动搭桥,需在删除齿间融合区域过程中保留已匹配的分支点。
2.3.2 牙齿形状恢复健康牙齿的侧面形状具有近似一阶连续的属性,并且侧面开口对应的曲面是规则的。文献[4]根据齿间孔洞边界的顶点信息,采用曲面能量约束的方式构建缺失部分对应的曲面,所得结果与原始牙齿有较高的逼近度,因此,本文采用该方法进行牙齿形状建模并进行适当的改进。
首先,采用面积最小化机制对齿间孔洞B={v1b, v2b, …, vnb}进行三角剖分,由于齿间孔洞具有典型的 “马鞍”形状,且每个孔洞为一对邻牙所共有,所以剖分前需要通过桥接生成两个独立的齿间开口,即B=B1+B2,其中B1与B2分别与单颗牙齿的缺失部分相对应。分别对侧面开口B1、B2进行剖分得到子曲面P1min、P2min,则齿间开口的初始恢复曲面为Pmin=P1min+P2min。鉴于文献[4]并未提及齿间孔洞的具体桥接方式,本文给出一种自动桥接方法:设2.3.1节已匹配的分支点集合为Map={(J1a, J1b), (J2a, J2b), …, (Jna, Jnb)},遍历Map找到一组分支点(Jia, Jib)满足{(Jia, Jib)|Jia∈B, Jib∈B, },则(Jia, Jib)即为一对搭桥点。进而,对于齿间孔洞B={v1b, …, Jia, …, vib, …, Jib…, vnb},两个独立的齿间开口可表示为B1={Jia, …, vib, …, Jib},B2={Jib, …, vnb, v1b, …, Jia}。通过本方法得到的初始恢复曲面Pmin如图 7(a)所示。
然后,对初始恢复曲面Pmin进行局部细分优化,得到与原始牙颌模型网格密度相近且近似符合Delaunay划分准则的中间恢复曲面(如图 7(b)所示),记作Prefine。
最后,根据牙齿的个性特征,以齿间孔洞边界点及其外侧1-邻域点作为约束变形点,对优化细分曲面Prefine进行二阶Laplacian变形,得到在边界和内部满足C1连续的最终恢复曲面Pdeform,其效果如图 7(c)所示。
2.4 获取牙齿分割线经过2.3节的牙齿形状建模,相邻牙齿之间重现清晰的牙缝,牙缝的“谷底”为齿间龈缘且与颊(唇)舌侧龈缘自然过渡。依照牙齿分割经验,此时的龈缘线即可作为牙齿分割线,但牙颌模型的数据量通常都较大,重新提取完整的龈缘线需要不小的时间消耗。考虑到前面提取的牙齿特征线已包含大部分龈缘线——除去融合区域的部分均为颊(唇)舌侧龈缘线,为提升牙齿分割整体效率,避免大量特征线的重复提取,本文在牙齿形状恢复后保留这部分龈缘线(如图 8(a)所示),而本环节只需再提取齿间的一小部分即可获得完整的龈缘线。
根据牙体形态,齿间龈缘线可视为已匹配的分支点间的特征路径。张长东等[14]将牙齿生物特征线提取问题转化为两点间的最优特征路径搜索问题,提出基于启发式搜索策略的半自动提取方法。本文采用该方法提取齿间龈缘线:对于每对匹配的分支点,以其中一点作为起点、另一点作为终点进行启发式搜索,相应的启发函数为:
$f(n) = {f_{{\rm{dir}}1}} + {f_{\rm{D}}} + {f_{{\rm{dir2}}}} + {f_{\rm{C}}}$ |
其中:fdir1表示当前搜索方向与上一搜索方向的夹角关系;fD表示下一搜索点到起点的欧氏距离;fdir2表示下一搜索方向与始末端点方向的夹角关系;fC表示前后搜索点平均曲率的差值。与文献[14]不同,上述搜索起点、终点是自动获得的,因而本文齿间龈缘线的提取也是自动的,提取效果如图 8(b)所示。
将齿间龈缘线与颊(唇)舌侧龈缘线一起作为牙齿分割线,以之分离出单颗牙齿,即完成牙齿分割。
3 实验结果分析为验证本文方法的有效性和适应性,对多副三维牙颌模型进行测试,所有测试均在处理器为Core i5-4460 3.20 GHz,内存4 GB,64位Windows 7系统的平台上进行。
图 9、10所示为两种具有典型代表性的三维牙颌模型及对应的牙齿分割结果。
图 9所示为完整的牙颌模型。其中,图 9(a)中对应的初始三维牙颌模型包含103541个顶点/205325个三角片,图 9(b)~(e)为牙齿分割几个关键步骤的结果,图 9(f)为最终牙齿分割结果,图 9(g)为文献[10]避开融合区域分离的单颗牙齿对应的放大显示,图 9(h)为本文算法分离的单颗牙齿对应的放大显示。
图 10所示为不完整的牙颌模型(包含基台),其中图 10(a)对应的初始三维牙颌模型包含68425个顶点/135119个三角片。
由图 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.111 s、0.068 s;若采用文献[4]手工框选的方式,在操作熟练的情况下,拾取每个齿间融合区域也平均需要2~5 s,识别所有融合区域则需26~65 s。对于常规的牙颌模型,本文算法均能在30 s以内完成牙齿分割。粗略估计,本文算法相比文献[4]算法对牙齿分割总时间减少60%~90%,相比操作更加复杂的文献[11-12]则提升效率更多。由此可见,本文算法在包含牙齿形状建模并去除大部分交互的情况下仍具有快速性。
针对牙齿分割需要恢复牙齿侧面形状和牙齿形状建模需要较多交互的问题,本文提出一种基于特征线分段的牙齿分割算法。经实验表明,该算法具有以下优点:1) 智能化程度高。整个牙齿分割过程交互极少,实现了全自动的牙齿形状建模。2) 分割精度高。避免了交互操作产生的误差,牙齿侧面恢复曲面达C1连续,与原始牙齿相比具有较高的逼近度。3) 适应性强。对不完整的牙颌模型也能准确地分割。4) 运行速度快。常规的牙颌模型均能在30 s以内完成牙齿分割。当然,本文算法也有一定的局限性,当牙颌模型特征不明显或网格质量较差时,需要在提取牙列特征线之前对模型进行一定的预处理操作。
[1] | MOTOHASHI N, KURODA T. A 3D computer-aided design system applied to diagnosis and treatment planning in orthodontics and orthognathic surgery[J]. European Journal of Orthodontics, 1999, 21 (3) : 263-274. doi: 10.1093/ejo/21.3.263 |
[2] | LIU P-R. A panorama of dental CAD/CAM restorative systems[J]. Compendium of Continuing Education in Dentistry, 2008, 26 (7) : 507-508. |
[3] | MIYAZAKI T, HOTTA Y, KUNII J, et al. A review of dental CAD/CAM:current status and future perspectives from 20 years of experience[J]. Dental Materials Journal, 2009, 28 (1) : 44-56. doi: 10.4012/dmj.28.44 |
[4] | YUAN T, LIAO W, DAI N, et al. Single-tooth modeling for 3D dental model[J]. International Journal of Biomedical Imaging, 2010, 2010 . |
[5] | 郝国栋, 程筱胜, 戴宁, 等. 基于形态学的牙齿模型交互分割[J]. 中国制造业信息化, 2008, 37 (1) : 36-39. ( HAO G D, CHENG X S, DAI N, et al. The morphology-based interactive segmentation of dental models[J]. Manufacturing Information Engineering of China, 2008, 37 (1) : 36-39. ) |
[6] | WONGWAEN N, SINTHANAYOTHIN C. Computerized algorithm for 3D teeth segmentation[C]//ICEIE 2010:Proceedings of the 2010 International Conference on Electronics and Information Engineering. Piscataway, NJ:IEEE, 2010, 1:277-280. |
[7] | KRONFELD T, BRUNNER D, BRUNNETT G. Snake-based segmentation of teeth from virtual dental casts[J]. Computer-Aided Design and Applications, 2010, 7 (2) : 221-233. doi: 10.3722/cadaps.2010.221-233 |
[8] | KUMAR Y, JANARDAN R, LARSON B, et al. Improved segmentation of teeth in dental models[J]. Computer-Aided Design & Applications, 2011, 8 (2) : 211-224. |
[9] | WU K, CHEN L, LI J, et al. Tooth segmentation on dental meshes using morphologic skeleton[J]. Computers & Graphics, 2014, 38 : 199-211. |
[10] | 尹骏, 刘森. 避开融合区域的牙齿分割算法[J]. 计算机工程与设计, 2016, 37 (1) : 180-184. ( YIN J, LIU S. Tooth segmentation algorithm based on fusion region avoidance[J]. Computer Engineering and Design, 2016, 37 (1) : 180-184. ) |
[11] | QIU N, FAN R, YOU L, et al. An efficient and collision-free hole-filling algorithm for orthodontics[J]. The Visual Computer, 2013, 29 (6) : 577-586. |
[12] | 范然, 钮叶新, 金小刚, 等. 计算机辅助牙齿隐形正畸系统[J]. 计算机辅助设计与图形学学报, 2013, 25 (1) : 81-92. ( FAN R, NIU Y X, JIN X G, et al. Computer aided invisible orthodontic treatment system[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25 (1) : 81-92. ) |
[13] | ROESSL C, KOBBELT L, SEIDEL H-P. Extraction of feature lines on triangulated surfaces using morphological operators[C]//Proceedings of the 2000 AAAI Symposium on Smart Graphics. Menlo Park, CA:AAAI Press, 2000:71-75. |
[14] | 张长东, 戴宁, 廖文和, 等. 基于启发式搜索策略的牙齿生物特征线提取技术[J]. 中国机械工程, 2012, 23 (13) : 1567-1571. ( ZHANG C D, DAI N, LIAO W H, et al. Extraction of dental biological feature line based on heuristic search strategy[J]. China Mechanical Engineering, 2012, 23 (13) : 1567-1571. ) |