点云分割是点云参数化、形状识别、编辑造型等领域的关键基础算法。提出一种基于最小生成树的点云模型分割算法,包括生成带状分割边界、区域增长、拆分带状分割边界以及生成最终区域4个步骤。算法采用Snake模型提取分割曲线并向两侧扩展形成带状分割边,利用最小生成树实现区域增长来提取区域内部点,最后拆分带状分割边界并与已有区域合并形成最终区域。实验结果表明,该算法能够有效避免过分割和欠分割,能够生成光顺分割边界,与Level Set分割算法相比具有较高的效率。

Point cloud segmentation is widely used in point cloud parameterization, shape recognition, and model editing. A point cloud segmentation algorithm based on a minimum spanning tree is proposed, which includes four steps: generating banded segmentation boundaries,region growing, splitting banded boundaries, and generating the final regions. The Snake model is used to extract the dividing lines, and the lines are expanded towards both sides to generate banded segmentation boundaries. Then the Minimum Spanning Tree is used to extract all interior points in each region using region growing. At the last step, the banded segmentation boundaries are split to several parts, and each part combined with its region to generate the final regions. Experiments show that the algorithm can avoid over segmentation or under segmentation and generate smooth segmentation boundaries. Compared with the Level Set segmentation algorithm, the algorithm can segment point cloud more efficiently.