● 摘要
随着三维扫描技术的迅速发展、三维建模工具的广泛使用以及互联网的快速传播，获取三维几何数据已经变得非常容易。作为对模型描述、语义特征提取和外形信息理解的基础，模型分割是近几年来国际学术界的一个前沿研究领域。由于不需要对曲面进行重建，也不需要维护各点之间的拓扑关系，点云模型为三维模型提供了一种精简、紧凑的表示形式。本论文以点云模型为研究对象，对点云模型分割算法的相关技术和理论背景进行了深入的分析和研究。主要研究内容如下：1. 由于点云模型只保存了采样点的坐标信息，能否获得采样点的正确邻域点集在点云模型处理中显得十分的重要。本文提出一种基于每个采样点的局部可见信息的点云邻域图构建方法。根据每个采样点及其邻域点集在一个对偶空间的凸包，定义每个采样点的一环可视邻域点为其邻域点。证明了该方法的理论保证，并且给出了一个时间复杂度为O(nlogn)的构建算法。实验结果表明，可视邻域图能够逼近真实的采样曲面，具有参数无关、能够自适应点云采样率等优点。2. 如果将点云模型表示为图，则点云模型的分割问题可以转化为图切割问题。图的最优切割问题是一个NP完全问题。如果将顶点个数为n 的点云模型P分成m部分，谱聚类算法提供了一个在空间Rn×m中的松弛解。通过移除掉多余的特征向量，本文提出的算法在一个更低维的空间中找到分割问题的松弛解。基于视觉理论的最小值原则，构造了点云模型的相似矩阵。同时使用几何矩使分割结果对模型的平移、旋转和缩放变换无关。通过递归的对已经分割好的模型的子部分进行谱聚类分割，实现了层次分割。算法的理论保证得到了证明，实验结果验证了算法的正确性。3. 模型的一致分割在模型描述、模型识别、模型检索和模型匹配等领域中有着广泛应用。该问题的主要任务是在模型上提取有意义的分割部分，并保证分割结果与模型的姿态无关。基于点云模型的Laplace-Beltrami算子，使用往返时间距离来描述采样点间的相似性。然后根据点云模型的相似矩阵将模型嵌入到谱空间中，通过使用基于薄板样条的非刚性配准算法将不同姿态的模型进行对齐。最后根据不同模型上顶点间的对应关系对模型进行一致分割。在聚类时，使用的K-means聚类法能够随着k的变化产生不同细节的分割结果，反映了模型的层次结构。实验结果表明了算法的有效性。4. 三维模型的语义分割在得到模型有意义的分割部分的同时，还能够获得模型的语义信息。由于Reeb图是表示定义在模型上实函数商空间的数据结构，提出使用Reeb图来表示模型的分割结果。Reeb图的顶点表示属于相同分割部分的采样点，Reeb图的边表示分割部分的邻接关系。通过对Reeb图的顶点添加注释，定义了一个包含分割信息、拓扑信息和语义信息的语义模板。在谱空间中对一组包含相同语义部分的模型使用近邻点迭代算法（Iterative Closest Point，ICP）找到与输入模型匹配的模板模型，得到对应的语义模板。通过和匹配的模板模型进行一致分割，实现了语义信息的传递。实验结果表明，提出的算法能在点云模型上获得很好的语义分割结果。