一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法

1.一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法，该方法包含下列步骤：
(A).使用场景拾取正方体、长方体、柱体选取包含目标牙齿三角网格曲面在内的待分割牙颌区域，在该区域上草绘前景线标识牙齿区域，该前景线由选取的目标牙齿区域的一组三角面片组成；草绘背景线标识牙龈区域，该背景线由选取的目标牙齿周边区域的一组三角面片组成；
(B).利用步骤(A)中指定的前景线与背景线信息作为区域增长算法的种子区域，使用贪婪算法进行区域增长，初步计算牙颌三角网格曲面中属于牙齿的区域，从而确定目标牙齿的初始边界；(C).在步骤(B)中确定的初始边界上，根据指定采样的数目均匀采样获取节点并计算空间控制曲线，依据牙齿、牙龈分界特征，交互式调整空间控制曲线到目标位置，空间控制曲线为大于等于2次的样条曲线；
(D).将步骤(C)中调整后的空间控制曲线投影为嵌入在牙颌三角网格曲面上的分割线，该分割线与经过的三角面片共面，所述的投影综合使用两种方法实现：(1)基于拓扑追踪的投影方式，利用空间控制曲线在三角网格曲面上投影的连续性追踪在顶点邻域内的延伸方向进行投影；(2)基于最近点查找的投影方式，利用空间剖分结构快速查找节点在网格上的最近点；(E).利用三角网格曲面上的活动轮廓算法光顺优化分割线，采用显示欧拉方法优化下述能量：
Emesh-curve＝∫Eint ernalds+∫Econstra intds
其中∫Einternalds代表分割线的光滑程度，∫Econstraintds代表外部因素对分割线形状的影响；
(F).根据步骤(E)中的分割线，分割牙颌三角网格曲面上的三角面片，得到边界光滑的牙齿三角网格曲面。
2.根据权利要求1所述的一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法，其特征在于贪婪算法的距离公式基于视觉极小原理：
其中dΓ(p，q)距离度量，ds是路径的欧氏距离，ds*是路径高斯映射的长度，w与w*是权重，f(kD)是对曲面上负曲率的度量，用于实现极小原理，即人类视觉对于物体形状的识别以极小负曲率线作为部分之间的边界。
3.根据权利要求1所述的一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法，其特征在于步骤(C)中生成的空间控制曲线的节点在待分割牙颌区域的三角网格曲面上。
4.根据权利要求1所述的一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法，其特征在于分割线分割牙颌三角网格曲面上的三角面片时，可根据拓扑情况细分成两个或三个三角面片。
5.根据权利要求1所述的一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法，其特征在于分割的操作对象牙颌三角网格曲面是牙齿全颌或部分颌的三角网格曲面。

