牙颌模型区域标记分割算法

岳彦芳，杨 光，张永弟，吴松和

（河北科技大学机械工程学院，河北石家庄 050018）

牙颌模型一般都是通过三维扫描得到的整体STL数字模型［1-2］，牙齿矫治通常只对单颗或者几颗牙齿进行移动或者转动。因此，将需要移动的牙齿从整体STL牙颌数字模型中自动分离出来便成为牙颌隐形矫治技术的关键。已有的自动分割算法主要有以下几种：边界识别法［3］、矢量逼近法［4］、交互标记控制法［5-6］等。边界识别法算法简单、效率较高，但分割边界比较粗糙、不明显，牙冠部分不完整，效果较差；矢量逼近法可以分割出较为理想的边界，但每次都会将所有牙冠和牙龈分割开来，不能只分割所需要移动的牙齿，效率较低，而且牙龈的部分边缘也可能被错误的分割到牙冠上；交互标记控制法是一种相对理想的算法，通过手动拾取面片作为标记，自动扩展完成分割，分割出的边界比较完整。但该算法的缺点是种子面片只是单个三角面片，如果一颗牙上有多个弯曲函数较小的局部表面，就会产生不完全分割的结果。

本文对交互标记控制法进行了改进，提出一种区域选择的分割算法。使用该算法可以高效的将单颗牙齿从牙颌模型中分割出来，完成牙齿的矫正。并在3DSMax平台上利用MAX Script脚本语言进行二次开发，实现了自动分割牙齿。

1 STL牙颌模型特点

STL模型可以通过点云逆向处理获得；也可以通过对已有的三维模型表面进行三角化离散得到，即按照精度要求使用一定数量的三角面片来逼近模型表面形状。在后一个方法中，每个三角面片用三角形的顶点坐标（xi，yi，zi）（其中i=1，2，3）和一个法向量n（用来指明实体包含在面片的哪一边）表示［7］。模型中每个面、边、顶点都有唯一的序列号，牙颌的STL模型较其他模型主要有以下特点：

1）切牙的舌向是凹的，唇向是凸的，但牙冠上邻接两三角形的弯曲函数值较龈缘处的要大，这也是该分割算法实现的依据，在分割算法中会讲到；

2）某些牙冠的表面可能凸凹不平的局部表面，由其在磨牙的顶部其邻接两三角形的弯曲函数值较龈缘处的要小，因此用阈值方法很难全部选择；

3）不同患者的牙颌模型形状不规则，大小不统一，不同人的牙颌模型基本没有任何的联系，因此很难对单个模型形状进行宏观的研究而运用到所有的模型。

2 分割算法

交互标记控制法［8］是目前牙齿分割算法中较为理想的一种算法，以下是该法所需完成的工作。

2.1 交互标记控制法

该算法是在分水岭算法［9-10］的基础上提出来的，将标记作为种子，从种子点出发，完成分割过程。主要包括3个关键步骤。

1）选取单个面片作为标记 本算法中，交互标记输入的是单个面片作为种子面片。缺点是在单颗牙上，有一些局部的弯曲函数值较龈缘处邻接两三角形的弯曲函数值小［12-13］。如果阈值（通过交互方式输入，与相邻面片的弯曲函数值进行对比的一个中间值）稍小，则这些局部部分无法选择，反之则会把牙龈部分也错误的选取，因此少数牙总是无法将牙冠完整的选择。

2）计算相邻面片弯曲函数 设2个三角面片f1和f2，其单位法向量分别为n1和n2，设AC为公共边，AB为非公共边，如图1所示。则面片f1，f2的相对弯曲函数为

图1 相邻两面弯曲程度函数Fig.1 Bending degree expression about adjacent surfaces

显然C（f1，f2）∈［-1，1］，当f1和f2的边界为凹边界时，C（f1，f2）为负，边界为凸边界时，C（f1，f2）为正，且两相邻面片之间的弯曲程度函数值只与它们之间的夹角有关［5］。

3）分割算法 将2.1中1）得到的种子面片的相邻面压入堆栈中，作为堆栈的初始化。计算出其与3个相邻面片的3个相对弯曲函数值C（curvature），将C由大到小重新排列后压入栈。这样，当前C值最大的元素位于栈顶，最先出栈；C值最小的元素位于栈底，最后出栈。重复以上的堆栈操作过程，从交互标记的种子面片开始，对全部选择合格且与标记连通的面片进行计算。该算法的面片进栈排序操作算法时间复杂度较高。

2.2 算法的改进——区域选择算法

通过上述对交互标记控制法的研究与描述，针对其的不足之处，区域选择分割算法提出如下的改进。

1）区域选择标记方式 针对该问题，本算法提出了区域选择的标记方式，将弯曲函数值较其他部分小的局部部分全部选择，将其按照序列号的大小依次插入队列，这些面片不需要计算其两临面间的相对弯曲函数值，直接作为合格的面片被选取，这样就很好地避免了有些局部弯曲函数值很小不能被自动选择的问题，具体原理如2.2中2）分割算法所讲，如图2所示。图2a）是以交互标记控制法选取的单个面片作为种子面分割结果，图2b）是通过区域选择法选择分割的结果。从分割结果也可以看出，区域选择法优胜于标记控制法。

图2 单面片和区域标记的分割结果对比Fig.2 Comparison of segmentation results using single surface and area mark

2）分割算法 区域选择法分割［13］的目标是把与标记连通且符合要求的面片选择出来。由2.2中1）确定分割的部分后，用一个队列S记录扩展的过程。以S［i］（i=0，1，2，3，…）为交互得到的种子面片，寻找其相邻面片，符合要求且未被选择的面片直接添加到队尾，此过程直到将队列中所有的面片按照队列序列号作为种子面片依次访问一遍，则S［i＋n］（n为后添加的面片）即为符合要求的面片集合，该算法的具体流程图如图3所示。

