基于并行粒子群優(yōu)化的三維點云配準算法

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

(1.河北工業(yè)大學　電子信息工程學院，天津　300401；2.天津商業(yè)大學　信息工程學院，天津　300134；3.天津大學　精密儀器與光電子工程學院，天津　300072)

?

基于并行粒子群優(yōu)化的三維點云配準算法

賈志成1，張希晉1，陳雷2,3，郭艷菊1

(1.河北工業(yè)大學電子信息工程學院，天津300401；2.天津商業(yè)大學信息工程學院，天津300134；3.天津大學精密儀器與光電子工程學院，天津300072)

摘要:針對基于群智能優(yōu)化的點云配準算法計算時間長的問題，提出一種基于CUDA的并行粒子群配準算法。以點對點距離最短為適應度函數(shù)，利用粒子群算法各粒子天然的并行性，將運算過程分配到GPU的各個線程中計算變換參數(shù)。由于GPU多個線程運算同時執(zhí)行互不干擾，極大地提高了粒子群的運算速度，從而可以實現(xiàn)點云的快速、精確配準。實驗結(jié)果表明，該算法既克服了ICP算法對點云初始位置要求高的缺點，又有效解決了基于群智能優(yōu)化的點云配準算法計算時間長的問題。

關(guān)鍵詞:點云配準；粒子群算法；并行計算；逆向工程

點云數(shù)據(jù)配準是逆向工程[1]的重要環(huán)節(jié)，它實現(xiàn)同一物體不同角度點云的坐標配準，配準精度直接影響后續(xù)建立完整三維模型的精確性。點云配準算法就是為了確立兩個點集之間的對應點的映射關(guān)系，目前的方法中Besl等提出的迭代最近點算法(IterativeClosestPoint，ICP)[2]及其改進算法[3-5]最具代表性。

ICP算法以粗配準后的兩片點云為基礎(chǔ)，迭代求解兩片點云之間的距離最短對應點及相對位置變換參數(shù)，直到對應點距離的誤差值滿足設(shè)定的收斂值。它具有較好的精度，簡單而且被廣泛應用。但當兩片點云初始相對位置相差過大時，收斂方向容易出現(xiàn)錯誤。且當出現(xiàn)噪聲以及外點的情況時也容易造成配準失敗。ICP的改進算法從不同程度上提高了原始算法的抗噪能力和配準效率，但也依然無法從根本上解決其對初始位置要求過高的局限。

為了克服ICP算法對初始位置要求高的局限，Chow[6]等提出基于遺傳算法的點云配準算法，以平移和旋轉(zhuǎn)角度組成的六維變量以及使用對應點距離最短為適應度函數(shù)求解點云的變換矩陣。Santamaria[7-8]，Silva[9]以及Garcia-Torres[10]也分別從自適應進化、表面滲透向量以及和聲搜索等角度提出了基于進化算法的點云配準方法。進化算法使用群體方式在解空間內(nèi)進行全局搜索，克服了ICP算法對初始位置要求過高的弊端。但隨著三維點云數(shù)據(jù)規(guī)模的擴大，單片點云的點數(shù)不斷增加，進化配準算法的全局搜索時間成倍增長，由此導致的計算效率大幅降低已經(jīng)無法滿足目前點云配準的發(fā)展需求。

針對以上問題，本文提出一種受初始位置狀態(tài)影響小且效率高的并行粒子群三維點云配準算法。粒子群優(yōu)化[11](ParticleSwarmOptimization，PSO)算法是一種典型的群智能優(yōu)化方法，基于PSO的配準算法具有邏輯結(jié)構(gòu)簡單、變量參數(shù)少和易于程序?qū)崿F(xiàn)等優(yōu)點。與ICP算法相比，PSO配準算法有著優(yōu)秀的全局搜索能力，且受點云相對初始位置和噪聲干擾影響小。盡管如此，將PSO算法用于點云配準也仍存在處理大規(guī)模點云時速度緩慢效率不高的問題。隨著GPU并行計算技術(shù)的快速發(fā)展，由NVIDIA公司提出的基于GPU的并行計算架構(gòu)——統(tǒng)一計算設(shè)備架構(gòu)[12](ComputeUnifiedDeviceArchitecture，CUDA)已開始在通用計算領(lǐng)域廣泛應用。本文利用粒子群算法的天然并行性配合通用GPU技術(shù)，在基于CUDA并行計算環(huán)境中，以對應點距離最小為適應度函數(shù)，將并行PSO算法作為尋優(yōu)策略實現(xiàn)點云的配準，最終得到一種速度快、精度高、受初始位置影響小的點云配準算法。

1基于改進粒子群算法的點云配準

