逐步求精的多视角点云配准方法

徐思雨 祝继华 田智强 李垚辰 庞善民

点云配准是计算机视觉[1−2]、移动机器人[3−4]、计算机图形学[5−6]和医学图像处理[7−8]等领域的一项关键技术,其实质是计算非基准帧点云与基准帧点云之间的变换关系.根据待配准点云的帧数,该问题可分为双视角点云配准和多视角点云配准两类子问题.通常情况下,多视角点云配准问题的复杂度要远高于双视角点云配准问题.

目前,已有多种解决双视角点云配准问题的算法,其中最流行的是迭代最近点算法[9],它通过交替地建立待配准点云之间的点对关系和更新刚体变换来实现配准.虽然迭代最近点算法具有高效率和高精度的特点,但它并未考虑待配准点云之间的非重叠区域.为此,国外学者提出了裁剪迭代最近点算法[10−11],该算法通过引入变量衡量待配准点云之间的重叠百分比,以便利用重叠区域点对计算点云之间的刚体变换.为了获得最优配准结果,粒子滤波[12−13]和遗传算法[14]均可被用于搜索全局最优解.目前,已有多种算法能有效地解决具有中等重叠百分比的双视角点云配准问题.

由于多视角点云配准问题需要求解大量的配准参数,其复杂程度要远高于双视角配准问题.为了解决多视角点云配准问题,有学者提出了顺序配准法[15].该方法不断地对两帧点云进行配准及合并,直到全部点云被合并成一个整体.顺序配准法虽然简单直观,但存在众所周知的误差累积问题.为了改善误差累积问题,有学者提出一种改进的多视角配准方法[16].针对非基准帧外的每帧点云,该方法通过建立该帧点云与其他各帧点云之间的点对关系,来计算该帧点云的配准参数.由于需要建立大量的点对关系,该方法的计算复杂度较高.

近年来,多视角点云配准问题逐渐受到学术界的关注,并出现了一些有效的解决方法.为了提高多视角配准精度,Mateo 等[17]将点云之间点的对应关系视为隐变量,以利用期望最大化法实现多视角点云配准.与此同时,Evangelidis 等[18]也提出了基于期望最大化算法的多视角点云配准方法.该方法将每个点视作是从高斯混合模型里抽取的一个样本,从而将多视角配准问题转换成聚类问题,并通过期望最大化方法计算高斯混合模型参数和配准参数,以获得多视角点云配准结果.此类方法虽然精度较高,但计算量惊人.为了提高配准效率,Tang 等[19]提出了层次多视角配准方法,该方法通过检测闭环,以便不断地对小闭环所涉及的点云进行多视角配准及合并,直到全部点云合并成一个模型.层次配准法可提高配准的精度和效率,但需要解决闭环检测这个难题.与此同时,Govindu等[20]将每个双视角配准结果视为多视角配准问题中的一组约束方程,并利用他们自己所提出的运动平均算法从多组约束方程中计算出多视角配准结果.为了获得精确的多视角配准结果,运动平均法要求所有的双视角配准结果都是准确可靠的.近年来,Arrigoni 等[21]提出了基于低秩稀疏矩阵分解的多视角配准方法.该方法可将计算得到的双视角配准结果组成一个近似矩阵,然后利用低秩稀疏矩阵分解法对近似矩阵进行补全以恢复出多视角配准结果.该方法允许存在不可靠的双视角配准结果,但要求近似矩阵的非零元素必须达到一定的比例.

由此可知,多视角点云配准仍然是一个有待解决的问题.为此,本文拟设计一种有效的多视角点云配准方法.给定多视角配准的初始值,该方法通过构建粗糙的物体模型,并借助所提出的双视角配准算法顺序地计算每帧点云的配准参数,修正物体模型,以便进一步计算后续点云的配准参数.通过交替地计算双视角配准结果和修正重建模型,该方法可实现多视角点云配准.

