基于并行粒子群优化的三维点云配准算法

贾志成，张希晋，陈　雷，郭艳菊

(1.河北工业大学　电子信息工程学院，天津　300401；2.天津商业大学　信息工程学院，天津　300134；3.天津大学　精密仪器与光电子工程学院，天津　300072)



基于并行粒子群优化的三维点云配准算法

贾志成1，张希晋1，陈雷2,3，郭艳菊1

(1.河北工业大学电子信息工程学院，天津300401；2.天津商业大学信息工程学院，天津300134；3.天津大学精密仪器与光电子工程学院，天津300072)

摘要:针对基于群智能优化的点云配准算法计算时间长的问题，提出一种基于CUDA的并行粒子群配准算法。以点对点距离最短为适应度函数，利用粒子群算法各粒子天然的并行性，将运算过程分配到GPU的各个线程中计算变换参数。由于GPU多个线程运算同时执行互不干扰，极大地提高了粒子群的运算速度，从而可以实现点云的快速、精确配准。实验结果表明，该算法既克服了ICP算法对点云初始位置要求高的缺点，又有效解决了基于群智能优化的点云配准算法计算时间长的问题。

关键词:点云配准；粒子群算法；并行计算；逆向工程

点云数据配准是逆向工程[1]的重要环节，它实现同一物体不同角度点云的坐标配准，配准精度直接影响后续建立完整三维模型的精确性。点云配准算法就是为了确立两个点集之间的对应点的映射关系，目前的方法中Besl等提出的迭代最近点算法(IterativeClosestPoint，ICP)[2]及其改进算法[3-5]最具代表性。

ICP算法以粗配准后的两片点云为基础，迭代求解两片点云之间的距离最短对应点及相对位置变换参数，直到对应点距离的误差值满足设定的收敛值。它具有较好的精度，简单而且被广泛应用。但当两片点云初始相对位置相差过大时，收敛方向容易出现错误。且当出现噪声以及外点的情况时也容易造成配准失败。ICP的改进算法从不同程度上提高了原始算法的抗噪能力和配准效率，但也依然无法从根本上解决其对初始位置要求过高的局限。

为了克服ICP算法对初始位置要求高的局限，Chow[6]等提出基于遗传算法的点云配准算法，以平移和旋转角度组成的六维变量以及使用对应点距离最短为适应度函数求解点云的变换矩阵。Santamaria[7-8]，Silva[9]以及Garcia-Torres[10]也分别从自适应进化、表面渗透向量以及和声搜索等角度提出了基于进化算法的点云配准方法。进化算法使用群体方式在解空间内进行全局搜索，克服了ICP算法对初始位置要求过高的弊端。但随着三维点云数据规模的扩大，单片点云的点数不断增加，进化配准算法的全局搜索时间成倍增长，由此导致的计算效率大幅降低已经无法满足目前点云配准的发展需求。

针对以上问题，本文提出一种受初始位置状态影响小且效率高的并行粒子群三维点云配准算法。粒子群优化[11](ParticleSwarmOptimization，PSO)算法是一种典型的群智能优化方法，基于PSO的配准算法具有逻辑结构简单、变量参数少和易于程序实现等优点。与ICP算法相比，PSO配准算法有着优秀的全局搜索能力，且受点云相对初始位置和噪声干扰影响小。尽管如此，将PSO算法用于点云配准也仍存在处理大规模点云时速度缓慢效率不高的问题。随着GPU并行计算技术的快速发展，由NVIDIA公司提出的基于GPU的并行计算架构——统一计算设备架构[12](ComputeUnifiedDeviceArchitecture，CUDA)已开始在通用计算领域广泛应用。本文利用粒子群算法的天然并行性配合通用GPU技术，在基于CUDA并行计算环境中，以对应点距离最小为适应度函数，将并行PSO算法作为寻优策略实现点云的配准，最终得到一种速度快、精度高、受初始位置影响小的点云配准算法。

1基于改进粒子群算法的点云配准

本文方法是使用粒子群算法以对应点距离平方和最小为准则，在六维空间(平移变量x,y,z和旋转变量α,β,γ)内搜索寻优，最终得到两片点云的相对旋转平移矩阵，经过空间变换使两片不同坐标系下的点云配准到同一坐标系。

1.1粒子群优化算法及其改进

