點鄰域尺度差異描述的點云配準算法*

陸 軍，陳 坤，范哲君

(1. 哈爾濱工程大學 自動化學院， 黑龍江 哈爾濱 150001；2. 哈爾濱工程大學 船海裝備智能化技術與應用教育部重點實驗室， 黑龍江 哈爾濱 150001)

隨著Kinect、3D激光雷達和地面激光掃描儀等新型傳感技術的發展，點云數據的獲取越來越高效。三維點云數據處理技術也得以快速發展，并且在計算機圖形學、CAD造型設計、文物古跡保護、汽車制造業等眾多領域都有廣泛應用。在點云獲取時，點云采集設備因為廣角不夠，物體太大等問題，有時不能一次完整的得到整個點云數據，需要分多次采集點云，采集的點云之間有位移角度偏移，想要完整的點云就需要點云配準。3D點云配準是后續工作的基礎和前提，是點云處理技術的一個重要組成部分。如何使點云配準方法更加快速準確已成為點云研究的熱點和難點之一。

在點云配準的眾多方法中，最經典且最常用的是迭代最近點算法[1]。迭代最近點(Iterative Closest Point, ICP)配準算法的核心方法是最小二乘法，由于它的強大功能和高精確度，得到了廣泛的應用。但是，ICP算法也存在一些缺點：要求待配準的點云重疊面積大，容易得到局部最優的結果，初始位置偏差不能太大。為了更有效地進行點云配準，一些其他方法被提出，其中應用比較廣泛的是基于特征描述符的點云配準方法。此類算法可以在不知道初始條件的情況下快速估算出一個轉換平移矩陣。Zhong[2]通過建立局部參考坐標系和各點三維柱狀圖的方法，設計了固有形狀特征來描述點特征信息，但點分布不均及測量噪聲會對配準結果產生影響。Rusu等[3]提出了一種點特征直方圖(Point Feature Histogram, PFH)算法和一種快速點特征直方圖(Fast Point Feature Histogram, FPFH)[4-5]算法作為局部特征描述符。PFH和FPFH根據從相鄰點集獲取的特征信息為每個點生成特征直方圖。局部二進制模式(Local Binary Patterns, LBP)[6]和方向特征直方圖(Signature of Histograms of OrienTations, SHOT)[7-8]也是常見的特征描述方法，但LBP算子特征信息的描述過于單一，SHOT算子緯度高、計算復雜。Jiao等[9]提出結合尺度不變特征變換(Scale Invariant Feature Transform， SIFT)和ICP的點云配準算法，提高了配準精度。王暢等[10]提出了一種基于點云結構特征的快速配準算法，用以解決數據點缺失、點云散亂時的配準問題。Li等[11]提出了從全景圖像和點云語義特征提取的自動配準方法。Lin等[12]提出結合固有形狀特征(Intrinsic Shape Signature， ISS)算法的特征提取方法，提取的特征具有尺度不變性。

為了減少特征描述的計算量,本文提出一種點鄰域尺度差異描述的配準算法。該算法利用擬合曲面的形狀指數隨曲面形狀變化的特性，選取局部擬合曲面變化大的點為關鍵點，提取的關鍵點在點云中具有一定的代表性。通過對關鍵點選取不同的鄰域空間提取特征信息，將這些特征信息組合成特征描述符，稱為點鄰域尺度差異描述符。該描述符具有計算簡單、辨識能力強的優點。最后通過對應點對二重篩選和全局最優查找，有效地篩除了錯誤的對應點對，提高了點云配準的效果。

1 點鄰域特征差異描述配準算法

本文提出了一種點鄰域尺度差異描述的點云配準算法。主要有以下幾個步驟：基于形狀指數的關鍵點選取方法、點鄰域尺度差異描述符的建立、對應點對二重篩選及最終變換矩陣的確定。

1.1 基于形狀指數的關鍵點選取

1.1.1 曲率計算

曲率是描述曲面的彎曲程度的概念，是曲面的一個基本屬性。點云是大量離散點的幾何，描述真實物體的表面輪廓。在點云處理過程中，曲率同樣是描述點云幾何特性的一個重要屬性。通常情況下，點云中的每個點和其鄰近的點都可以擬合成一個局部的曲面，用局部曲面曲率作為點云中該點的曲率。本文使用最小二乘法進行曲面擬合[13]，得到離散點鄰域的局部曲面參數方程z=r(u,v)。通過得到的離散點所擬合的曲面，可以計算出高斯曲率K和平均曲率H。計算公式可見式(1)和式(2)。其中，E、F、G和L、M、N分別為二次參數曲面的第一類基本量和第二類基本量。

