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

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

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

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

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

1 ICP 算法

ICP算法在參考點(diǎn)云pi(i為粒子序號(hào))和目標(biāo)點(diǎn)云qi之間進(jìn)行最近點(diǎn)搜索，對(duì)N個(gè)點(diǎn)進(jìn)行連續(xù)的坐標(biāo)變換，以更接近于目標(biāo)點(diǎn)云位置。最近點(diǎn)搜索評(píng)價(jià)指標(biāo)為所有pi與qi的距離差的平均值f(R，T)[6]，即

(1)

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

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

(2)

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

為了對(duì)參考點(diǎn)云中所有點(diǎn)進(jìn)行距離評(píng)估，引入點(diǎn)云重心，參考點(diǎn)云和目標(biāo)點(diǎn)云計(jì)算公式分別為

(3)

(4)

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

(5)

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

配準(zhǔn)精度評(píng)價(jià)的一般方法為計(jì)算所有點(diǎn)云的距離的均方根誤差σ，計(jì)算公式為

(6)

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

2.1 PSO算法

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

(7)

(8)

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

2.2 分層PSO算法

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

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

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

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

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

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

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

(9)

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

2.3 分層PSO的三維點(diǎn)云特征提取

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

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

3 實(shí)例仿真

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

3.1 分層PSO算法的三維點(diǎn)云配準(zhǔn)性能

3.1.1 三維點(diǎn)云配準(zhǔn)可視化

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

圖4 長(zhǎng)方形木桌的源點(diǎn)云和目標(biāo)點(diǎn)云空間分布

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

圖5 長(zhǎng)方形木桌源點(diǎn)云的配準(zhǔn)結(jié)果

表1 長(zhǎng)方形木桌的配準(zhǔn)性能標(biāo)準(zhǔn)

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

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

表2 不同速度權(quán)重時(shí)的點(diǎn)云配準(zhǔn)性能

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

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

表3 不同子群數(shù)時(shí)的點(diǎn)云配準(zhǔn)性能

3.2 不同算法的點(diǎn)云配準(zhǔn)性能

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

表4 不同樣本的配準(zhǔn)誤差

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

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

表5 不同樣本的配準(zhǔn)時(shí)間

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

4 結(jié)語(yǔ)

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