在基本粒子群算法中，单个个体可以理解为在n维变量空间中重量和体积忽略不计的粒子，每个粒子在n维搜索空间中运动，由给定的速度参数决定其运动的方向和距离。受这个速度参数的影响，粒子会朝着位置最优的粒子方向移动，并不断发现新的最优位置，经过一代代搜寻最后找到最优解的位置。在每一代搜索中，粒子将追踪两个最优位置，一个是粒子本身到当前为止找到的最优位置pbest，另一个为全种群的所有粒子当前找到的最优位置gbest。

设在D维搜索空间里，有一个规模大小为M的种群，第i个粒子在空间中的位置可以表示为xi=(xi1,xi2,…，xiD)，第i个粒子所经历过的当前最好位置(最优的适应度)可记为Pi=(pi1,pi2,…，piD)，每个粒子自己的飞行速度记为Vi=(vi1,vi2,…，viD),i=1,2,…，M。在整个群体中，所有粒子经历过的最好位置为Pg=(pg1,pg2,…，pgD)，每一代粒子根据式(1)和(2)更新自己的速度和位置

vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)

(1)

xid=xid+vid

(2)

w=(wini-wfin)(Tmax-t)/Tmax+wfin

(3)

这里引入了Shi和Eberhart[13]的惯性权重方案，可以动态控制前一速度对当前速度的影响。其中，w为惯性权重；c1和c1为学习因子；r1和r2为[0，1]之间的随机数。Tmax为最大迭代次数，wini为开始时惯性权重值，wfin为最终惯性权重值。PSO算法在搜索后期会趋于聚集到同一个或多个位置上，种群多样性被减弱，可在式(1)后端加上一个扰动项，以增强粒子的多样性[14]。

vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)+r

(4)

式中：r为扰动项，是[0，1]之间的随机数，取值大小遵循标准正态分布。结合式(2)～(4)就是本文粒子速度与位置更新规则。

为了保证粒子能在规定的搜索空间内寻优，同时又避免粒子向边界聚集，陷入范围边界上的局部最优，改进算法对越界的粒子采用重新初始化的方案：当xid>xdmax或者xid

1.2三维点云的配准

点云配准的过程是将不同坐标系下的两片点云经过坐标变换使两片点云对应的部分相互重合，判断配准效果的标准即粒子群算法的适应度函数至关重要。

点对点距离最近法的基本原理是：对于原始点集中一点，在目标点集中寻找与之对应的最近点。最近点搜索的实现通常是使用kd-tree[15]，它可以缩短最近点集搜索的速度，极大地减少运算量，大幅提高运算的效率。

对于原始点云S1={Pi}，目标点云中与其相对应点S2={Qi}，目的是求两片点云的旋转平移变化T。假设S2是由S1经过变换矩阵T转变而来，那么对于所有点i来说，T(Pi)与Qi距离应该为0。然而由于点云是经过激光扫描采集而来的，必然会存在测量误差和量化误差，所以T(Pi)与Qi距离差不为0。这个距离差越接近于0，则表示配准效果越精确。可以把点云配准问题转化为关于求T(Pi)与Qi距离最小的优化问题[如式(5)]。而粒子群算法对于这种离散优化问题具有非常高的寻优效率和精度。因此把对应点距离最短作为粒子群算法的寻优准则，找到最优值对应的旋转平移矩阵，按照这个矩阵将两片点云的相对位置重合在一起，从而实现点云的配准。

minEi(T)=min[|T(Pi-Qi)|]foralli

(5)

变换矩阵T包含6个元素：平移向量x,y,z以及旋转矩阵α,β,γ。这是一个六维函数的优化问题。当两片点云最大限度重合时，sum(minEi)的值最小。

在未确定对应点时，对于给出S1(大小为N1)中的点Pi和S2(大小为N2)中的点Qj，Ei是T(Pi)到S2所有点的距离最小值[6]，由此可得到

Ei(T)=min|T(Pi-Qj)|,1≤j≤N2

(6)

F(T)=Median(Ei)2,1≤i≤N1

(7)

式中:F(T)表示对应点的距离平方和，利用粒子群算法在六维空间内找到F(T)最小值，就能得到对应的旋转平移矩阵T，从而达到配准两片点云的目的。

2基于CUDA的PSO配准算法

