1 引言

三维激光扫描技术^[1]又称实景复制技术,通过发射和接收激光束来获取被测物表面点的三维坐标和纹理信息。在虚拟可视化领域,三维激光扫描技术突破了传统式的测量限制,采用整体且连续的测量方式在短时间内可扫描得到完整的点云数据,进而重构三维模型。但现实情形中因测量方式受到角度和空间等自然测量条件的限制,往往需要多站点配合扫描才能得到完整准确的点云模型。正是如此,利用算法对扫描得到的三维点云数据进行整合和配准的研究工作变得非常有吸引力^[2-4]。

点云模型的配准通常分为粗配准^[5]和精配准两个步骤。粗配准称为全局配准,主要研究任意初始位置处一对三维点云模型间的全局最优配准。精配准称为局部配准,研究初始位置处较好的一对三维点云模型间细化的配准。粗配准可为精配准提供良好的初始位置,而精配准则进一步优化粗配准的配准结果,二者缺一不可。迭代最近点(ICP)算法是精配准的一种经典算法^[6],而ICP算法是一种基于自由形态曲面的配准算法,具有简单易行的优点,但ICP算法的效率较低,要求数据点云上的每一点在模型点云上都要找到对应点。为了寻找对应点,ICP算法需要遍历点云模型上每一点,配准速度很慢,且易于陷入局部最优。因此科研人员在此基础上对算法进行许多改进,如王育坚等^[7]使用KD树的数据结构搜索算法、王畅等^[8]利用相关结构特征加速点云配准算法,黄源等^[9]提出的基于特征提取的点云配准法和唐志荣等^[10]提出的基于典型相关分析法。以上算法均可完成点云配准,但都具有较明显的缺陷,即计算量大,且配准耗时长。在一些要求即时配准的情形下,就需要提高配准效率,加快算法的收敛速度,以适用于手持扫描设备的快速扫描和配准。

随着计算设备处理大数据能力的提升,深度学习在多个领域中有较大的进步和发展。卷积神经网络(CNN)在物体识别和图像分类等领域取得了重大突破,基于CNN的点云配准也是点云智能处理的研究方向之一。大多数情况下,CNN处理的都是具有直观解释的特征图^[11],所以为了使用CNN来处理点云数据模型,还需要对算法进行更深入的研究和改进。

点云模型的配准问题中,由于大量非结构化点云难以找到待配准点云模型之间点对点的对应关系,大多数算法的算力也是消耗于此^[12],这也是面对大型点云模型配准,配准效率低的主要原因。针对该问题,本文提出改进的Harris-SIFT(Harris-Scale Invariant Feature Transform)算法。首先利用该算法提取点云模型的关键点信息,可以降低后期精配准的计算复杂度。然后提取到具有刚性尺度不变性的关键点后,计算生成关键点间权重特征图并馈送给CNN,以匹配关键点间的对应关系。最终基于已匹配的关键点采用ICP算法完成精配准,可以得到所要求的配准精度。从实验配准结果来看,所提算法能够完成三维点云配准的任务,同时降低配准的计算量,提高配准效率。

2 基本原理

2.1 基于CNN结合改进Harris-SIFT的点云配准方法

三维点云的配准即存在两个三维点云数据S和T,其中S为源点云模型,T为源点云模型平移旋转后的目标点云模型,寻找适当的平移旋转参数,使得配准后的点云在同一空间坐标系中对齐。三维刚体的配准^[13]一般由平移向量t和旋转矩阵R来确定,分别由三个方向的平移参数t_x、t_y、t_z和三个旋转参数R_α、R_β、R_γ组成,通过这6个参数使得目标函数E(R, t)最小化以实现点云模型的配准,表达式为

E(R,t)=∑i=1N‖Si-(RTi+t)‖2,(1)

式中:N为模型的点位数量;S_i∈S;T_i∈T;‖·‖为取范数。实际的配准情形中,扫描得到的两个点云模型会出现部分点位缺失或被过滤的情况,所以两个模型的点位数量并不相同,只能期望寻找具有代表性的S_i和T_i之间的对应关系,并实现配准。

