基于启发式策略和区域生长的智能分割算法及应用研究

　　摘要：针对三维模型的智能分割算法问题，对传统的区域生长方法进行改进，优化种子点的扩展和生成策略，实现了种子点选取、种子点区域扩展和区域生长的一系列算法，避免了种子点选取不当造成错误分割的情况，通过实验证明设计的算法在分割效率和效果上得到一定程度的提升。

　　引言

　　近年来，随着三维扫描、计算机视觉等技术的快速发展，针对三维网格模型和三维点云模型的分割，在最新的研究文献[1]中可以看到，分割在生产生活的各个领域有着广泛的应用，通过将三维模型按照某种语义特性分割成不同的部分，有助于实现特征识别、产品生产、医疗诊断和辅助治疗等方面的应用。由于各类三维模型的复杂性，使得基于网格模型的几何处理等相关技术成为计算机辅助设计和图形学的重要研究热点。原始三维网格模型缺少足够的结构特征和语义信息，对原始三维网格模型的理解成为许多几何处理亟待解决的重要问题。网格分割按照一定的分割准则将原始模型分解为不同的部件或曲面片，有助于有效解决相关几何处理问题如曲面压缩、网格重构、参数化、纹理映射、模型检索。其中区域生长法因其算法原理简单且容易实现，成为分割领域中的经典分割算法，被广泛应用到各类三维模型的分割中，以质心作为种子点采用区域生长算法实现了肝脏的自动分割[2]，这些研究成果都说明区域生长算法能广泛应用到三维网格和三维点云的分割。区域生长算法中初始种子点的选取是相当重要的一环，一般可以通过交互式选取种子点或通过机器学习自动选取种子点，传统的区域生长算法对初始种子点的选取依赖性较高，选取错误会造成欠分割或者过分割的错误结果。本文给出了一种基于深度学习的方法实现种子点的自动选取[3]，相比手动选取种子点效率高得多，同时分割的正确率能达到88%，但是针对部分情况机器学习后期还需手动调整。本文的算法将结合启发式策略和种子区域扩展的方法对区域生长法进行改进，能有效避免上述情况，提高算法的鲁棒性并减少种子点的进栈次数，有效提高分割的效率和准确度。

　　1. 种子点的选取

　　基于种子点的分割类算法对于种子点的选取有自动选取和手动选取两种方式，大批量自动分割可以通过机器学习后完成种子点的自动选取，但是针对个别种子点位置不准确的情况还是要通过人工干预手动辅助纠正。我们采用手动选取，有一定经验者可以很容易选取种子点，还可以人工交互修正，提高分割的准确性，通用性和鲁棒性强，可适应不同类型的三维数字模型。

　　种子点交互选取算法步骤如下：

　　（1）通过菜单功能选择要选取的对象的标签，每种标签对应的种子点赋与不同的颜色；

　　（2）在OpenGL开发环境中通过对三维模型的观察，对每个待分割部分用鼠标在较凸的位置按下鼠标左键以确定种子点映射在屏幕上的两维坐标（以窗口视区左上角为坐标原点，单位为像素），设该坐标为screenPt(数据类型为CPoint类型的二维点坐标)；

　　（3）针对每个种子点对应的二维坐标，在OpenGL环境中实现屏幕坐标screenPt到三维世界空间坐标的转化，利用函数 gluUnProject可以直接得到屏幕坐标相应的三维空间坐标pt；

　　（4）再由视点pv与pt连接成一条从观察坐标原点出发经过pt的射线L，通过遍历模型中所有的面片，找出与射线L相交且离视点距离最近的面片，求出该面片与射线L的交点即是种子点的三维坐标点pseed。

　　通过该种子点交互选取算法可准确地确定种子点所在的面片位置，下一步就按照下面的分割算法从种子点所在面片出发进行区域扩展实现分割。

　　2. 基于启发式策略的三维模型分割算法

　　本分割方法是一种交互式地分割算法，针对待分割模型结构较复杂的情况能够通过种子点的合理选取达成高准确率的分割结果。该算法的实现流程是由曲率计算、种子点区域扩展和启发式区域生长三部分组成。

　　2.1 曲率计算

　　作为一种基于面片的分割算法，可以利用曲面的曲率作为判断是否边界的条件，曲面的曲率估计位于相邻的两个面片之间，曲率的大小表示相邻两面片的相对弯曲程度。我们设计了一个简化的曲率估计函数，设两个三角面片f1、f2的单位法向量分别为n1和n2，其共享边界为AC(如图1所示)，则标记两个面相对弯曲程度的函数定义为

　　（1）

　　易见，且当f1和f2具有凹的边界时为负，具有凸的边界时为正。只是对曲率的一个粗略的反映，其实在分割过程中我们只需要比较其相对大小，因此计算曲率的精确值是不必要的。面片的邻接关系可通过对面片的拓扑结构进行重建实现。

　　2.2 基于阀值设定的种子点区域扩展

　　本分割方法采用了自动阀值加手动阀值相结合的交互式设置方式，这样可以避免种子点陷入局部较低点而造成一个部分被一分为二的错误划分。

　　该区域扩展算法的实现步骤如下：

　　（1）对模型中的每个部分通过前面的种子点拾取算法得到的种子点分别分配一个唯一的聚类号；

　　（2）对每个种子点坐标进行计算，以与相邻部分上的种子点的平均距离乘以一个阀值作为种子点扩展半径，可以通过交互软件上工具栏的相应功能按钮进行手动微调，可以实时观察到每个部分种子点扩展半径的变化情况；

