基于相對幾何不變性的點云粗配準算法研究

陳亞超，樊彥國，樊博文，禹定峰

1.中國石油大學（華東）海洋與空間信息學院，山東 青島 266580

2.哈爾濱工程大學 水聲工程學院，哈爾濱 150001

3.齊魯工業大學（山東省科學院）山東省科學院海洋儀器儀表研究所，山東 青島 266061

配準技術的研究主要是從特征提取、粗配準算法、精配準[1-3]算法三個方面去改進提高[4]。而精配準對初值具有較高要求，所以在大數據場景下亟需一個效率高、精度高、穩定性強的粗配準算法。點云粗配準中匹配對獲取主要依靠點云的局部特征，Rusu等提出了著名的點特征描述子（point feature histogram，PFH）[5]和快速點特征描述子（fast point feature histogram，FP‐FH）[6]，算法兼具特征差異性和運行效率；而在近年也涌現出了差異性更強的SHOT（signature of histograms of orientations）[7]，RoPs（the rotational projection statis‐tics）[8]等描述子。由于不同描述子的特性，產生了多種點云粗配準算法，Aiger等[9]提出著名的四點一致集（4-points congruent sets，FPCS）算法，算法依據兩點對的仿射不變性，尋找穩定結構，但算法要求較高，參數難以設置，穩定性差。而后Rusu等提出采樣一致性初始配準（sample consensus initial alignment，SAC-IA）[6]算法，依靠隨機采樣一致性算法和FPFH描述子獲取配準初值，算法計算量大，且控制參數較多。針對此算法，Bu‐ch等[10]在SAC-IA隨機選點的基礎上考慮了幾何距離，加快了算法速度，但仍需定義大量控制參數。近年來，國內學者也對粗配準算法有大量研究，張晗等[11]在SAC-IA基礎上考慮點位間角度特征，提高了配準效率；劉世光等[12]提出基于邊界帶查找的FPCS改進算法，使得FPCS算法更加穩定；侯彬等[13]對現有的特征描述子進行了粗配準對比，分析了特征描述子的適用情況；在配準效率問題上，研究者們也提出了多種基于關鍵點提取的粗配準算法，但大部分粗配準算法仍需設置大量控制參數，穩定性較差。

根據以上研究進展與分析，為了解決粗配準算法穩定性差及控制參數難以設置等問題，本文提出一種基于關鍵點的相對幾何不變性特征的粗配準算法（keyrelative geometric invariance initial alignment，K-RGI），算法為了在大數據下的可用性，采取對關鍵點進行匹配對選取的策略，通過關鍵點提取算法獲取一定量的點云，應用FPFH特征進行最鄰近匹配對初步篩選，然后通過在源點云與目標點云上的對稱候選尋點策略及兩組匹配對連接邊的2-范數比例不變性，精確獲取可靠的匹配對，最后通過奇異值分解（singular value decomposition，SVD）算法求解多元線性最小二乘目標函數。實驗結果表明，本文算法相比傳統粗配準算法，時間和精度都有顯著提升，且參數更易設置，在真實場景下，算法表現優異。

1 點云粗配準相關原理

1.1 數據預處理

激光掃描儀獲取的點云數據一般都是無序散亂的，而獲取過程中不可避免地存在許多冗余點和噪聲點，且真實場景需要海量點云數據進行表達，所以直接獲取的原始數據需要經過預處理過程得到便于計算的數據結構和體量，如圖1所示，通常點云預處理包括拓撲鄰域的建立、法線計算、點云噪聲去除、點云數據量壓縮等過程。拓撲鄰域采用kdtree（k-dimension tree）數據結構進行構建，便于最鄰近搜索。法線計算主要依靠目標點鄰域范圍內的最小二乘擬合平面求出，一般通過鄰域最小特征值方向近似代替。點云噪聲去除分為離群點與噪聲浮點，離群點采用統計濾波算法，浮點采用雙邊濾波[14]算法。點云數據壓縮則構建點云整體的八叉樹結構，通過立方體內密度去除冗余點。

圖1 點云預處理流程示例Fig.1 Example of point cloud preprocessing process

1.2 關鍵點提取

