一种基于调和场算法的三维牙齿网格数据的分割方法

摘要

本发明涉及一种基于调和场算法的三维牙齿网格数据的分割方法，导入一个三维牙齿网格数据，对三维牙齿网格数据中要分割的每颗牙齿依次拾取两点，确定要分割的每颗牙齿的前景约束点和后景约束点；判断三维牙齿网格数据中的顶点是否处于凹面，进而确定顶点的凹面信息；计算三维牙齿网格数据中顶点的高斯曲率值；计算基于调和场算法中的调和场标量值；计算出未知系数矩阵x；通过边界轮廓阈值划分处理得到要分割的每颗牙齿的分割边界轮廓并对所述分割边界轮廓进行光滑处理，最终完成了三维牙齿网格数据的分割。本发明很好的解决了因牙齿边界不明显造成分割错误的现象，此外能够对缺牙、拥挤度高等情况的牙齿有较好的分割效果，健壮性高。

说明书

技术领域

本发明涉及一种基于调和场算法的三维牙齿网格数据的分割方法，三维网格分割技术领域。

背景技术

随着经济生活的发展，人们对牙齿的美观有着极大的追求。然而，在我国大概有20％-30％的人有着牙齿不齐的状况，人们对牙齿的正畸需求会越来越高。传统的牙齿矫正方案如带钢牙套，不仅对患者的饮食带来不便，更会影响患者在治疗期间的美观。近年来，3D打印的隐形牙套应运而生，给患者来了很大的方面。在医学牙齿临床正畸过程中，精确的牙齿分割是极其至关重要的一步。然而，对于牙齿分割中的牙齿边界确定并不是一项简单的任务，因为在临床实验上不同患者的牙齿之间的形状、拥挤度、排列等有着很大的区别，这对于能够处理所有牙齿分割的方案带来很大的复杂度。

传统的牙齿分割算法是按照顶点的平均曲率信息，比如由Kan Wu,LiChen,JingLi,YanhengZhou发表的文章《Tooth segmentation on dental meshes usingmorphologic skeleton》中就是使用了这种算法，因为顶点的平均曲率信息反映出了牙齿边界的特征，然后经过对顶点的曲率进行阈值处理我们会得到特征点，对这些特征点运用形态学调整以及区域增长后将会得到牙齿、牙龈边界实现牙齿分割，这也是一种非常常用的网格分割算法。然而，对于一些扫描后的牙齿模型的边界处的曲率不明显，换句话说就是牙齿边界比较光滑，这种分割算法就会出现少分割或过分割等错误，牙齿的分割结果对牙齿的曲率信息依赖性大，程序不够健壮。

网格分割算法较多，但是在三维网格牙齿数据上进行牙齿分割的可使用的算法较少，并且有的分割算法中交互操作较多，对使用者来说成本较高。此外，有的不能够适应各种形状的牙齿分割，比如根据网格顶点的曲率信息进行分割，会产生少分割、多分割现象，分割算法不够健全。

为解决这种曲率不明显的情况，需要桥接工具，对于一颗牙齿上的噪声点所构成的闭环特征点，需要删除工具，比如专利201610065608.1提出了牙齿三维网格数据的分割方法及装置发明创造，通过这些交互才能够保证牙齿分割的正确性。此外，这种交互需要使用者有较高的牙齿医学解剖常识、计算机熟练操作等知识，学习成本比较高。

发明内容

本发明技术解决问题：克服现有技术的不足，提供一种基于调和场算法的三维牙齿网格数据的分割方法，基于调和场算法，交互比较少且交互简单，并且不依赖牙齿的复杂度，很好的解决了因牙齿边界不明显造成分割错误的现象，此外能够对缺牙、拥挤度高等情况的牙齿有较好的分割效果，健壮性高。

本发明技术解决方案：一种基于调和场算法的三维牙齿网格数据的分割方法，包括以下步骤：

