本文针对以上缺点,提出了一种基于改进的自适应k均值(k-means)聚类引导的L1-中值骨架提取算法,主要的流程图如图1所示.给定一个三维点云模型,首先采用八叉树对散乱点云进行组织,每个体素基于当前密度包含的点数不一;在此结构下完成中值采样,并利用采样点集自适应确定初始聚类中心实现k均值区域划分,应用局部中值迭代收缩得到各区域内的骨架分支;最后通过对L1局部分支拟合曲线完成骨架平滑及连接.本算法将密度因素及野点的影响考虑到采样问题中,保证模型的细节不会丢失,同时减少了后续骨架提取的迭代次数;区域划分约束下提取骨架,解决了跨区域连接错误的问题.实验结果表明,本文算法与L1-中值骨架提取算法相比,有效地提升了点云骨架的准确性与可重复性,可以达到更好的提取效果.
最经典的骨架提取技术是Blum[12]在1967年提出的中轴变换,该方法能够快速地提取二维形状内部的一维骨架(中轴线),但对形状表面的噪声十分敏感.Dey等[13]首先定义了模型中轴面的子集为三维模型的一维曲线骨架.Cornea等[14]对现有的一维曲线骨架提取技术做了很好的综述,提出了理想骨架应该具有的属性.虽然骨架并没有一个完全统一、标准的定义,但大多数骨架提取的方法都运用了中轴的概念,满足中心性;同时,骨架又不同于中轴,中轴能够感知到模型的边界上比较微弱的扰乱,而曲线骨架必须要具备较少的对模型边界上的声音的感知能力,具有鲁棒性.
将输入点云体素化,利用八叉树算法覆盖输入点云.选择基于指针区域的八叉树进行实验,可以达到以下3个目的:1)把散乱点云数据有序组织好,起到索引的作用;2)实现有计划地数据简化;3)为特征点估计定义邻域点.
八叉树分割方法递归地将空间上的所有节点都分解成8个一样的子节点,即在这个空间上的所有体素的几何信息是一致的[28].图3为八叉树分割的示意图,从递归结构上可以看出,该方法使用树遍历算法来查找节点,并且可以在节点上递归生成新节点,具有良好的拓扑结构.
本文对于给定点云模型,首先计算输入点云数据的一个包围框如图4(a),对其进行八叉树分割,图4(b)、图4(c)给出了分割过程示意图;若子立方体内包含点云数据则保留,否则抛弃如图4(d),重复上述步骤直至满足判别条件,分割结果如图4(e)所示.基于后续点云下采样对八叉树的要求,采用固定的最小体素值作为判别条件,此时均匀排列的体素网格代表着输入点云的局部表面特征.
基于密度进行下采样把采样点收缩为骨架点,从而生成骨架.对于一些点云密度不均匀的数据,随机采样会使得密度较高的区域采样点多,而密度较低的区域采样点少,收缩得到的骨架容易丢失细节,甚至出现较多的小骨架.
针对这种现象,本文提出基于八叉树的中值下采样方法,即取每个体素中包含的所有点的中值点作为采样点.在此,中值点是基于体素中心进行求解的,计算公式:
具体实现如下:首先通过八叉树进行点云数据组织并得到体素中心集合(如图5(a)中心位置的点所示),然后计算每个体素内的点到中心点的距离以赋予权重,接着根据式(1)求得体素中值点,最后作为采样点输出(如图5(b)所示).
图6为植物模型点云中值下采样的过程及结果.图6(a)为源点云;图6(b)表示八叉树分割点云的可视化过程,可以看出,由于第2.1节中八叉树拆分的终止条件,最终得到的体素大小都是一样的,故可实现在点密集的区域和点稀疏的区域采样平衡,达到消除质量差异的目的;图6(c)中将基于体素中心的均值采样结果与本文采用的基于体素中值点的中值采样结果进行了对比,左图均值采样得到的采样点排列规整,在保持源点云结构和尺度的基础上进行了简化,右图中本文采样方法得到的采样点保留原有结构的同时对分支进行了细化,如枝干部位,这是因为取中值点作为采样点,很好地利用了中值滤波,起到弱化噪声点和离群点的作用.
因此,基于八叉树的中值下采样方法,不仅实现了基于密度的采样平衡,而且基于中值思想得到的采样点集收敛于真实骨架,大大减少了后续骨架提取的迭代次数.
本文提出一种基于八叉树采样的自适应k均值聚类算法对点云模型进行划分,主要考虑到以下三点:1)八叉树组织点云数据可以减少后续聚类的工作量;2)自适应聚类中心和类簇个数k可明显减少迭代次数,同时降低人为误差;3)提前划分区域可有效降低骨架错误连接的发生.
k均值聚类算法[29]的主要特征是随机确定k个初始聚类中心,基于距离比较对源点进行归类划分并计算得到新的聚类中心,进行下一轮迭代,中心位置不变时结束归类.归类的过程实际上也是最小化误差的过程,k均值最小化,是要最小化所有点与其关联的聚类中心点之间的距离之和,即评估指标(Sumofsquarederrors,SSE),计算公式为:
k均值算法中涉及到类簇个数k的指定,但在实际中k值的选择即给定点云划分的区域个数非常难以估计.为降低因人为误差造成划分结果的不准确性以及最小化误差平方和SSE,本文采用肘部法则对SSE曲线图进行分析,以自适应得到一个建议的k值.
肘部法则使用SSE作为性能度量,SSE值越小则说明各个类簇越收敛.但并不是SSE越小越好,考虑极端情况下将采样点集内的每个点都视为一个类簇,那么SSE的值降为0,显然达不到分类的效果.肘部法则为本文提供的是在类簇数量与SSE之间寻求一个平衡点的方法.
由图7可以看出,当设定的类簇数不断接近最佳类簇数时,SSE呈现快速下降态势,而当设定类簇数超过最佳类簇数时,SSE仍会继续下降,但下降态势趋于缓慢,因此拐点处的k值已经达到了合适的分类效果,即类簇数量与SSE之间的一个平衡点.
对于拐点的确定,为避免目测法带来的人为误差且结合折线图的走势,本文借鉴主成分分析中保留方差百分比的方法,即k值的选取类似于主成分个数的选取,可通过当前k值对误差平方和SSE的降低贡献率来判断,计算公式:
k均值算法随机确定初始聚类中心,很可能会收敛到局部最优.实验证明,初始聚类中心的好坏,对聚类的效果以及算法的迭代次数都有着很明显的影响.
最坏的情况如图8(b)所示,两个初始点选在了同一个类簇中,很有可能导致原本属于一个类簇的点被分成了两类.另外,初始中心最好选择数据中的点,若中心在点云数据之外,其移动到最终位置势必会增加迭代次数.
图9给出了飞机模型点云自适应得到的k个初始聚类中心.如图中圆点标注的位置,初始聚类中心正好分散在最终得到的类簇中,避免了因初始中心聚集而导致的迭代次数的大幅增加.箭头上的数字表示自适应得到k个中心的先后顺序,验证了k-means++算法中相互距离尽可能的远的取点原则.
该方法可以实现初始聚类中心的分散选取,从而减少聚类迭代次数,大大改善了k均值算法的有效性.算法流程如图10所示.
基于八叉树采样的自适应k均值聚类算法流程如图10所示,具体步骤如下:
步骤3.基于初始聚类中心进行k均值聚类,计算源点云所有点到每个聚类中心的距离,选择最近的中心进行归类.
步骤6.进行类簇染色,使用不同颜色对类簇加以区分.
步骤7.停止算法,输出点云.
通过八叉树分割得到一系列采样点后利用L1-中值骨架算法进行区域内骨架收缩提取.骨架收缩提取的基本思想是通过选取采样点邻域内的中值而不是平均值进行收缩,产生新的骨架点,不停地迭代并重新将其分配至所在区域的源点的中心.直接应用L1-中值算法往往会产生稀疏分布,造成结果中的一些中心点过度收缩产生一团点簇.为此使用了一个调整函数在局部空间中轴形成一种排斥力,完成规整排布.
实际情况中,对于形状不规则的模型,区域点集粗细不一,给定一个邻域半径难免出现过收缩和欠收缩的情况.为减少迭代次数,本文提出一种基于区域划分的自适应半径骨架提取的算法,针对不同区域设定不同的初始邻域半径,避免由于初始半径设定的太小导致迭代次数增加;以相同的增长率扩大半径,寻找新的分支并进行骨架连接,对于已经收缩到位的分支进行固定.
使用上述公式计算收缩得到的粗骨架,在连续性和平滑性这两点上还存在不足,甚至会影响到骨架的准确性,所以本文在原有最优化公式上添加了一个正则项,用于局部分支的曲线拟合,以形成密切联系的骨架.定义以下平滑函数:
基于区域划分的骨架连接,由于本身是一个整体,每个区域一般都会存在跨区域连接.基于骨架分支拟合曲线,分支两个端点沿伸长方向加值延长至当前邻域半径的2倍,若与其他区域骨架点相交,则以相交点为端点固定该伸长分支,并进行标记,否则偏转角度进行连接;若与本区域内骨架点相交,则遍历该区域所有骨架是否已存在跨区域连接,若不存在,待本区域分支均连接完毕后,再伸长一个半径长度的活动段进行寻找,找到则连接,否则结束骨架连接,示意图见图14.最后采用四边形细分的方法[32]对骨架平滑化和椭圆拟合方法[33]进行骨架中心化.
为验证算法的提取效果,本文选用点云由FastScan三维扫描仪采集,是没有经过任何预处理、包含噪声或离群点的非均匀密度的点云数据.该数据集[11]包括植物、动物、静物和人体动作等15类三维模型,部分采用本文算法的骨架提取结果数据如表2所示.
图15是在情侣雕塑的点云模型上做骨架提取的结果,该模型由自适应k均值聚类算法大体对称地分为了7个区域,涉及多处跨区域环状连接.实验结果表明,本文算法可以很好地处理对称环状连接问题,得到平滑骨架.同时,点云模型中含有部分噪声和离群点,并且扫描出的点云密度并不均匀,在这种情况下,能够提取出较为理想的骨架,显示了算法的强鲁棒性.
图16是在瑜伽动作的点云模型上做骨架提取的结果,该模型属于四肢型动作模型的一种,身躯和四肢在区域大小、点数和形状上存在差异,且骨架提取在扁平区域很容易出现过度收缩的现象.实验表明,在采样点和区域分割约束下,提取的骨架具有较高的准确度,保留了骨架的连续性.
图17(a)含羞草模型中存在叶子点云密度不均匀及数据缺失的现象.提取的骨架结果表明,本文算法对原始点云的质量并没有严格的先验要求,仍可以提取出较为准确的骨架线,具有强鲁棒性.
为进一步说明本文算法的优越性,将其与2种最先进的骨架提取算法L1-中值算法[11]和基于距离场引导的L1-中值算法[18]进行了比较.以下是分别在鹿模型、珊瑚模型和较复杂的树木模型上进行骨架提取的实验结果.
图18是鹿雕塑的点云模型做骨架提取的结果,该模型上半部分包含细小分叉,同时底部较分支部分尺度和点数都相差较大;在图18(b)展示的L1-中值骨架提取结果中,丢失了很多骨架分支,且存在多处骨架连接错误,造成这些现象的原因主要有2个:1)L1-中值算法采用随机下采样使得原本点稀疏的分支点数减少以致无法形成骨架;2)骨架分支距离过近导致错误连接;图18(d)方法[18]的结果除以上问题外,还出现了错误的骨架闭环,且该算法本身易受点云缺失的影响,导致模型底部的骨架连续性较差;然而这些在图18(c)本文算法得到的结果中有相当明显的改善,本文通过八叉树中值采样保证分支的密度平衡,以减少骨架的丢失,另外区域划分对骨架连接进行了约束,提高了骨架准确率.
图19是珊瑚雕塑的点云模型做骨架提取的结果,该模型形状可看似骨骼明显的树形结构,在图19(b)展示的L1-中值骨架提取结果中,多处出现骨架不连续,提取效果较差;图19(d)方法[18]相较于L1-中值算法,虽然在连续性上有所改善,但仍然丢失了大量的骨架分支;而图19(c)本文算法通过区域约束使得提取结果很好地保持了同一区域内骨架的连通,且尽可能多的保留细节,极少丢失骨架.
图20是树木点云模型做骨架提取的结果,树木模型相对复杂,含有较多错综连接的树杈及细小无形的枝叶,且较为集中.图20(b)展示的L1-中值骨架提取结果中,树木丢失了接近一半的骨架,且枝叶部分几乎无骨架分支形成;图20(d)方法[18]的结果中不仅丢失了较多关键骨架,而且提取出的骨架离散不连通,效果较差;图20(c)中本文算法通过区域划分首先将枝叶和树干分类隔开,分别提取骨架再进行连接,避免发生枝叶分离或提取不出骨架的情况,很好地保持了树干的拓扑结构,并且具有很好的连通性.
但同时该算法也存在着一些缺陷,均匀子空间采样在保留细节的同时偶尔会导致产生多余的小骨架,如图21(b)标注,因恐龙脚部点云呈平面分布且离散而收缩成了两个骨架分支;另外,局部点云内部缺失严重时,易形成局部骨架闭环,如图22(b).
本文针对传统骨架提取算法中提取结果可重复性差、易丢失细节及连接错误等问题,提出了一种基于改进的自适应k均值区域划分的骨架提取算法,对骨架提取和连接进行约束.该算法利用八叉树中值采样,起到抵御野点和平衡点云分布密度的作用;基于采样点进行自适应k均值区域划分,实现保留局部细节;基于区域自适应半径进行L1-中值骨架收缩,有效地减少了工作量.实验结果表明,该算法大大减少了迭代次数,有效避免了细节的丢失及错误骨架的连接,具有强鲁棒性、高准确率等优点.
需要注意的是,本文算法尽管在k均值聚类时实现了自适应确定参数,可客观地进行合理的区域划分,但在L1-中值算法中的参数仍使用了实验观察法,这些参数对骨架提取结果有着一定的影响;同时提取的骨架结果保留细节的同时偶尔会有多余的小骨架产生,且在局部点云内部缺失严重时易形成局部骨架闭环,因此如何更加便捷准确地确定参数及完善骨架,这将是下一步重点解决的问题.