基于圖神經卷積網絡的點云配準算法

摘 要：為了解決現有點云配準算法對配準點云的初始位置或噪聲敏感，對獨特幾何結構的需求以及算法設計復雜、通用性差等問題，本文提出了基于圖神經卷積網絡的點云配準算法。該算法利用圖神經網絡在不規則點云圖形結構中尋找關鍵頂點特征，簡化原有點云結構，利用在頂點所屬對象特征和局部幾何信息中學習到的混合特征來構建點對應的分配網絡，并提取所需的圖特征。同時，通過將模擬配準信息輸入另一卷積網絡中，計算最佳的配準擬合參數。該算法降低了對配準初始值的依賴，使算法快速收斂，提高了在點云局部可見情況下的配準質量。

關鍵詞：圖神經卷積網絡；點云；迭代；收斂

中圖分類號：P 237 " " " " 文獻標志碼：A

隨著激光雷達（Light Detection and Ranging，LiDAR）、3D體感攝影機（Kinect）等高精度傳感器的快速發展以及基于深度學習的點云配準算法的提出，點云已成為表征三維世界的主要數據格式。如何將傳感器探測到的有限場景數據組成的點云采用配準算法生成完整的三維場景點云，成為當前的主要問題[1-2]。根據變換矩陣，可以將同一個三維場景或物體的部分掃描點云合并為一個完整的三維點云。

1 點云配準算法現狀分析

1.1 基于距離的匹配算法

基于距離的匹配算法包括迭代最近點（Iterative Closest Point，ICP）算法、RPM（Robust Point Matching，RPM）等。ICP算法通過迭代的方式解決點云的剛性配準問題，主要步驟如下。1）基于最近的空間距離尋找hard點的對應關系。2）求解最小二乘變換。其中，步驟1）對配準點云的初始位置和噪聲點/離群點敏感，可能導致在迭代的過程中收斂到錯誤的局部最小值。這類算法對配準點云的初始位置或噪聲敏感，因此需要采取措施降低對初始位置和噪聲的影響。

1.2 基于特征的匹配算法

一種是基于局部坐標系（LRF）的算法[3]，其中典型的是基于局部特征描述符的旋轉圖像（Spin Image，SI）。該算法首先將關鍵點的法向量作為參考軸，其次將局部鄰域點投影到以水平和垂直投影距離為坐標的二維平面，最后通過二維累加運算的方式得到1張二維灰度圖。這個特征描述符主要依賴采樣點的法向量方向，對噪聲的魯棒性較差并且計算復雜度較高。另一種是點特征直方圖（PFH）。首先，PFH 描述符采樣點和其鄰域點的法線和位置差異構建局部坐標系，其次，根據局部坐標系描述兩點的局部特征信息，最后，計算所有鄰域點兩兩之間的局部信息并用直方圖表示。PFH具有較強的鑒別能力，但是計算耗時較長。為了提高效率，筆者產生了利用簡化版點特征直方圖（SPFH）來構造快速點特征直方圖（FPFH）的思路。FPFH具有快速、鑒別能力強的特點，但是降低了特征維度和通用性。

這類算法要求計算的點云具有獨特的幾何結構，否則不能有效地進行信息配準。

1.3 基于學習的匹配算法

例如點云配準（PointNetLK）、 深度最近點（DCP）以及PRNet等。PointNetLK將LK算法和PointNet融合到一個單一的可訓練的遞歸神經網絡中，具有較好的泛化能力和高效的計算能力。但是它主要用于局部到整體的配準變換，需要主體模板。DCP是局部到局部的配準算法，通過一種基于注意力機制的深度神經網絡模型（Transformer）中的注意力機制計算出1個“假想的目標點云”。這個假想的目標點云與待調整點云之間點的對應關系已知（soft matching：使用一種概率方法來生成從一個點云到另一個點云的“軟映射”）。再通過損失函數約束，間接使假想的目標點云向真正的目標點云不斷逼近，最終實現點云的對齊匹配。但是DCP的收斂性不高，在計算中多次使用軟映射，導致計算過程較復雜。這類算法大多基于整體特征的提取，不能有效地解決局部到局部的點云匹配問題。同時，算法設計復雜，無法在較短的時間內得到理想的結果。綜上所述，現有的配準算法大多通過對應搜索和變換估計2個過程來縮小幾何投影誤差。這2個過程交替進行，直到幾何重投影誤差最小。在已知精確對應的情況下，變換估計有一個閉環形式的解[4]。

