基于ISS-CPD 算法的三維激光點云數據處理技術

白光亞,宋 濤,李 丹,成七一

1.國家電網有限公司直流建設分公司,北京100032

2.北京恒華偉業科技股份有限公司,北京100032

隨著社會的發展和城市的進步，數字城市的概念逐漸普及。在構建數字城市的過程中，不可避免地要構建三維建筑模型[1]。三維激光掃描作為一種新興的測繪技術，可以從目標對象的表面收集大量的點云數據，它具有非接觸、高精度和高速度的特點。這些點云數據真實和準確的反映了物體表面的實際狀態，并為重建物體的數三維模型提供了新的構想。因此，該技術廣泛用于數字城市、文化遺產保護和考古測繪等諸多領域[2]。如何處理大量點云數據，獲得高質量點云并提高數字模型重構效率，是當前研究的熱點和難點。

目前，國內外研究人員對基于三維激光云數據的快速提取方法進行了大量的研究。在文獻[3]中，根據現有的二維GIS 數據，結合在現場采集的建筑物高程和紋理信息，構建建筑物的三維模型。在文獻[4]中，對通過車輛激光掃描系統獲得建筑物的點云數據進行了研究，提出了一種從未校正的距離影像中提取建筑物信息的方法。在文獻[5]中，利用地面激光掃描儀獲取城市大型復雜建筑的三維空間信息，建立三維數據模型。在文獻[6]中，在分析車載激光點云掃描特性的基礎上，提出了一種點云過濾方法。使用此方法提取建筑物的垂直點信息，同時提取建筑物立面的詳細特征。這些研究為基于三維激光點云數據的建筑物快速提取方法提供了理論基礎。

在此基礎上，本文提出了一種基于ISS（Intrinsic Shape Signature）特征點的快速CPD（Coherent Point Drift）建筑物LiDAR（Light Detection and Ranging）點云配準算法。通過ISS 算法提取點云數據的特征點，并通過CPD 算法對這些特征點進行配準。并通過實驗對該算法有效性進行驗證。

1 配準算法

myronenko 和song 在概率統計的基礎上提出CPD 配準算法，與ICP 算法相比，提高了抗噪聲和異常點的能力[7]。但是，CPD 算法計算復雜，不適合大規模點云數據。針對建筑點云數據的大規模，提出了一種結合ISS 算法和CPD 算法用于建筑物LiDAR 點云配準，利用ISS 算法提取點云數據的特征點，這些特征點在通過CPD 算法進行配準，提高運算效率。

1.1 ISS 算法

特征點(也稱為關鍵點或興趣點)是設置在點云上的穩定且獨特的點集，是連續且穩定的結構點。在本文中，通過ISS 算法提取點云數據的特征點。

設置點云數據的總數n，(xi，yi，zi)，i=0,1,…,n-1，其中，記pi=(xi，yi，zi)。

（1）定義了點云上各點pi的局部坐標系，并給出每個點的搜索半徑r。

（2）對點云數據中的每個點pi在半徑r范圍內的所有點查詢，并計算其權重，如式（1）所示[8]。

（3）根據式（2）對各點pi的協方差矩陣進行計算[9]。

（4）對各點pi的協方差矩陣特征值進行計算{λ1 i,λ2 i,λ3 i}，并按大小順序排列。

（5）設置閾值ε1與ε2，如果滿足，則將其視為關鍵點。

1.2 ISS-CPD 算法

根據建筑物結構的規律性，提出了一種結合ISS 算法和CPD 算法點云配準算法。CPD 算法是一種概率點集配準算法，可以看作速度場運動的一致性約束極大似然估計問題。用變分法表示運動的一致性約束，得到規則化極大似然估計[10]。該算法以兩個點云數據集的配準為概率密度估計問題，以一組點云數據集為高斯混合模型的質心。另一組為其數據。最大似然估計是通過EM（Expectation Maximization）優化，找出這兩個點集之間的關系，即核心點集到數據點集的配準。首先使用ISS 算法提取建筑物點云的特征點，保持建筑物的結構特征，使用傳統CPD 對這些特征點進行配準，降低復雜度和提高配準效率。ISS-CPD 配準算法的具體步驟如下。