第一步，导入一个三维牙齿网格数据，对所述三维牙齿网格数据中要分割的每颗牙齿依次拾取两点，确定要分割的每颗牙齿的前景约束点和后景约束点；判断三维牙齿网格数据中的顶点是否处于凹面，进而确定顶点的凹面信息；计算三维牙齿网格数据中顶点的高斯曲率值；

第二步，根据第一步中的前景约束点、后景约束点、顶点的凹面信息、顶点的高斯曲率值，计算基于调和场算法中的调和场标量值；由基于调和场算法中的调和场标量值构造三维牙齿网格数据的拉普拉斯矩阵L，惩罚因子矩阵P，系数矩阵b；

第三步，根据第二步中的拉普拉斯矩阵L，惩罚因子矩阵P和系数矩阵b计算出未知系数矩阵x；未知系数矩阵x表示三维牙齿网格数据中要分割的每颗牙齿的边界轮廓阈值，通过边界轮廓阈值划分处理得到要分割的每颗牙齿的分割边界轮廓并对所述分割边界轮廓进行光滑处理，最终完成了三维牙齿网格数据的分割。

所述步骤第一步中，三维牙齿网格数据中要分割的每颗牙齿前景约束点、后景约束点确定方法具体如下：

对要分割的每颗牙齿的牙尖即牙齿顶部区域沿着牙弓方向，依次拾取两点标记为A、B，根据A、B两点计算出要分割的每颗牙齿的半径，根据每颗牙齿的半径使用k邻近算法顶点搜索得到要分割的每颗牙齿的前景约束点和后景约束点。

所述第一步中，对三维牙齿网格数据顶点的凹面信息的确定方法如下：

使用顶点凹面计算公式确定顶点的凹面信息，其中凹面计算公式通过计算三维牙齿网格数据顶点的位置与k邻近算法搜索到的三维牙齿网格数据顶点的平均位置差异，反映的是三维牙齿网格数据中的顶点是否处于凹面，进而确定顶点的凹面信息。

所述第二步中，由基于调和场算法中的调和场标量值构造三维牙齿网格数据的拉普拉斯矩阵L，惩罚因子矩阵P和系数矩阵b，具体方法如下：使用三维牙齿网格数据中顶点的高斯曲率值作为拉普拉斯矩阵L的权重值，根据顶点的凹面信息修正拉普拉斯矩阵L的权重值同时修改惩罚因子矩阵P、系数矩阵b。

所述第三步中，通过阈值划分处理得到要分割的每颗牙齿的分割边界轮廓并对所述分割边界轮廓进行光滑处理，具体实现如下：

(1)根据求解后未知系数矩阵x，将未知系数矩阵x进行颜色映射显示，对颜色的结果值根据要分割的每颗牙齿的前景约束点和后景约束点位置的不同进行统计得到要分割的每颗牙齿的分割边界轮廓；

(2)将得到的每颗牙齿的分割边界轮廓通过三次B样条进行光滑，最终完成了三维牙齿网格数据的分割。

本发明与现有技术相比的优点在于：

(1)现有的网格分割算法较多，但是在三维网格牙齿数据上进行牙齿分割的可使用的算法较少，并且有的分割算法中交互操作较多，对使用者来说成本较高。此外，有的不能够适应各种形状的牙齿分割，比如根据网格顶点的曲率信息进行分割，会产生少分割、多分割现象，分割算法不够健全。对此，本发明了使用调和场分割算法，很大程度上解决了牙齿分割中的很多问题，能够处理复杂形状、拥挤度高的牙齿分割，交互性少，交互简单，实用性强，分割后的牙齿边界更符合牙齿医学解剖，能够适应不同复杂度的牙齿模型分割，为以后的牙齿畸形矫正的进行提供了保证，同时这种算法将会降低使用者的操作难度，将会具有重要的实际意义和应用价值。

