一種基于PVDAC 描述子的RGB-D三維點云配準方法

白創，陳立 ，閆昱

（長沙理工大學 物理與電子科學學院，湖南 長沙 410114）

三維點云配準技術是工業制造中逆向工程、古文物修復以及醫學三維圖像構建、三維地圖構建勘測［1］等領域應用的關鍵技術，其目的是求解同一坐標下不同姿態三維點云的剛體變換矩陣，利用該矩陣實現多視角點云的精確配準，最終獲得完整的三維數字模型與場景.

Besl 和Mckay 在1992 年提出了經典的迭代最近點算法（Iterative Closest Point，ICP）［2］.該算法雖然具有簡單、收斂性好等優點，但其收斂速度和配準精度依賴于點云初始位置與算法迭代過程中的對應關系，因而算法計算量大且容易陷入局部最優［3-5］.為了解決這些問題，一般將三維點云的配準過程分為“粗”配準和“精”配準兩部分，首先通過粗配準算法對點云原始位姿進行粗調，得到良好的初始位置，然后利用ICP算法或其改進型算法［6-7］對點云位姿進行微調，完成三維點云的配準.其中粗配準是業界研究的重點，常用的方法是基于特征匹配的配準方法.Kumar等人［8］利用A-KAZE 進行特征檢測匹配，并利用二維下的良好匹配點對映射到三維空間中獲得3D 稀疏點來進行點云的配準.Ran和王鵬等人［9-10］分別通過SIFT 算子和幾何信息、光度信息進行特征檢測描述與匹配，來完成點云粗配準.趙明富等人［11］通過一種改進型的FPFH 算子實現了點云的粗配準.這些基于特征匹配原理實現點云粗配準的方法雖然都取得了較好的效果，但復雜的特征計算很難兼顧算法的效率，且僅利用了單一的二維特征或者三維特征，RGB-D 數據特征并沒有得到充分的利用.除了利用特征匹配的方法進行點云粗配準外，Ji 等人還提出了一種利用遺傳算法將點云轉換到3D 形狀附近的全局特征粗配準算法［12］，該方法在對單一模型進行粗配準時效果較好，但當場景較為復雜時便很難保證算法的準確性.

RGB-D 數據同時包含RGB 圖像數據和深度圖像數據，在此基礎上本文構建了一種二維特征和三維特征相結合的全新PVDAC（Pixel Value Distance Angle and Curvature，PVDAC）特征描述子，根據深度圖像數據生成的三維點云，利用PVDAC 特征描述子完成未知姿態下的點云粗配準并將粗配準后具有良好初始位置的點云通過ICP 算法進行精細化配準.相比現有方法，本文提出的算法不僅充分利用了RGB-D 數據特征，而且在保證點云配準精度的同時擁有更高效的算法效率.

1 算法原理

基于PVDAC 描述子的RGB-D 三維點云配準算法根據點云配準的“粗+精”策略分為兩部分完成.首先利用ORB 算子［13］對二維數據中的RGB 圖像進行關鍵點的提取，同時根據數據對齊的原理確定三維數據中的對應關鍵點，然后計算關鍵點的二維灰度特征、三維空間分布特征以及曲率特征，生成由多維特征聯合描述的PVDAC 描述子，并利用全新的描述子完成點云的粗配準.最后采用ICP 算法對點云之間的位姿進行微調完成點云之間的精細化配準，如圖1所示.

圖1 PVDAC描述子的點云配準算法原理Fig.1 Principle of point cloud registration algorithm of PVDAC descriptor

2 粗配準

2.1 關鍵點提取

對于大規模數據的點云配準，選取良好的特征點不僅能夠提高算法效率，還能提高配準的精度.為了保證數據的一致性和算法效率，首先，利用ORB算子對RGB 數據進行一定數量關鍵點的檢測與提取，得到初始的關鍵點點集和但原始關鍵點集中的部分關鍵點可能位于圖像的邊界處，不利于后續描述子的計算，因此，需要對原始關鍵點集中的關鍵點進行初步篩選.假設描述子計算模板大小為S×S(S=2n-1；n=1，2，…，n)，則邊界的定義為：

式中，x和y分別表示關鍵點的像素坐標，W和H則表示圖像的寬度和高度.若原始點集中的關鍵點超出計算邊界，則不計入描述子的計算得到新的關鍵點點集