常用的關鍵點提取包括八叉樹結構數據過濾法，內部 簽 名 法（intrinsic shape signatures，ISS）[15]，Har‐ris3D[16]關鍵提取法、尺度不變特征變換（scale-invariant feature transform，SIFT）[17]等，針對不同提取算法特點，八叉樹結構過濾法屬于區域降采樣以獲取更少量的點云數據，但并不能剔除平面點，而SIFT計算需要強度屬性，對于一般的點云數據并不適用，所以結合ISS與Har‐ris3D的算法特點，兩者均通過特征值與關鍵點的相關關系進行篩選，適用范圍廣，且計算簡單，對于點云關鍵點提取步驟，兩種算法通過合理的參數設置均可適用于提取邊緣點或角點。

ISS主要通過控制計算點鄰域范圍內特征平面與關鍵點的關系進行提取，通過計算局部鄰域范圍內坐標協方差矩陣的特征值，對其排序后設置閾值，ε1和ε2控制關鍵點輸出條件：

Harris3D則是從Harris2D提取算法衍生而來，關鍵點提取依據為一定大小的立方體軸向移動，相應體內點數量變化情況。在Harris2D算法中，通過各向灰度梯度值描述變化，針對點云描述，Harris3D[16]采用各點法向量類比梯度，則變化矩陣M為：

式中，W為滑動立方體，ω為窗體函數，表示不同窗體的權重，Nx,Ny,Nz表示點法向量的軸向分量。

進而可計算Harris3D響應值控制關鍵點輸出條件：

式中，R為Harris響應值，det為矩陣的行列式，tr為矩陣的跡，k為常量用于擴大響應值區別。

1.3 點云粗配準基本原理

點云配準即兩個點云數據，點云源數據S與點云目標數據T，主要依靠求得一定量的匹配對，構建以下目標函數，求取齊次旋轉矩陣R：

式中，R為4×4的旋轉平移齊次矩陣，N為源點云與目標點云匹配對的數量，Si、Ti為第i個匹配對在源點云與目標點云中的坐標值。

為了能夠準確獲得配準結果，需要尋找三個以上的正確匹配對，以滿足三維空間的坐標轉換。配準需要通過局部鄰域特征進行最鄰近匹配，其中具有代表性的SAC-IA算法，使用FPFH作為特征匹配描述子，通過隨機選擇點機制和迭代計算機制尋找合適的旋轉矩陣，主要步驟如下：

（1）計算源點云與目標點云各點的FPFH描述子。

（2）在S源點云中選擇3個以上的隨機樣本點，同時確保它們的成對距離大于用戶定義的最小距離dmin。

（3）對于每個樣本點，在T目標點云中找到直方圖與樣本點直方圖相似的點列表。從這些中，隨機選擇一個將被認為是樣本點的對應。

（4）計算由樣本點及其對應關系定義的剛性變換，并應用變換矩陣計算源點云變換后與目標點云的誤差度量，若不符合要求，回到（2）重新隨機選擇，直到達到誤差要求或迭代最大數。

由算法過程可知，SAC-IA算法的隨機機制使得參數設置較為困難，迭代機制使得匹配對查找過程若出現匹配對錯誤將降低計算效率，目前基于特征匹配下的粗配準算法仍然以隨機與迭代機制為主要計算框架，粗配準算法中本質的隨機與迭代機制是阻礙效率與精度的關鍵。

2 基于相關幾何不變性的粗配準算法（K-RGI）

本文配準算法則以更精準快速地獲取匹配對及更易設置控制參數為目的，受源點云與目標點云匹配對之間幾何特性的啟發下，提出基于相關幾何不變性的粗配準算法（K-RGI），算法主要思想是從關鍵點中利用計算量小差異性強的FPFH描述子進行初步匹配對篩選，而后通過多步策略剔除錯誤對，獲取更精確的匹配結果，該算法能夠有效快速獲取匹配對的核心點在于三大策略的提出：

（1）對稱候選尋點策略

對稱候選點剔除指在源點云中某點Si尋找目標點云中特征直方圖最鄰近的n個候選點T1,T2,…,Tn，記Tj為Si的第j個候選點，再對稱通過目標點云中的候選點T1,T2,…,Tn分別查找其在源點云中特征直方圖最鄰近的n個點得到TSj1,TSj2,…,TSjn，記TSj為Tj的對稱候選點，若TSj1,TSj2,…,TSjn中至少存在一個與Si為同一點，取相應候選點為匹配對應點，得到匹配對{Si,Tj}，若不存在則無對應匹配，如圖2所示。