本文方法是使用粒子群算法以對應點距離平方和最小為準則，在六維空間(平移變量x,y,z和旋轉(zhuǎn)變量α,β,γ)內(nèi)搜索尋優(yōu)，最終得到兩片點云的相對旋轉(zhuǎn)平移矩陣，經(jīng)過空間變換使兩片不同坐標系下的點云配準到同一坐標系。

1.1粒子群優(yōu)化算法及其改進

在基本粒子群算法中，單個個體可以理解為在n維變量空間中重量和體積忽略不計的粒子，每個粒子在n維搜索空間中運動，由給定的速度參數(shù)決定其運動的方向和距離。受這個速度參數(shù)的影響，粒子會朝著位置最優(yōu)的粒子方向移動，并不斷發(fā)現(xiàn)新的最優(yōu)位置，經(jīng)過一代代搜尋最后找到最優(yōu)解的位置。在每一代搜索中，粒子將追蹤兩個最優(yōu)位置，一個是粒子本身到當前為止找到的最優(yōu)位置pbest，另一個為全種群的所有粒子當前找到的最優(yōu)位置gbest。

設(shè)在D維搜索空間里，有一個規(guī)模大小為M的種群，第i個粒子在空間中的位置可以表示為xi=(xi1,xi2,…，xiD)，第i個粒子所經(jīng)歷過的當前最好位置(最優(yōu)的適應度)可記為Pi=(pi1,pi2,…，piD)，每個粒子自己的飛行速度記為Vi=(vi1,vi2,…，viD),i=1,2,…，M。在整個群體中，所有粒子經(jīng)歷過的最好位置為Pg=(pg1,pg2,…，pgD)，每一代粒子根據(jù)式(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]的慣性權(quán)重方案，可以動態(tài)控制前一速度對當前速度的影響。其中，w為慣性權(quán)重；c1和c1為學習因子；r1和r2為[0，1]之間的隨機數(shù)。Tmax為最大迭代次數(shù)，wini為開始時慣性權(quán)重值，wfin為最終慣性權(quán)重值。PSO算法在搜索后期會趨于聚集到同一個或多個位置上，種群多樣性被減弱，可在式(1)后端加上一個擾動項，以增強粒子的多樣性[14]。

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

(4)

式中：r為擾動項，是[0，1]之間的隨機數(shù)，取值大小遵循標準正態(tài)分布。結(jié)合式(2)～(4)就是本文粒子速度與位置更新規(guī)則。

為了保證粒子能在規(guī)定的搜索空間內(nèi)尋優(yōu)，同時又避免粒子向邊界聚集，陷入范圍邊界上的局部最優(yōu)，改進算法對越界的粒子采用重新初始化的方案：當xid>xdmax或者xid

1.2三維點云的配準

點云配準的過程是將不同坐標系下的兩片點云經(jīng)過坐標變換使兩片點云對應的部分相互重合，判斷配準效果的標準即粒子群算法的適應度函數(shù)至關(guān)重要。

點對點距離最近法的基本原理是：對于原始點集中一點，在目標點集中尋找與之對應的最近點。最近點搜索的實現(xiàn)通常是使用kd-tree[15]，它可以縮短最近點集搜索的速度，極大地減少運算量，大幅提高運算的效率。

對于原始點云S1={Pi}，目標點云中與其相對應點S2={Qi}，目的是求兩片點云的旋轉(zhuǎn)平移變化T。假設(shè)S2是由S1經(jīng)過變換矩陣T轉(zhuǎn)變而來，那么對于所有點i來說，T(Pi)與Qi距離應該為0。然而由于點云是經(jīng)過激光掃描采集而來的，必然會存在測量誤差和量化誤差，所以T(Pi)與Qi距離差不為0。這個距離差越接近于0，則表示配準效果越精確。可以把點云配準問題轉(zhuǎn)化為關(guān)于求T(Pi)與Qi距離最小的優(yōu)化問題[如式(5)]。而粒子群算法對于這種離散優(yōu)化問題具有非常高的尋優(yōu)效率和精度。因此把對應點距離最短作為粒子群算法的尋優(yōu)準則，找到最優(yōu)值對應的旋轉(zhuǎn)平移矩陣，按照這個矩陣將兩片點云的相對位置重合在一起，從而實現(xiàn)點云的配準。

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

(5)

變換矩陣T包含6個元素：平移向量x,y,z以及旋轉(zhuǎn)矩陣α,β,γ。這是一個六維函數(shù)的優(yōu)化問題。當兩片點云最大限度重合時，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)表示對應點的距離平方和，利用粒子群算法在六維空間內(nèi)找到F(T)最小值，就能得到對應的旋轉(zhuǎn)平移矩陣T，從而達到配準兩片點云的目的。

