基于并行粒子群優化的三維點云配準算法

賈志成，張希晉，陳　雷，郭艷菊

(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.