一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的\n方法\n技术领域\n[0001] 本发明涉及数字几何处理中的模型分割技术，提出了一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法。\n背景技术\n[0002] 近年来口腔CAD正畸系统发展迅速，各种综合运用扫描技术、数字几何处理等软硬件技术而组成的新型口腔计算机辅助治疗系统层出不穷。其中最为典型的两个系统是OrthoCAD与Invisalign隐形矫治系统。口腔计算机辅助治疗系统的典型模式是通过光学方法扫描石膏模型获取牙颌三维数据，再利用数字几何处理技术分离牙齿牙龈数据，修复牙齿，最终进行矫治方案设计。牙齿分割是口腔计算机辅助治疗系统的基础功能，后续功能如矫治方案设计均需要牙齿作为独立的模型进行刚体运动、干涉检测等操作。由于牙齿具有不同的形状并且不同个体之间也有很大的差异，所以快速、精确地分离出单颗牙齿比较困难。\n[0003] 2004年Kondo使用两幅距离图像识别相邻两牙齿的分裂边界，该方法将三维空间问题转化为图像问题，但是该方法最终是用平面去裁剪牙齿数据，无法精确定位牙齿牙龈边界，参见Toshiaki Kondo，S.H.Ong，Kelvin W.C.Foong.Tooth segmentation of dental study models using range images.IEEETransactions on Medical Imaging，2004，23(3)：350-362.郝国栋等人通过计算三角网格顶点的曲率，根据顶点曲率值筛选出特征区域，由用户交互连接特征区域，之后对特征区域进行形态学操作得到特征区域的骨架线，依据获得的骨架线可以把牙齿精确地分离出来。该方法分离牙齿模型的主要思路是寻找牙齿之间的边界线，主要方法是基于曲率的自动特征计算，但通常得到的特征线并不能完全符合牙齿边界，因此需要提供更加精确的边界确定方法，参见郝国栋，程筱胜，戴宁，俞青.基于形态学的牙齿模型交互分割[J].中国制造业信息化，2008，(01)：36-39。设计牙齿分割系统时可以采用多种常用的三维模型分割算法，Chen等人论证了没有任何一种分割算法能够适合所有种类的模型，参见Xiaobai Chen，Aleksey Golovinskiy and Thomas Funkhouser.A benchmark for 3D mesh segmentation.ACM Transactions on Graphics，\n2009，28(3).\n[0004] 总体而言，现有的从牙颌三角网格曲面分割牙齿三角网格曲面的方法通常有两种思路：(1)确定区域从而确定边界；(2)确定边界直接根据边界分割。前者无法获得光滑精确的分割边界，后者所需要的用户交互过于烦杂、效率低下。\n发明内容\n[0005] 本发明提供了一种适用于从牙颌三角网格曲面分割牙齿三角网格曲面的方法。该方法使用数字几何处理中的多种技术并提出新的分割线定位算法-采用拓扑追踪进行空间控制曲线向三角网格曲面投影，实现快速自动分割与边界精确调整两种模式的结合，使得牙齿裁剪快速、精确、边界光滑。\n[0006] 本发明主要包括六个步骤，流程如下所示：\n[0007] A.选取包含目标牙齿三角网格曲面在内的待分割牙颌区域，在该区域上草绘前景线标识牙齿区域，草绘背景线标识牙龈区域。该步骤提供了新颖的交互方式用于确定目标牙齿区域。\n[0008] (1)使用场景拾取几何体作为空间包围盒拾取待分割牙颌区域以提高操作速度，待分割牙颌区域包括目标牙齿三角网格曲面及其周边三角网格曲面。景拾取几何体主要包括但不限于：正方体、长方体、柱体。场景拾取几何体可以进行平移、旋转、缩放操作及其组合操作。\n[0009] (2)在上述待分割区域上草绘前景线与背景线。其中前景线为用户选取的目标牙齿三角网格曲面上的一组三角面片，标识目标牙齿区域；背景线为用户选取的目标牙齿周边三角网格曲面上的一组三角面片，标识目标牙齿周边的牙龈区域。\n[0010] B.计算待分割牙颌区域中属于目标牙齿的区域，确定目标牙齿的初始边界。\n[0011] 将步骤A中的前景线，背景线信息作为区域增长算法的种子区域，采用贪婪算法进行区域增长，使得目标牙齿区域近似分出，得到目标牙齿的初始边界，为后续操作提供基础。贪婪算法的距离公式基于视觉极小原理：\n[0012]\n[0013] 其中dΓ(p，q)距离度量，ds是路径的欧氏距离，ds*是路径高斯映射的长度，w与w*是权重。f(kD)是对曲面上负曲率的度量，根据视觉原理物体各部分之间的分界线一般在最小负曲率线上，f(kD)项的目的在于提高曲面上负曲率区域的距离影响，定义如下：\n[0014]\n[0015] 其中g(x)定义为增长率较大的函数如x2或者ex等。\n[0016] C.根据指定的数目均匀采样初始边界获取节点，并计算空间控制曲线，依据牙齿、牙龈分界特征，交互式调整空间控制曲线到目标位置。\n[0017] 由于牙颌模型特征复杂、细节丰富，根据步骤B中得到的目标牙齿初始边界通常无法直接作为分割边界，本发明采用计算机自动生成空间控制曲线，并进行交互式调整，以获取边界目标位置。\n[0018] 首先由用户指定采样数目，根据该数目，计算机自动均匀采样初始边界获取节点，并根据这些节点信息生成空间控制曲线。空间控制曲线可以是2次及2次以上的样条曲线，本发明采用3次B样条曲线作为空间控制曲线。分割线是嵌入在三角网格上的多边形，其形状的改变需要通过多边形顶点或边的位置调整来实现，该位置调整也需限制在三角网格曲面上。由于分割线多边形的顶点及边数目巨大，如果直接调整，交互式操作工作量非常大，效率非常低，也很难整体控制分割线多边形形状，所以本发明通过调整空间控制曲线的形状间接调整分割线。该方法相对于前者具有灵活精确的优点。空间控制曲线的形状调整通过节点的增加、删除以及节点在待分割牙颌区域的三角网格曲面上的位置变动来实现。通过交互式调整空间控制曲线到目标位置，精确指定边界目标位置，适应了牙齿边界复杂多变的实际情况。\n[0019] D.将调整后的空间控制曲线投影为嵌入在牙颌三角网格曲面上的分割线，该分割线与经过的三角面片共面。\n[0020] 分割牙颌三角网格曲面首先需要确定嵌入在该曲面上的分割线，而空间控制曲线接近分割线形状但不重合，因此需将空间控制曲线投影在牙颌三角网格曲面上。本发明将空间控制曲线投影转化为嵌入在牙颌三角网格曲面上的分割线的方法采用两个算法：(1)基于拓扑追踪的空间控制曲线投影；(2)基于最近点的空间控制曲线投影。\n[0021] (1)基于拓扑追踪的空间控制曲线投影\n[0022] 如附图1所示，设空间控制曲线参数表示为α(t)，p(t)是空间控制曲线上的一点，q(t)是该点在牙颌三角网格曲面上对应的投影点，空间控制曲线上每一点在牙颌三角网格曲面上的投影线向量为  以空间控制曲线作为准线构造直纹面  则\n空间控制曲线投影问题可转换为直纹面X(t，s)与牙颌三角网格曲面求交问题。\n[0023] 本发明将空间控制曲线离散为多边形，直纹面求交问题可转化为利用局部拓扑关系追踪投影点问题。具体实现中空间控制曲线由多边形逼近，设空间控制曲线L由顶点{Q1，Q2，…，Qn}组成，节点包含在该点集中。设F为当前三角面片，设Proj(Plane，Q)为点到平面的投影操作，该操作等价于求点到平面的最近点。\n[0024] 拓扑追踪算法的核心思想是仅仅考虑控制曲线L的顶点在F上的投影，如果追踪到投影点不在面F内搜索当前面F的邻域三角面片，计算投影点所在面片并将其设置为当前面，对L的每个顶点进行上述操作，可以高效实现空间控制曲线投影操作。该算法的最大优点是最小化搜索范围，充分利用了三角网格曲面上的局部拓扑信息，最大限度地提高了路径查找效率。\n[0025] 对空间控制曲线L的每个顶点执行算法步骤如下：\n[0026] Step1：计算Proj(F，Q)，判断投影是否在当前面内；\n[0027] Step2：如果投影点没有离开当前面，判断L的下一个顶点；\n[0028] Step3：如果投影超出当前面，搜索F邻域三角面片，如果没有找到算法退出；\n[0029] Step4：如果搜索到投影点在邻域内的某个面片内，设置为当前三角面片。\n[0030] 拓扑追踪通常在曲率较大的区域出现不精确的问题，本发明采用基于最近点的控制曲线投影解决这一问题。基本思路是对投影点进行采样，即采样空间控制曲线上的点，求取三角网格曲面上的最近点，采样投影点应足够密集使得两个相邻投影采样点最多与网格上的一条边相交。但是因为三角网格曲面通常是扫描后进行重建，甚至可以进行后续优化操作改变网格质量，采样密度无法很好地控制，本系统中最近点投影采样仅仅作为自动加密控制节点的手段。用户发出自动加密控制节点指令后，系统加密控制曲线上采样点使之增加一倍，计算采样点到三角网格的最近点，以这些最近点作为控制顶点重新计算控制曲线以增加拓扑追踪投影的稳定性。\n[0031] (2)基于最近点的空间控制曲线投影\n[0032] 本系统中求解空间控制曲线上点到三角网格曲面上的投影采用均匀空间剖分结构加速查找最近点的方法。\n[0033] 设q是曲面S(u，v)中的点，空间点p到q的欧式距离为d＝‖p-q‖，则p到曲面S(u，v)的最短距离定义为D＝min{d(p，q)|q∈S}。\n[0034] D2＝(p-Sq)(p-Sq)取到极值的必要条件是，\n[0035]\n[0036] Nq是曲面上q处单位法线，如果曲面光滑，则(p-q)×Nq＝0，即最近点到空间点的向量与最近点处法向平行。将曲面离散为三角网格，本系统利用均匀空间剖分结构加速最近点查找。\n[0037] 算法步骤如下：\n[0038] step1：对目标三角网格划分为均匀单元格，将三角网格顶点索引分别存储在单元格中；\n[0039] Step2：利用邻域拓扑关系搜索空间点p附近的三角面片，计算p到三角面片所在平面的投影点；\n[0040] Step3：如果投影点在三角面片内则标记为最近点候选点，并记录距离；\n[0041] Step4：取距离最小的投影点作为最近点。\n[0042] 上述算法充分利用了几何邻域信息、拓扑邻域信息，两种方法相结合可以快速确定嵌入在三角网格曲面上分割线的形状。\n[0043] 由于空间控制曲线接近牙齿牙龈分割边界，计算空间控制曲线上的顶点在三角网格曲面上的最近点等价于计算该顶点在三角网格曲面上的投影。由此方法获得的投影点作为拓扑追踪投影算法中的分段节点，增加拓扑追踪投影的稳定性。\n[0044] E.光顺优化分割线\n[0045] 本发明利用拓扑追踪算法与最近点投影算法求解空间控制曲线生成的直纹面与牙颌三角网格曲面求交问题虽然实现了高效灵活的曲线控制但无法保证嵌入在网格上的分裂线保持光滑。我们采用牙颌三角网格曲面上的活动轮廓算法作为后续优化方法保证分割边界保持光滑。这一过程通过分割线顶点在三角网格边上的运动实现。\n[0046] 活动轮廓算法的原理是利用能量函数优化曲线形状，使之更加光滑或者更加贴近控制用户指定的形状。它的优点是直接通过嵌入在网格上的曲线进行运动达到理想形状，操作较为直观，可以根据三角网格曲面上的标量场进行控制。本系统将该算法作为后续优化操作，增加曲线形状的光滑程度。\n[0047] 嵌入在三角网格曲面上的分裂线能量公式如下：\n[0048] Emesh-cnrve＝∫Einternalds+Econstraintds\n[0049] 其中Eint ernal决定了曲线的光滑程度，Econstra int是作用在三角网格上的外部约束。\n根据变分原理，本系统利用显式欧拉迭代求解该方程，对于嵌入在网格上分裂线的每一个顶点使其沿边移动减少能量值，重复这一过程最终使分裂线保持光滑。\n[0050] F.分割牙颌三角网格曲面上的三角面片，得到边界光滑的牙齿三角网格曲面[0051] 使用步骤E中的分割线分裂牙颌三角网格曲面，获取目标牙齿三角网格曲面。分割线是顶点嵌入在牙颌三角网格曲面中三角面片边上的空间多边形，分裂后分割线成为目标牙齿三角网格曲面的边界。嵌入在牙颌三角网格曲面上的分割线与经过的三角面片共面，可以与经过的三角面片有一个或两个交点，分裂后对应细分为两个或三个三角形。分裂后牙齿三角网格曲面从牙颌三角网格曲面中分出。\n附图说明\n[0052] 图1基于拓扑追踪的空间控制曲线投影示意图\n[0053] 图2从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的上牙颌三角网格曲面\n[0054] 图3从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的选取的待分割上牙颌区域\n[0055] 图4从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的草绘的前景线和背景线\n[0056] 图5从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙的初始边界[0057] 图6从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的调整到目标位置的空间控制曲线\n[0058] 图7从上牙颌三角网格曲面分割右切牙三角网格曲面案例中由空间控制曲线投影生成的分割线\n[0059] 图8从上牙颌三角网格曲面分割右切牙三角网格曲面案例中经过光顺优化后的分割线\n[0060] 图9从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙三角网格曲面的牙齿牙龈图\n[0061] 图10从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙三角网格曲面的牙齿个体图\n[0062] 本发明的实施是为了对本发明进一步说明，而非对本发明的发明范围的限制。\n具体实施方式\n[0063] 实施例1从上牙颌三角网格曲面分割右切牙三角网格曲面。\n[0064] 1.打开软件，导入上牙颌三角网格曲面数据，如说明书附图：图2从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的上牙颌三角网格曲面。\n[0065] 2.使用场景拾取立方体选取包含右切牙三角网格曲面在内的待分割上牙颌区域，如说明书附图：图3从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的选取的待分割上牙颌区域。\n[0066] 3.在待分割上牙颌区域草绘前景线和背景线，以标识牙齿区域和牙龈区域，如说明书附图：图4从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的草绘的前景线和背景线。\n[0067] 4.根据第三步中的前景线、背景线信息，通过基于视觉极小原理的距离公式的分割区域增长算法，计算上牙颌三角网格曲面中属于右切牙的区域，确定右切牙的初始边界，如说明书附图：图5从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙的初始边界。\n[0068] 5.指定采样数目为30，均匀采样第四步中的初始边界获取节点，并计算空间控制曲线，依据右切牙与牙龈的分界特征，交互式调整空间控制曲线到目标位置，如说明书附图：图6从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的调整到目标位置的空间控制曲线。\n[0069] 6.将第五步中的空间控制曲线投影为嵌入在上牙颌三角网格曲面上的分割线，如说明书附图：图7从上牙颌三角网格曲面分割右切牙三角网格曲面案例中由空间控制曲线投影生成的分割线。\n[0070] 7.光顺优化第六步中的分割线，如说明书附图：图8从上牙颌三角网格曲面分割右切牙三角网格曲面案例中经过光顺优化后的分割线。\n[0071] 8.沿第七步中光顺优化后的分割线，切分该分割线穿越的三角面片获得边界光滑的右切牙三角网格曲面，如说明书附图：图9从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙三角网格曲面的牙齿牙龈图；图10从上牙颌三角网格曲面分割右切牙三角网格曲面案例中的右切牙三角网格曲面的牙齿个体图。