基于SAC-IA和NDT融合的點云配準(zhǔn)方法

荊 路 武 斌 李先帥

1 天津城建大學(xué)計算機(jī)與信息工程學(xué)院,天津市津靜路26號,300384

Besl等[1]提出的迭代最近點 (iterative closest point,ICP)算法是目前最經(jīng)典的點云精配準(zhǔn)算法,但此算法對點云初始位置要求高，否則容易陷入局部最優(yōu)，且存在收斂速度較慢的問題[2]。許多學(xué)者對該算法進(jìn)行了改進(jìn)和創(chuàng)新，提出了一些新的算法[3-4]。Rusu等[5]提出一種依據(jù)點云的快速點特征直方圖(fast point feature histogram,FPFH)特征，并使用采樣一致性初始配準(zhǔn)(sample consensus intial alignment, SAC-IA)的方法，該方法雖然顯著提高了配準(zhǔn)精度，但降低了配準(zhǔn)效率，常用來進(jìn)行初始配準(zhǔn)。正態(tài)分布變換(normal distribution transformation,NDT)算法[6]不依據(jù)對應(yīng)點的特征進(jìn)行匹配，而是通過最優(yōu)化技術(shù)確定點云之間的最佳匹配。與ICP算法相比，NDT算法在配準(zhǔn)海量點云數(shù)據(jù)時速度較快、精度較高[7]，但仍需要較好的初始位置，因此需要對點云進(jìn)行初始配準(zhǔn)，以提高配準(zhǔn)的精度和效率。

基于以上研究，本文提出一種融合SAC-IA和NDT的點云配準(zhǔn)方法，并通過實驗對該方法的配準(zhǔn)精度和效率進(jìn)行驗證。

1 點云配準(zhǔn)流程

本文提出的點云配準(zhǔn)方法流程見圖1。首先計算待配準(zhǔn)點云和目標(biāo)點云的FPFH特征，并依據(jù)二者相似的FPFH特征，利用SAC-IA算法求出變換矩陣，從而完成初始配準(zhǔn)；在此基礎(chǔ)上，對點云進(jìn)行體素化處理，求得點云的均值向量和協(xié)方差矩陣，并求出點云的概率密度函數(shù)；接著將點云的最優(yōu)轉(zhuǎn)換參數(shù)用各個映射點的概率分布之和來代替；然后利用Hessian矩陣法求出點云概率分布函數(shù)的最小值，進(jìn)而得到最優(yōu)變換矩陣；最后判斷是否滿足終止條件，完成點云的精配準(zhǔn)。

圖1 點云配準(zhǔn)流程Fig.1 Process of point cloud registration

2 基于采樣一致性的初始配準(zhǔn)

2.1 點云FPFH特征描述

FPFH算法基于局部特征描述，是通過對點特征直方圖(point feature histograms,PFH)[8]改進(jìn)得到的。PFH將查詢點與鄰域點之間的空間差異進(jìn)行參數(shù)化處理，形成一個對點的k鄰域幾何屬性進(jìn)行描述的多維直方圖。關(guān)于PFH的詳細(xì)介紹可參考文獻(xiàn)[8]。與PFH相比，F(xiàn)PFH由于沒有計算全互聯(lián)Mq的所有鄰近點，因而降低了算法的計算量，把復(fù)雜度由O(k2)降低到O(k)，F(xiàn)PFH的計算原理見圖2。

圖2 FPFH計算原理Fig.2 Calculation principle of FPFH

計算FPFH特征描述子的步驟如下。

1)計算出每個待計算點Mq與其所有鄰域點之間的相對關(guān)系，從而建立簡化的點特征直方圖(simplified point feature histogram,SPFH)，并記為S(Mq)。

2)根據(jù)步驟1)計算得到的k個鄰域點的SPFH特征計算FPFH特征，記為F(Mq)，表示為：

(1)

2.2 SAC-IA算法