设R是需要分割的全部面片集合，R1（i=1，2，3，…，i-1）和R2（i，i＋1，i＋2，…）是交互得到的区域标记，队列S存储全部种子面片，V是一个变量，如图4所示。

第1步：将种子面片插入队列。交互得到的种子面片根据ID号由小到大（假设ID（1）＜ID（2）＜ID（3）＜…）插入S中（S=R1∪R2）。第2步：寻找相邻面片。取S第1个元素ID（1）放入V中，找出该面片公共边的3个邻面（ID（2），ID（4），ID（a）），由于面片ID（2），ID（4）已经被访问（2，4交互选入R2），则a是所需要的相邻面片。第3步：判断临面是否符合要求。由2.1中2）算法得到面片1和a的相对弯曲函数值C，将其与交互输入的T进行对比，若C＞T且未被选择，将a直接添加到S中（即插入队尾），种子面片不删除。若C＜T，直接进入下一步。第4步：取下一个元素继续分割。判断是否是队尾元素，是，结束，否则取下一个元素重复上述循环。在该算法的扩展过程中，先按ID号从小到大把S中交互选择的面片全部被作为种子面片访问，再按照插入队列的时间访问新增加的面片，此过程直到S中的面片全部遍历完为止，则S［i］即所需合格面片。

图3 牙齿分割算法流程Fig.3 Procedure of segmentation algorithm

图4 种子面片的临面寻找Fig.4 Seeking the adjacent surface of seed surface

如果按初始阈值分割模型不能获得满意的结果，通过交互输入方式调节阈值的大小，重新进行分割。一般情况下，分割出的都是封闭的区域，可以达到需求。如果牙齿边界上存在一些局部只调节阈值则无法达用户所需要的结果，可以通过交互方式添加到已选择的区域，从而分割出所需要的部分。

3 分割算法比较与分析

从算法中堆栈的操作次数和整个分割过程所需时间来分析［7］，交互标记控制法进入堆栈的是弯曲函数值，栈次数与所选择区域模型三角面片的边数相等，区域选择法进入队列的是面片ID。其进入队列的次数与所选择区域模型三角面片的面数相等，在STL模型中，三角面片的边数目大约是面的1.5倍，因此区域选择法在操作次数节省了大量的时间，排序运算上，原算法在每次进栈都需要进行大小排序，因此时间复杂度是平方阶。而本算法根据阈值判断三角面片的邻面片是否符合要求，不用排序直接插入队列，算法时间复杂度是一个常数阶，程序运行速度得到了明显的提高。2种算法的对比如表1所示。

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

从表1中可以得到如下结论：改进的算法——区域选择法的算法复杂度明显优于传统的交互标记法。

4 基于3DSMax平台对牙齿分割的完成

在3DSMax平台［14-15］上创建浮动窗口，其包含标记选取、阈值微调器以及牙齿分割按钮。标记按钮作用是区域选择种子面片，阈值微调器按钮的作用是交互输入阈值，牙齿分割按钮作用是通过点击该按钮在3DSMax中自动完成牙齿的分割。

在牙齿的矫治中，有时需要将多颗牙同时移动，前面所讲算法中牙每颗之间是分割开的，不能将多颗牙齿同时移动或转动。本算法先在不同的牙齿上同时标记，再进行分割，多颗牙齿合为一组被分割到指定的区域，因此区域选择法很好地解决了该问题，分割结果如图5所示。图5a）是将牙颌模型的两切牙同时选取且向舌向移动，图5b）是将牙颌模型一颗侧切牙选取且向唇向移动。在3DSMAX中以该算法为依据完成牙齿的分割及移动，由表1的比较可以得到分割速度和精度完全的达到了用户的要求。

图5 多颗或单颗牙齿的移动Fig.5 Movements of multiple teeth or single tooth

5 结 论

提出一种快速的区域选择分割算法，算法利用相邻两面之间的弯曲程度作为对应的高度场函数，由用户输入的标记出发，选取全部合格面片，完成STL模型的分割。实验结果表明，算法不影响交互的实时性。用户通过标记和阈值确定分割的区域，能够使同种标记被分割到同一区域，因此该算法满足实际应用的需要。利用该算法，在3DSMax中成功的实现了牙齿的分割。除了牙颌模型，本算法还适用于其他有类似特征的STL模型边界查找与分割。该算法的不足之处在于，用户难以一次给出合适的阈值分割出想要的结果，另外，许多复杂的模型中还是需要一些必要的用户交互才能得到需要的结果。

［1］ 王邦康.口腔正畸矫治方法的新进展——无托槽隐形矫治器的研究与展望［J］.北京口腔医学，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］.计算机辅助设计与图形学学报，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］ 陈有兰，李占利，师玉璞.一种三角网格模型的边界提取快速算法［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］.北华大学学报：自然科学版，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］ 刘 瑜.计算机辅助口腔正畸算法研究［D］.重庆：重庆大学，2012.

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

［6］ 李成军，张 弛，汪国平.交互标记控制的快速网格分割［J］.北京大学学报（自然科学版），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］ 宁小娟.牙齿数字模型的分割方法研究［D］.西安：西安科技大学，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］ 管慧娟.基于区域的图像分割方法［D］.大连：大连理工大学，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］.燕山大学学报，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］.无锡：江南大学，2007.

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

［13］ 全红艳，张田文.基于区域生长的网格模型分割技术［J］.计算机辅助设计与图形学学报，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］.河北工业科技，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编程模型中存储体冲突的研究［J］.河北工业科技，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.