(1)

(2)

由上式可以計算得到曲面的最大主曲率k1和最小主曲率k2：

(3)

(4)

其中：E=ru·ru；F=ru×rv；G=rv×rv；L=ruu·n；N=rvv·n；M=ruv·n；ru、rv、ruu、rvv、ruv為擬合曲面的偏微分；n是曲面的單位法向量。

1.1.2 關鍵點選取方法

Dorain和Jain[14]提出了一個能夠定量描述曲面的形變狀態的量，稱之為形狀指數。形狀指數的定義如式(5)所示。

(5)

式中：p為曲面上的一點；k1和k2分別表示包含點p的曲面的最大和最小主曲率。

由式(5)中的定義可以看出，形狀指數S的取值范圍為[0,1]，可以將曲面特征用0到1的數值表示，k1、k2分別為曲面的最大、最小曲率，如式(3)所示。形狀指數是用來表示曲面形狀的，形狀指數的大小隨著曲面的變化而變化。

通過形狀指數的性質可知，如果點云中某一點的用于描述其局部曲面特征的形狀指數與其附近點的形狀指數相差很大，則可以判斷出該點周圍的曲面變化劇烈。通常曲面中的這種點在點云中有很強的代表性和可區分性，適合被選作關鍵點。

分別在源點云和目標點云中找出形狀指數變化大的點作為關鍵點。對于點云中的每一點p，當滿足式(6)或式(7)中任一條件時，可將其選為關鍵點：

(6)

(7)

(8)

1.2 點鄰域尺度差異描述符

針對獲得的關鍵點，本文設計了根據點鄰域尺度差異得到的特征描述符。首先對關鍵點集中的每一點建立局部參考坐標系，然后根據局部幾何信息，獲得其特征信息。圖1為點云中不同尺度的鄰域空間示意圖，用黑色標記關鍵點，藍色標記鄰域點，灰色標記無關點。如圖1所示，對同一關鍵點，不同尺度的鄰域空間的鄰域點分布各不相同，因此建立的局部坐標系也會存在差異，同時在不同局部坐標系下的相同類型的特征信息同樣會存在差異。這樣，通過不同尺度的點鄰域空間信息描述關鍵點特征，擴大了描述關鍵點信息的空間范圍，提高關鍵點描述的顯著性和計算效率。下面介紹具體的計算過程：

對于采樣點p，取l個大小不同的鄰域半徑，相鄰鄰域半徑之差為Δr，有r1

(9)

在局部參考坐標系建立的過程中，傳統方法受點云密度分布和噪聲點的影響較大，建立的局部坐標系不準確，還會導致依據局部坐標系計算的法線等幾何信息不準確。為了改善這個問題，在求協方差矩陣過程中，引入關鍵點與其鄰域點的歐式距離作為權值，如式(9)所示，鄰域中各點與關鍵點的距離的不同對協方差矩陣的構建產生不同的影響，距離越近，影響越大。這樣的加權方法能夠有效地抑制外圍噪聲和雜波的干擾。圖1中灰色無關點對局部參考坐標系的影響將大大降低。

圖1 點云中不同尺度的鄰域空間Fig.1 Neighborhood spaces of different scales in point clouds

特征值{λl1，λl2，λl3}(λl1>λl2>λl3)和對應的特征向量{vl1，vl2，vl3}可由式(9)所求得的Cl進行奇異值分解得到。將三個特征向量作為三個坐標軸，建立關鍵點的局部坐標系。特征向量vl1、vl2對局部鄰域中鄰域點密度變化敏感，但是特征值之和與特征向量vl3具有很強的旋轉不變性，局部穩定性高[15]，所以基于特征值λl1、λl2、λl3和特征向量vl3建立局部描述符。由于本文是通過歐氏距離加權的方式求取的協方差矩陣，所以所求得的特征向量vl3與傳統方法所求的特征向量存在差異，但是其仍然具有良好的局部穩定性，而對點的局部描述符的建立與該描述符是否具有現實的幾何意義無關，因此這不會影響到vl3對關鍵點的描述性，下文稱vl3為法向量。