2.2 特征描述子構建

2.2.1 二維灰度特征計算

PVDAC 描述子以BRIEF 算法［14］的思想為核心，構建關鍵點二維下基于灰度的特征.首先，以關鍵點為中心確定一個S×S大小的采樣區域，選取n對符合(0，S2/25)高斯分布的像素點ai、bi(i=1，2，…，n)，為了滿足算法的旋轉不變性，通過t灰度質心法計算關鍵點的主方向：

式中，I(x，y)為圖像灰度表達式，則質心可表示為Cm=(m10/m00，m01/m00).假設關鍵點的坐標為O，則通過公式（3）計算向量的角度θv，得到特征點的主方向.

以關鍵點的主方向建立新坐標系，將原始n對像素點變換到新坐標系下得到全新的像素點對.通過逐一比較新的像素點對灰度值的大小，得到關鍵點二維下基于灰度特征的描述.

2.2.2 三維鄰域平均距離特征計算

與二維下關鍵點的鄰域不同，三維下關鍵點與其鄰域點之間的平均距離反映了該點的局部空間分布特征.當該點與其鄰域點之間的平均距離較大時，表示該點的局部點云分布密度較大，反之則表示該點的局部點云分布密度較小.當局部點云分布較稀疏時通常會形成點云的平滑區域，而關鍵點在點云中無論采樣是否規則，只要在關鍵點的鄰域數相同，則鄰域點的個數是一致的.根據關鍵點在三維下的坐標，利用kd樹對關鍵點進行K鄰域搜索，如圖2 中右側圖所示.

圖2 關鍵點二維和三維下的8近鄰Fig.2 8-nearest neighbors of key points in 2D and 3D

假設關鍵點三維下K鄰域點的集合為G{gj}，j=1，…，K，(xk，yk，zk)為關鍵的三維坐標，那么關鍵點與其K鄰域點之間的平均距離可表示為：

以關鍵點的K鄰域平均歐氏距離為距離閾值Td，將鄰域點到關鍵點的歐式距離與Td進行逐一比較，得到關鍵點三維下基于鄰域平均距離特征的描述.

2.2.3 三維鄰域角度特征計算

表面法線作為幾何表面的重要屬性，其角度的變化反映出了點云表面的平坦程度或者光滑程度.點云采樣于物體的表面，物體表面的法線即為點云的法線，因此可以先對物體的表面進行幾何估計即可計算出點云法線.一般利用低階多項式擬合的方法對曲面進行擬合，如圖3（a）所示，但如果點云分布均勻，那么可以利用平面進行局部擬合加速計算，此時平面的法線即為點云法線，如圖3（b）所示.

圖3 法線計算的兩種方式Fig.3 Tow ways of normal calculation

采用主成分分析法（Principal Component Analy?sis，PCA）對關鍵點及其鄰域點的法線進行分析.由于曲面局部是平坦的，法線所在的方向是主成分最低的方向，也就是PCA 中最小特征值對應的特征方向.設關鍵點其K鄰域點構成的點集為Wi={w1，w2，…，wN}，N=1，2，…，K，首先通過公式（6）計算Wi中所有點的均值，

計算完均值后利用公式（7）和公式（8）進行樣本方差和協方差的計算.

通過公式（8）構建三維下的協方差矩陣Cov：

對協方差矩陣Cov 進行特征值分解得到特征值λ1，λ2，λ3.假設存在0 ≤λ1≤λ2≤λ3，那么λ1對應的特征方向即為該點的法線.

根據PCA 主成分分析法求解得到關鍵點及其K鄰域點的法線及其方向，假設關鍵點的鄰域點的法線為Ni={n1，n2，…，nK}，i=1，2，3，…，K，關鍵點的法線方向為nk，那么鄰域點于關鍵點之間的法線夾角之間的余弦可以表示為：

假設K=4，那么關鍵點與其鄰域點的法線和法線角度可由圖4表示.

圖4 關鍵點4鄰域法線和夾角Fig.4 Key point 4 neighborhood normal and included angle

通過反三角函數得到關鍵點法線與鄰域點法線之間的夾角θ(θ∈[0，π])，計算鄰域點與關鍵點之間的法線夾角的平均角度-θ，將平均角度-θ作為角度閾值Tθ.同理，將鄰域點和關鍵點之間的夾角與角度閾值逐一進行比較，得到鄰域法線角度對關鍵點的特征描述.