本文的后续安排如下:第1 节简要地介绍迭代最近点算法,第2 节给出本文所提出的多视角点云配准方法,并在第3 节利用公开数据集对所提出的方法进行实验测试和对比分析,最后在第4 节给出本文的结论.

1 迭代最近点算法

在所有的点云配准算法当中,迭代最近点算法是最基础的一种双视角配准方法.给定两帧待配准的点云,观察数据和模型数据Q=双视角点云配准可表示成如下的最小二乘问题

其中,(pi,qc(i))是模型数据和观测数据之间具有对应关系的点对,R与t分别表示刚体变换中的旋转矩阵和平移向量.给定初始配准参数(R0,t0),迭代最近点算法需要交替执行以下两步:

1)建立待配准点云之间的点对关系

2)根据当前建立的点对关系,更新刚体变换

当迭代次数k达到设定的阈值K或前后两次迭代所求得刚体变换无明显差异时,即可输出最优的配准参数.虽然迭代最近点算法具有效率高的优点,但它未考虑待配准点云之间的非重叠区域,如将它直接应用于具有非重叠区域点云的配准,则无法获得精确的结果.

2 多视角点云配准

为了叙述的完整性,本文先给出多视角点云配准问题的定义,然后提出逐步求精的策略,并给出逐步求精过程中所依赖的双视角配准方法.

2.1 问题定义

如图1 所示,给定从不同角度所采集到某物体上的N帧点云在初始配准参数已知的前提下,多视角点云配准目标是计算精确的配准参数以便将所有点云转换到基准帧点云的坐标系下,从而获得完整的三维物体模型.为了确保获得可靠的多视角配准结果,对于给定的任意一帧点云,必须存在其他点云,使得它们之间的重叠百分比接近或大于50%.与双视角配准问题相比,多视角配准问题需要求解更多的配准参数,因此难度更大.不失一般性,通常选择第1 帧点云作为基准帧,故第1 帧的配准参数不需要计算.

图1 从兔子模型上采集得到的多视角点云Fig.1 Multi-view point sets acquired from the Bunny model

2.2 逐步求精的多视角点云配准方法

假设物体的精确模型Q已知,则多视角点云配准问题可表示为如下的最小二乘问题

其中,点qc(ij)是点pij在Q中的对应点,wij是与点对(pij,qc(ij))相关的一个权重系数.为了求解式(4),可将各帧点云分别与物体模型进行配准,以便求出精确的配准参数.即给定物体精确模型的前提下,多视角点云配准问题可分解成多个双视角配准问题.

然而,在完成多视角配准之前,精确的物体模型是无法获得的,只能根据给定的初始配准参数构造粗糙的物体模型

以及不完整模型

此时,可以用不完整模型Qi替代物体的精确模型,并利用双视角配准算法计算第i帧点云Pi的配准参数所获得的双视角配准结果可立即用于修正粗糙模型P,以便进一步计算第i+1 帧点云的配准参数.顺序遍历完所有点云后,即可获得改进的物体模型P.在计算第i帧点云的配准参数时,由于只能采用粗糙模型Qi替代精确模型,因此双视角配准算法计算得到的配准参数精度有限,所构造的物体模型也不准确.为此,需要多次循环遍历各帧点云,以便获得精确的多视角配准结果.

在多视角点云配准问题中,需要考虑两个重要因素:1)每帧点云包含其他点云所未覆盖的物体区域,即第i帧点云Pi与不完整模型Qi之间存在非重叠的区域;2)基准帧的位置是固定的,即第1 帧点云中所有点的位置是精确的.非重叠区域的点对不可用于计算配准参数,否则会降低配准精度.如果对基准帧与其他帧点云一视同仁,则不利于获得精确的配准结果.基于这两个因素,本文设计如下的权重系数

其中,dij代表点对(pij,qc(ij))之间的欧氏距离,标准差是一个二值变量:当qc(ij)属于第1 帧点云时取1,否则取0.5.由于非重叠区域点对的距离比重叠区域点对的距离大,故引入指数函数可以削弱非重叠区域点对对配准结果的影响;而引入二值变量则有利于充分发挥第1 帧点云的特殊作用.