　　（3）利用设置好的种子点扩展半径通过欧氏距离的计算，把每个种子点所在扩展半径中的面片按照该种子点的聚类号进行标记。

　　作为一种区域分割算法，一般与种子点邻近的面片都是和种子点属于同一个分类的，因此通过该算法的处理，种子点周边邻近的一些面片通过区域扩展快速地实现了分类，避免了种子点选在凹处时造成欠分割的情况，同时也避免参与后面算法的排序和进栈操作，提高了分割效率。

　　2.3 基于曲率的启发式区域生长算法

　　结合前面给出的曲率计算公式和种子点的选取方法，就可以采用区域生长的方式进行每个聚类的扩展以完全模型的准确分割。笔者的算法是基于曲率的计算以局部最小曲率为选择策略进行分割区域生长的方法，确保提高分割结果的准确性，具体算法步骤如下所示：

　　（1）应用公式（1）把种子面片的法矢量值与相邻接面处的法矢量值进行曲率值的计算；

　　（2）按照曲率值从小到大进行排序，排序的目的是因为该区域生长算法是从曲率最小的点开始生长的，这个点就是初始种子点，初始种子点所在的区域即为最平滑的区域，从最平滑的区域开始生长可减少分割片段的总数，提高效率；

　　（3）对每个种子点的所在的面片搜索其邻域面片，对未分类的每一个面片比较其法线与当前种子点面片的法线之间的夹角，小于阀值的将当前面片标记该种子点的聚类号，遍历所有面片，直到所有的面片都被标记聚类号结束算法。

　　3. 实验结果与分析

　　仿真实验的实验数据采用的是以STL格式文件存储的三维模型数据，该模型数据中包含了每个三角形面片的法矢量和三个顶点坐标，针对该数据先做预处理，利用哈希表进行拓扑结构的重建，建立了顶点表、边表和面表三个数据结构，存储了顶点之间、边之间和面片之间的邻接关系，再采用笔者的算法进行种子拾取、阀值设定、区域扩展和模型分割。通过在多种不同的三维模型上用鼠标进行拾取的可视化实验结果来看（如图2中两个三维模型拾取若干个种子点的效果图所示），通过射线拾取法所选取的种子点能正确地相交于三维模型的种子面片上，为了达到优良的显示效果，把不同聚类号的种子点用不同的颜色进行渲染，同时把种子点进行了放大显示，方便进行交互操作。该算法将广泛应用到后序的工作中去，为交互式操作提供了便利。

　　针对面片结构复杂的牙颌模型，分割实验过程按照算法分为三步进行。第一步，通过对每颗牙齿的咀嚼面和牙龈各拾取一个种子点（如图3（a）所示），每个种子点指定一个聚类号，并用不同的颜色显示种子点；第二步，按照拾取的种子点的坐标自动计算阀值并辅助手动调整阀值，通过实验测试阀值取0.3比较合适，再通过区域扩展算法对种子点区域进行扩展，扩展效果如图3（c）所示，从图上可以看出来种子点邻近的扩展半径内的面片都被标记成和种子点相同的聚类号，并以与种子点相同的颜色进行标识；第三步，从种子点出发采用基于曲率的启发式区域生长算法进行分割区域生长，分割效果如3（d），从效果图来看分割效果非常好，牙龈和每颗牙齿都能正确地分割出来，没有出现欠分割和过分割的情况，如果未采用区域扩展算法，分割效果就如图3（b）所示的欠分割情况，左第一双尖牙和左第三磨牙分别有大概一半被分割到牙龈部分去了。本文的算法针对各种三维表面模型的分割都具良好效果，并应用于自主研发的分割软件中。

　　结语

　　本文提出了一种基于改进的区域生长策略的交互式分割算法，实现了三维模型的准确分割，提出的算法分为种子点拾取、曲率计算、种子点区域扩展和启发式区域生长四个步骤，能实现各种三维模型的准确分割。市面上一些牙齿正畸软件在进行牙齿分割时，需要在个别牙齿的咀嚼面增加种子点以避免出现错误分割，本文的算法针对这种种子点邻接区域处于局部凹处具有较强的鲁棒性，在不需要增加新的辅助种子点都能够准确分割，不会出现欠分割的情况。本文的算法还可推广到自动化分割中，通过深度学习自动生成种子点的位置就可以按照我们的方法实现自动分割，只要自动生成的种子点偏差不大，本文算法中区域扩展方法就能够保证分割的正确性，尽量减少人工的干预，提高分割的效率。

　　参考文献：

　　[1]刘玮,李岩,贾科,等.非结构环境下一种改进的区域生长点云分割方法[J].科学技术与工程,2021,21(27):11650-11655.

　　[2]孔德明,张娜,王书涛,等.基于多视角区域生长的复杂点云模型分割[J].计量学报,2021,42(6):704-709.

　　[3]李占利,孙志浩,李洪安,等.图卷积网络下牙齿种子点自动选取[J].中国图象图形学报,2020,25(7):1481-1489.

　　作者简介：王增波，硕士，讲师，研究方向：计算机图形学、数学建模、智能算法。

　　基金项目：湖南省教育厅项目——三维模型智能分割算法及应用研究（编号：20C0270）；教育部产学合作协同育人项目——Web开发类课程的综合教学改革（编号：202102150030）；湖南省“双一流”应用特色学科项目——衡阳师范学院数学学科（编号：湘教通[2018]469号）。