(2)基于调和场分割算法的发明，交互性少，交互简单，减少了使用者的交互劳动强度。此外，无需使用者有太多的医学、计算机等知识技能。目前国内的一些牙齿分割软件基本基于网格顶点的曲率信息进行分割，一方面交互劳动强度高，另一方面分割的结果受石膏等扫描后的牙齿模型噪声点影响大。然而，基于调和场的分割算法更加健壮，能够处理缺牙、拥挤度高等较复杂的牙齿模型，基本不受牙齿模型噪声点的影响，使用者只需在要分割的每颗牙齿上按照前面的规则拾取两点即可。由此可见，本发明将具有重要的实际意义和应用价值，具有很高的市场应用潜力。

附图说明

图1为本发明方法的实现流程图；

图2为三维牙齿网格数据中要分割的每颗牙齿前景约束点FS、后景约束点BS示意图；

图3为三维牙齿网格数据顶点凹面信息确定图；

图4为三维牙齿网格数据的拉普拉斯矩阵L图；

图5为本发明分割效果图，其中(a)(c)(e)是三维牙齿网格数据原始模型数据，(b)(d)(f)经过本发明进行分割的效果图。

具体实施方式

下面结合附图及实施例对本发明进行详细说明。

如图1所示，本发明流程主要有三维牙齿网格数据中要分割的每颗牙齿前景约束点FS、后景约束点BS、三维牙齿网格数据顶点的凹面信息的确定；由基于调和场算法中的调和场标量值构造三维牙齿网格数据的拉普拉斯矩阵L，惩罚因子矩阵P，系数矩阵b，未知系数矩阵x；求解得到未知系数矩阵x,阈值划分处理得到要分割的每颗牙齿的分割边界轮廓，使用三次B样条进行边界轮廓的光滑。

1.三维牙齿网格数据中要分割的每颗牙齿前景约束点FS、后景约束点BS确定：

如图2所示，要分割的每颗牙齿前景约束点FS、后景约束点BS构造：

(11)使用者对要分割的牙齿分别依次拾取两点，程序会自动标记为A、B，该两点A、B的位置尽可能靠近相邻牙齿牙缝处。

(12)利用距离最短路径搜索算法获得A点到B点的路径标记为Path(A，B)，取Path(A，B)路径中的中心点所对应的网格顶点C作为球心，以A、B两点之间的欧几里得距离的一半为半径r构造一个球体方程。以C点作为起始点进行k邻近算法网格搜索得到集合S，k值取Path(A，B)中网格顶点个数。

(13)对集合S中的网格顶点进行遍历，将遍历过程中的顶点代入球体方程，判断是否位于球体内，若在球体内将该点标记为该牙齿的约束点，否则舍弃，对其他要分割的牙齿重复上述操作，直至所有要分割的牙齿的约束点确定完毕。在执行分割过程中会根据交互结果逐颗牙齿分割，会将当前牙齿的约束点作为前景约束点并标记为FS,其余牙齿的约束点作为后景约束点并标记为BS，分割下一颗牙齿与此类似，直至分割结束。

2.三维牙齿网格数据顶点的凹面信息的确定方法：

如图3所示，三维牙齿网格数据顶点的凹面信息的确定：基于调和场的分割算法中，分割结果对网格凹面比较敏感，所以本发明在进行拉普拉斯矩阵L的权重计算过程中要判定该点是否处于凹面，修改权重来达到很好的分割效果。网格顶点处于凹面判定计算公式：

(V_avg，i-V_i)·N_i>λ

其中V_i表示该点的位置，N_i表示V_i的法线，V_avgii表示顶点V_i的k邻近(k＝1)的平均位置，n表示k邻近顶点的个数，·表示两向量的点积，E表示网格中的边。在实验过程中，根据λ的经验值，λ取0.001值会得到正确的凹面判断结果。

3.如图4所示，构造三维牙齿网格数据的拉普拉斯矩阵L，惩罚因子矩阵P，系数矩阵b，未知系数矩阵x：