为了求解目标函数(4),本文提出如图2 所示的基于迭代思想的逐步求精方法,图中每个圆圈代表一帧点云,黑色圆圈代表基准帧点云,圆圈的颜色表示点云配准参数的精度,颜色越深则精度越高.该方法通过执行以下步骤实现多视角点云配准:

2)顺序遍历基准帧以外的每帧点云,针对第i帧点云:a)利用有效的双视角配准方法计算Pi与Qi之间的最新刚体变换关系根据当前计算获得的最新参数更新模型P.

3)重复执行步骤2),直到满足循环停止条件.

当循环次数k超过设定阈值K或前后两次循环所求的刚体变换变化小于设定的阈值时,即可停止循环,输出多视角点云配准结果.由此可见,逐步求精策略的关键在于设计有效的双视角点云配准算法.为此,本文提出了如下的权重迭代最近点算法.

2.3 权重迭代最近点算法

在逐步求精的第k次循环过程中,Pi与Qi之间的最新刚体变换关系需要通过求解以下最小二乘问题后得到

图2 逐步求精的多视角点云配准方法原理图Fig.2 The framework of stepwise refinement approach for the registration of multi-view point sets

1)建立点云Pi与模型Qi之间的点对关系

2)为所建立的最新点对计算相应的权重

3)根据最新点对及其权重,计算最优刚体变换

其中,式(9)是最近邻搜索问题,可采用基于k-d 树的搜索算法[22]解决;最近邻搜索算法一般提供点对的距离和对应点的序号,故可直接计算式(10);式(13)代表权重最小二乘问题,可采用文献[23]的方法进行求解.当迭代次数k到达设定的最大值K或前后两次迭代所求出的刚体变换无显著差异时,即可停止迭代,并利用更新模型P.

根据上述描述,结合图1 的循环过程,可以给出如算法1 所示的单帧点云更新算法.循环地遍历基准帧以外的各帧点云,并采用单帧点云更新算法处理所遍历到的每帧点云,即可达到最小化目标函数(4)的目的,从而获得最终的多视角点云配准结果.

算法1.单帧点云更新算法

输入.更新前模型P和点云序号i;

输出.更新后的模型P;

根据式(6)构造不完整模型Qi;

利用Qi构建k-d 树;

Do while

k=k+1;

根据式(9)建立点对关系(ij,ck(ij));

利用式(10)计算点对的权重wij,k;

从式(13)计算最新的刚体变换(Ri,k,ti,k);

Untilk≤K或(Ri,k,ti,k)无明显变化;

2.4 复杂度分析

由算法1 可知,在某次循环里处理第i帧点云需要执行多个操作.其中,构造不完整模型和更新模型只需执行1 次,即从完整模型中删除第i帧点云和将更新后的第i帧点云加入不完整模型,相应的计算复杂度为O(Mi).在进行迭代前,需要一次性建立M=(M −Mi)个点的k-d 树,以加速最近邻的搜索,复杂度为O(MlgM).其他操作的计算复杂度与权重迭代最近点算法的迭代次数相关.基于k-d 树结构,为Mi个点建立对应关系的复杂度为O(MilgM);为Mi对点对计算权重的复杂度为O(Mi);根据Mi对带权重的点对计算刚体变换的复杂度为O(Mi).假设权重迭代最近点算法的最大迭代次数为K,则针对循环过程中单帧点云的更新算法,可给出如表1 所示的复杂度分析结果.

表1 复杂度分析结果Table 1 Complexity analysis results

3 实验结果

为了验证本文所提出多视角点云配准方法的有效性,实验采用斯坦福大学图形学实验室公开的4个数据集[24]对其进行了测试和验证.表2 给出了实验所使用4 个数据集的基本信息,包括点云帧数和总点数.这些数据集除了包含多帧的待配准点云,还提供多视角配准结果的真实值为了加快程序执行速度,本文对原始点云进行了10 倍的降采样.多视角点云配准算法的程序均采用MATLAB 语言编写,并采用基于k-d 树的最近邻搜索方法建立点云之间的点对关系.所有程序均运行在一台内存为16 GB,主频为3.7 GHz 的双核台式电脑上.

