基于分層粒子群優(yōu)化的三維點云配準

黃筱佟，溫佩芝，蕭華鵬，賀 杰，邸臻煒

(1.梧州學(xué)院 a.廣西高校圖像處理與智能信息系統(tǒng)重點實驗室，b.大數(shù)據(jù)與軟件工程學(xué)院，廣西 梧州 543002；2.桂林電子科技大學(xué) 計算機與信息安全學(xué)院，廣西 桂林 541004；3.廣西師范大學(xué) 物理科學(xué)與技術(shù)學(xué)院，廣西 桂林 541004)

隨著圖像技術(shù)的發(fā)展，借助圖像數(shù)據(jù)挖掘獲取有價值數(shù)據(jù)的方法在多個行業(yè)廣泛應(yīng)用，并且取得了良好的效果。當(dāng)前的圖像數(shù)據(jù)研究多是基于二維的，三維圖像的研究主要集中在圖像的建模和重構(gòu)，攝像機從不同角度對同一實體拍攝圖像數(shù)據(jù)，根據(jù)這些圖像還原實體空間結(jié)構(gòu)[1]。由于拍攝時受到背景、光線和噪聲等的影響，因此根據(jù)多張二維圖像重構(gòu)三維實體的過程并不簡單。當(dāng)前三維圖像重構(gòu)采用的主要手段為三維點云配準，即通過攝像機對實體表面的多角度二維圖像的采集，獲得圖像點云，根據(jù)二維圖像所包含的點云RGB三原色和坐標值、點云與攝像機的距離值[2]等獲取三維實體有效特征，去除多個二維圖像包含的冗余特征，將多個圖像點云平移變換至同一坐標系。

對于三維點云配準的研究成果較多。文獻[3]中采用八叉樹實現(xiàn)大規(guī)模點云樣本的配準，點云的坐標變換結(jié)合了鄰居節(jié)點拓撲。文獻[4]中將遺傳算法運用于點云配準，并運用熵值計算點的關(guān)聯(lián)性，兩者均取得了較好的配準效果。在小規(guī)模的點云數(shù)據(jù)匹配過程中，迭代最近點(iterative closest point，ICP)算法可以獲得較好的匹配準確度，而且效率較高[5]。由于在進行較大實體的重建過程中，需要處理數(shù)量龐大的數(shù)據(jù)點云配準，標準ICP算法會消耗大量的配準時間，因此，本文中在標準ICP算法的基礎(chǔ)上，引入分層粒子群優(yōu)化 (PSO)算法，以提高配準的效率。

1 ICP 算法

ICP算法在參考點云pi(i為粒子序號)和目標點云qi之間進行最近點搜索，對N個點進行連續(xù)的坐標變換，以更接近于目標點云位置。最近點搜索評價指標為所有pi與qi的距離差的平均值f(R，T)[6]，即

(1)

式中R、T分別為坐標變化的選擇和平移操作。當(dāng)求解的f(R,T)值滿足設(shè)定的閾值時，算法停止。

設(shè)參考點云P和目標點云Q滿足P={pi|pi∈3,i=1,2,…,M}，M為參考點個數(shù)，Q={qj|qj∈3,j=1,2,…,N}，在Q中尋找與pi最近的qj，它們之間的距離d(P，Q)的計算公式為

(2)

對P中所有的點尋找最近點，構(gòu)成Y=C(P,Q)，其中C為映射函數(shù)。

為了對參考點云中所有點進行距離評估，引入點云重心，參考點云和目標點云計算公式分別為

(3)

(4)

然后在式(3)、(4)的基礎(chǔ)上構(gòu)建三維點的協(xié)方差矩陣ζ[7]，即

(5)

設(shè)定閾值τ，當(dāng)fk(R,T)-fk+1(R,T)<τ時，算法迭代停止，其中k為迭代次數(shù)。

配準精度評價的一般方法為計算所有點云的距離的均方根誤差σ，計算公式為

(6)

2 分層粒子群優(yōu)化

2.1 PSO算法