圖2 對稱候選尋點示例Fig.2 Example of symmetric candidate point elimination

（2）相對幾何不變性篩選策略

相對幾何不變性指若存在正確的兩組匹配對{S1,T1},{S2,T2}，滿足條件：

式中S1、S2表示源點云的兩點，T1、T2表示目標點云的對應點，‖‖2表示向量2-范數。如圖3所示，由于點云數據的無序散亂性，及點云采集結果的不唯一性，無法找到完全正確的匹配對，但考慮到誤差影響，實際中正確的匹配對的公式（5）結果仍然在1的小范圍內，因此，只需要判斷篩選出的匹配對按公式（5）計算后是否保持在比例閾值中即可。

圖3 相對幾何不變性示例Fig.3 Example of relative geometric invariance

對于三維空間來說，僅僅使用兩組匹配對并不能完全說明匹配正確，所以實際計算中將匹配符合公式的兩組匹配點分別列為候選點并對應計數，由于正確的匹配對在計算過程中會多次被使用形成穩定的多邊形非共面幾何結構，所以當統計數大于計數閾值時，匹配對則可信任，閾值根據數據量自定義設置。

（3）重疊區域連續性搜索策略

針對幾何不變性，需要確定一種查找策略，而不是隨機選取兩點進行計算，如圖4所示，通過點云數據觀察，可發現重疊區域在局部范圍內都是連續的，匹配對必然存在于重疊區域，所以通過匹配對連續性，本文提出待匹配點的空間鄰域搜索策略，即在現有匹配對中，在源點云中建立源匹配點的稀疏kdtree結構，通過每個源匹配點的k鄰域感知野，k設置為源匹配點總數的倍數，分別與其鄰域點連接，計算公式（5）并依據結果計數統計。

圖4 重疊區域匹配對連續性示例Fig.4 Example of matching pairs of overlapping regions

由點云配準原理可知閾值的選取對結果尤為重要，K-RGI三大策略中對稱候選閾值表達了對特征描述子匹配結果的信任程度，當點云數據特征不明顯時，可調整到較大閾值，當數據特征差異明顯時，可設置較小閾值，取3~5個候選數在準確率和運行時間平衡上更為通用。幾何比例閾值表達了匹配對之間的幾何差距程度，采用去單位化的比例形式閾值比傳統的絕對閾值更加方便有效，按實際精度要求設置即可，一般設置為1.01~1.03。感知野倍數閾值表達了對重疊區域的預估程度，根據實際數據重疊的預估程度設置源匹配點倍數為0~1之間，對于無法預估重疊的未知數據及對運行時間的考慮，一般設置0.5倍即可。計數閾值表達了匹配對準確程度，感知野區域越大，匹配點的總計算次數越多，若匹配點被統計的次數越多，則結果越準確，一般設置2~3次即可保證大部分匹配對是正確的。

當匹配對確定后，由于粗配準不需要完全精確的配準結果，后續只需利用3個以上的匹配對求解點云配準目標函數，常用的計算方法有奇異值分解法（SVD）和LM（Levenberg-Marquardt）法，對于多元線性最小二乘方程，兩種方法求解結果一致。

綜上所述，基于相關幾何不變性的粗配準算法（KRGI）的算法描述為：

（1）設置對稱候選閾值，幾何比例閾值，感知野倍數閾值，計數閾值并輸入源點云與目標點云，進行預處理。

（2）通過ISS或Harris3D算法提取源點云與目標點云的關鍵點。

（3）分別計算源點云與目標點云中關鍵點在原數據基礎上的FPFH描述子。

（4）利用特征直方圖最鄰近搜索與對稱候選尋點策略，篩選初步匹配對。

（5）構建篩選后的源匹配點的kdtree結構，利用重疊區域連續搜索策略，對各計算單元通過相對幾何不變性得到候選匹配對，并進行計數統計。

（6）選擇計數大于計數閾值的匹配對，若大于三對則利用SVD或LM算法求解目標函數，若匹配對數量不足則返回步驟（2）提取更多關鍵點。

3 實驗結果與分析

3.1 實驗概述

