基于點密度調整的激光雷達點云配準改進方法?

王翊成 李明磊 魏大洲 吳伯春

（1.南京航空航天大學電子信息工程學院 南京 211106）（2.中國航空無線電電子研究所 上海 200233）

1 引言

激光雷達掃描（Light detection and ran-ging，Li-DAR）技術，采用非接觸式的測量方式，能夠在較短時間內獲取三維空間中物體表面的觀測點云數據［1］。點云配準是許多三維建模工作的基礎，為了得到待測物體的完整數據模型，需要確定一組坐標轉化關系，將各個視角采集的點云融合到一個統一的坐標系下，形成一個完整的點云數據模型。線掃LiDAR 設備采集數據時沿俯仰角方向掃描不是連續的，采集的點云數據會呈現明顯的環形條紋結構。這些條紋結構使點云數據具有極不均勻的點密度分布，對配準產生負面影響。點云密度的不均勻會影響觀察點的定向法向量估計，而定向法向量在物體識別和表面重建中起著至關重要的作用［2］。為了改進點云質量，可以對點云數據進行重采樣處理。在計算機圖形學領域，一些算法依賴于局部幾何分析來改進點集曲面［3］。Lipman 開發了一種高效的、無參數化的局部最優投影（Locally optimal projection，LOP）來處理異常值［4］。然而，當輸入數據點的分布高度不均勻時，LOP 不能很好地工作。Huang 等［5］改進了LOP 算法，提出了基于局部自適應密度權重的WLOP算法，來處理原始數據中的不均勻分布。但在處理大規模數據時，WLOP 算法的效率較低。因此本文采用了一種基于超體素的重采樣技術來調整點云密度，使點云分布更加均勻，以支撐后續的精配準操作。

目前常用的精配準算法有Besl 等于1992 年提出的迭代最近點（Iterative Closest Points，ICP）算法［6］，該算法精度高、容易實現，但對初始位置要求較高。為此，國內外研究人員對該算法進行了許多改進，戴靜蘭等［7］提出了一種基于曲率特征點和K-D樹搜索改進的ICP算法，提高了ICP配準的精度，但當待配準點云數據過大時，該算法配準效率較低；李若白等［8］提出了一種基于特征點法向量夾角的改進點云配準算法，一定程度上減少了配準算法的迭代次數。此外，還有PICP（Probability ICP）［9］、MICP（Modified ICP）［10］和CICP（Cluster ICP）［11］等許多變種算法。

本文結合線掃LiDAR 設備采集數據的特點提出了一種基于點密度調整的激光雷達點云配準改進方法，可有效提高配準精度，減少配準耗時。

2 算法設計

本算法首先將輸入點云分割為彈性超體素框架，以超體素為節點構建K 最近鄰圖（K nearest neighbor，KNN）。然后使用該彈性框架來約束重采樣過程，使原先條紋狀點云更加均勻地分布。最后，以重采樣的點云為輸入，通過ICP 算法實現點云配準。

2.1 點投影重采樣

點云重采樣算法流程圖如圖1 所示。第一階段是利用八叉樹算法對點云進行子集抽樣，從而根據八叉樹節點計算靈活的支撐點。基于這些支撐點，實現基于分割的區域生長生成超體素，將其視為節點，進一步生成作為彈性框架的K 最近鄰（KNN）圖［12］。在第二階段，使用基于超體素的框架來約束重采樣過程。重新采樣點被插入框架的網格中，并被調整為沿著法向量方向投射到場景表面上。然后，所有插入點的分布根據一個能使點均勻分布的能量函數進行細化。基于超體素的圖就像一個篩子，使用迭代方法均勻分配重采樣點的分布。

圖1 基于點密度調整的激光雷達點云配準流程圖

建立約束框架：超體素是一種過度分割的結果，將局部一致的點聚集成許多塊。種子點的選擇至關重要，為了得到較為一致的分割結果，很多方法采用平坦區域的點作為種子點［13］，但是這些方法對于突出結構會失去適用性。因此本文采用八叉樹提取種子點。