采用PSO算法對三維點云的特征點進行提取，將源點云坐標作為粒子群的粒子，將多個點云坐標作為粒子群算法的輸入集合，求解所有點云中曲率值較大的點作為點云特征點[10]。設(shè)第i個粒子xi=(xi1,xi2,…,xiN)的飛行速度為vi=(vi1,vi2,…,viN)，以點的曲率值作為適應(yīng)度函數(shù)，求解第i個粒子適應(yīng)度極大值pi=(pi1,pi2,…,piN)，然后計算所有粒子的適應(yīng)度極大值pg=(pg1,pg2,…,pgN)。粒子速度更新公式[11]為

(7)

(8)

式中：d為第i個粒子的屬性序號；c1、c2為學(xué)習(xí)因子；ω為上一個時間段的速度權(quán)重；r1,r2∈rand(0,1)，為速度因子；r∈rand(0,1)，為全局速度因子。

2.2 分層PSO算法

為了提高粒子群搜索速率和尋優(yōu)性能，引入分層PSO算法。分層PSO算法的核心思想是將整個粒子群分成若干子群，根據(jù)子群的最優(yōu)個體和全局最優(yōu)進行對比[12]，從而能夠在所有粒子中快速找到最優(yōu)個體的位置。

首先將粒子按空間分塊，對每一塊空間中的粒子分別求解最優(yōu)值，同時根據(jù)全局最優(yōu)值不斷調(diào)整位置。分層粒子群的空間分割原理如圖1所示。

圖1 分層粒子群的空間分割原理

按照粒子的初始位置，將粒子群中的160個粒子分為10組，每組均包含16個粒子。在10個子群中分別執(zhí)行PSO算法進行速度和位置更新，每次更新后都與全局最優(yōu)解對比，以調(diào)整下一次粒子更新方向，這樣更容易獲得全局最優(yōu)解，且提高了獲取效率。

先將M個粒子群按等額分成L份，建立L個子群，分別在L個子群中采用式(7)、(8)進行迭代，然后將第i(1≤i≤L)個子群的適應(yīng)度極大值pig與pg對比[13]，從而來指導(dǎo)子群粒子的運動方向，分層粒子群結(jié)構(gòu)如圖2所示。

pg—全部粒子的適應(yīng)度極大值；pig—第i個子群的適應(yīng)度極大值，i=1,2,…,L。圖2 分層粒子群結(jié)構(gòu)

子群粒子在進行速度更新時，將子群個體、pig與pg三者結(jié)合，共同修正粒子位置，分層粒子群速度更新將在式(7)的基礎(chǔ)上進行改進，具體公式[14]為

(9)

式中：c3為全局學(xué)習(xí)因子；c1、c2和c3值默認設(shè)置為2；r3∈rand(0,1)，為速度因子。

2.3 分層PSO的三維點云特征提取

將PSO算法用于特征點的提取，選取曲率值大的點作為特征點，采用粒子群快速搜索點云中曲率值大的點，根據(jù)數(shù)值排序，選擇排序靠前的點為特征點。曲率值的閾值決定了入選特征點的數(shù)量，然后采用ICP算法來執(zhí)行特征點配準。具體實現(xiàn)流程如圖3所示。

ICP—迭代最近點。圖3 分層粒子群優(yōu)化的三維點云配準流程

3 實例仿真

為了驗證分層PSO算法的三維點云數(shù)據(jù)配準的性能，首先，選擇長方形的桌面帶紋理的木桌進行可視化點云配準仿真，并計算配準的均方根誤差σ和配準時間；其次采用斯坦福點云數(shù)據(jù)庫[15]分別對ICP和分層粒子群優(yōu)化ICP進行點云配準性能仿真。初始值L=5,ω=1.0。仿真平臺為MATLAB 2018。

3.1 分層PSO算法的三維點云配準性能

3.1.1 三維點云配準可視化

圖4所示為長方形木桌的源點云和目標點云空間分布，其中紅色點為源點云，源點云是經(jīng)過分層粒子群優(yōu)化后的特征點云分布；藍色為目標點云，可以更好地實現(xiàn)源點云配準的可視化對照。從圖中可以看出，經(jīng)過分層PSO后的點云特征提取性能更好，可以反映該木桌的空間結(jié)構(gòu)，并且在所有特征點云中，僅出現(xiàn)1個明顯噪聲特征點。

圖4 長方形木桌的源點云和目標點云空間分布