(31)本发明中牙齿的分割主要使用调和场的计算，并且牙齿要分割的边界更符合牙齿的医学解剖。此外，基于调和场算法中的调和场值是一个标量值，计算结果对网格顶点的凹面信息敏感，牙齿的边界一般处于凹面处，因此使用调和场将会很好的将牙齿的边界提取出来。

(32)调和场标量值的计算可以由泊松方程△x＝0求解，并且符合狄更斯边界条件，其中x是未知系数矩阵，△是Laplacian算子，由Laplacian算子所构成的矩阵将会是一个对称正定矩阵，对此矩阵进行Cholesky分解，构成的等式方程如下：

(L+P)x＝Pb,

其中L为拉普拉斯矩阵，P是惩罚因子矩阵，b为系数矩阵，x是未知系数矩阵。

其中i、j分别是三维牙齿网格数据顶点索引，L_ij表示三维牙齿网格数据对应顶点索引i、j的拉普拉斯矩阵L，FS、BS分别是前景约束点、后景约束点，α为惩罚因子系数，P_ij表示三维牙齿网格数据对应顶点索引i、j的惩罚因子，b_ij表示三维牙齿网格数据对应顶点索引i、j的系数矩阵b，E表示三维牙齿网格数据的边，w_ij为三维牙齿网格数据对应顶点索引i、j的拉普拉斯矩阵L中L_ij的权重，w_ij权重的计算方式与大多数的Laplacian余切权重计算公式不同，综合考虑了三维网格牙齿的医学解剖形状等得出以下结论：计算的权重会使调和场足够的光滑和对凹面形状的敏感。前者的约束会使分割后的牙齿边界更加光滑，后者的约束会使牙齿的分割边界沿着正确的方向分割。

(33)w_ij的具体计算方式如下：

其中，|e_ij|表示三维牙齿网格数据一条边e_ij的长度，G_i和G_j分别是三维牙齿网格数据顶点V_i和V_j的高斯曲率，γ是一个比较小的浮点数，取值γ＝10^-4，为了避免分数中的除零错误，对于一些凹面处的顶点权值给予较大的变化量如乘以β，使之明显区别于其他点，设置合理的β值，取值β＝10^-2，即可达到正确的分割效果。

4.线性方程组(L+P)x＝Pb求解，边界轮廓的光滑：

(41)根据(32)求解线性方程组(L+P)x＝Pb，将求解得到的未知系数矩阵x进行颜色直方图统计分析。

(42)根据颜色直方图统计和每颗要分割牙齿的前景约束点FS、后景约束点BS，通过阈值处理得到要分割牙齿的边界轮廓，对初步得到的粗糙的牙齿边界轮廓进行三次B样条光滑处理，达到临床医学正畸所需要的牙齿分割精度，最终完成了三维牙齿网格数据的分割。

(43)如图5中的(a)(c)(e)是要分割的三维牙齿模型数据原始数据，(b),(d),(f)是经过本发明计算后的分割效果。其中图5中的(a)比较常见的三维牙齿模型数据经过本发明算法能够很好的达到正确的分割效果，图中的红色点表示经过三次B样条光滑处理得到的控制点；其中图5中的(c)中三维牙齿模型数据密度较大，拥挤度较高，但经过本发明的分割依然能达到正确的分割效果，说明本发明对拥挤度较高的三维牙齿模型数据的分割的健壮性；图5中的(e)中的三维牙齿模型数据中丢失了一颗牙齿，经过基于调和场算法的分割依然能达到正确的分割效果，说明本发明对缺牙的三维牙齿模型数据的分割依然有着较强的健壮性；综上，经过以上多组三维牙齿模型数据的分割，本发明能够对缺牙、拥挤度高等情况的牙齿有较好的分割效果，健壮性高，能够适用较复杂的三维牙齿模型数据的分割。

提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修改，均应涵盖在本发明的范围之内。