2 解決方案

針對點云配準的現狀，本文提出一種有效的圖神經卷積網絡。該網絡從局部到局部的微分網絡保留基于距離匹配算法中對離群點的魯棒性，同時訓練得出所屬對象特征中的對應關系，減少對初始值的依賴。具體實施步驟如下。

步驟1：將原始輸入的點云命名為X點云數據，將目標點云命名為Y點云數據。在X中，將N個點組成的點云數據定義為一個集合P={p1，…，pN}，其中每個元素pi=（xi，si）。這里，xi為三維坐標系中該點的坐標，si為點屬性的k維度向量，這個值包括自身與周圍點的信息以及自身的位姿信息和條件信息。給定點云P，使用此點云P作為1個頂點Pi，此時X點云數據就變為1個少量的點云集合I={P1，……，Pn}。

步驟2：對減少后的點云集合I使用FPS最遠點采樣方法（采用歐幾里得距離度量點之間最遠距離）。在對第一個點采樣的過程中，可以隨機從數據中選取1個點，或者求整個數據點（點云）的重心（即所有點坐標求和平均得到的坐標點），選取距離重心最遠的點為初始采樣點，記為K0。繼續選取剩余的所有點中距離初始采樣點最遠的點，記為K1。對剩下的每個點，分別計算其到K0和K1的距離，并選取距離最小的點作為這個點到K0和K1整體的距離。完成這些距離的計算后，選擇距離最大的點，記為K2。重復以上操作，最終取到所需的M個點。根據M個點的特征，概括稠密點云特征，最后進行編碼，將其概括為頂點的初始狀態si1（表示初始點云所有頂點經過第一次計算后得到的Si）。利用體素濾波再次減少點的數量，然后使用3D稀疏卷積進行特征提取，確立最終的頂點點云數據集合P。在集合中，每個點Pi利用固定的半徑r尋找另一個相鄰頂點Pj進行連線E，構建圖形Gx=（P，E），其中E={（Pi，Pj）| ||xi-xj||2lt; r}。

步驟3：對圖形G使用圖神經網絡（GNN）細化頂點狀態進行配準特征提取。這里采用鄰接表表達圖的關聯性，如果采用鄰接矩陣，其多表示性（指多種鄰接矩陣表示一種連通性）就會導致細化結果不準確，從而影響后續的操作。采用頂點間的相對坐標作為輸入，同時根據相鄰的頂點結構特征調整坐標，計算得到每個頂點的不同特征信息。如公式（1）所示。

sit+1=gt（ρ（{f（xj-xi+?xit，sjt）}），sjt） " " " " " "（1）

式中：t為迭代次數；xj為三維坐標系中與Pi相鄰點Pj的坐標；sj為與Pi相鄰點Pj的屬性的k維度向量，這個值是自身與周圍點的信息以及自身的位姿信息和條件信息；ρ（…）為聚合每個頂點邊要素的函數集合；gt（…）為利用聚合的邊特征跟新頂點特征的函數；f（…）為輸入變換幅度，用于減少平移和變換造成的特征差異；?xit為頂點要配準的偏移量大小，由公式ht-（…）決定。

使用多層感知器（MLP）對這些函數進行建模輸出。在輸出過程中，引入添加殘差結構以消除?x在計算過程中產生的偏移誤差。值得注意的是，每個迭代次數t都使用不同的MLP，即每次迭代并不共享MLP。

步驟4：將經過迭代計算后的屬性向量特征si寫入頂點的元素向量Pi中。同時，為了提高魯棒性，本文將ρ（…）設置為Max聚類。在完成t次迭代的圖神經網絡中，使用頂點狀態值來預測初步的特征，并對這些特征進行歸一化處理，以生成所需的圖特征Ux。