为了能让粒子群配准算法能有更高效的计算效率以适应目前大规模点云配准的需求，本文采用GPU加速技术在CUDA的环境中将PSO配准的运算过程分配到GPU各个线程当中去执行，把多路运算的时间缩短到跟单路运算的时间相似，从而大幅提高运算效率。

2.1CUDA编程模型

CUDA(ComputeUnifiedDeviceArchitecture)，是一种将GPU作为数据并行计算设备的软硬件体系，它能够利用GPU的并行处理单元比CPU更高效地解决复杂的计算任务[16]。在使用CUDA对PSO算法加速时，先要在CPU上提前做好各项准备，例如复制点云据到GPU设备的内存中，线程的规划分配等。然后，CPU开始调用Kernel入口函数，程序会自动跳转到GPU上运行，多路线程同时开始并行执行。CUDA编程模型如图1所示。

图1中CPU在调用Kernel函数程序时需要向设备输出两个参数，使GPU能确定要分配Grid和Block的数目。在CUDA编程架构下，一个Grid中包含若干个Block块，一个Block块又包含若干个thread(线程)，thread是GPU设备中最小的执行单位，能够并行执行的最大线程数取决于设备显卡配置和显卡上的处理器数目。

2.2基于CUDA的并行PSO配准算法实现

粒子群配准算法和其他进化类配准算法一样，都是基于群体模型的优化搜索算法。由1.2节可知，其高效的全局寻优能力非常适合解决点云配准问题。

基于粒子群的点云配准算法中要计算点与点在三维空间中的距离，由于点云中所含点的数目庞大，在寻找最近点的过程中会产生非常大的计算量。假设两片点云规模都是30 000个数据点，每个点都是一个三维坐标，则每寻找一次对应点就会产生至少3×30 000×30 000次的平方差计算，而这仅仅是迭代一次计算量中的一小部分。如果配准程序放在CPU中串行执行，即使使用高频率多核心的处理器仍然会显得运行时间过长，效率不高。而GPU上有着比CPU多数十倍的运算执行单元，蕴含非常强大的计算能力。

在粒子群配准算法中每个粒子六维变量T和其速度的更新是互不干扰的，每个粒子计算最优距离F(T)的过程是相互独立的，粒子个体六维变量最优位置的更新也是可并行的。算法中蕴含的这种并行性可以使笔者借助CUDA并行架构调动GPU中庞大的运算单元并行的执行点云配准中大量数据计算。

因此笔者在GPU中建立与粒子数相同的线程，每个粒子与每个线程一一对应，将本来需要在CPU中轮流执行每个粒子的计算转变为在GPU中所有粒子多路同时执行的计算。在每个线程中单独执行一个粒子的六维变量和最小距离的更新与计算，利用GPU计算的并行性，把多个粒子的总计算时间缩短到接近一个粒子的计算时间，从而大幅提高计算速度，缩短PSO配准算法的运行时间。算法流程如图2所示。

3实验与分析

为了验证本文算法的可行性和通用性，实验采用了斯坦福大学计算机图形学实验室[17]提供的不同大小不同形状的点云数据进行配准。

3.1实验设计

实验以点云数据库中的Stanfordbunny00和Stanfordbunny45两片点云为例进行配准验证。浅色点云(bunny000)含有40 256个数据点，深色点云(bunny045)含有40 097个数据点。实验所采用的计算环境配置如表1所示。配准中PSO算法以F(T)为适应度函数，在六维空间内搜索(平移变量x,y,z以及旋转变量α,β,γ。)设置平移变量的搜索范围为两片点云最大距离的2倍，旋转变量搜索范围-45°～45°。CUDA环境中，在CPU设置PSO初始种群为1 000，在变量范围内随机初始化粒子位置和速度，GPU调用一个Block块内含1 000个thread线程与每个粒子一一对应并分配合适的空间。

表1计算平台配置

程序开始时，CPU完成初始化PSO的各项参数并调用内核模块，程序跳转到GPU上并行执行。此时每个粒子互不干扰的同时依次执行计算适应度函数，更新自身个体最佳位置，计算全局最佳位置和更新自身位置和速度。并依此循环直至满足PSO算法所设定的收敛条件。

3.2实验结果

程序运行结果如图3～6所示，可以看出不同角度的兔子点云相同部分重叠在一起，交错有致，达到较好的配准效果。