2.2.4 三維曲率特征計算

三維點云中，三維點曲率的變化則反映出三維點局部表面在空間中偏離平面的程度或者是三維表面局部凹凸程度的變化.為了對關鍵點進行基于曲率變化的局部特征描述，首先需要對關鍵點及其鄰域點進行曲率的求解.在法線角度計算的過程中，針對關鍵點及其鄰域點集Wi中的每一個點都進行了法線的求解，并根據PCA 主成分分析法構建了協方差矩陣，通過對協方差矩陣進行特征值分解得到了特征值λ1，λ2，λ3.設關鍵點的特征值為λk1，λk2，λk3，則關鍵點的表面曲率可由公式（11）近似表示.

同理，根據公式（11）對關鍵點的鄰域點集Wi中的每個點進行曲率的求解，得到關鍵點鄰域點曲率的集合Cvi={Cv1，Cv2，…，Cv i}，i=1，2，…，K.以關鍵點的曲率Ck為曲率閾值Tc，通過鄰域點的曲率與閾值Tc進行逐一比較得到關鍵點基于曲率特征的描述.

2.3 匹配與粗配準

根據基于特征匹配的點云配準算法思路，首先利用暴力匹配算法對關鍵點進行初步的匹配，假設兩幀圖像中經過PVDAC 描述子描述后的關鍵點集合分別為，其中i表示關鍵點的個數，從集合中的第一個關鍵點開始與集合中的每一個關鍵點進行描述子之間距離的計算，假設第一幀中第一個關鍵點的二進制描述子為1011101，第二幀中第一個關鍵點的二進制描述子為1001001，則描述子之間的距離為2.通過將集合中的所有點依次進行遍歷計算得到每一個點對應的距離集合，根據對距離集合進行排序將距離最近的兩個點最為正確地匹配點對.

接著，為了消除初始匹配點對中存在的錯誤匹配點對以保證算法的可靠性，本文利用RANSAC 算法對錯誤匹配點對進行濾除.最后將良好的匹配點對通過坐標系的轉換映射到三維下得到兩組三維點集PA和PB，通過奇異值分解的方法求解點集之間的變換矩陣R和T，并利用求解的變換矩陣對三維點云進行剛體變換完成三維點云的粗配準.

3 精配準

利用PVDAC 描述子完成三維點云的粗配準后，兩片三維點云在三維空間下的位置已經非常接近但還是存在一定的誤差.為了縮小誤差并進一步提高點云配準的精度，本文采用結構簡單高效的ICP 算法作為點云位姿微調的精配準算法.ICP 算法的核心在于優化點與點之間的空間歐式距離，如公式（12）所示：

式中：n為臨近點對的個數，pi為目標點云P中的一點，qi為源點云Q中與pi對應的最近點，R為旋轉矩陣，t為平移向量.

ICP算法的基本步驟為：

1）在目標點云P中選擇一些隨機點pi，i=1，2，3，…，n；

2）在目標點云Q中找到每個點pi的最近點qi；

3）剔除一些距離較遠的點對；

4）構建距離誤差函數E(R，t)；

5）極小化誤差函數，如果對應點距離小于給定閾值設置則算法結束，否則根據計算的變換矩陣更新點云繼續重復上述步驟.

通過ICP 算法的不斷迭代更新變換矩陣，最終求得最優的變換矩陣，并通過該變換矩陣完成對三維點云的配準.

4 算法測試與分析

實驗在一臺CPU 為Intel Core i5，3.4 GHz 頻率，8 G 運行內存的筆記本上進行算法測試，采用TUM數據和自采集數據對本文粗配準算法和整體算法進行測試評估.在粗配準測試中，分別從二維下的匹配精度、召回率以及三維下的粗配準得分進行算法的快速評估，在整體上以算法的運行時間和配準得分作為最終的測試評估標準.三維點云配準得分實際上是配準后對應點之間的距離的平方之和，如公 式（13）所示.相較于傳統的RMSE 均方根誤差，避免了因點云空間位置相差較大時配準錯誤的點被剔除，而得到較小虛假最小均方根誤差的問題.