步驟5：對Y點云數據進行隨機的平移、翻轉等變換，并將此時的變換狀態記作σ，然后對變換后的Y點云數據按照上述X點云數據的處理方式，求出所需的圖特征Uy。

步驟6：通過上述步驟，確定了2個圖特征Ux和Uy、它們構成的圖形Gx和Gy以及點集I和連線E。將X、Y的點云數據進行標記，并通過通道數模式疊加（即使用concat鏈接）。然后，通過一個共享參數的MLP結構網絡，并使用最大池化層進行歸一化和維度縮減，得到所需的2組關聯性結果數據α和β。為了確保數值為正，使用leaky_relu作為激活函數。如公式（2）所示。

?xit=MLPht（sit） （2）

式中：MLPht為t層感知機網絡。

步驟7：根據關聯性結果數據，并結合基礎數據，計算X與Y點云之間的相關性，如公式（3）所示。

（3）

式中：nKC為點與點云核之間的相關度；Qi為目標點云的點；Pi為輸入點云對應Qi的點；|E（Qi）|為根據Y點云數據建立的圖Gy中求出的關于i的E中所有的點的個數；len（E）為根據Y點云數據建立的圖Gy中求出的關于i的E中所有的邊的個數；m為當前求和步驟中目標點云的Q點在圖Gy中對應的邊；n為當前求和步驟中作為對象被分析的點，其屬于E（Qi）域；E（Qi）為根據Y點云數據建立的圖Gy中求出的關于i的E中所有的點；sn為與Pi相鄰點Pj的屬性的k維度向量；Kσ（…）為構建核的函數，是高斯函數一種公式，通過相關度⊙點乘參數，擴大頂點之間相關度關系，完成對X、Y點云數據的相關性特征的編碼提取。如公式（4）所示。

（4）

步驟8：進行奇異值分解（Singular Value Decomposition，SVD）以求解位姿問題。對給定的2個待配準點云X和Y，其中P為源點云，Q為源點云經過變換后的目標點云，三維點云配準任務為尋找合適的變換參數即旋轉矩陣R和平移向量T，使配準后的點云在同一坐標系下對齊。在確定點云之間的對應關系后，變換參數可以通過優化以下目標函數來求得，如公式（5）所示。

（5）

式中：O為函數名；N為整個點云的數量。

在配準過程中，不是所有的點都有一一對應的關系，設置一個權重ωi，增加數據的可用性，減少因為強制匹配產生的錯誤配準。

使用SVD求解配準變換參數的計算步驟如下：通過下列公式分別計算源點云和目標點云的質心，即求取點云中點的均值，如公式（6）所示。

（6）

式中：N1為點集I中頂點的數量。

求解點云的協方差矩陣H，如公式（7）所示。

（7）

對協方差矩陣H進行SVD分解，如公式（8）所示。

[U，S，V]=SVD（H） " " " "（8）

式中：U、S、V分別為進行SVD分解后得到的降維矩陣的均值、方差與中心矩陣。

求解旋轉矩陣R和平移向量T，如公式（9）、公式（10）所示。

R=VUT " " " " " " " （9）

T=-R·+ " " " " "（10）

解算出初始變換矩陣后，將其應用于源點云得到初始配準結果。由于點云位姿變換具有復雜性，神經網絡難以一次性地對配準參數進行精確估計，因此利用RANSAC算法（隨機抽樣一致算法，這是一種通用且非常成功的估計算法，它能夠應付大比例野值的情況）的方法迭代將變換后的源點云與目標點云重新輸入網絡計算，使配準誤差不斷變小，直到達到最大迭代次數或兩次產生的矩陣之差小于閾值，點云精細配準過程如公式（11）所示。

（11）

式中：Rl為最終旋轉矩陣；T l為利用RANSAC算法估算后的平移向量。

步驟9：定義Loss函數，在點的分類判斷中，1個頂點在1個對象的框中，筆者將對象值賦給這個頂點。如果1個頂點位于任何邊界框之外，則它屬于背景類。筆者用平均交叉熵損失作為分類損失，如公式（12）所示。

（12）

式中：Lcls為平均交叉熵損失；yi cj為第i個點的真實概率；Pi cj為

第i個頂點的預測概率。

