HTML
-
本文中使用八叉树建立3-D立方栅格。将初始两组点云数据放至同一空间中, 对两组点云数据分别进行中心化处理,将质心移至坐标原点后对合成的点云数据建立3-D立方栅格。由于每个栅格大小一致,而包含在栅格中的点云数量不同,即可通过同一栅格中点云数量的大小来表示在该区域内点云的稀疏程度, 点云数量大表明该区域点云密集,数量小则表明该区域点云稀疏。
点云分布熵可用于描述点云在空间中的位置关系,通过密集程度反映点云的分布情况[19]。点云数据的采集往往是在不同视角的条件下进行的,点云数据之间并没有明显的对应关系[20],在经历配准操作后,点云数据会相对集中而非表现出配准前的不确定状态,这表现在两组点云数据相对距离最小,且空间中的位置关系唯一。点云信息熵可准确反映两组点云在配准过程中位置变换关系,故适用于点云配准过程中的优化对象。求解点云分布熵的具体步骤如图 1所示。
在点云空间中,按照栅格数量切分,将同一空间下的两个点云数据切分为2M×2M×2M个栅格,即每个栅格的大小为:
式中, Xmax, Ymax, Zmax为点云数据坐标轴方向的最大值,Xmin, Ymin, Zmin为最小值,x, y, z为每一个立体栅格沿坐标轴方向的长度。
将点云数据按照边界以及栅格数量进行栅格化后,统计落入每一个栅格中点云数量n(i, j, k),求得其分布概率p(i, j, k):
式中,N为两组点云的总点云数量。点云分布熵的表达形式为:
相比ICP算法通过求算均值平方差(mean square error, MSE)来评价点云配准的精度,点云分布熵的求算方式时间复杂度更小。MSE的求算方法需要为待配准点云中每一个点在目标点云中找寻与之距离最小的点,这需要多次全局遍历,而点云分布熵的评价方式只需进行一次遍历,运算速度有较大提高。
对完全重合的两组bunny点云数据P, Q进行点云分布熵计算操作。在-180°~180°范围内将Q绕x轴旋转, 每1°生成一个新的点云数据Qm,Qm与P共同组成新的点云数据Tm,计算Tm的点云分布熵ESDE和均值平方差EMSE。下标m表示旋转角α, β, γ的角度。以旋转角度α为横坐标,ESDE与EMSE为纵坐标建立与旋转角度的对应关系,如图 2所示。Q绕x轴与y轴旋转计算两个维度变换的点云分布熵。
Figure 2. SDE and MSE curve with rotation angle α a—correspondence between SDE and rotation angle b—correspondence between MSE and rotation angle
如图 3所示,SDE与MSE都能很好地反映两组点云的重合程度,当旋转角度为0°时,SDE与MSE均为最小值,适合作为点云配准的评价标准。
在运算速度方面,对不同大小的点云数据,点云分布熵的计算方式都明显优于均值平方差的计算方式,实验数据如表 1所示。
data (point number) time of MSE/s time of SDE/s bunny(35947) 52.4695 0.9349 horse(48485) 86.6042 1.2046 dragon(109411) 262.6325 2.6982 Table 1. Compare between SDE and MSE calculation time
-
为验证算法可行性及优化效果,作者在Intel Core-i7,8 GB内存的Windows 10操作系统上使用MATLAB R2018a软件对斯坦福大学点云数据库中的bunny, horse, dragon点云进行点云配准实验,以不同视角下的点云数据P, Q为操作对象,使用以点云分布熵为优化目标,基于BAS-PSO算法进行点云粗配准。基于经验对算法中的参量设置如表 2所示。
parameter number c1 1.4995 c2 1.4995 θ 0.95 population size 100 number of evolutions 100 step π Table 2. Algorithm parameter setting
为观测BAS-PSO算法中每一代更新后SDE的优化效果,提取出每一代配准后点云的SDE,以bunny模型为例,构建了SDE随进化次数变化的曲线图,如图 5所示。
从图 5中可以看出,随着粒子种群的进化,SDE不断减小并向优化方向进行,在第30次更新种群后,SDE趋于平稳,其值接近于两点云重合时计算获得的DE值,证明BAS-PSO算法是一种有效的优化算法。
针对部分缺失的点云数据以及含有噪声的点云数据,本文中的算法依旧有较好的鲁棒性,配准效果如图 6所示。
Figure 6. Abnormal point cloud data registration effect a—partial cloud missing before registration b—post-registration effect c—point cloud with noise before registration d—post-registration effect
使用BAS-PSO算法配准效果与主成分分析法(principal component analysis, PCA)、四点集法(4-point congruent sets, 4PCS)以及基于遗传算法的粗配准算法进行对比,配准后的模型如图 7所示。对比实验结果如表 3所示。
4PCS SGA PCA BAS-PSO bunny 62.39s 78.62s 1.02s 47.83s horse 89.74s 109.25s 1.33s 53.55s dragon 146.53s 167.82s 2.11s 95.64s Table 3. Registration time of different point cloud coarse registration method
由仿真结果可知,在粗配准效果上,BAS-PSO算法与4PCS算法以及基于遗传算法的粗配准方法均明显优于PCA算法,在配准速度上,虽然PCA算法速度快,但在考虑配准效果的前提下,BAS-PSO算法优于4PCS算法与基于遗传算法的粗配准方法,如图 8所示。针对不同大小的点云数据,BAS-PSO算法在配准速度上同样具有优势,且针对数据量大的点云数据,配准速度优势越大。