基于B-SHOT特征和3D-NDT的點(diǎn)云自動(dòng)配準(zhǔn)

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

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

地面激光點(diǎn)云技術(shù)作為目前空間地理信息獲取的重要手段，廣泛用于三維重建[1]、文物保護(hù)[2]等領(lǐng)域。地面激光掃描儀由于其視角限制，需要多角度掃描才能獲取完整的目標(biāo)物體點(diǎn)云，并且不同角度掃描數(shù)據(jù)位于掃描儀局部坐標(biāo)系下，需要通過點(diǎn)云配準(zhǔn)算法將多站不同坐標(biāo)系下的掃描數(shù)據(jù)進(jìn)行坐標(biāo)系統(tǒng)一。2009年，Magnusson[3-4]提出了3D-NDT算法，在精度和效率上都優(yōu)于經(jīng)典的ICP算法[5]，但和ICP一樣需要初始值。因此，國內(nèi)學(xué)者提出了基于2D特征點(diǎn)[6]、3D特征點(diǎn)[7]、2D特征點(diǎn)和3D特征點(diǎn)結(jié)合[8]的粗配準(zhǔn)算法對(duì)3D-NDT算法進(jìn)行改進(jìn)。2014年，Salti等[9]提出了SHOT（signatures of histograms of orientations）3 D特征描述子，速度和精度都優(yōu)于FPFH[10]、3D-SURF[11]等3D特征描述子。2015年，Prakhya等[12]對(duì)SHOT 3D特征描述子進(jìn)行改進(jìn)，提出了二進(jìn)制SHOT(binary signatures of histograms of orientations,b-SHOT)的3D特征描述子，提高了SHOT特征描述子的速度和精度。本文主要研究利用B-SHOT特征描述子進(jìn)行點(diǎn)云粗配準(zhǔn)并結(jié)合3D-NDT實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的自動(dòng)配準(zhǔn)。

1 B-SHOT特征描述子

B-SHOT特征描述子與SHOT特征描述子的區(qū)別在于，B-SHOT通過迭代的方式將SHOT的特征描述子由十進(jìn)制編碼為二進(jìn)制。利用雙向漢明距離搜索兩視點(diǎn)云之間的同名點(diǎn)，提高了配準(zhǔn)的效率和精度。

B-SHOT特征描述子通過結(jié)合符號(hào)（signatures）和直方圖（histograms）進(jìn)行特征描述，主要包括建立唯一局部參考框架、子空間直方圖統(tǒng)計(jì)、二進(jìn)制編碼等3個(gè)步驟。

為了使特征描述子對(duì)旋轉(zhuǎn)、平移和尺度保持不變，采用修改后的鄰域協(xié)方差矩陣C的特征向量創(chuàng)建局部參考框架，如式（1）：

式中，r表示支持區(qū)域半么，di=||qi-q||表示支持區(qū)域r中的采樣點(diǎn)qi與參考點(diǎn)q的距離。

將局部x和z軸的方向朝向它們所代表的向量的多數(shù)方向，通過z和x的叉積，即y=z×x獲得局部y軸，這樣便可以得到唯一的局部參考框架。

圖1 球形柵格示意圖[12]

確定了局部參考框架以后，將參考點(diǎn)的所有鄰域點(diǎn)變換到局部參考框架下，以保證后面計(jì)算的直方圖對(duì)剛體變換的魯棒性。然后利用球體柵格方法將局部參考空間按照距離、俯仰和方位分成32個(gè)子空間（如圖1）。通過建立每個(gè)子空間的局部直方圖得到每個(gè)子空間的子特征，然后將每個(gè)子特征連起來就得到了SHOT特征描述子。最后通過迭代方式對(duì)SHOT特征描述子進(jìn)行二進(jìn)制編碼得到B-SHOT特征描述子。

2 3D-NDT算法原理

3D正態(tài)分布變換算法的目標(biāo)是找到目標(biāo)點(diǎn)集在參考點(diǎn)集表面匹配的似然函數(shù)最大化時(shí)的姿態(tài)。3D-NDT算法首先將三維點(diǎn)集均勻地劃分為規(guī)則立方體，每個(gè)立方體內(nèi)包含一定數(shù)量的點(diǎn)。對(duì)于立方體中每一個(gè)點(diǎn)xi的概率密度函數(shù)可以表示為：

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