圖5所示為長方形木桌源點云的配準結(jié)果。對比圖4的藍色目標點云，本文中提出的配準算法較精確，具體配準性能標準如表1所示。從圖5還可以看出，ICP算法對噪聲點也進行了配準，表明ICP算法并不能有效去除噪聲，因此要使用ICP算法得到點云的精確配準，必須在ICP迭代之前進行有效的噪聲消除。

圖5 長方形木桌源點云的配準結(jié)果

表1 長方形木桌的配準性能標準

3.1.2 分層PSO算法的點云特征優(yōu)化性能

分層粒子群的子群數(shù)L和粒子速度權(quán)重ω值影響著PSO算法的收斂速度和全局尋優(yōu)性能。為了驗證L和ω對點云配準的優(yōu)化性能，差異化選取L和ω，驗證本文中提出的算法在點云配準中的性能，仿真結(jié)果如表2、3所示。

表2 不同速度權(quán)重時的點云配準性能

從表2可以看出：ω增大，點云配準的均方根誤差呈現(xiàn)先減小后增大的趨勢，而配準時間差異并不大；在ω=1.2處，粒子群搜索得到的源點云的特征點經(jīng)過ICP配準能夠獲得最優(yōu)的配準精度。

從表3可以看出：隨著子群數(shù)的增加，配準均方根誤差減小，可見子群數(shù)量越多，特征點提取更有效，點云配準的精度更高；當(dāng)子群數(shù)為7時，均方根誤差趨于穩(wěn)定，數(shù)值為4.893 3×10-6，但是隨著L的增大，配準時間也在逐漸增加，原因是子群數(shù)過多引起分層PSO特征點的提取耗時更長。在時間差別不大的情況下，選擇子群數(shù)為7更適合于該方法的點云配準。

表3 不同子群數(shù)時的點云配準性能

3.2 不同算法的點云配準性能

為了進一步驗證分層PSO的ICP算法在三維點云配準中的性能，采用常用的斯坦福點云數(shù)據(jù)樣本[15]，對標準ICP算法和經(jīng)過分層PSO優(yōu)化后的ICP算法分別進行仿真，仿真結(jié)果見表4。

表4 不同樣本的配準誤差

從表中數(shù)據(jù)可以看出，相比于傳統(tǒng)ICP算法，經(jīng)過分層PSO的ICP算法在斯坦福點云數(shù)據(jù)庫常用的6種不同樣本的配準精度略高，但兩者差異并不大。該算法在“Blade”樣本的配準性能最優(yōu)，均方根誤差僅為4.001 7×10-6，“Dragon”樣本配準性能最差，均方根誤差為5.160 2×10-6。

6類不同樣本在標準ICP和本文中提出的算法的配準時間見表5。在標準ICP中，配準時間主要消耗在ICP迭代過程中，而在分層PSO的ICP算法中，配準時間主要消耗在分層粒子群的點云特征點提取和點云配準2個方面。雖然后者增加了分層粒子群的特征提取時間，但是特征點提取后，減少了ICP迭代的點云數(shù)，節(jié)省了配準時間。通過與3.1節(jié)中長方形木桌配準效率進行對比，當(dāng)需配準的點數(shù)量增加時，配準時間增加，木桌的配準時間為0.951 6 s，而斯坦福點云數(shù)據(jù)庫常用的6種不同樣本配準時間均為5～7 s。

表5 不同樣本的配準時間

綜上，分層PSO的ICP算法在三維點云數(shù)據(jù)配準中的效率提升明顯，但配準準確率優(yōu)勢不大，主要應(yīng)用環(huán)境是大規(guī)模點云樣本的快速配準，特別適用于大型物體的點云數(shù)據(jù)匹配。

4 結(jié)語

本文中采用分層PSO的ICP算法進行三維點云數(shù)據(jù)配準，在合理設(shè)置粒子速度權(quán)重和粒子子群數(shù)量的前提下，能有效地提高點云配準效率，并提高配準的精度。通過對不同量級樣本的仿真可知，分層PSO的ICP算法配準性能更優(yōu)。后續(xù)研究將對分層粒子群進行差異化調(diào)參，進一步提高分層PSO的ICP算法在三維點云配準中的性能。