传统的点云配准算法中,算法的计算量主要集中于遍历点云对应的点集和寻找点位之间的对应关系,所以方法的配准速度慢,且效率低。因此,选取稳定的点云关键点,并快速准确地对点云关键点进行匹配,将成为提高点云数据的配准效率及配准精度的关键步骤。为了解决这些问题,实验提出基于CNN结合改进Harris-SIFT的点云配准方法,流程如图1所示。

图 1. 基于CNN结合改进Harris-SIFT的点云配准方法流程图

Fig. 1. Flow chart of point cloud registration method based on CNN combined with improved Harris-SIFT

下载图片 查看所有图片

该方法主要包括。

1) 改进Harris-SIFT算法:该算法用于检测点云数据中稳定的关键点。待配准的点云数据中,数量适中且相对稳定的关键点可降低对应点匹配的复杂度以及配准的计算量。

2) CNN关键点匹配模型:将关键点之间的关系矩阵作为CNN的输入特征图,以实现关键点的匹配,为后期精配准提供准确的关键点对应关系。由于关键点之间的内部关系对于刚性变换是不变的,因此利用CNN对关键点的正确匹配有助于整个点云数据的复杂映射。

3) ICP算法精配准:经过CNN匹配关键点的对应关系后,基于已经匹配的关键点采用ICP算法来精配准,达到所要求的配准精度的目的。

该配准方法在点云配准的问题中有两点优势:其一是提取点云数据关键点后由CNN匹配对应关系,避免传统点云配准算法中全局搜索点云数据以寻找对应关系,降低算法的复杂度;其二是得到关键点的对应关系后,仅需要对已匹配的关键点进行精配准计算,极大地减少配准步骤的计算量,从而提高点云模型的配准效率。

2.2 改进Harris-SIFT算法提取点云关键点

点云模型关键点是指点云模型数据集中具有较强的表面形状描述性能的点,且这些点间需要具有一定的刚性尺度不变性。关键点的检测与提取是降低点云配准的计算量,提高点云配准效率的第一步。常见的关键点提取算法有SIFT^[14]、Harris角点提取算法和基于曲率极限阈值的关键点提取算法等。其中SIFT算法是一种局部特征检测算法,通过在图像中搜索特征点来计算相关尺度和方向的描述符,进而提取图像特征并匹配图像特征点,这可以取得较好的检测效果。SIFT特征具有刚性尺度不变性,即使改变拍摄的旋转角度和图像的亮度或视角,仍能获得良好的检测效果。针对三维点云配准算法存在的问题:1) 使用卷积平滑运算和加权直方图统计,需要大量的浮点数运算,因此特征提取的复杂性使其难以应用于实时的三维重建系统;2) 由于提取的特征关键点过多,但只有一小部分特征关键点能够被正确匹配,对于其中无对应关系的关键点,在后期CNN对其匹配对应关系时需要花费大量时间,大大降低匹配效率;3) SIFT算法主要针对的是二维平面图像的检测,对于三维空间的点云数据需要对算法进行改进;4) 点云模型中的角点往往是模型的重要特征,而SIFT算法对角点不敏感,同时也因为在模型角点附近的点位聚集度高,真正有表面形状描述性能的点位信息难以准确提取。因此实验将SIFT算法与Harris角点检测算子结合,通过在Harris角点邻域范围内筛选SIFT特征关键点,进而提取点云数据关键点。改进Harris-SIFT算法提取点云关键点的流程如图2所示。

图 2. 改进Harris-SIFT算法提取点云关键点流程图

Fig. 2. Flow chart of improved Harris-SIFT algorithm to extract key points of point cloud

下载图片 查看所有图片

关键点的检测与提取步骤如下。

1)采用改进Harris算法来检测和提取三维点云数据的角点:在传统Harris角点提取算法的基础上改进Harris算子,将自相关矩阵C拓展到三维空间中,表达式为

C=G*Ix2IxyIxzIxyIy2IyzIxzIyzIz2,(2)

式中:I_x为点I在水平方向上的梯度;I_y为点I在竖直方向上的梯度;I_z为点I在垂直方向上的梯度;I_xy=I_x×I_y,I_yz=I_y×I_z和I_xz=I_x×I_z分别为点I对应方向上的元素积;*为卷积符号;G为高斯卷积核函数。在三维空间点位I(x,y,z)处的角点响应函数H为