表2 测试数据集的基本信息Table 2 The basic information of testing datasets

3.1 合理性验证

为了验证本文所提出多视角配准方法的合理性,本文利用Bunny 和Dragon 数据集对未考虑重叠区域且未考虑基准帧点云特殊性的逐步求精策略(SRICP)、只考虑重叠区域的逐步求精策略以及本文所提出的逐步求精策略(SRwICP)进行了实验测试.其中只考虑重叠区域的求精策略采用两种权值:指数权重函数(SReICP)和二值权重函数(SRbICP).前者采用本文所设计的指数权重函数,后者通过将点对距离按升序方式排序,给排在前80%的点对赋予权重1,给排在后20% 的点对赋予权重0,以便消除非重叠区域对配准结果的影响.实验中,本文将噪声加入到数据集所包含的配准真值中,并以此作为多视角点云配准策略的初始值.然后利用不同的策略进行多视角点云配准,得到相应的配准结果为了对比不同策略的配准结果精度,可以定义两类配准误差:旋转矩阵误差和平移向量误差et=表3 记录了各种多视角配准策略所对应的实验结果,包括配准初始值的误差、获得配准结果的误差和程序运行时间.

由表3 的实验结果可知,逐步求精的策略可以有效地降低旋转矩阵误差.受遮挡等因素的影响,不同视角所采集获得的点云均包含其他点云所未覆盖的区域,如不考虑非重叠区域,则会降低多视角点云配准结果的精度,甚至会出现平移向量在配准后变差的情景.另外,由于基准帧点云的配准参数是固定的,在配准过程中,如果能有效地利用这类可靠数据,则可以提高多视角配准的精度.二值权重函数只考虑固定的重叠百分比,对于高重叠百分比的点云对,它无法充分地利用全部有效信息,对于低重叠百分比的点云对,它会将非重叠区域的点云用于计算刚体变换,两种情景都将降低配准精度.由于非重叠区域的点无法从其他点云中找到真实对应的点,采用最近邻搜索法所建立的点对距离较大,故可通过引入指数型权重系数,削弱非重叠区域的点对对配准结果的影响;与此同时,通过增加基准帧点云的权重,可合理地利用基准帧点云的可靠信息.正是由于考虑了这两类因素,本文所提出的逐步求精策略可获得高精度的多视角配准结果.

3.2 实验对比

在实验中,将本文所提出方法与两类当前流行的多视角配准方法进行对比,它们分别是基于运动平均(Motion averaging,MA)[20]的方法和基于低秩稀疏矩阵分解(Low-rank and sparse matrix decomposition,LRS)[21]的方法.首先,本文利用前面所提到的4 个数据集对三种配准方法进行精度对比.配准前,可将噪声加入到数据集所包含的配准真值中,以此作为多视角点云配准方法的初始值.然后利用不同的配准方法进行多视角点云配准,并得到相应的配准结果表4 记录了各种方法所获得的配准结果,包括配准初始值的误差,所获得的配准结果的误差和程序运行时间.为了便于对比,图3 给出了不同配准方法所获得配准结果的横截面图.根据表4 和图3 的结果可知,本文所提出的多视角配准方法精度最高.且与其他同类算法相比,所提出方法的程序运行效率也具有一定的可比性.

表3 各种逐步求精策略的配准结果Table 3 Registration results of different stepwise refinements

表4 不同多视角点云配准方法的实验对比结果Table 4 Results of different multi-view registration approaches

图3 逐步求精的多视角点云配准方法原理图Fig.3 The framework of stepwise refinement approach for the registration of multi-view point sets