式中：pi代表第一幀點云中的點，qi代表第二幀點云變換后與之對應的點.

4.1 粗配準測試

為了便于對比分析，文中將基于SIFT 算子、SURF 算子的粗配準方法與本文方法分別在TUM 數據和自采集數據上進行測試，首先對三種算法在二維下的匹配結果進行對比分析，結果如表1所示.

表1 二維匹配結果對比Tab.1 Comparison of matching result in 2D

由表1 可知，在保證原始特征點個數和原始匹配個數一致的情況下，三種算法在特征提取及描述環節SIFT算法最為耗時，而PVDAC 算法在耗時上與SIFT 和SURF 算法相比平均提高了60.8%和36.3%，在匹配精度上，與SIFT、SURF算法相比，本文算法平均提高了34.3%和34.1%，在匹配的召回率上平均提高了2.6%和3.1%.雖然在召回率上本文算法并沒有得到很大的提高，但在匹配的速度上體現出了較大的優勢.

接著將二維下良好的匹配點對映射到三維下進行點云初始位姿剛體變換矩陣進行求解，并利用初始剛體變換矩陣對點云進行變換得到三維點云粗配準結果，配準效果如圖5和圖6所示.

由圖5 可知，TUM 數據通過三種算法粗配準后兩片點云的矩形框區域的公共點云基本上已經完全重疊.在對自采集數據進行粗配準后，可以看出利用SIFT 算法進行粗配準的方法明顯要差于利用SURF算法和PVDAC 算法的粗配準算法，在圖6 中SURFCoarse 和PVDAC-Coarse 的非矩形框區域點云基本上都已經重疊，但矩形框區域的公共點云還沒有完全重疊，為了對粗配準前后的誤差進行評估，分別將三種算法的配準誤差與原始誤差進行了計算對比，結果如表2所示.

圖5 TUM數據粗配準結果Fig.5 Coarse registration result of TUM data

圖6 自采集數據粗配準結果Fig.6 Coarse registration result of self-collected data

根據表2 中的粗配準得分可知，在對兩種數據進行粗配準時，基于PVDAC 描述子的配準方法在粗配準精度上比基于SIFT、SURF 粗配準的精度高，較小的配準得分將更有利于點云的精細化配準.

表2 不同粗配準算法比較Tab.2 Comparison of different coarse registration algorithms

4.2 整體算法測試

為了對整體的配準算法進行評估，將基于SIFT算子、SURF 算子以及本文PVDAC 描述子的粗配準算法與ICP 算法結合構成完整的三維點云配準算法，并與傳統的ICP 算法進行測試對比，最終的配準效果如圖7和圖8所示.

圖7 TUM數據配準結果Fig.7 Registration result of TUM data

圖8 自采集數據配準結果Fig.8 Registration result of self-collected data

由圖7和圖8的配準結果可知，兩種數據在僅利用ICP 算法進行配準時，點云的公共部分并沒有很好的重疊，出現了明顯的錯位情況，配準效果較差.而其他的三種算法都很好地實現了點云的配準.同理，根據粗配準環節的評估方法對整體配準算法進行了對比，結果如表3所示.

由表3 可知，基于SIFT 算子的配準算法在算法耗時上表現最差，在對自采集數據進行配準時算法耗時甚至超過了ICP 算法.而文中提出的PVDAC 算法在幾種算法中耗時最短，且最終的配準結果點云基本上完全重合.與傳統的ICP 算法相比，本文提出的算法在算法速度和配準精度上平均提高了50.2%和36.6%，實現了點云的快速精確配準.

表3 不同配準算法比較Tab.3 Comparison of different registration algorithms

5 結論

本文提出了一種二維特征和三維特征聯合描述的像素描述子用于三維點云的配準.該方法在三維點云位姿未知的情況下，通過全新的描述子實現點云位姿的初始粗估計，為點云的精細化配準提供了良好的初始值.實驗結果表明，本文提出的算法穩定，效率較高，提供的良好初始值加快了三維點云配準的過程.同時，本文提出的算法也存在一定的局限性，在針對單一物體三維重建時的多視角多幀點云配準時，背景的干擾會導致點云粗配準的效果變差，接下來的工作可以考慮如何在特定場景下消除背景干擾的影響，從而實現特定場景下多幀點云的良好配準.