H=det(C)-ζtrac2(C),(3)

式中:ξ为常系数,一般取0.04;det(·)为矩阵的行列式值;trac(·)为矩阵的迹。在以点I为中心的空间邻域内,判断H值是否为局部最大值或最小值,判断为真则记录该点的坐标,判断为假则继续下一处检测。

确定Harris角点后,以Harris角点为中心,取空间半径r为8 pixel,将空间范围内的点云数据转换为局部深度图像。通过计算点云的局部深度图像^[15],将三维数据投影到二维平面,这有利于SIFT算法检测具有尺度不变性的极值点,深度图像灰度值λ可表示为

λ=255-255×2×RF+R-D(F-R)×4,(4)

式中:F和R为合适值,对计算得到的深度图像进行对比分析;D为观测视角处距离点云点位的深度。

2)采用SIFT算法来检测在角点I(x,y)周围的局部深度图像,构建尺度空间来检测极值点,利用高斯卷积核来构建单一尺度空间函数,表达式为

L(x,y,σ)=I(x,y)*G(x,y,σ),(5)

式中:σ为尺度空间因子,值越大则对应的空间尺度越大,大尺度空间用来描述图像轮廓,小尺度空间用来描述图像的详细信息,σ取值为1.52,实验使用小尺度空间来描述局部深度图像的详细特征。为了有效地检测尺度空间中稳定的关键点,提出由不同σ的高斯卷积核与图像卷积得到DoG(Difference of Gaussian)差分尺度空间函数,表达式为

D(x,y,σ)=[G(x,y,kσ)-G(x,y,σ)]*I(x,y)=L(x,y,kσ)-L(x,y,σ),(6)

式中:k为整数。

3)极值点的精确定位:因为点云数据转化为深度图像,图像中的点位是离散值,所以对D(x,y,σ)在深度图像内进行二阶泰勒展开。利用二阶泰勒展开对D(x,y,σ)进行插值,最后采用最小二乘法拟合空间函数曲线和求导计算曲线的极值,该极值点即为点云模型中的关键点,关键点包含模型角点特征,具有尺度不变性。

改进的Harris-SIFT算法的计算过程简单,提取的关键点均匀合理,能够较好地反映点云数据的结构特征,即使存在旋转变换和视点变换,也能够提取到有较强的表面形状描述性能的点。通过该算法来剔除重复响应点和不稳定的边缘响应点,以此减少关键点配准的计算量,同时提高抗噪声能力。在关键点检测的实验中,采用斯坦福Bunny模型和Horse模型对改进算法进行评估,结果如图3所示。从图3可以看到,所提算法可以检测提取Bunny模型9个关键点,检测提取Horse模型6个关键点。

图 3. 改进的Harris-SIFT算法提取的不同模型的关键点。(a) Bunny模型;(b) Horse模型

Fig. 3. Extracted key points of different models by improved Harris-SIFT algorithm. (a) Bunny model; (b) Horse model

下载图片 查看所有图片

2.3 CNN架构

实验利用改进后的Harris-SIFT算法分别在目标点云和源点云中提取关键点,其中源点云关键点集合为{ pS1, pS2,…, pSm},目标点云关键点集合为{ pT1, pT2,…, pTn}。神经网络训练的过程中,随机选择源点云集合中的S_m个关键点,选择目标点云集合中的T_n个关键点,其中S_m和T_n不一定相等。将选择的T_n关键点对应分配给S_m中的某个子集,使关键点之间达到最优匹配,并将此设置为CNN的训练目标。

相较于一般情况下的图像配准,实验使用的配准方法并不是将数据集中点位坐标作为CNN模型的输入,而是将关键点的加权邻接矩阵M作为CNN的输入特征图,即将目标点云关键点T_n作为关键点特征图中的顶点,以关键点之间的欧几里德距离作为权重,将关键点映射到加权邻接矩阵M中(源点云关键点S_m同理),表达式为

M=(muv)Tn×Tn,(7)mTuv=(pTu-pTv)2,(8)

