引用本文

鲁斌, 范晓明. 基于改进自适应k均值聚类的三维点云骨架提取的研究. 自动化学报, 2022, 48(8): 1994−2006 doi: 10.16383/j.aas.c200284

Lu Bin, Fan Xiao-Ming. Research on 3D point cloud skeleton extraction based on improved adaptive k-means clustering. Acta Automatica Sinica, 2022, 48(8): 1994−2006 doi: 10.16383/j.aas.c200284

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200284

关键词

骨架提取，自适应聚类，L1-中值算法，八叉树采样，区域引导 

摘要

针对三维点云中心骨架提取问题, 提出一种基于改进的自适应k均值聚类预分割引导的点云骨架提取算法. 首先, 将输入点云体素化, 利用八叉树算法覆盖输入点云并下采样实现点云化简; 其次, 在采样点中自适应选取初始聚类中心对点云进行区域划分, 并颜色标记; 最后, 在区域分割的引导下应用L1-中值骨架提取算法实现点云骨架的提取. 该算法主要针对L1-中值算法可重复性差、易丢失细节等缺点进行了改进, 并且对输入点云的质量以及形状的几何或拓扑信息, 都没有严格的先验要求, 可以直接应用到未经任何预处理、含有噪声或离群点的初始扫描点云上. 展示了从多种不规则点云提取的骨架结果, 包括矮小植物、人体动作等. 与传统算法相比, 该算法具有高准确率、强鲁棒性、强学习扩展能力等优点.

文章导读

随着三维扫描技术和建模技术的不断发展, 点云模型已经被广泛地应用于实际的生产生活和科学研究[1], 相关的模型处理技术也在不断地深入. 骨架模型[2]作为三维模型的概括型表现形式, 直观地显示了模型的拓扑连接性和几何结构, 目前已有很多三维处理技术如三维重建[3]、模型分割[4−5]、点云配准[6−7]和模型形状检索[8-10]等以此为基础实现. 因此, 三维点云技术的飞速发展及模型种类的不断增多对骨架提取算法的准确性提出了更高的要求. L1-中值骨架提取算法[11]因其快速高效的特点, 被广泛地应用于点云模型骨架提取中. 该算法基于全局中值的思想, 提出应用局部中值对点云提取初始骨架, 通过不断扩大邻域半径达到针对不同区域实现不同程度收缩的目的; 同时, 根据点分布情况引入了引力约束和斥力约束来实现规整化, 可以快速计算出较好的一维骨架. 但该算法也存在随机采样造成的可重复性差, 密度不均匀情况下采样很容易丢失细节, 以及基于阈值的骨架伸长导致的错误骨架连接等问题.

本文针对以上缺点, 提出了一种基于改进的自适应k均值(k-means)聚类引导的L1-中值骨架提取算法, 主要的流程图如图1所示. 给定一个三维点云模型, 首先采用八叉树对散乱点云进行组织, 每个体素基于当前密度包含的点数不一; 在此结构下完成中值采样, 并利用采样点集自适应确定初始聚类中心实现k均值区域划分, 应用局部中值迭代收缩得到各区域内的骨架分支; 最后通过对L1局部分支拟合曲线完成骨架平滑及连接. 本算法将密度因素及野点的影响考虑到采样问题中, 保证模型的细节不会丢失, 同时减少了后续骨架提取的迭代次数; 区域划分约束下提取骨架, 解决了跨区域连接错误的问题. 实验结果表明, 本文算法与L1-中值骨架提取算法相比, 有效地提升了点云骨架的准确性与可重复性, 可以达到更好的提取效果.

图 1  本文算法流程图

图 2  2011 ~ 2019年点云骨架提取方向论文发表年度趋势图

图 3  八叉树分割示意图

本文针对传统骨架提取算法中提取结果可重复性差、易丢失细节及连接错误等问题, 提出了一种基于改进的自适应k均值区域划分的骨架提取算法, 对骨架提取和连接进行约束. 该算法利用八叉树中值采样, 起到抵御野点和平衡点云分布密度的作用; 基于采样点进行自适应k均值区域划分, 实现保留局部细节; 基于区域自适应半径进行L1-中值骨架收缩, 有效地减少了工作量. 实验结果表明, 该算法大大减少了迭代次数, 有效避免了细节的丢失及错误骨架的连接, 具有强鲁棒性、高准确率等优点.

需要注意的是, 本文算法尽管在k均值聚类时实现了自适应确定参数, 可客观地进行合理的区域划分, 但在L1-中值算法中的参数仍使用了实验观察法, 这些参数对骨架提取结果有着一定的影响; 同时提取的骨架结果保留细节的同时偶尔会有多余的小骨架产生, 且在局部点云内部缺失严重时易形成局部骨架闭环, 因此如何更加便捷准确地确定参数及完善骨架, 这将是下一步重点解决的问题.

作者简介

鲁斌

华北电力大学(保定)计算机系副教授. 分别于2001年和2003年获西北工业大学硕士学位和博士学位. 主要研究方向为计算智能, 计算机视觉和综合能源系统. E-mail: lubin@ncepu.edu.cn

范晓明

华北电力大学(保定)计算机系硕士研究生. 主要研究方向为计算智能, 计算机视觉和综合能源系统. 本文通信作者. E-mail: xmingF@163.com