以Intel core i7，2.5 GHzCPU，8 GB內存的Linux虛擬機作為實驗平臺，應用PCL（point cloud library）[16]庫對Stanford實驗室提供的含有437 645個點的Dragon三維數據進行算法實驗對比。為解釋關鍵點引入的必要性及更客觀地驗證實驗對比結果，根據特征和方法的不同選用對比算法，通過對工業軟件及近年科研成果相關調研，為突出實驗的綜合性與前沿性，采用非關鍵點提取的SAC-IA-FPFH[6]算法、SAC-IA-SHOT[6-7]算法、SAC-IA-PRE[10]算法及關鍵點Harris3D[16]算法提取下的K-SAC-IA-FPFH算法、K-SAC-IA-SHOT算法、K-SACIA-PRE算法、K-SAC-IA-FEA[11]算法、K-FPCS[9]算法和本文算法K-RGI。各算法控制參數數量如表1所示，本文算法K-RGI實驗參數設置為通用型數值，其中對稱候選閾值為3，幾何比例閾值為1.01，感知野倍數閾值為0.5，計數閾值為2，另外八種算法參數值設置為PCL源碼的默認值。從表中可觀察到本文算法比其他算法參數設置數量減少了2~3個，且部分參數設置從絕對距離改進為比例設置，對于尺度不同的數據參數更易設置。

表1 粗配準算法控制參數數量表Table 1 Control parameters quantity of each coarse algorithm

3.2 誤差與效率分析

為比較粗配準算法的匹配誤差與效率，采用Dragon數據隨機執行旋轉平移，通過對比其初始位置獲得實驗結果如圖5所示，各算法在相同參數設置一致情況下，本文算法表現良好，證明了算法的有效性，為進一步對比實驗細節，對各算法的旋轉誤差，平移誤差及時間效率進行對比，結果如圖6、圖7所示，圖6誤差結果表明本文算法相比其他算法具有較高配準精度，且證實了FPFH特征描述子時間和特異性上的優勢，而圖7結果表明，引入關鍵點能顯著提高計算效率且本文算法在效率上同樣優于大部分粗配準算法。

圖5 龍點云配準效果Fig.5 Registration effect of dragon point cloud

圖6 粗配準算法旋轉與平移誤差對比Fig.6 Comparison of rotation and translation errors of coarse registration algorithms

圖7 粗配準算法時間效率對比Fig.7 Comparison of time efficiency of coarse registration algorithms

3.3 算法穩定性分析

為進一步說明算法穩定性，采用關鍵點提取下的粗配準算法，通過多次實驗觀察結果變化，調整迭代次數為500~5 000次，旋轉平移誤差及時間效率變化如圖8、圖9所示，實驗結果表明，當迭代次數設置較少時，傳統算法可能出現算法誤差偏大問題，設置過多又會導致時間效率低下。由于傳統算法的隨機機制，算法穩定性較差，而本文算法在誤差和效率方面均能保持穩定結果，證明了本文算法的穩定性優于其他算法。

圖8 粗配準算法旋轉與平移誤差對比Fig.8 Comparison of rotation and translation errors of coarse registration algorithm with number of iterations

圖9 粗配準算法隨迭代次數的時間效率對比Fig.9 Comparison of time efficiency of coarse registration algorithm with number of iterations

3.4 真實場景粗配準分析

為驗證關鍵點提取下的粗配準算法的實際應用效果，采用PCL提供的含有103 266個點的真實牛奶掃描數據進行再次實驗，分割提取其中一個牛奶盒，并作隨機旋轉平移，在僅有30%重疊率及桌面和其他物品干擾下，進行部分粗配準實驗對比。如圖10所示，圖10（e）結果表明由于點云結構未滿足FPCS算法要求而導致計算失敗，圖10（f）表明本文算法結果具有良好的配準效果，能夠穩定地應用到真實場景中。

圖10 牛奶點云配準效果Fig.10 Registration effect of milk point cloud

4 結束語

提出在關鍵點提取下的基于幾何不變性的粗配準算法，與傳統算法實驗結果對比表明，本算法在參數設置及穩定性上具有顯著優勢，在精度及效率上高于大部分粗配準算法。在實際應用場景及使用者角度提供了一個在時間和精度上能夠滿足需求，參數設置更簡單，穩定性更強的粗配準算法。

粗配準算法仍然存在需要用戶自定義設置參數的問題，不利于工業自動化應用，因此，下一步工作是在現有信息中盡可能通過算法獲得自適應參數，簡化操作流程。