式中:u,v∈{1,2,…,n}。CNN模型的结构如图4所示,该模型由两层卷积(Conv)层和一层全连接(FC)层组成。以大小为5×5的加权邻接矩阵M为例,M作为CNN的输入特征图,对输入特征图的边缘使用零值进行填充,这可以对输入图像矩阵的边缘进行滤波。首先经过10个卷积核大小为3×3、步长为1的卷积层Conv1,得到10组3×3大小的图像矩阵。然后经过卷积核大小为2×2、步长为1的卷积层Conv2,对Conv1的特征图边缘使用零值填充后进行卷积运算,得到10组3×3大小的图像矩阵。经过Conv2后,输出图像矩阵使用激活函数ReLU来加快网络收敛。最终在FC层得到120维特征向量,经过Softmax函数的输出层后对关键点进行预测分类。源点云数据集中的一组点与目标点云数据集中的一组点被预测匹配为对应关系,对于所有可能的对应关系,通过奇异值分解(SVD)法估计最小二乘误差变换,将计算得到粗配准参数代入(1)式,从而得到最小误差的一个匹配组合,即得到关键点间的最优匹配关系组合。同时在这一步也可以通过SVD算法完成点云数据的粗配准。

图 4. CNN模型的结构

Fig. 4. Structure of CNN model

下载图片 查看所有图片

采用的PASCAL3D+数据集包含12类点云数据模型,每一类均超过3000个实例,实验选择其中2000个点云数据模型作为CNN训练数据。将原始点云模型作为源点云数据集,对源点云数据集进行数据过滤以剔除部分点位,将过滤后的点云模型随机平移旋转得到目标点云数据集。CNN的训练过程中,采用随机梯度下降(SGD)算法^[16]对权重和偏向进行更新,同时采用Dropout方法来防止过拟合。在CNN预测出最佳的匹配组合后,采用ICP算法来执行迭代精配准直至满足配准精度,此时ICP算法并不需要遍历所有的点云数据来寻找对应点,只需要针对CNN中预测匹配的两对关键点来计算t和R,减小ICP算法在精确配准步骤的计算量。

3 实验验证

3.1 配准误差的评价标准

采用相对旋转误差E_R和相对平移误差E_M来评价点云数据的配准精度,表达式为

ER=∑i=13θi,(9)θ=A(RG-1RC),(10)EM=‖tG-tC‖2,(11)

式中:R_G为真值旋转矩阵;R_C为计算旋转矩阵;t_G为真值平移矢量;t_C为计算平移矢量;A(·)为三个方向上的欧拉角。实验中将E_R和E_M值均小于1%的配准视为成功配准。

3.2 实验结果及分析

实验数据采用斯坦福大学3D扫描数据库中的Bunny、Horse以及Dragon点云模型,并将其作为点云配准的实验数据,将所提配准方法与ICP算法进行对比分析。实验在Intel Core i5-5575处理器,配有64 G内存和Nvidia 1080显卡的工作站上进行。神经网络采用开源深度学习框架Caffe。点云模型的数据集信息如表1所示。

假设目标点云集合中每个检测到的关键点可以在源点云集合中找到并与之匹配,此时存在 ASmTn种组合数,其中每一种可能的组合都是 ASmTn种配准选择之一。关键点数量的增长会导致存在对应关系的组合数增加快速,后期精确配准的计算复杂性会迅速增大。所以在实际配准情形中,相对适量的关键点(至少三个)有益于提高点云的配准速率。表2为Bunny模型中提取到的关键点,对其经过CNN进行预测匹配。从表2可以看到,Bunny点云模型中,源点云数据集和目标点云数据集中关键点的对应关系:5号点位对应1号点位,8号点位对应3号点位,3号点位对应2号点位。图5为Bunny点云模型的关键点对应矩阵。

图5Fig. 5表3为Horse模型中提取到的关键点,对其经过CNN进行预测匹配。从表3可以看到,Horse点云模型中,源点云数据集和目标点云数据集中关键点的对应关系:1号点位对应1号点位,4号点位对应5号点位,6号点位对应3号点位。图6为Horse点云模型的关键点对应矩阵。