本文設計的多尺度特征描述符向量由兩部分組成：

1)根據特征值{λl1，λl2，λl3}和對應的特征向量{vl1，vl2，vl3}構建特征值歸一化向量hl：

(10)

當用于建立局部坐標系的鄰域半徑改變時，通過式(9)求得的協方差矩陣也會不同，奇異值分解出的特征值也會改變，式(10)所求的hl則會發生變化，此時可以將不同鄰域半徑下的特征值歸一化向量hl的差值作為局部特征描述符的一部分特征。不同鄰域半徑所求得的特征值歸一化向量hl的差值分別為Δhk=Δhk+1-Δhk(k=1,2,…,l-1)，隨后得到一個3l-3維的向量H：

H=(Δh1， Δh2， …， Δhl-1)

(11)

2)法向量之間的夾角余弦。對每個關鍵點，不同鄰域半徑下所求得的特征值不相同，該點在不同尺度鄰域空間的法向量也不同，這些法向量之間的夾角同樣可以作為點鄰域尺度差異描述符的組成部分。

首先，選取l個互異的鄰域半徑值，通過求協方差矩陣，奇異值分解等步驟得到l個法向量n1,n2,…,nl，計算不同鄰域空間的法向量之間的夾角余弦值為：

(12)

將計算得到的l-1個法向量夾角余弦值αi組合為一個l-1維的向量N：

(13)

綜上，不同鄰域半徑下所求得的特征值歸一化向量hl的差值組合為H，法向量夾角的余弦值組合為N，將H和N組合為一個4l-4維的向量F作為點鄰域尺度差異描述符：

(14)

1.3 對應關系二重篩選及全局優化算法

由于點云模型可能是對稱的，或者局部多處高度相似，上文中得到的對應點對集E中可能存在錯誤的點對，如果只用特征描述符向量的歐式距離查找對應點對，得到錯誤的對應關系的概率很大，并且傳統的隨機采樣一致性(RANdom SAmple Consensus, RANSAC)算法在輸入樣本集高度相似的情況下也很難避免這種錯誤。故本文設計了一種基于全局距離的全局優化算法，能夠有效地剔除上述情況帶來的錯誤對應點對。

定義兩點云之間的全局距離為：

(15)

(a) 遠離(a) Faraway (b) 相交(b) Crossover (c) 接近(c) Approach圖2 兩點云相對位置情況示意圖Fig.2 Relative position of two point clouds

利用上述方法得到的全局距離D(P,Q)，提出了對應關系全局優化算法，以求取最終旋轉變換矩陣，具體過程如下：

令P表示源點云，Q表示目標點云，對應關系構成的集合為E={e1,e2,…,en}，從E中隨機抽選n(n≥3)組對應關系，計算變換矩陣Ti，利用Ti將源點云P變換到新的坐標系PT，利用式(15)獲得D(PTi,Q)。選取合適的閾值Dε，當D(PTi,Q)

2 實驗結果分析

本小節通過設計實驗來驗證本文算法的可行性和有效性。本文實驗均是在Windows 7 64位操作系統下，使用C++語言實現。實驗所用PC機配置為Intel(R) Core(TM) i5-4210M處理器，物理內存為8 GB。實驗所用點云為3個斯坦福大學點云模型庫中雙視角掃描點云數據Bunny、Dragon和Armadillo，實驗室設備采集點云Toy。這四組點云中，源點云和目標點云的采集視角差各不相同，分別為45°、48°、60°和45°，圖3展示了4組點云配準前的初始位置，其中用綠色點標記的點云為源點云，用紅色點標記的點云為目標點云。

(a) Bunny (b) Dragon

(c) Armadillo (d) Toy圖3 四組點云配準前初始相對位置Fig.3 Initial relative positions of four sets of point clouds

(a) Bunny (b) Dragon

(c) Armadillo (d) Toy圖4 四組點云的基于形狀指數的關鍵點分布Fig.4 Key point distribution of four point clouds based on shape index

(a) Bunny (b) Dragon

(c) Armadillo (d) Toy圖5 四組點云數據配準結果Fig.5 Registration results of four sets of point cloud data