根據變換矩陣網絡設計2個損失函數：Lreg和Lest進行迭代傳送，并獨立計算，使預測配準參數與真實配準參數之間誤差最小，如公式（13）～公式（15）所示。

（13）

式中：I為點云內的比例系數；Rgt為真實變換矩陣；tgt為真實平移向量值；Rpred為網絡估計的變換矩陣；tpred網絡估計的平移向量值。

Lest=||（Rpred）-1·Rgt-E4|| " " " " " " " " " " " " （14）

式中：E4為Rpred與Rgt相等時的單位陣。

Lt=Lreg+λLest " " " " （15）

式中：Lt為兩類損失加權求和得到的損失值；λ為權值。

考慮每次迭代的損失，將損失設置為每次迭代損失的加權和并且每次迭代都是獨立的，確保最終得到的R、T結果預測值符合真實值。如公式（16）所示。

（16）

式中：L為總體的配準損失；N為總迭代次數；i為當前迭代數；Lti為第i次迭代產生的損失值。

3 本點云配準算法優勢

3.1 特征篩選與點云量化改進

步驟1～4利用圖神經網絡中的點與臨近點之間的關系以及自身的位姿信息和條件信息等篩選特征，建立頂點之間的相關性信息。并結合網格繪制（gird-based）和點繪制（point-based）在量化點云的同時使特征被賦予更良好的定位信息，使網絡能更好、更快地提取特征信息。

3.2 濾波與平移誤差優化

步驟5、步驟6利用初步統計和擬合信息，創建初步的濾波和確定平移誤差，并通過殘差網絡鏈接至后續的變換網絡中，加速計算并使計算結果更方便、準確。

3.3 高斯方程求解與預測變換優化

步驟7、步驟8將計算結果與KC（核相關）算法結合，建立核相關高斯方程，通過密度估計相關性和圖形點之間對應關系求解預測變換的R、T值，不斷迭代更新直至2次產生的矩陣之差小于閾值，完成預測。

3.4 創立新Loss函數

步驟9創立了新的Loss函數鏈接預測值和正值，迭代更新且保持迭代的獨立性，完成點云配準變換。

4 效果展示

該算法利用圖神經網絡考慮點與臨近點之間的關系，結合自身的位姿信息和條件信息篩選特征。從而降低了對配準初始值的敏感度，并減少了異常點對算法結果的影響。在存在異常點輸入的情況下（如圖1所示），該算法仍能夠輸出較為準確的配準結果（如圖2所示）。

圖3為該算法的配準過程模型圖，該過程將持續進行，直到達到最大迭代次數，或者某次迭代與前一次迭代產生的矩陣之差小于預設閾值，最終得到精確化的配準模型。

5 結語

截至2023年底，基于距離的匹配算法仍然容易受到噪聲的干擾，而基于特征的匹配算法則要求計算的點云具有獨特的幾何結構，否則無法有效地進行信息配準。與此同時，基于學習的匹配算法較為復雜且收斂性較差。基于圖神經卷積網絡的點云配準算法則利用點與鄰近點之間的關系簡化了點云的結構，確立了頂點間的相關性，同時提供了更準確的定位信息。在配準計算中，該算法通過殘差網絡加快了計算過程，并得到了更精確的R、T結果。與KC算法的結合使其在迭代更新中計算出的矩陣差值能夠收斂于閾值內，同時保證了每輪迭代的獨立性。最終，該算法能夠完成點云配準變換，為相關領域的研究和應用提供了有力的支持。

參考文獻

[1]楊必勝，董震.點云智能研究進展與趨勢[J].測繪學報，2019，48（12）：1575.

[2]王暢，舒勤，楊赟秀，等.利用結構特征的點云快速配準算法[J].光學學報，2018，38（9）： 175.

[3]耿國華，劉曉寧，周明全.基于局部坐標系和哈希技術的空間曲線匹配算法[J].計算機工程， 2003， 29（4）：3.

[4]GUO Y，WANG H，HU Q，et al.Deep learning for 3d point clouds：

A survey[J].IEEE transactions on pattern analysis and machine intelligence，

2020，43（12）：4338.