3.3GPU加速前后运算时间对比

为了进一步说明GPU并行计算对PSO配准算法速度的增幅，将之与传统CPU上串行的PSO配准算法做对比，针对点云StanfordBunny，Dragon，HappyBuddha，以bun000(40 256个点)，dragonUpRight_0(42 641)和happyStandRight_0(78 056)作为源点集，bun000(40 097)，dragonUpRight_24(35 774)和happyStandRight_24(75 582)作为目标点集在相同的硬件条件下进行配准，都设置粒子数为1 000，进行30次迭代，此时3组点云的配准误差相似，配准效果都良好。耗时对比结果如表2所示(保留5位有效数字)。由于GPU并行环境中所有粒子同时执行计算，而CPU中每个粒子轮流串行的执行计算过程，从表中可以看出前者要比后者节约大量的计算时间。

表2GPU与CPU下PSO配准算法耗时对比

3.4本文算法与ICP算法受初始位置影响对比

为了验证两片点云初始位置变化时对本算法的影响，以StanfordBunny为例，人工的对源点集bun000进行旋转平移，再与目标点集bun045进行配准。分别使用ICP算法和本文算法进行配准，不考虑时间的情况下，只看最终能否配准成功。在误差(对应点距离平方和)都趋于收敛基本不变时，对比两种方法的配准结果。通过多次显示试验，当误差在0.018及以下时两片点云已经达到很好的配准效果，当误差高于0.1则表示完全无法配准。如表3所示。

3.5结果分析

综合以上实验，受限于硬件配置和对CUDA编程优化有限，基于GPU并行加速的PSO配准算法已经比未经GPU加速的PSO配准时间缩短10倍左右，如若使用专业的计算显卡或提高对CUDA编程优化，则能带来更大幅度的速度提升。而表3也表明本文算法在点云初始相对位置不断改变时仍能达到较好的配准效果。受点云初始位置影响小，克服了ICP算法受初始位置限制大的弊端，具有较高的通用性和稳定性。

表3改变初始位置后与ICP配准效果对比

4结语

本文以对应点距离最小为适应度函数将点云配准转过程变为粒子群优化算法搜索变换矩阵最优参数的过程，并通过CUDA架构平台对PSO算法进行GPU上的并行加速，充分利用了粒子群算法的全局搜索寻优能力和GPU高速并行的浮点计算能力。经过不同的对比试验，验证了本文算法的可行性、高效性和稳定性，并且有效降低了配准效果受点云初始位置的影响，具有更强的适应性和通用性。

参考文献：

[1]许智钦，孙长库.3D逆向工程技术[M].北京：中国计量出版社，2002.

[2]BESLPJ，MCKAYND.Amethodforregistrationof3-Dshape[J].IEEEtransactionsonpatternanalysisandmachineintelligence，1992，14(2)：239-256.

[3]RUSINKIEWICZS，LEVOYM.EfficientvariantsoftheICPalgorithm[C]//TheThirdInternationalConferenceon3-DDigitalImagingandModeling.Canada：[s.n.]，2001：211-215.

[4]FITZGIBBONAW.Robustregistrationof2Dand3Dpointsets[J].Imageandvisioncomputing，2001，21(12)：1145-1153.

[5]CHETVERIKOVD，STEPANOVD，KRSEKP.Robusteuclideanalignmentof3Dpointsets：thetrimmediterativeclosestpointalgorithm[J].Imageandvisioncomputing，2005，23(3)：299-309.

[6]CHOWC，TSUIH，LEET.Surfaceregistrationusingadynamicgeneticalgorithm[J].Patternrecognition，2004，37(1)：115-117.

[7]SANTAMARIAJ，CORDONO，DAMASS.Acomparativestudyofstate-of-the-artevolutionaryimageregistrationmethodsfor3dmodeling[J].Computervisionandimageunderstanding，2011，115(9)：1340-1354.

[8]SANTAMARIAJ，CORDONO，DAMASS，etal.Self-adaptiveevolutiontowardnewparameterfreeimageregistrationmethods[J].IEEEtransactionsonevolutionarycomputation，2013，17(4)：545-557.

[9]SILVAL，ORPBELLON，KLBOYER.Precisionrangeimageregistrationusingarobustsurfaceinterpenetrationmeasureandenhancedgeneticalgorithms[J].IEEEtransactionsonpatternanalysis, 2005，27(5)：762-776.