2.1 關鍵點提取

本文通過基于形狀指數的方法對圖3四組點云提取關鍵點。圖4所示為四組點云的關鍵點分布情況，其中關鍵點為藍色。

由圖4可知，源點云和目標點云中的關鍵點分布很相似，說明找到的關鍵點具有很強的代表性，有助于接下來的對應關系查找。同時，可以看到提取的關鍵點在整個點云中分布均勻，為局部區域中特征突出的點，能夠代替整個點云完成接下來的點云配準。

2.2 配準實驗

采用本文提出的配準算法對四組點云進行配準實驗。由四組待配準點云得到的最終配準結果如圖5所示。從圖5中可以看到，四組數據中的源點云和目標點云基本重疊在一起，配準效果良好。表1展示了本文配準算法與基于快速點特征直方圖的點云配準算法和正態分布變換算法(Normal Distributions Transform, NDT)在四組點云的配準精度和時間。通過對比可以看出，本文算法與兩種配準算法相比較配準精度更高，且消耗的時間更短。

表1 點云配準算法時間精度對比

2.3 參數a, b對關鍵點分布的影響

實驗中對鄰域半徑進行手動調節，通過多次試驗，最終將鄰域半徑r設定為0.003 m來進行點云曲率、法向量估計及特征描述符建立。

為了驗證參數a,b對關鍵點提取的影響，設計實驗進行驗證，結果如圖6所示。對比圖6中第一行點云(源點云)，圖6(b)中a和b都為0，可以看出關鍵點密度較大。當a或b增大時，如圖6(a)和圖6(c)所示，關鍵點數量減少。從圖6(b)可以看出，源點云和目標點云中的關鍵點分布情況基本相同，重疊區域存在大量關鍵點，關鍵點選取方法效果較好。

(a) a=1,b=0 (b) a=0,b=0 (c) a=0,b=1圖6 不同a和b值下的關鍵點分布Fig.6 Distribution of key points with different parameters a and b

表2列出了參數a和b不同取值下的關鍵點個數。Bunny點云(源點云和目標點云)初始個數分別為40 256、40 097，表2列出了6組關鍵點個數。從第2、3、4、7列可以看出，隨著參數a和b的增加，關鍵點個數有明顯減少，但a和b都為1時，兩點云關鍵點個數分別只有2、3。從第2、5、6列可以看出，單獨增加a、b值同樣會減少關鍵點個數。

表2 不同參數a, b下的關鍵點個數

2.4 對應關系查找

設計實驗驗證1.3節中的對應關系查找算法的效果。通過對比候選對應點集和對應點對二重篩選算法得到的對應點集進行分析，對比效果圖如圖7所示。圖7中每組圖中包含候選對應點對(左圖)和對應點對二重篩選算法得到的對應點對(右圖)。從圖7中可以看出每組圖中左圖都比右圖多出許多錯誤對應點對。在圖7(a)中，左圖為基于歐式距離最近原則確立的候選對應點對圖，共有84對對應關系，右圖為本文二重篩選算法得到的對應點對結果，共有24對，從圖中可以看出對應關系準確且均勻。同樣地，在圖7 (b)～(d)中，左圖分別有90、85、112對對應點對，明顯可以看出其中有一些錯誤對應關系，右圖分別為本文二重篩選算法篩選出的27、29和51對對應點對，基本上剔除了錯誤對應，對應點對的分布也比較均勻，有利于最終配準效果的提高。

(a) Bunny (c) Dragon

(c) Armadillo (d) Toy圖7 候選對應點對集與最終對應點對集分布Fig.7 Distribution of candidate correspondence point pair set and final correspondence point pair set

3 結論

設計了一種點鄰域特征差異描述的點云配準算法。首先根據擬合曲面的形狀指數隨著曲面的形狀變化而變化的特性，選取局部擬合曲面變化大的點為關鍵點。然后，對于每個關鍵點，將不同鄰域半徑下所求得的特征值歸一化向量的差值和法向量夾角的余弦值組合為點鄰域尺度差異描述符。最后，在基于歐式距離的對應點查找方法的基礎上，提出了對應點對二重篩選及全局優化算法，提高了對應關系的準確率。實驗證明本文配準算法的配準速度快，計算效率高，同時配準精度高，具有很強的噪聲魯棒性。