2基于CUDA的PSO配準算法

為了能讓粒子群配準算法能有更高效的計算效率以適應目前大規(guī)模點云配準的需求，本文采用GPU加速技術(shù)在CUDA的環(huán)境中將PSO配準的運算過程分配到GPU各個線程當中去執(zhí)行，把多路運算的時間縮短到跟單路運算的時間相似，從而大幅提高運算效率。

2.1CUDA編程模型

CUDA(ComputeUnifiedDeviceArchitecture)，是一種將GPU作為數(shù)據(jù)并行計算設(shè)備的軟硬件體系，它能夠利用GPU的并行處理單元比CPU更高效地解決復雜的計算任務[16]。在使用CUDA對PSO算法加速時，先要在CPU上提前做好各項準備，例如復制點云據(jù)到GPU設(shè)備的內(nèi)存中，線程的規(guī)劃分配等。然后，CPU開始調(diào)用Kernel入口函數(shù)，程序會自動跳轉(zhuǎn)到GPU上運行，多路線程同時開始并行執(zhí)行。CUDA編程模型如圖1所示。

圖1中CPU在調(diào)用Kernel函數(shù)程序時需要向設(shè)備輸出兩個參數(shù)，使GPU能確定要分配Grid和Block的數(shù)目。在CUDA編程架構(gòu)下，一個Grid中包含若干個Block塊，一個Block塊又包含若干個thread(線程)，thread是GPU設(shè)備中最小的執(zhí)行單位，能夠并行執(zhí)行的最大線程數(shù)取決于設(shè)備顯卡配置和顯卡上的處理器數(shù)目。

2.2基于CUDA的并行PSO配準算法實現(xiàn)

粒子群配準算法和其他進化類配準算法一樣，都是基于群體模型的優(yōu)化搜索算法。由1.2節(jié)可知，其高效的全局尋優(yōu)能力非常適合解決點云配準問題。

基于粒子群的點云配準算法中要計算點與點在三維空間中的距離，由于點云中所含點的數(shù)目龐大，在尋找最近點的過程中會產(chǎn)生非常大的計算量。假設(shè)兩片點云規(guī)模都是30 000個數(shù)據(jù)點，每個點都是一個三維坐標，則每尋找一次對應點就會產(chǎn)生至少3×30 000×30 000次的平方差計算，而這僅僅是迭代一次計算量中的一小部分。如果配準程序放在CPU中串行執(zhí)行，即使使用高頻率多核心的處理器仍然會顯得運行時間過長，效率不高。而GPU上有著比CPU多數(shù)十倍的運算執(zhí)行單元，蘊含非常強大的計算能力。

在粒子群配準算法中每個粒子六維變量T和其速度的更新是互不干擾的，每個粒子計算最優(yōu)距離F(T)的過程是相互獨立的，粒子個體六維變量最優(yōu)位置的更新也是可并行的。算法中蘊含的這種并行性可以使筆者借助CUDA并行架構(gòu)調(diào)動GPU中龐大的運算單元并行的執(zhí)行點云配準中大量數(shù)據(jù)計算。

因此筆者在GPU中建立與粒子數(shù)相同的線程，每個粒子與每個線程一一對應，將本來需要在CPU中輪流執(zhí)行每個粒子的計算轉(zhuǎn)變?yōu)樵贕PU中所有粒子多路同時執(zhí)行的計算。在每個線程中單獨執(zhí)行一個粒子的六維變量和最小距離的更新與計算，利用GPU計算的并行性，把多個粒子的總計算時間縮短到接近一個粒子的計算時間，從而大幅提高計算速度，縮短PSO配準算法的運行時間。算法流程如圖2所示。

3實驗與分析

為了驗證本文算法的可行性和通用性，實驗采用了斯坦福大學計算機圖形學實驗室[17]提供的不同大小不同形狀的點云數(shù)據(jù)進行配準。

3.1實驗設(shè)計

實驗以點云數(shù)據(jù)庫中的Stanfordbunny00和Stanfordbunny45兩片點云為例進行配準驗證。淺色點云(bunny000)含有40 256個數(shù)據(jù)點，深色點云(bunny045)含有40 097個數(shù)據(jù)點。實驗所采用的計算環(huán)境配置如表1所示。配準中PSO算法以F(T)為適應度函數(shù)，在六維空間內(nèi)搜索(平移變量x,y,z以及旋轉(zhuǎn)變量α,β,γ。)設(shè)置平移變量的搜索范圍為兩片點云最大距離的2倍，旋轉(zhuǎn)變量搜索范圍-45°～45°。CUDA環(huán)境中，在CPU設(shè)置PSO初始種群為1 000，在變量范圍內(nèi)隨機初始化粒子位置和速度，GPU調(diào)用一個Block塊內(nèi)含1 000個thread線程與每個粒子一一對應并分配合適的空間。