步驟1：選擇兩個視角LiDAR 點云重疊區域。

步驟2：使用ISS 算法提取關鍵點。

步驟3：初始化參數旋轉變換矩陣R、平移向量t、尺度參數s、高斯函數協方差δ2的值。

步驟4：計算后驗概率p(m|xn)和相關概率矩陣。

步驟5：EM 算法求解參數R、s、t、δ2；

步驟6：判斷概率P是否收斂。如果沒有，返回到步驟4 直到它收斂。

步驟7：將R、s、t參數用于建筑物達點云數據A、B，并完成配準。

2 結果與分析

實驗數據由奧地利Riegl 公司制造的VZ-400 激光掃描儀獲得。掃描密度為垂直和水平方向上各0.05 度，掃描頻率為300 Hz。點云數據中兩個采樣點間距約為8 cm。使用matlab 實現該算法。在該實驗中，從兩個不同的角度對選取的建筑物進行點云配準，分別為建筑物1 號和2 號。如圖1 所示，左側兩個分別為1 號和2 號。左側兩幅和右側兩幅分別是從A、B 視角采集的建筑LiDAR 點云數據。

圖1 不同視角Li DAR 點云數據Fig.1 Li DAR point cloud data from different perspectives

由圖1 可知，其中1 號幾乎重疊（無噪音），而2 號重疊區域包含更多的樹和草（更多的噪音）。圖2 所示為建筑Li DAR 點云的重疊區域。從上到下為1 號和2 號建筑，左側和右側分別為從A、B視角獲得的建筑Li DAR 點云數據。

圖2 Li DAR 點云數據重疊區域Fig.2 Li DAR point cloud data overlapping regions

通過ISS 算法從重疊區域提取特征點，結果如圖3 所示。在圖中，左側兩幅對應的是1 號和2號，左側和右側分別為從A、B 視角獲得的建筑Li DAR 點云數據。

圖3 ISS 算法在重疊區域提取的特征點Fig.3 Feature points extracted by ISS algorithm in overlapping regions

如圖3 所示，在1 號建筑物重疊區域提取的點云數分別為視角A 的12702 和視角B 的11197，2號建筑物點云數分別為視角A 的105154 和視角B 的92559。ISS 提取特征點的個數為1 號建筑物視角A 的837 和視角B 的998，2 號建筑物的視角A 的5265 和視角B 的5057。

為了驗證改進算法的準確性和有效性，與傳統的CPD 配準算法進行比較。迭代次數設置為100，收斂閾值設置為1×10-8。圖4 所示配準結果。左側兩幅對應的是1 號和2 號，在右側是本文提出ISS-CPD 算法提取。表1 所示這兩種配準算法的執行時間。

圖4 改進前后配準結果比較Fig.4 Comparison of registration results before and after improvement

表1 算法配準時間比較Table 1 Comparison of algorithm registration times

將ISS-CPD 算法配準得到的參數用于建筑物的整體LiDAR 點云數據。結果如圖5 所示，從左到右，對應的是1 號和2 號。

圖8 改進前后配準結果對比Fig.8 Comparison of registration results before and after improvement

實驗結果表明，該配準算法比傳統配準算法具有更高的效率。與傳統的算法相比，該算法提取特征點所需的時間可以忽略不計。改進算法的執行時間比傳統算法要短得多，運行時間僅為傳統CPD算法的 1/320左右。

3 結論

本文提出了一種結合ISS 算法和CPD 算法用于LiDAR 點云配準。通過ISS 算法提取了點云數據的特征點，并通過CPD 算法對這些特征點進行了配準，大大提高了算法的效率。實驗驗證了算法的有效性，結果表明，改進算法的配準效率高于傳統算法。考慮到目前的實驗室設備和數據規模，本文還處于起步階段。在此基礎上，逐步改進和完善將成為下一步工作的重點。