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

白創(chuàng)，陳立 ，閆昱

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

三維點云配準(zhǔn)技術(shù)是工業(yè)制造中逆向工程、古文物修復(fù)以及醫(yī)學(xué)三維圖像構(gòu)建、三維地圖構(gòu)建勘測［1］等領(lǐng)域應(yīng)用的關(guān)鍵技術(shù)，其目的是求解同一坐標(biāo)下不同姿態(tài)三維點云的剛體變換矩陣，利用該矩陣實現(xiàn)多視角點云的精確配準(zhǔn)，最終獲得完整的三維數(shù)字模型與場景.

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

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

1 算法原理

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

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

2 粗配準(zhǔn)

2.1 關(guān)鍵點提取

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

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

2.2 特征描述子構(gòu)建

2.2.1 二維灰度特征計算

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

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

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

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

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

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

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

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

2.2.3 三維鄰域角度特征計算

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

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

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

計算完均值后利用公式（7）和公式（8）進(jìn)行樣本方差和協(xié)方差的計算.

通過公式（8）構(gòu)建三維下的協(xié)方差矩陣Cov：

對協(xié)方差矩陣Cov 進(jìn)行特征值分解得到特征值λ1，λ2，λ3.假設(shè)存在0 ≤λ1≤λ2≤λ3，那么λ1對應(yīng)的特征方向即為該點的法線.

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

假設(shè)K=4，那么關(guān)鍵點與其鄰域點的法線和法線角度可由圖4表示.

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

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

2.2.4 三維曲率特征計算

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

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

2.3 匹配與粗配準(zhǔn)

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

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

3 精配準(zhǔn)

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

式中：n為臨近點對的個數(shù)，pi為目標(biāo)點云P中的一點，qi為源點云Q中與pi對應(yīng)的最近點，R為旋轉(zhuǎn)矩陣，t為平移向量.

ICP算法的基本步驟為：

1）在目標(biāo)點云P中選擇一些隨機(jī)點pi，i=1，2，3，…，n；

2）在目標(biāo)點云Q中找到每個點pi的最近點qi；

3）剔除一些距離較遠(yuǎn)的點對；

4）構(gòu)建距離誤差函數(shù)E(R，t)；

5）極小化誤差函數(shù)，如果對應(yīng)點距離小于給定閾值設(shè)置則算法結(jié)束，否則根據(jù)計算的變換矩陣更新點云繼續(xù)重復(fù)上述步驟.

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

4 算法測試與分析

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

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

4.1 粗配準(zhǔn)測試

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

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

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

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

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

圖5 TUM數(shù)據(jù)粗配準(zhǔn)結(jié)果Fig.5 Coarse registration result of TUM data

圖6 自采集數(shù)據(jù)粗配準(zhǔn)結(jié)果Fig.6 Coarse registration result of self-collected data

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

表2 不同粗配準(zhǔn)算法比較Tab.2 Comparison of different coarse registration algorithms

4.2 整體算法測試

為了對整體的配準(zhǔn)算法進(jìn)行評估，將基于SIFT算子、SURF 算子以及本文PVDAC 描述子的粗配準(zhǔn)算法與ICP 算法結(jié)合構(gòu)成完整的三維點云配準(zhǔn)算法，并與傳統(tǒng)的ICP 算法進(jìn)行測試對比，最終的配準(zhǔn)效果如圖7和圖8所示.

圖7 TUM數(shù)據(jù)配準(zhǔn)結(jié)果Fig.7 Registration result of TUM data

圖8 自采集數(shù)據(jù)配準(zhǔn)結(jié)果Fig.8 Registration result of self-collected data

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

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

表3 不同配準(zhǔn)算法比較Tab.3 Comparison of different registration algorithms

5 結(jié)論

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