針對經(jīng)典ICP算法配準(zhǔn)易陷入局部最優(yōu)的問題，本文在初始配準(zhǔn)階段使用SAC-IA算法,其算法步驟如下。

1)對采樣點進(jìn)行選取。在待配準(zhǔn)點云M中選取n個采樣點，并且要滿足采樣點兩兩之間的距離大于預(yù)先設(shè)定的最小距離閾值d,用以保證各采樣點的FPFH特征均不相同。

2)對采樣點的對應(yīng)點進(jìn)行查找。依據(jù)采樣點的FPFH特征，在目標(biāo)點云N中通過近鄰搜索找到與采樣點中每個點FPFH相差最小的點，即為特征相似的點，將其作為目標(biāo)點云N中與待配準(zhǔn)點云M中的采樣點相對應(yīng)的點，并通過RANSAC算法剔除錯誤的對應(yīng)點對，從而保證相似特征點對的正確匹配。

(2)

式中，ml為預(yù)先設(shè)定的值，li為第i組對應(yīng)點經(jīng)過變換之后的距離差。最后為了使誤差函數(shù)取得最小值，需要從所有的變換中找出一組最優(yōu)的變換，從而進(jìn)行初始配準(zhǔn)。

3 基于NDT的精配準(zhǔn)

SAC-IA初始配準(zhǔn)讓待配準(zhǔn)的兩片點云位置盡可能地靠近，縮小點云之間的旋轉(zhuǎn)和平移誤差，使得源點云和目標(biāo)點云具有較好的初始位置。為了進(jìn)一步縮小偏差，在初始配準(zhǔn)的基礎(chǔ)上進(jìn)行NDT配準(zhǔn)以提高配準(zhǔn)的精度，從而使精配準(zhǔn)后的結(jié)果達(dá)到預(yù)設(shè)的約束條件。NDT是把三維點云分成大小均勻的立方體，并把立方體中的點云數(shù)據(jù)轉(zhuǎn)換成概率密度函數(shù)，然后依據(jù)矩陣法求出轉(zhuǎn)換關(guān)系。相對于ICP算法，該方法不需要每次迭代都重新匹配對應(yīng)點對，因此配準(zhǔn)效率較高。其算法步驟如下。

1)把點云模型劃分為均勻大小的立方體。

2)求出各個立方體中點的均值向量q和協(xié)方差矩陣C：

(3)

(4)

式中，n為立方體中點的總數(shù)，xk為立方體中的一點。

3)對點xk進(jìn)行正態(tài)分布建模N(q,C)，其中xk的概率密度函數(shù)表示為：

(5)

4)根據(jù)變換矩陣T對待配準(zhǔn)點云的每個點進(jìn)行變換，然后依據(jù)變換后的點T(xi)所在的立方體的概率密度分布函數(shù)計算相應(yīng)的概率分布函數(shù)。

5)把各個待配準(zhǔn)點的相應(yīng)概率分布相乘，并將相乘的結(jié)果作為變換矩陣T的分?jǐn)?shù)值s(p)：

(6)

6)依據(jù)Hessian矩陣法計算s(p)的最優(yōu)解，從而得出最佳變換矩陣。

4 實驗結(jié)果與分析

本文實驗的硬件環(huán)境為Inter(R) Core(TM) i7-8750H CPU @2.20 Hz處理器，8.00 GB內(nèi)存；系統(tǒng)環(huán)境為64位Win10操作系統(tǒng)；軟件環(huán)境為Visual Studio2013、開源點云庫PCL1.8.0。實驗使用的點云模型為斯坦福大學(xué)點云庫的bunny和horse。為了進(jìn)一步分析該方法的普適性，用采集的點云椅子進(jìn)行驗證。如圖3所示為初始點云可視化結(jié)果，其中綠色點云為源點云，紅色點云為目標(biāo)點云。為了證明本文方法的有效性，分別使用經(jīng)典ICP算法、文獻(xiàn)[3]方法和本文方法對點云模型bunny、horse以及椅子進(jìn)行配準(zhǔn)實驗，并對3者結(jié)果進(jìn)行對比分析。