3D-NDT算法通過目標(biāo)點(diǎn)集經(jīng)過初始坐標(biāo)轉(zhuǎn)換參數(shù)映射到參考點(diǎn)集中的概率密度之和s(p)作為坐標(biāo)變換參數(shù)的分?jǐn)?shù)值進(jìn)行評(píng)價(jià)，通過對(duì)s(p)進(jìn)行最優(yōu)化估計(jì)，便可以得到2個(gè)點(diǎn)集對(duì)于坐標(biāo)系的轉(zhuǎn)換參數(shù)：

式中，x'i表示當(dāng)前掃描點(diǎn)映射到參考點(diǎn)集的坐標(biāo)；T(p,xi)表示當(dāng)前點(diǎn)集的坐標(biāo)轉(zhuǎn)換矩陣。為了得到兩個(gè)點(diǎn)集之間的轉(zhuǎn)換矩陣，可以把最優(yōu)化問題看成最小化問題，即s(p)最小化。通過牛頓迭代法結(jié)合Hessian矩陣進(jìn)行目標(biāo)函數(shù)求取最小值。令s(p)為0，為了使目標(biāo)函數(shù)最小，需求解以下方程：

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

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

實(shí)驗(yàn)在ubuntu16.04系統(tǒng)（內(nèi)存4G）下進(jìn)行，算法通過C++語言并結(jié)合點(diǎn)云數(shù)據(jù)庫PCL編碼實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)采用斯坦福的bunny數(shù)據(jù)，如圖2a所示。為驗(yàn)證本文算法的可行性，首先對(duì)兩視點(diǎn)云分別計(jì)算B-SHOT特征描述子，然后利用雙向漢明距離（Hamming distance）計(jì)算兩視點(diǎn)云的同名點(diǎn)集，最后通過隨機(jī)采用一致性算法（random sample consensus,RANSAC）進(jìn)行初始參數(shù)估計(jì)，再利用3D-NDT進(jìn)行精確配準(zhǔn)，實(shí)驗(yàn)結(jié)果如圖2（c）。同時(shí)，與基于FPFH特征描述子的3D-NDT算法對(duì)比，結(jié)果如表1。為了提高配準(zhǔn)的效率，原始數(shù)據(jù)進(jìn)行體素柵格采樣（柵格大小為0.001）。

圖2點(diǎn)云配準(zhǔn)過程示意圖

圖2b和2c分別為基于B-SHOT特征描述子的粗配準(zhǔn)結(jié)果和3D-NDT的精配準(zhǔn)結(jié)果。實(shí)驗(yàn)證明了B-SHOT結(jié)合3D-NDT進(jìn)行點(diǎn)云自動(dòng)配準(zhǔn)的可行性。兩種粗配準(zhǔn)實(shí)驗(yàn)對(duì)比結(jié)果如表1所示。在粗配準(zhǔn)中，基于B-SHOT特征描述子的粗配準(zhǔn)時(shí)間少于基于FPFH特征描述子的粗配準(zhǔn)，使用3D-NDT進(jìn)行精配準(zhǔn)的時(shí)間基本不變。最后基于B-SHOT特征描述子的粗配準(zhǔn)使得3D-NDT的精度高于基于FPFH特征描述子的粗配準(zhǔn)，也間接證明了3D-NDT算法需要好的初始值才能表現(xiàn)出好的配準(zhǔn)精度。

表1 點(diǎn)云自動(dòng)配準(zhǔn)實(shí)驗(yàn)結(jié)果

4 結(jié) 語

本文針對(duì)3D-NDT點(diǎn)云配準(zhǔn)算法需要初始值的問題，提出了結(jié)合B-SHOT特征描述子與3D-NDT的點(diǎn)云自動(dòng)配準(zhǔn)算法，不需要提供初始值便能完成相鄰兩個(gè)點(diǎn)云之間的高精度配準(zhǔn)。通過實(shí)驗(yàn)對(duì)比，本文算法有效可行，且在精度和效率上均優(yōu)于目前最優(yōu)秀的FPFH特征配準(zhǔn)算法。但是3D-NDT算法還有許多需要改進(jìn)的地方，在三維網(wǎng)格大小等參數(shù)確定過程中很難快速確定最佳參數(shù)，降低了整個(gè)實(shí)驗(yàn)過程的效率，常研究如何快速自適應(yīng)地確定網(wǎng)格大小等參數(shù)。這也將是下一步的研究方向。