表1計算平臺配置

程序開始時，CPU完成初始化PSO的各項參數(shù)并調(diào)用內(nèi)核模塊，程序跳轉(zhuǎn)到GPU上并行執(zhí)行。此時每個粒子互不干擾的同時依次執(zhí)行計算適應度函數(shù)，更新自身個體最佳位置，計算全局最佳位置和更新自身位置和速度。并依此循環(huán)直至滿足PSO算法所設(shè)定的收斂條件。

3.2實驗結(jié)果

程序運行結(jié)果如圖3～6所示，可以看出不同角度的兔子點云相同部分重疊在一起，交錯有致，達到較好的配準效果。

3.3GPU加速前后運算時間對比

為了進一步說明GPU并行計算對PSO配準算法速度的增幅，將之與傳統(tǒng)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)作為目標點集在相同的硬件條件下進行配準，都設(shè)置粒子數(shù)為1 000，進行30次迭代，此時3組點云的配準誤差相似，配準效果都良好。耗時對比結(jié)果如表2所示(保留5位有效數(shù)字)。由于GPU并行環(huán)境中所有粒子同時執(zhí)行計算，而CPU中每個粒子輪流串行的執(zhí)行計算過程，從表中可以看出前者要比后者節(jié)約大量的計算時間。

表2GPU與CPU下PSO配準算法耗時對比

3.4本文算法與ICP算法受初始位置影響對比

為了驗證兩片點云初始位置變化時對本算法的影響，以StanfordBunny為例，人工的對源點集bun000進行旋轉(zhuǎn)平移，再與目標點集bun045進行配準。分別使用ICP算法和本文算法進行配準，不考慮時間的情況下，只看最終能否配準成功。在誤差(對應點距離平方和)都趨于收斂基本不變時，對比兩種方法的配準結(jié)果。通過多次顯示試驗，當誤差在0.018及以下時兩片點云已經(jīng)達到很好的配準效果，當誤差高于0.1則表示完全無法配準。如表3所示。

3.5結(jié)果分析

綜合以上實驗，受限于硬件配置和對CUDA編程優(yōu)化有限，基于GPU并行加速的PSO配準算法已經(jīng)比未經(jīng)GPU加速的PSO配準時間縮短10倍左右，如若使用專業(yè)的計算顯卡或提高對CUDA編程優(yōu)化，則能帶來更大幅度的速度提升。而表3也表明本文算法在點云初始相對位置不斷改變時仍能達到較好的配準效果。受點云初始位置影響小，克服了ICP算法受初始位置限制大的弊端，具有較高的通用性和穩(wěn)定性。

表3改變初始位置后與ICP配準效果對比

4結(jié)語

本文以對應點距離最小為適應度函數(shù)將點云配準轉(zhuǎn)過程變?yōu)榱Ｗ尤簝?yōu)化算法搜索變換矩陣最優(yōu)參數(shù)的過程，并通過CUDA架構(gòu)平臺對PSO算法進行GPU上的并行加速，充分利用了粒子群算法的全局搜索尋優(yōu)能力和GPU高速并行的浮點計算能力。經(jīng)過不同的對比試驗，驗證了本文算法的可行性、高效性和穩(wěn)定性，并且有效降低了配準效果受點云初始位置的影響，具有更強的適應性和通用性。

參考文獻：

[1]許智欽，孫長庫.3D逆向工程技術(shù)[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]劉志剛，曾嘉俊，韓志偉.基于個體最優(yōu)位置的自適應變異擾動粒子群算法[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— )，碩士，教授，碩士生導師，主要研究領(lǐng)域為智能信號處理、信號與編碼理論；

張希晉(1991— )，碩士研究生，主要研究領(lǐng)域為機器視覺；

陳雷(1980— )，博士后，副教授，為本文通信作者，主要研究領(lǐng)域為三維成像技術(shù)，仿生智能計算；

郭艷菊(1980— )，女，博士，主要研究領(lǐng)域為圖像處理，通信編碼。

責任編輯：閆雯雯

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)；天津市應用基礎(chǔ)與前沿技術(shù)研究計劃項目(15JCYBJC17100)

作者簡介：

收稿日期：2015-06-12

文獻引用格式：賈志成，張希晉，陳雷，等.基于并行粒子群優(yōu)化的三維點云配準算法[J].電視技術(shù)，2016,40(1)：36-41.

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