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

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

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

?

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

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

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

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

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

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

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

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

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

1基于改進粒子群算法的點云配準(zhǔn)

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

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

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

設(shè)在D維搜索空間里，有一個規(guī)模大小為M的種群，第i個粒子在空間中的位置可以表示為xi=(xi1,xi2,…，xiD)，第i個粒子所經(jīng)歷過的當(dāng)前最好位置(最優(yōu)的適應(yīng)度)可記為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)控制前一速度對當(dāng)前速度的影響。其中，w為慣性權(quán)重；c1和c1為學(xué)習(xí)因子；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ù)，取值大小遵循標(biāo)準(zhǔn)正態(tài)分布。結(jié)合式(2)～(4)就是本文粒子速度與位置更新規(guī)則。

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

1.2三維點云的配準(zhǔn)

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

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

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

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

(5)

變換矩陣T包含6個元素：平移向量x,y,z以及旋轉(zhuǎn)矩陣α,β,γ。這是一個六維函數(shù)的優(yōu)化問題。當(dāng)兩片點云最大限度重合時，sum(minEi)的值最小。

在未確定對應(yīng)點時，對于給出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)表示對應(yīng)點的距離平方和，利用粒子群算法在六維空間內(nèi)找到F(T)最小值，就能得到對應(yīng)的旋轉(zhuǎn)平移矩陣T，從而達(dá)到配準(zhǔn)兩片點云的目的。

2基于CUDA的PSO配準(zhǔn)算法

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

2.1CUDA編程模型

CUDA(ComputeUnifiedDeviceArchitecture)，是一種將GPU作為數(shù)據(jù)并行計算設(shè)備的軟硬件體系，它能夠利用GPU的并行處理單元比CPU更高效地解決復(fù)雜的計算任務(wù)[16]。在使用CUDA對PSO算法加速時，先要在CPU上提前做好各項準(zhǔn)備，例如復(fù)制點云據(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配準(zhǔn)算法實現(xiàn)

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

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

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

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

3實驗與分析

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

3.1實驗設(shè)計

實驗以點云數(shù)據(jù)庫中的Stanfordbunny00和Stanfordbunny45兩片點云為例進行配準(zhǔn)驗證。淺色點云(bunny000)含有40 256個數(shù)據(jù)點，深色點云(bunny045)含有40 097個數(shù)據(jù)點。實驗所采用的計算環(huán)境配置如表1所示。配準(zhǔn)中PSO算法以F(T)為適應(yīng)度函數(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線程與每個粒子一一對應(yīng)并分配合適的空間。

表1計算平臺配置

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

3.2實驗結(jié)果

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

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

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

表2GPU與CPU下PSO配準(zhǔn)算法耗時對比

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

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

3.5結(jié)果分析

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

表3改變初始位置后與ICP配準(zhǔn)效果對比

4結(jié)語

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

參考文獻：

[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)位置的自適應(yīng)變異擾動粒子群算法[J].西南交通大學(xué)學(xué)報，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— )，碩士，教授，碩士生導(dǎo)師，主要研究領(lǐng)域為智能信號處理、信號與編碼理論；

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

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

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

責(zé)任編輯：閆雯雯

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

文獻標(biāo)志碼：A

DOI：10.16280/j.videoe.2016.01.007

基金項目：中國博士后科學(xué)基金項目(2014M561184)；天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計劃項目(15JCYBJC17100)

作者簡介：

收稿日期：2015-06-12

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

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