假設輸入點云P={p1,p2,…,pn}，一個自適應八叉樹可以提取其中一組葉子節點L={l1,l2,…,ln}作為種子點，大致表示場景的結構［14］。使用包含P的最小三維邊界框作為根節點。然后，根節點被細分為8 個子立方體，大小相同，這樣遞歸地進行空間分解以分割非空立方體，直到滿足閾值標準或達到最小體素大小［15］。只有滿足特定深度的八叉樹節點才會被選作超體素的初始聚類中心。

其中的乘數5 是一個經驗值，它加強了空間鄰近度的權重，以產生更為緊湊的體素形狀。基本上，λDS的值應接近1。

在一個超體素中心周圍2w*2w*2w（w=W/2Dept?）的三維空間中尋找相似的點。一旦每個點都與最近的一個節點相關聯，一個迭代步驟將每個聚類中心的位置Vj=[x,y,z]T和法向量nVj=[nx,ny,nz]T更新為屬于該聚類的所有點的平均值。新的聚類中心與原聚類中心之間的空間距離即為殘差。當收斂時，較大的體素通過移動擴大出現在平滑區域，較小的體素通過移動收縮出現在邊緣和角落，而均勻區域的體素大小相似。在模型中，體素可以看作是一個緊湊的表面貼片，一個體素表示模型中的一個節點。然后在歐幾里得空間中建立一個KNN 圖，該圖被作為一個約束框架，為后續重采樣提供鄰近點關系。

插入重采樣點：重采樣階段包括兩個步驟：一是獲取插入點的初始位置；二是優化數據點的全局分布，如圖2 所示。對于一個給定的超體素節點集合V={V1,V2,…,Vm} ，定義某個節點Vi和它的鄰域集合NVi的最大間隙的中點為p0i，利用鄰域點集的法向量的平均值來估計初始的法向量npi。上述的最大間隙被定義為以Vi和它的領域集合NVi中的某點作為直徑的兩個端點構成的最大圓形區域，且該區域內沒有其他點。當場景表面是彎曲形狀時，中點pi0并不總是在表面上，如圖2（a）所示。因此，需要將插入點投影到場景的潛在表面，以獲得實際位置。投影移動是通過沿著法線方向npi移動距離Δ來實現的：

圖2 重采樣點的插入過程

到目前為止，只考慮體素節點之間的約束，插入點的分布并不理想，如圖2（b）所示，需要作均勻優化。

優化點云分布：對于給定的超體素集合V和上一步得到的插入點集P′，目標是通過最小化能量函數式（7）來調整插入點位置，使其均勻分布：

其中：

迭代公式中第一項實現對離群值和數據噪聲的抑制，第二項反映采樣點受到的框架約束的調整，系數μ用于平衡這兩項。求解最小化能量函數為迭代優化過程，如式（10）所示。收斂時pk+1i為重采樣點的最終位置，最終得到完整的重采樣點云數據，如圖2（c）所示。

2.2 點云配準

本文使用重采樣后的優化點云數據作為配準的輸入數據。配準的關鍵是如何得到坐標轉化參數旋轉矩陣R和平移矩陣T，使得兩視角下測得的匹配對應三維數據經坐標變換后的距離最小［16］。

經典ICP 算法是一種迭代縮小的方法，通過最小化重疊區域之間的歐氏距離誤差度量來尋找兩個數據集之間的最優配準參數［17］。若存在兩個完全對應的點集P（點數Np）和X（點數Nx），點集內點數相等（Np=Nx）且匹配對應。

ICP配準流程如圖3所示：

圖3 ICP算法流程圖

1）通過重采樣得到目標點云P（點數Np）和參考點云X（點數Nx）；

2）在點云P中尋找特征點集F并初始化；

3）計算點集F在點云X中的最近點Y；

4）計算坐標轉化參數向量和誤差(q,dms)；

5）判斷誤差是否收斂，如果dk-dk+1<ε，ε為設定值且ε>0，滿足閾值條件，則收斂，否則跳轉至步驟3）繼續迭代計算；

6）得到最終坐標變換矩陣R和T，完成配準。

ICP 算法在較好的初值情況下，可以得到很好的算法收斂性以及精確的配準結果。但ICP 算法對初始配準條件要求相對嚴格，要求待配準點云的重疊度很高，否則容易陷入局部最優陷阱。此外，ICP 算法魯棒性較差，異常點對掃描匹配影響較大，因此本文對輸入點云進行重采樣，以提高點云數據的質量。