圖3 初始點云可視化Fig.3 Visualization of the initial point cloud

4.1 實驗結(jié)果

圖4～6分別為經(jīng)典ICP算法、文獻(xiàn)[3]方法和本文方法的點云bunny、horse和椅子的配準(zhǔn)結(jié)果，圖7為點云bunny、horse和椅子使用本文方法配準(zhǔn)時得到的剛體變換結(jié)果。

圖4 Bunny配準(zhǔn)結(jié)果Fig.4 Registration results of bunny

圖5 Horse配準(zhǔn)結(jié)果Fig.5 Registration results of horse

圖6 椅子配準(zhǔn)結(jié)果Fig.6 Registration results of chair

圖7 剛體變換結(jié)果Fig.7 Results of rigid transformation

4.2 結(jié)果分析

通過上述配準(zhǔn)結(jié)果可以看出，使用ICP算法配準(zhǔn)時，點云模型bunny和horse的頭部、尾部、腳掌及耳朵等多處部位出現(xiàn)明顯的配準(zhǔn)偏差。對比直接使用ICP算法，本文方法在使用采樣一致性算法初始配準(zhǔn)的基礎(chǔ)上使用正態(tài)分布變換進(jìn)行精配準(zhǔn)，可以大幅提高配準(zhǔn)的質(zhì)量，點云模型多處部位的配準(zhǔn)結(jié)果得到有效改善。對于點云椅子而言，使用本文方法得到的配準(zhǔn)效果也明顯優(yōu)于ICP算法。同時，與文獻(xiàn)[3]方法相比，本文方法的配準(zhǔn)結(jié)果更好。

本文實驗以歐氏適合度評分作為配準(zhǔn)誤差評判指標(biāo)。歐氏適合度評分表示輸出點云到最近目標(biāo)點云對應(yīng)點對的距離平方和，距離平方和越小，說明重合度越好、配準(zhǔn)精度越高。同時，比較配準(zhǔn)所用的時間，以衡量配準(zhǔn)的效率。表1為配準(zhǔn)用時和配準(zhǔn)誤差的統(tǒng)計結(jié)果。

由表1可見，對于點云bunny、horse和椅子，本文方法的配準(zhǔn)誤差分別是ICP算法的18.9%、18.4%和18.8%，同時配準(zhǔn)效率也有一定的提高。與文獻(xiàn)[3]方法相比，雖然本文方法需要消耗更長的時間，但配準(zhǔn)精度更高，取得了更好的配準(zhǔn)效果。

表1 配準(zhǔn)結(jié)果比較

5 結(jié) 語

針對兩片點云初始位置差距較大時使用ICP算法配準(zhǔn)易陷入局部最優(yōu)的問題，本文提出一種基于SAC-IA和NDT融合的點云配準(zhǔn)方法。該方法首先提取點云的FPFH特征，依據(jù)FPFH特征和SAC-IA算法對點云進(jìn)行初始配準(zhǔn)，然后在此基礎(chǔ)上使用NDT算法進(jìn)行精配準(zhǔn)。通過與ICP算法的對比實驗表明，該方法的配準(zhǔn)精度有顯著提高，同時效率也有一定的提升。由于在三維重建過程中點云數(shù)據(jù)配準(zhǔn)是十分關(guān)鍵的一步，配準(zhǔn)的成功與否會對后續(xù)的重建結(jié)果造成直接影響，因此，本文的配準(zhǔn)方法可為后期點云模型重建提供參考。但需要注意的是，初始配準(zhǔn)時計算點云FPFH特征仍需消耗一定的時間，這是該方法日后需要優(yōu)化的地方；同時，該方法中NDT配準(zhǔn)時參數(shù)的閾值設(shè)置還需進(jìn)一步優(yōu)化。