基于B-SHOT特征和3D-NDT的點云自動配準

王 鵬，李少達，趙 雪

（1.成都理工大學，成都 610059；2.西南交通大學地球科學與環境工程學院，成都 611756）

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

1 B-SHOT特征描述子

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

B-SHOT特征描述子通過結合符號（signatures）和直方圖（histograms）進行特征描述，主要包括建立唯一局部參考框架、子空間直方圖統計、二進制編碼等3個步驟。

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

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

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

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

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

2 3D-NDT算法原理

3D正態分布變換算法的目標是找到目標點集在參考點集表面匹配的似然函數最大化時的姿態。3D-NDT算法首先將三維點集均勻地劃分為規則立方體，每個立方體內包含一定數量的點。對于立方體中每一個點xi的概率密度函數可以表示為：

式中，x和V分別表示單個立方體內點云的均值和方差。

3D-NDT算法通過目標點集經過初始坐標轉換參數映射到參考點集中的概率密度之和s(p)作為坐標變換參數的分數值進行評價，通過對s(p)進行最優化估計，便可以得到2個點集對于坐標系的轉換參數：

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

其中g為f的梯度，用一階導數表示；H為Hessian矩陣，用f的二階導數表示。

3 實驗與分析

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

圖2點云配準過程示意圖

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

表1 點云自動配準實驗結果

4 結 語

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