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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

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

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

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

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

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

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

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

(5)

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

在未確定對(duì)應(yīng)點(diǎn)時(shí)，對(duì)于給出S1(大小為N1)中的點(diǎn)Pi和S2(大小為N2)中的點(diǎn)Qj，Ei是T(Pi)到S2所有點(diǎn)的距離最小值[6]，由此可得到

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

(6)

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

(7)

式中:F(T)表示對(duì)應(yīng)點(diǎn)的距離平方和，利用粒子群算法在六維空間內(nèi)找到F(T)最小值，就能得到對(duì)應(yīng)的旋轉(zhuǎn)平移矩陣T，從而達(dá)到配準(zhǔn)兩片點(diǎn)云的目的。

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

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

2.1CUDA編程模型

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

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

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

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

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

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

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

3實(shí)驗(yàn)與分析

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

3.1實(shí)驗(yàn)設(shè)計(jì)

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

表1計(jì)算平臺(tái)配置

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

3.2實(shí)驗(yàn)結(jié)果

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

3.3GPU加速前后運(yùn)算時(shí)間對(duì)比

為了進(jìn)一步說明GPU并行計(jì)算對(duì)PSO配準(zhǔn)算法速度的增幅，將之與傳統(tǒng)CPU上串行的PSO配準(zhǔn)算法做對(duì)比，針對(duì)點(diǎn)云StanfordBunny，Dragon，HappyBuddha，以bun000(40 256個(gè)點(diǎn))，dragonUpRight_0(42 641)和happyStandRight_0(78 056)作為源點(diǎn)集，bun000(40 097)，dragonUpRight_24(35 774)和happyStandRight_24(75 582)作為目標(biāo)點(diǎn)集在相同的硬件條件下進(jìn)行配準(zhǔn)，都設(shè)置粒子數(shù)為1 000，進(jìn)行30次迭代，此時(shí)3組點(diǎn)云的配準(zhǔn)誤差相似，配準(zhǔn)效果都良好。耗時(shí)對(duì)比結(jié)果如表2所示(保留5位有效數(shù)字)。由于GPU并行環(huán)境中所有粒子同時(shí)執(zhí)行計(jì)算，而CPU中每個(gè)粒子輪流串行的執(zhí)行計(jì)算過程，從表中可以看出前者要比后者節(jié)約大量的計(jì)算時(shí)間。

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

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

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

3.5結(jié)果分析

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

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

4結(jié)語

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

參考文獻(xiàn)：

[1]許智欽，孫長(zhǎng)庫.3D逆向工程技術(shù)[M].北京：中國計(jì)量出版社，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]劉志剛，曾嘉俊，韓志偉.基于個(gè)體最優(yōu)位置的自適應(yīng)變異擾動(dòng)粒子群算法[J].西南交通大學(xué)學(xué)報(bào)，2012，47(5)：761-768.

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

[16]張舒，趙開勇.GPU高性能運(yùn)算之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)域?yàn)橹悄苄盘?hào)處理、信號(hào)與編碼理論；

張希晉(1991— )，碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器視覺；

陳雷(1980— )，博士后，副教授，為本文通信作者，主要研究領(lǐng)域?yàn)槿S成像技術(shù)，仿生智能計(jì)算；

郭艷菊(1980— )，女，博士，主要研究領(lǐng)域?yàn)閳D像處理，通信編碼。

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

中圖分類號(hào)：TP391.7

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

DOI：10.16280/j.videoe.2016.01.007

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

作者簡(jiǎn)介：

收稿日期：2015-06-12

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

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