基于布谷鸟优化的三维点云配准算法

马 卫

(南京大学计算机软件新技术国家重点实验室 江苏 南京 210093)(南京旅游职业学院酒店管理学院 江苏 南京 211100)

0 引 言

逆向工程是通过激光扫描等技术从样品原件获取三维数据并进行预处理，然后对预处理的点云数据通过曲面分块、数据拟合等操作实现三维重建。点云数据配准是逆向工程中的一个核心问题，是计算机视觉所有后续处理的基础，其配准结果在三维测量的精度和后续数据处理中起着至关重要的作用。

在三维重建过程中，获取三维物体表面的真实数据却因受测量设备、自遮挡与环境等因素的影响，实际测量过程中获取的点云数据只是实体表面的部分数据，且易导致平移或旋转错位[1]，故需对被测物体在不同视角下进行多次测量，并将各个视角下的点云数据合并到统一的坐标系下，形成最终完整的点云数据，方便后续可视化等操作。点云数据配准的实质是把在不同的坐标系中测量得到的数据点云进行坐标变换，以得到统一坐标系下的整体数据模型。这给点云配准带来了许多挑战[2]：(1)数据本身存在高噪声、离群点等会影响配准的精度；(2)在数据采集过程中，因三维扫描仪的自遮挡、视角和光线等问题，存在数据获取的缺失或部分重合等问题，导致后期配准对应关系难以寻找，搜索难度较大；(3)点云数据的初始位置对配准的性能影响较大。

最近邻迭代配准ICP(Iterate Closed Point)算法[3]则是当前点云数据配准过程中最具代表性、应用最广泛的刚性配准算法。该算法以四元数配准算法为基础，在两片点云中搜索相互对应的欧氏距离最短的最近点对，通过不断搜索迭代优化，最终得到两片点云刚体变换的最优参数。ICP算法由于简单而被广泛应用，但却易于陷入局部最优。同时，该算法特别依赖于点云配准的初始位置，当两片点云模型的初始位置变换较大，且当存在噪声点和离群点时则极易导致配准失败。为了解决这一系列问题，许多学者提出了改进策略[4-7]，如：基于概率论和统计的配准策略[8-12]，基于特征对应的配准方法[13-14]，基于尺度迭代最近点的配准方法SICP(Scaled Iterative Closest Point)[15]。ICP的改进策略从不同程度上提高了原始算法的抗噪能力和配准精度，但始终无法从本质上解决其对初始位置敏感的缺陷。

点云配准分为粗配准和精配准。粗配准是在满足降低配准搜索维度的前提下，实现两片点云的位置在同一坐标系下的粗对齐。为了克服ICP算法对初始位置敏感的缺陷，一些基于群智能优化策略[16-19]的粗配准方法相继提出，如：参数自适应进化算法[20]SaEvo(Self-Adaptive Evolution)、人工蜂群算法ABC(Artificial Bee Colony)、和声搜索算法HS(Harmony Search)、生物地理学优化算法BBO(Biogeography-Based Optimization)[21]等。这类方法为解决三维点云配准问题提供了新的思路和突破口，如基于粒子群算法PSO(Particle Swarm Optimization)[22]和基于遗传算法GA(Genetic Algorithm)[23-24]的粗配准技术可以为精配准提供良好的初始位置，但全局优化能力和配准的鲁棒性还不够。相比于传统的配准方法，这类优化方法有利于提高配准精度，但又存在搜索时间长、运算效率低等问题。虽然这些策略使用群体方式在求解空间内加强寻优搜索，但还是存在易陷入全局最优的不足。针对上述问题，本文提出一种布谷鸟全局优化的三维点云配准算法。

布谷鸟搜索算法(Cuckoo Search，CS)最早于2009年提出，是一种元启发式全局优化方法[25]，该方法模拟布谷鸟寻窝产卵的繁殖机理并基于莱维飞行(Lévy flights)而形成的一种搜索策略，从而表现出较好的全局优化性能，算法参数设置少，全局寻优速度快，与其他智能优化算法相比具有较好的搜索性能。目前，该算法广泛应用于神经网络、工程设计和全局最优化等领域[26-27]。