图6Fig. 6基于已具有明确对应关系的关键点,采用ICP算法对关键点进行精确配准。图7~9分别为所提方法在Bunny、Horse和Dragon模型上的配准结果。 图7Fig. 7图8Fig. 8图9Fig. 9将提出的配准方法分别与传统的配准算法ICP、提取法向量(NV)特征点配准算法^[17]和提取内部形态描述子(ISS)配准算法进行比较,结果如表4所示。从表4可以看到,在数据量较少的Bunny和Horse模型中,ICP算法的配准效率高于其他配准算法,但配准精度最差。NV-ICP算法和ISS-ICP算法的本质上都是提取点云模型特征点的配准算法,但当面对点云数据量较多的Dragon模型时,配准精度还有待提高。所提的点云配准方法可以提前预测匹配点云模型的对应关键点,避免方法在点云精配准中需要进行全局搜索匹配点位的对应关系,极大地减少在精配准中ICP算法满足配准精度时所需的迭代次数,且缩短配准耗时,当面对复杂点云模型时,在保证配准精度的同时配准效率更高。

最后以西安市大兴善寺基师塔作为实验对象,使用三维激光扫描仪对基师塔进行多次扫描,共获得5个基师塔点云数据模型,随机选择其中两个点云模型进行配准实验。基师塔的点云数据模型信息如表5所示。从表5可以看到,源点云模型和目标点云模型均包含点云数据点位,扫描时受到实际地理位置的限制,点云模型都有部分点位缺失,同时扫描得到的点云数据模型均包含古塔周围的环境噪点。利用改进的Harris-SIFT关键点检测算法可以提取到基师塔源点云模型13个关键点,提取到目标点云模型15个关键点,由CNN对该点云数据关键点进行分类和匹配。最后对匹配的关键点使用ICP算法进行精配准,使其满足所需的配准精度,配准结果如图10所示。从图10可以看到,古塔点云模型具有数据量大和局部点位密集度高的特点,且模型数据有局部缺失并伴有数据噪点,使用该模型来验证所提配准方法有一定的实际配准参考意义。

图 10. 基师塔点云模型配准结果。(a)配准前,(b)粗配准后,(c)精配准后

Fig. 10. Registration results of Jishi tower point cloud model. (a) Before registration; (b) after coarse registration; (c) after accurate registration

下载图片 查看所有图片

图11为三种配准算法的配准效果。与其他三种配准算法的配准精度和效率进行对比,结果如表6所示。从图11和表6可以看到,ICP算法当面对复杂点云模型时,容易陷入局部最优,随着算法迭代的进行,E_R始终未能满足所需的精度要求。NV-ICP算法和ISS-ICP算法在数据缺失和噪声干扰的情况下,配准精度和配准效率明显下降。所提的配准方法耗时少且精度高,配准效率相较于另外三种配准算法可以提升超过55%。实验结果表明,基于CNN结合改进Harris-SIFT的点云配准方法能够准确完成古塔点云的配准任务,在实际的工程测绘中具有更高的配准精度和配准效率,以及较好的可靠性和鲁棒性。

图 11. 基师塔模型配准效果对比。(a) ICP算法,(b) NV-TICP算法,(c) ISS-ICP算法

Fig. 11. Comparison of registration effects of Jishi tower model. (a) ICP algorithm; (b) NV-TICP algorithm; (c) ISS-ICP algorithm

下载图片 查看所有图片

4 结论

在大型场景的三维建模领域中,针对点云数据的配准效率低且耗时长等问题,提出基于CNN结合改进Harris-SIFT的点云配准方法。该方法首先改进Harris-SIFT算法来检测提取关键点,再经过CNN对关键点构建匹配对应关系,最终基于匹配的关键点对目标点云模型采用ICP算法进行精配准,达到所要求的配准精度。实验结果表明,该方法在提高配准效率、减少配准计算量和缩短配准耗时上有一定的效果,基于该方法的点云实时配准将在大型建筑的逆向建模、古建筑的修复和勘测等领域得以应用。未来在关键点的有效提取策略以及CNN配准网络模型的改进上依然有进一步研究的空间。