基于擬牛頓法改進(jìn)的3D正態(tài)分布變換點云配準(zhǔn)算法

王 鵬，李少達(dá)，趙 雪

(1.成都理工大學(xué) 地球科學(xué)學(xué)院，四川 成都 610059；2.西南交通大學(xué) 地球科學(xué)與環(huán)境工程學(xué)院，四川 成都 611756)

0 引 言

地面激光掃描技術(shù)以速度快，高精度獲取3維數(shù)據(jù)的特點，廣泛應(yīng)用于3D重建，滑坡監(jiān)測，文物保護(hù)，城市規(guī)劃等領(lǐng)域[1]。由于地面激光掃描儀需固定設(shè)站的缺陷，目標(biāo)物體的完整數(shù)據(jù)需要進(jìn)行不同角度的多次掃描才能獲取。因為每次掃描數(shù)據(jù)都是基于儀器默認(rèn)的局部坐標(biāo)系，因此需要將不同坐標(biāo)系下的掃描數(shù)據(jù)統(tǒng)一到同一坐標(biāo)系，即點云配準(zhǔn)。

3D正態(tài)分布算法（3D Normal Distribution Transform，3D-NDT）于2009年被首次提出[2-3]，并成功應(yīng)用在3D點云配準(zhǔn)中，而且相對于經(jīng)典的ICP[4]算法有更好的精度和收斂速度。但是3D-NDT仍然有需要較好的初始值，參數(shù)難以確定等問題。隨后，多層NDT（MLNDT）算法[5]被提出，并在一定程度上降低了參數(shù)難確定性的復(fù)雜性。同時針對3D-NDT算法需要較好初始值的問題，基于SIFT特征的3D-NDT點云自動配準(zhǔn)算法[6]，基于曲率特征的3D-NDT點云配準(zhǔn)算法[7]，結(jié)合NARF的3D-NDT自動配準(zhǔn)算法[8]被相繼提出。雖然與3D-NDT算法相比ICP[4]算法能夠快速高精度地進(jìn)行點云配準(zhǔn)，但是面對不斷增加的大量高密度點云數(shù)據(jù)，配準(zhǔn)效率仍然是一個難題[9]。因此，本文在已有研究的基礎(chǔ)上，針對3D-NDT算法在大型點云配準(zhǔn)中效率低的問題，提出基于擬牛頓法的3D-NDT算法。

1 擬牛頓法改進(jìn)的3D-NDT算法

1.1 3D-NDT算法原理

3D-NDT的目標(biāo)是找到當(dāng)前掃描點在參考掃描點云表面匹配的似然函數(shù)最大化時的姿態(tài)。3D-NDT算法首先將三維點云數(shù)據(jù)集均勻地劃分為規(guī)則立方體，每個立方體內(nèi)包含一定數(shù)量的點x={x1,x2,…,xn}。對于立方體中每一個點xi的概率密度函數(shù)可以表示為：

式中，x-和V分別表示立方體內(nèi)點云的均值和方差。

3D-NDT算法通過當(dāng)前掃描點云經(jīng)過初始坐標(biāo)轉(zhuǎn)換參數(shù)映射到參考掃描點云中的概率密度之和s(p)作為坐標(biāo)變換參數(shù)的分?jǐn)?shù)值進(jìn)行評價。因此兩視點云的最優(yōu)轉(zhuǎn)換參數(shù)求解過程，就轉(zhuǎn)換成了概率密度之和s(p)的最優(yōu)化問題。

式中，xi＇表示當(dāng)前掃描點映射到參考掃描表面的坐標(biāo)。T(p,xi)表示當(dāng)前掃描點的坐標(biāo)轉(zhuǎn)換。

1.2 擬牛頓法改進(jìn)

最優(yōu)化問題通常被看成最小化問題，因此，3D-NDT求解最優(yōu)參數(shù)的過程即s(p)最小化過程。3D-NDT是通過牛頓迭代法求解最優(yōu)參數(shù)，令?=s(p)為目標(biāo)函數(shù)，為使目標(biāo)函數(shù)最小需求解以下方程：

其中g(shù)為f的梯度，用一階導(dǎo)數(shù)表示，H為Hessian矩陣，用?的二階導(dǎo)數(shù)表示。