[10]GARCIA-TORRESJM，DAMASS，CORDONO，etal.Acasestudyofinnovativepopulation-basedalgorithmsin3Dmodeling：artificialbeecolony，biogeography-basedoptimization，harmonysearch[J].Expertsystemswithapplications，2014，41(4)：1750-1762.

[11]KENNEDYJ，EBERHARTRC.Particleswarmoptimization[C]//IEEEInternationalConferenceonNeuralNetworks，Ⅳ.Piscataway，NJ：IEEEServiceCenter，1995：1942-1948.

[12]NVIDIA.NVIDIAcudaCprogrammingguide：version3.2[EB/OL].(2013-05-01)[2015-06-20].http：//www.nvidia.com/object/cuda_home.html.

[13]EBERHARTRC，SHIYH.Particleswarmoptimization：developments，applicationandresources[C] // 2001CongressonEvolutionaryComputation.NewYork：IEEEPress，2001： 81-86.

[14]刘志刚，曾嘉俊，韩志伟.基于个体最优位置的自适应变异扰动粒子群算法[J].西南交通大学学报，2012，47(5)：761-768.

[15]VANCOM，BRUNNETTG，SCHREIBERT.Ahashingstrategyforefficientk-nearestneighborscomputation[C]//Proc.InternationalConferenceComputerGraphics.[S.l.]：IEEEPress，1999：120-128.

[16]张舒，赵开勇.GPU高性能运算之CUDA[M].北京：中国水利水电出版社，2009.

[17]StanfordUniversity.Stanford3Dscanningrepository[EB/OL].(2012-12-18)[2015-06-20].http：//www.graphics.stanford.edu/data/3Dscanrep/.

贾志成(1957— )，硕士，教授，硕士生导师，主要研究领域为智能信号处理、信号与编码理论；

张希晋(1991— )，硕士研究生，主要研究领域为机器视觉；

陈雷(1980— )，博士后，副教授，为本文通信作者，主要研究领域为三维成像技术，仿生智能计算；

郭艳菊(1980— )，女，博士，主要研究领域为图像处理，通信编码。

责任编辑：闫雯雯

Researchof3Dpointclouddataregistrationbasedonparallelparticleswarmoptimizationalgorithm

JIAZhicheng1，ZHANGXijin1，CHENLei2,3，GUOYanju1

(1.College of Information Engineering,Hebei University of Technology,Tianjin 300401,China;2.College of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China;3.College of Precision Instrument and Opto Electronics Engineering,Tianjin University,Tianjin 300072,China)

Keywords:pointclouddataregistration;PSO;CUDA;reverseengineering

Abstract:Tosurmountthelimitationoflongcomputingtimeofpointcloudregistrationbasedonswarmintelligenceoptimizationalgorithm,aparallelparticleswarmoptimizationalgorithmbasedonCUDAisproposed.Regardingtheshortestdistancebetweenpointandpointasthefitnessfunction,utilizingtheparralismofparticleswarmoptimizationalgorithm,operationprocessisdistributedtovariousthreadsofGPUandcalculatethetransformationparameters,torealizethepreciseregistrationofpointcloud.Asimplementationofmultiplethreadsoperationatthesametimedonotinterferewitheachother,whichgreatlyimprovestheoperationspeedofparticleswarmoptimization.TheexperimentalresultsshowthatthealgorithmnotonlyovercomesthedisadvantageoftheICPalgorithmwithhighrequirementtotheinitialpositionofpointcloud,butalsoeffectivelysolvestheproblemofoperationswarmintelligentalgorithmwhichcoststoomuchtime.

中图分类号：TP391.7

文献标志码：A

DOI：10.16280/j.videoe.2016.01.007

基金项目：中国博士后科学基金项目(2014M561184)；天津市应用基础与前沿技术研究计划项目(15JCYBJC17100)

作者简介：

收稿日期：2015-06-12

文献引用格式：贾志成，张希晋，陈雷，等.基于并行粒子群优化的三维点云配准算法[J].电视技术，2016,40(1)：36-41.

JIAZC,ZHANGXJ,CHENL,etal.Researchof3Dpointclouddataregistrationbasedonparallelparticleswarmoptimizationalgorithm[J].Videoengineering,2016,40(1)：36-41.