利用CS算法较强的莱维飞行全局搜索能力从而避免搜索过程陷入局部最优。CS算法不仅具有较好的全局勘探能力，还大幅提高了局部搜寻的开发性能，且适用于求解点云配准优化问题。本文以对应点距离最小为适应度函数，将布谷鸟优化算法作为寻优策略实现点云数据的粗配准，再利用ICP进行精细配准。计算机仿真实验结果表明，本文算法取得很好的搜索结果，寻优率和精度显著提高，效果令人满意。

1 算法设计

1.1 点云配准模型

点云数据配准的两个点集为待配准点云P和目标点云Q，其数学表示形式分别为：P={pi|pi∈R3,i=1,2,…,m}和Q={qi|qi∈R3,i=1,2,…,n}，其中m和n为两片点云中点的数量。寻找两个点集的空间变换，应用最小二乘法使目标函数值最小，目标是使两者离差平方和最小。

点云配准的本质是将多个视角下扫描获取的点云数据统一到同一个坐标系下，其过程是寻找两片点云数据集的一系列空间变换，可以用变换矩阵T来表示三维空间几何模型的变换关系。对于待配准点云P和目标点云Q，就是寻求三维空间内最优的变换矩阵T，其表示形式如式(1)所示。变换矩阵T有6个参数，包含了坐标轴方向的平移量Vx、Vy、Vz和坐标轴的旋转角α、β、γ。

T=RxRyRzV

(1)

(2)

(3)

(4)

(5)

待配准点云P和目标点云Q经过一系列空间变换，其对应位置点的理想欧氏距离为最小值0，然而受测量时的误差以及噪声干扰等其他因素影响，两片点云经过空间变换无法到达理想欧氏距离。所以，点云配准问题实质为求解全局最优化问题，寻求三维空间内两片点云最优的刚体变换矩阵。布谷鸟优化算法作为近年来新提出的一种群智能优化方法，在解决复杂的多维空间优化问题中，具有很好的全局搜索和局部寻优的性能。

1.2 点云简化与特征点提取

对于输入的两片点云，为了更有效地进行特征点的提取，按一定比率参数进行均匀采样，从而降低点云后续运算的数据处理量，提高运算效率。

特征点是描述曲面几何形状最基本的一种特征基元，在不同的坐标系下能保持较好的一致性。目前，特征点提取的方法各异，主要有基于曲面重建的点云特征点提取方法[28]，通过领域选择、张量投票和张量分析，降低了算法对噪声和采样质量的依赖性。另外还有局部表面面片法LSP(Local Surface Patches)[29]，关键点特性评估法KPQ(Quality of Keypoints)[30]，固有形状特性法ISS(Intrinsic Shape Signatures)[31]等，这类方法有不同的适应范围，LSP更适用于三角网格模型，而对于数据量较大的点云，KPQ方法有其一定局限性，本文采用ISS特征点提取算法相比于基于曲面重建的方法，其原理简单，便于实现，适用于分布均匀的点云数据的处理。

设点云数据有N个点，任意一点pti坐标为(xi,yi,zi),i=0,1,…,N-1，则ISS特征点提取算法的具体步骤为：

(1)对点云上的每个点pti定义一个局部坐标系，并设定每个点的搜索半径rISS；

(2)查询点云数据中每个点pti在半径rISS周围内的所有点，计算其权值：

(6)

(3)计算每个点pti的协方差矩阵：

(7)

(5)设置阈值ε1和ε2，满足式(8)的点即被标记为ISS特征点。

(8)

1.3 布谷鸟优化算法

基本布谷鸟搜索算法是模拟布谷鸟寻窝产卵的过程，将布谷鸟孵化寄生、寻窝搜索的生物特性形成理论和搜索策略，算法基于3条理想的规则[24]：