3 實驗結果與分析

為驗證基于點密度調整的激光雷達點云配準改進方法的優勢，利用三維點云模型進行重采樣實驗，將未經過點密度調整算法處理和處理過的數據分別采用經典的ICP 算法和標準3D-NDT 算法［19］進行配準，對比實驗結果。

3.1 ICP配準對比實驗

實驗測試的點云數據由Velodyne 公司的VLP-16型線掃激光雷達采集得到。一組輸入點云配準前的位姿如圖4 所示，紅色數據點是目標點云，包含21112 個數據點；黑色數據點是源點云，包含15282 個數據點。墻面存在著明顯條紋式的結構，數據點分布較為離散。

圖4 初始點云位姿圖（ICP）

首先直接使用原始數據進行ICP 配準，得到的配準結果如圖5（a）所示，子圖（b）和（c）為配準結果的細節圖。該算法耗時為5418.31ms，配準迭代次數為45 次。由于線掃機制造成的條紋狀結構，直接進行ICP 配準算法得到的配準效果并不好，如（b）處門框存在較明顯的錯位，（c）處墻面沒有對齊。

圖5 ICP配準結果

使用重采樣點云配準的結果如圖5（d）所示，（e）、（f）為同位置結果對比。本算法總耗時4243.34ms，其中包含點密度調整處理耗時2018ms、ICP 配準耗時2225.34ms，配準迭代次數為18次。

可以看到重采樣的點云固有結構并沒有較大的改變，但原先突兀的條紋狀結構得到了一定的改進。這是因為重采樣處理減少了線掃雷達方位角方向數據點密集排布的趨勢，而在俯仰角方向的條紋間隙間均勻插入了較多數據點，整體上降低了輸入點云的數據量。經過點密度調整后，ICP 配準時間縮短至未重采樣點云的41%，配準算法迭代次數大大降低，提高了運行效率。兩種算法的詳細對比數據如表1所示。

表1 不同ICP算法的配準結果比較

3.2 3D-NDT配準

除了使用ICP 算法驗證外，本文還測試了重采樣點云對于NDT配準算法的影響，如圖6所示。子圖（a）顯示了原始點云配準前的相對位姿關系，目標點云包含10258個數據點；源點云包含4108個數據點。

圖6 NDT算法配準結果

直接使用原始數據進行NDT 配準，得到的配準結果如子圖（b）所示。顯然，未經過點密度調整的點云并不能在規定的20 次最大迭代次數內完成配準。經過密度調整算法處理得到的配準結果如子圖（c）所示。該算法總耗時1864.63ms，其中包含點密度調整處理耗時1212ms、NDT 配準耗時652.63ms，配準迭代次數為19 次，配準誤差21.94cm。配準數據統計如表2所示。

表2 不同NDT算法的配準結果比較

超體素的框架建立可以被看作是散點數據到數據“骨架”的過渡，相當于是一種從粗到細的機制。均勻密度調整算法可以被看作往抽象的數據“骨架”的表面填充均勻數據點的過程，從而使結果趨向于補償線掃激光雷達的稀疏數據，削減局部密集的冗余數據。在總體上，使數據近似呈現出更加均勻的正態分布，提高了NDT 算法的配準效率和精度。此外，該方法也提供了更加豐富的局部表面信息，有助于局部特征提取、法向量估計等工作。

本文方法也存在一個問題：該算法不能確定一個小的間隙和孔是真實存在的空洞，還是掃描時數據缺失。因此，一些實際存在的空隙可能會在重采樣時被填補；一些數據點會被誤插入到墻角之間，影響配準精度。為了解決該問題，未來的工作可能是先從點云數據中識別出空隙、墻面等結構，再進行重采樣點的插入和密度調整。

4 結語

點云配準是三維重建的關鍵環節，決定了后續工作的準確性。線掃激光雷達由于機械式的旋轉掃描機制，采集的點云數據會呈現明顯的環形條紋結構。本文提出了一種基于點密度調整的激光雷達點云配準改進方法。將輸入點云分割為超體素框架，然后使用該彈性框架來約束重采樣過程，使點云分布更加均勻合理。實驗表明，通過點密度調整算法處理的數據，能提高經典ICP 和3D-NDT 算法的配準精度，減少算法迭代次數，提高配準效率。