從式（3）可以看出，Hessian矩陣的求解需要計算目標(biāo)函數(shù)的二階導(dǎo)數(shù)。但是目標(biāo)函數(shù)的二階導(dǎo)數(shù)計算復(fù)雜，特別是隨著點云數(shù)量的增加，二階導(dǎo)數(shù)的計算需要消耗大量的時間。而擬牛頓法(Quasi-Newton Methods)作為求解非線性優(yōu)化問題最有效的方法之一[10]。他通過近似Hessian矩陣的方式代替通過二階導(dǎo)數(shù)求解Hessian的過程，能夠解決牛頓迭代法需要計算復(fù)雜二階導(dǎo)數(shù)的問題。因此，本文具體采用擬牛頓法中的DFP方法對3D正態(tài)分布變換算法進(jìn)行優(yōu)化。

DFP算法首先假設(shè)Heissian矩陣為單位陣I，計算搜索方向Δp=-Hkgk（Hk為Hessian矩陣，gk為梯度）。然后通過校正方程更新Hessian的值，不斷逼近Hessian的真實值，直到算法收斂。校正方程如下：

式中，sk=λkΔp，λk=argmin?(xk+λΔp)，yk=gk+1-gkgk+1，gk表示參數(shù)為xk+1，xk時，函數(shù)?對應(yīng)梯度值。

1.3 擬牛頓法改進(jìn)的3D-NDT算法步驟

針對3D-NDT算法中Hessian矩陣計算復(fù)雜，導(dǎo)致配準(zhǔn)效率降低的問題，提出擬牛頓法改進(jìn)的3D-NDT點云配準(zhǔn)算法。假設(shè)x為源點云，y為參考點云，將源點云x配準(zhǔn)到參考點云y的具體步驟如下：

①建立參考點云y的正態(tài)分布變換；

②根據(jù)轉(zhuǎn)換參數(shù) 將點云x中的點轉(zhuǎn)換到到點云y中，得到x＇；

③計算點云x＇中每一個點的正態(tài)變化分布；

④計算點云x＇中每一個點的概率之和s(p)。

⑤根據(jù)式（4）得到Hessian矩陣優(yōu)化s(p)，得到Δp；

⑥若算法達(dá)到收斂條件Δp＜ε則停止，否則更新轉(zhuǎn)換參數(shù)p=p+Δp繼續(xù)轉(zhuǎn)至步驟②如圖1所示。

圖1 算法流程圖Fig.1 Algorithm flowchart

2 實驗結(jié)果

在ubuntu16.04操作系統(tǒng)（內(nèi)存3G，處理器1核）上，采用C++語言結(jié)合點云數(shù)據(jù)庫（point cloud library，PCL）實現(xiàn)編程，為驗證本文算法的精度和效率，實驗數(shù)據(jù)采用PCL官方網(wǎng)站（www.pcl.org）提供的一組室內(nèi)采集的樣例數(shù)據(jù)（兩視點云cloud1、cloud2數(shù)據(jù)量分別為112,586,112,624），對本文算法與3D-NDT算法進(jìn)行對比測試，參數(shù)設(shè)置中最大迭代次數(shù)50，收斂條件為兩次迭代參數(shù)結(jié)果之差小于0.01，配準(zhǔn)精度采用均方根誤差（Root Mean Squared Error，RMSE）進(jìn)行對比。

在試驗中分別對點云cloud1進(jìn)行尺寸分別為0.1,0.2,0.3的三維體素格網(wǎng)采樣，得到3組不同數(shù)量的點云數(shù)據(jù)（見表1）。實驗結(jié)果見表2。通過擬牛頓法改進(jìn)的3D-NDT算法大大提高了算法的配準(zhǔn)效率，而且隨著點云數(shù)量的增加本文算法在配準(zhǔn)效率方面的優(yōu)勢更加明顯,。同時，本文算法的配準(zhǔn)精度與原算法基本保持不變。

表1 實驗數(shù)據(jù)Tab.1 Experimental data

表2 點云數(shù)據(jù)采樣配準(zhǔn)算法實驗結(jié)果對比Tab.2 Comparison of experimental results of sample point cloud registration algorithm

3 結(jié)束語

本文針對牛頓法Hessian矩陣計算復(fù)雜的特點，提出了基于擬牛頓法的3D正態(tài)分布變換算法，在精度保持不變的情況下，提高了3D正態(tài)分布算法進(jìn)行點云配準(zhǔn)的效率。但是，3D正態(tài)分布算法的參數(shù)如最大步長，格網(wǎng)大小很難快速確定最優(yōu)值，這些參數(shù)的快速確定將是下一步的研究方向。