然后,本文利用斯坦福Bunny 数据集验证各种配准方法在不同噪声水平下的鲁棒性.实验中,本文将三组不同的均匀噪声:1)[−0.01,0.01]rad;2)[−0.02,0.02]rad;3)[−0.03,0.03]rad 随机地加入到斯坦福Bunny 的模型当中.为了消除随机性,每种多视角点云配准方法在不同的噪声水平下进行了20 次蒙特卡洛独立测试,并记录了各种方法的程序运行时间和配准误差.图4 给出了各种方法在不同噪声水平下的程序平均运行时间,误差平均值和标准差.由图4 可知,在低噪声水平下,基于运动平均的配准方法精度较高,随着噪声水平的升高,其配准精度迅速下降,因此该方法的鲁棒性较差.此外,即使在低噪声水平下,基于低秩稀疏矩阵分解的配准方法精度也不高,且随着噪声水平的升高,其配准精度立即下降,因此该方法也不够鲁棒.而本文所提出的方法无论是在低噪声还是在高噪声水平下,均可获得较高精度的配准结果,且配准精度稳定,因此具有较强的鲁棒性.

下面分析导致各种配准方法性能存在差异的原因.基于运动平均的方法利用双视角配准方法对具有一定重叠百分比的点云对进行配准,并根据双视角配准结果建立一系列的约束方程,然后利用运动平均算法从约束方程中求出多视角配准结果.如果运动平均算法的输入中存在一组或多组不可靠的双视角配准结果,则必将导致多视角配准失败.精度对比实验中Bunny 数据集的初始值较差,导致不易估计双视角点云之间的重叠百分比,以致于在运动平均算法中输入了一组不可靠的双视角配准结果,导致最终获得较差的多视角配准结果.此外,随着噪声水平的升高,该方法配准结果精度下降较快的事实也验证了上述分析.另外,基于低秩稀疏矩阵分解的方法利用可获得的双视角配准结果恢复全部双视角配准结果,以实现多视角点云配准.虽然该方法对少量的不可靠双视角配准结果具有一定的容错性,但配准精度不高,且配准效率较低,精确性和鲁棒性验证的实验结果均验证了上述分析.本文所提出方法顺序地将各帧点云与其他点云所组成的初始模型进行双视角配准,在保证待配准点云具有较高的重叠百分比的同时可逐步修正配准参数,并利用双视角配准结果修正初始模型,以进一步提高后续双视角配准结果的精度,从而获得准确可靠的多视角点云配准结果.由此可知,本文所提出的多视角配准方法具有优良的性能.

3.3 三维场景重建

本文采用公开数据集[18]对所提出的多视角点云配准方法进行测试,以验证该方法可应用于三维场景重建.该数据集包含10 帧由深度摄像头所采集获得的颜色–深度数据,不同视角下的数据采集场景如图5(a)所示.给定多视角配准初始值,可用本文所提出的方法对深度数据进行配准,以获得三维场景重建结果.由于原始数据包含噪声,配准后的颜色–深度数据需要进行噪声删除处理,以获得满意的三维场景重建结果.图5 给出了本文方法所重建的三维场景,由此可见,本文所提出的多视角点云配准方法可应用于三维场景重建.

4 结束语

本文提出了一种逐步求精的多视角点云配准方法.该方法根据初始参数构造粗糙模型并设计合理的目标函数,将多视角点云配准问题分解为多个双视角配准问题.随后循环遍历各帧点云,利用权重迭代最近点算法计算各帧点云的配准参数修正模型,并通过循环迭代的方式实现多视角配准参数的逐步求精.公开数据集上的实验结果表明,该方法能可靠地实现多视角点云的精确配准.后续的研究将关注配准初值的分析,并参考文献[1]设计全局收敛的求解方法,实现无序点云的自主配准.

图4 不同噪声水平下的各多视角点云配准方法对比结果Fig.4 Comparison results of competed approaches under different noise levels

图5 基于多视角点云配准方法的三维场景重建结果Fig.5 3D reconstructed result of scene based on the multi-view registration approach