(1)每只布谷鸟随机选择寄生巢来孵化，每次只产生一个蛋；

(2)寄生巢被随机选择，最好的寄生巢将会被继承到下一代；

(3)设定固定值的寄生巢，寄生巢的主人宿主鸟发现一个外来寄生蛋的概率是Pa[0,1]。

基于上述规则，宿主鸟可以抛出鸟蛋，或者放弃鸟巢并重新构建一个新巢穴。其基本流程如算法1所示，其中：nFE为当前评价次数；MaxNFEs为最大评价次数。

算法1CS算法

Begin

初始化种群n个宿主巢位置Xi(i=1,2,…,n);

计算适应度值Fi=f(Xi),Xi=(xi1,xi2,…,xiD)T;

While(nFE

根据莱维飞行机制产生新的位置Xi;

计算新的位置Xi的适应度值Fi;

随机选择候选位置Xj;

If(Fi>Fj)

用新位置解替代候选位置;

End

按发现概率pa丢弃差的位置;

偏好随机游动产生新的位置进行替代;

最好位置保存;

End while

End

莱维飞行随机游动和偏好随机游动是布谷鸟优化算法中两个重要的搜索策略，负责局部搜索和全局搜索。CS算法在搜索过程主要包括三个步骤：(1)布谷鸟先在当前位置的基础上按莱维飞行随机游动方式产生新的位置，根据适应度函数的评价，通过贪婪方式选择较好的搜索位置。(2)为了增加搜索的多样性，按照一定的概率pa丢弃部分新产生的位置。(3)采用偏好随机游动方式重新生成与被放弃位置相同数量的新位置，根据适应度值评价，保存较好的搜索位置，完成一轮寻优过程。

(9)

莱维飞行搜索机制除了随机优化搜索外，另一特性表现为偏好随机游动搜索策略，随机游动的各个新位置通过式(10)的混合变异和交叉操作产生。

(10)

在布谷鸟搜索策略中，莱维飞行搜索机制通过随机游动和偏好随机游动搜索策略达到全局勘探和局部寻优的有效平衡。

1.4 CS算法在点云配准中的应用

点云配准的过程是将两个不在同一坐标系下的点云数据集经过一系列坐标变换后，实现两片点云对应部分的重叠，配准的效果取决于配准误差，通常由适应度函数来体现。迭代最近点搜索采用k-D树的方式提高最近点集的搜索速度，降低求解计算量，提高运算效率。

三维点云配准就是寻找待配准点云到目标点云间的变换矩阵T。在理想状态下，变换求解误差为0。然而由于获取的点云在三维激光扫描中受环境或机器的干扰，获取的点云数据过程会产生大量的干扰和噪音点，影响点云配准的精度，导致存在误差。受到测量误差、噪声点等影响，对应点之间的距离通过不断迭代计算始终无法达到理想位置，因此，点云配准问题实质为全局优化问题的求解：寻求最优的变换矩阵，使得扫描点集P={pi∈R3,i=1,2,…,m}与待配准点集Q={qj∈R3,j=1,2,…,n}间的欧氏距离最小，将CS算法应用到点云配准优化中，对点云配准目标函数中的变换矩阵进行优化，通过参数编码和归一化处理后对应宿主巢的位置，利用布谷鸟优化算法对点云模型进行目标函数的优化，其建立模式搜索趋化的布谷鸟全局优化函数为：

F(T)=min‖T(Pm)-Qn‖2

(11)

配准算法用配准后两片点云对应点之间的均方根(Root Mean Square, RMS)数值来表示两片点云的配准精度：

(12)

式中：数据集S表示点云P和Q的重叠部分。使用CS优化的点云配准算法定义目标函数来描述配准精度：RMS(P,Q)表示配准后的两片点云之间对应点之间配准误差，衡量点云配准的吻合度，值越小则配准的精度越高。

在布谷鸟优化算法粗配准的基础上，采用ICP方法进行精细配准，进一步利用k-D树快速搜索最近点对，提高点云配准的效率。

2 实 验

为了验证本文CS算法在点云配准优化应用上的有效性，选用不同点云库中的模型和扫描有噪声的模型进行配准实验。

2.1 点云库模型配准实验

在本节中，验证本文所引入CS算法实现由粗到精的三维点云配准算法的有效性和可行性。本文的实验数据集包括斯坦福大学经典的3个模型数据(Bunny，Happy Buddha和Dragon)和文献中的3个模型数据(Hippo，Coati和Angel)，如表1所示，选择2个不同视角下的点云，部分数据含有噪音和离群点，其数据集大小如表2所示。

表1 实验测试数据集

表2 实验数据集说明

在实验中，ICP算法和CS算法分别最大迭代50次和100次，旋转角度范围[0°,360°]，平移量范围[-40 mm,40 mm]，实验通过MATLAB R2012b编程实现，计算机硬件配置为Intel Core i5-4300U，内存8 GB。

点云配准中，需要模式搜索趋化的布谷鸟全局优化算法进行目标函数的优化，对于算法的参数设置应考虑种群规模、迭代次数、初始位置(旋转角度和平移量)对性能的影响。通过实验和测试，最终参数设置为：布谷鸟巢穴的规模为20，发现概率Pa=0.25。本文实验设定最大迭代次数并独立运行30次。

配准算法常常采用两片点云配准后对应点集间的距离来表示两片点云的吻合程度，其值越小配准精度就越高，点云数据的单位为mm，为了便于比较，经过算法优化的结果如表3所示。

表3 粗精配准精度结果

2.2 点云简化与特征点提取

在这次实验中，需要测试点云简化与特征点提取的尺度对后续配准的影响，从而确定合适的采样参数和特征点提取的参数r、ε1和ε2的设置。首先测试点云均匀采样率，采样的尺度大小会影响后期的点云配准过程中算法的计算量，采样过高会影响计算的效率，采样太低不能很好地表达点云数据的局部信息，合适的采样比率对后期的配准至关重要。本文通过多次实验，在6组模型数据的采样测试中，最终确定采样参数设定为0.1，可以有效保持点云数据的整体性，降低后续数据处理的运算量，实验结果如表4所示。

表4 点云由粗到精配准结果

在均匀采样的基础上，本文进一步验证特征点提取，通过6组模型数据的特征提取实验，确定搜索半径范围rISS和特征点识别阈值ε1和ε2，其中模型数据，由于扫描点云的差异性，其搜索范围rISS分别为0.02、5和10，ε1=ε2=0.6，可以有效保持点云数据的固有形状特征信息，对于数据本身存在高噪声、离群点等会影响配准精度的点云具有较好的鲁棒性。

2.3 布谷鸟优化算法粗配准性能

将CS与传统的ICP算法进行比较，在种群规模SN=20和最大的迭代次数100的前提下进行实验。结果如表3和表4所示。

表3中给出两个算法在6个模型数据配准精度上比较的结果，本文的CS比传统的ICP求解精度更好，表现出更加优异的性能。表4中列举了6个模型数据在视角1和视角2视角下的配准结果，从表3和表4的结果可以看出，CS算法在粗配准的精度上表现出了较好的性能。这是因为其更好的莱维飞行全局搜索机制使得算法在配准过程中很好地达到全局搜索与局部寻优的有效平衡，在点云配准中表现出更好的搜索效率和求解精度。

2.4 由粗到精配准算法的验证

为了验证本文配准策略流程的有效性和鲁棒性，实验分别在6个模型数据进行测试。配准结果通过可视化的方式进行呈现，如表4所示，给出输入点云，进行简化和特征点提取，然后利用CS进行粗配准，在粗配准的基础上进行ICP精配准，最后将变换参数映射到输入的点云上得到最终的配准结果。同时使用式(12)均方根差(Root Mean Square Error, RMSE)在对应点间进行量化，反映了点云配准的精度，值越小，配准效果越好。

表3显示了模型数据的配准结果，以视角1和视角2的配准为例，本文的方法都能达到较好的配准结果，RMS值在配准后满足配准的精度要求，达到理想的精度数量级。

表3和表5中分别统计了本文算法在测试集数据视角1和视角2视角下的点云由粗到精配准的求解精度和时间统计，从结果上来看，本文算法配准效果较好，有一定的应用价值。

表5 配准时间统计

2.5 算法运行时间和精度的比较

运算时间和精度能够很好地考量点云配准算法的性能。为了验证本文算法在初始位置旋转或者平移变换后配准的鲁棒性，本文选择Bunny的视角1和视角2进行实验，并进一步将本文算法(CS+ICP)与传统的ICP直接配准在初始位置变换的情况下进行实验比较。结果如表6和图1所示。

表6 本文算法与传统的ICP在初始位置变换下的配准比较

(a)初始位置变换后的配准比较(π/4,-π/4,-π/4,0.04,-0.03,0.04)

表6中，旋转角度是指沿三个坐标轴旋转的角度大小，平移参数表示沿三个坐标轴平移的数值，tICP、tCS、tICP′、tsum分别表示直接用ICP配准时间、本文CS粗配准时间、ICP精配准时间和本文粗精配准总的时间，时间单位为s。

为了比较的公平性，ICP最大迭代50次，CS初始配准迭代100次，运行时间和求解精度如表7所示。传统的ICP在初始位置变换后，往往陷入了局部最优，配准时间急剧上升，平均耗时22.79 s，而且配准失败，如图1所示。而本文算法中ICP收敛速度快速，配准时间平均为0.74 s，这是因为采用CS算法保障了ICP配准的初始位置。虽然CS平均耗时8.36 s，但这是在最大迭代次数100的情况下所测，实际情况下，多数配准只需要50次左右迭代即可满足ICP精配准初始位置迭代要求，并且配准精度显著提高，达到理想的配准精度要求。经过旋转平移变换的两片点云，整体上粗精配准的平均时间在10.84 s，时间相比于直接ICP配准降低明显，而且能有效配准。

为了进一步与已有的群智能优化的点云配准算法相比较，本文选用通用点云库SAMPL中的2个典型点云模型(Frog和Angel’)进行比较实验。两个模型分别选用0和40度视角下的两片点云进行旋转90度，并用ICP、BBO、ABC和HS算法进行对比实验。算法参数根据文献[22]进行设置，ABC、BBO和HS的种群规模分别为20、100和50，最大迭代时间统一设置为20 s。实验结果如表7所示。

表7 本文算法与其他算法的配准比较

从表7中可以看出，传统的ICP算法对初始位置比较敏感，容易陷入局部最优导致配准失败。本文算法相比于其他群智能优化算法具有较好的精度优势，表现出较好的搜索性能。

通过多次实验和配准效果来看，当两片点云在没有旋转角度和平移的情况下，ICP算法能得到较好的配准效果，但随着待配准点云的初始位置产生旋转和平移变换后，ICP算法很容易陷入局部最优，配准效果大大降低，而采用本文算法进行粗配准则有助于解决该问题，降低算法对配准初始位置的敏感性。由表6可知，利用本文搜索策略相比于传统的ICP算法求解精度更优，能有效降低对点云配准初始位置的要求，不同的初始变换位置下能得到更好的搜索优化结果，配准效果较好。

3 结 语

本文采用莱维飞行机制的布谷鸟全局优化算法来解决点云配准优化问题。在整个配准过程中先采用点云简化与特征点提取，然后利用CS算法进行目标函数的优化，获得点云变换矩阵的全局最优解，然后再通过精配准获得最终的点云配准效果。通过不同的模型数据对算法的性能进行测试，结果表明，本文算法在点云配准优化问题中，较好地解决ICP算法对点云初始位置严重依赖的问题，且很好地抑制早熟的能力，提高全局寻优能力，同时求解精度也相比于传统的ICP算法大幅提高，在点云配准中有很好的鲁棒能力，具有较好的应用价值。