基于線特征及迭代最近點算法的地基建筑物點云自動配準方法

徐景中，王佳榮

（武漢大學遙感信息工程學院，武漢 430079）

（?通信作者電子郵箱jz_xu@whu.edu.cn）

0 引言

由于掃描視角的限制，利用地基激光掃描設備進行地物目標三維點云采集時，通常需要設置多個測站才能獲取到完整的目標點云。由于不同視角采集到的點云并不在同一個坐標系下，通常需要將點云旋轉、平移到統一的坐標系，才能得到完整的地物數據，因此需要進行點云配準處理。

點云配準方法目前主要包括：人工配準方法和自動配準方法。雖然人工方法通過人為選取同名特征進行匹配，能可靠地得到配準結果，但精度有限，且耗時耗力；因此，近年來越來越多的學者開始研究自動配準方法。考慮到點云與點云之間缺乏嚴格意義的同名點，點云自動配準方法又可以分為基于迭代最近點（Iterative Closest Point，ICP）算法的點云配準方法［1］以及基于特征的點云配準方法［2-3］。前者是利用數學方法迭代尋找兩組點集之間的最小距離作為最佳位置，點對的匹配度高，但其存在對初始點云的位置條件要求苛刻、易陷入局部最優等不足。對此，部分學者從配準效率入手進行ICP 算法的改進，如：楊帆等［4］在ICP 算法中引入kd-tree 來提高最近點的搜索速度，而周春艷等［5］采用主成分分析（Principal Component Analysis，PCA）變換，Du 等［6］采用仿射法等方法，這些研究也只是解決了部分問題，仍存在配準完成度低的問題。而基于特征的點云配準方法則是從點云中提取點特征、線特征或面特征，然后通過特征匹配完成點云配準。如：沈長江等［7］、趙明富等［8］直接從點云中提取快速點特征直方圖（Fast Point Feature Histogram，FPFH），然后基于FPFH 特征相對關系進行點云配準；但此類基于點特征的配準通常存在受噪聲影響較大、時間復雜度較高等問題，因此，部分學者通過構建點的域拓撲信息來提取幾何特征，然后基于域特征優化點云配準過程［9］，在一定程度上改善了對噪聲的敏感性，但仍存在魯棒性低的問題。Aiger 等［10］基于共面四點對的仿射不變性，實現了四點全等集合（4-Points Congruent Sets，4PCS）點云配準方法，該方法不需要計算復雜的幾何特征，效率較高；但對于點云重疊率較低的情況，算法耗時長且配準容易失敗。相較于點特征，線特征幾何拓撲穩定性更高，配準結果也更加可靠。Jaw 等［11］提出了一種基于三維直線特征的地面激光雷達點云配準方法，該方法包括三個主要步驟：基于平面擬合相交的三維直線特征提取、基于直線夾角的相似性匹配和基于四元數的多站激光點云配準。王永波等［12］通過平面相交得到線特征并將其作為激光點云配準的基元，利用線特征約束的四元數法構建參數解算模型。此類方法可以快速實現點云配準，但由于提取的線特征的完整性和精確性是有限的，配準結果精度仍需提高。由于面特征包含的信息多于點、線特征，面特征配準方法受噪聲影響較小，部分學者使用最小二乘法、隨機樣本一致性算法［13］和主成分分析方法［14］等曲面擬合方法進行特征面提取，以提高配準精度；但此類方法，要求兩組數據重疊區域必須包含許多面特征，否則很難保證配準的準確性。

基于上述分析，本文提出了一種基于線特征及ICP 算法的建筑物點云自動配準方法，該方法包括基于線特征的點云粗匹配以及基于ICP 的點云精匹配過程。該方法利用線對作為配準基元，以線對夾角和距離作為相似性測度，可以提高配準結果的可靠性；此外，采用由粗到精的配準策略，不僅能改善ICP 算法易陷入局部最優的不足，同時可以保證點云配準的精度。

1 本文方法

1.1 點云特征線提取1.1.1 點云平面分割

點云平面分割，主要是基于點云局部特征的一致性進行區域增長，將建筑物墻面、屋頂區域分割成多個同質區域。考慮到待分割目標為平面上的點，為了快速得到建筑物點云的平面區域，本文首先利用建筑物點云構建kd-tree［15］，在此基礎上通過PCA 變換分析方法估算點云的法向信息［16］，然后從任一種子點開始，以法向一致性進行鄰域點的判斷，實現平面區域增長。區域增長條件可表示為：

其中：pi為種子點；pj為鄰域點；Npi與Npj分別為兩點處的法向量；thdvv為頂點距離閾值；thθ為法向夾角閾值。

由于區域增長過程中種子點的選擇具有一定的隨機性，上述區域增長結果中，通常會存在同一個平面被分割成多塊的現象，因此，需要進行區域合并處理。合并過程如下：對于平面Ri中的每個點pi，遍歷其鄰域中所有點，如果其鄰域點所屬的平面號和當前點pi不同，則認為該鄰域點所屬的平面為當前點所在平面的相鄰平面，若二者法向夾角小于夾角閾值thθ，則進行合并處理。

1.1.2 特征線提取及優化

雖然建筑物點云不僅包含屋頂區域，還包括墻面、窗戶等區域，經過平面分割處理，各部分基本得到有效分割，為了提取不同區域點簇的特征線，本文直接采用Alpha-shape 算法［17］進行區域輪廓線的提取，在此基礎上通過拆分處理得到平面區域特征線。Alpha-shape輪廓線提取過程如下：

1）對于平面點簇S，設定半徑閾值α。

2）選取S中任意兩點pi、pj，若其連線的長度小于2*α，則根據幾何關系可計算過pi、pj圓周的圓心。

3）若點簇S中存在與圓心的距離小于α的點，則表明pi、pj非輪廓點；否則標記pi、pj為輪廓點，其連線即為輪廓線段。

4）繼續按步驟2）～3）搜索判斷其他點，直到所有點均被處理時停止。

為了便于后續特征線匹配，本文對輪廓線提取結果進行分段和擬合處理得到特征線段。分裂時，利用輪廓線上距離首尾端點所連直線的最大偏差點，將輪廓線拆分成多個子線段；然后，采用最小二乘法擬合方法［18］對輪廓點進一步擬合得到特征線段。

考慮到激光掃描的隨機性以及點簇噪聲的影響，上述特征線提取結果中，通常會存在因點云分布不均勻或小平面導致的冗余特征線，需要進一步進行優化處理。

1）短線剔除處理。若線段長度小于閾值Th_L，或相鄰線段之間角度小于閾值Th_θ，則剔除短線。

2）冗余線段合并。如圖1 所示，若線段Li與線段Lj滿足如下條件，則進行合并處理。

其中：dLi和dLj分別是從原點到Li和Lj所在直線的距離；L是投影區域長度；ε為比例系數；max{dprj}為Lj的兩個端點與線段Li的垂直距離最大值；davg為該組點云的平均點間距。

合并處理時，將Lj端點投影在線段Li上，并取4 個端點中距離最遠的兩個點更新Li的端點：若Li距離較遠的端點包含線段Lj投影端點，則將Lj的投影端點作為Li新的端點，圖中L*線段為線段合并后得到的新線段。

圖1 冗余線段合并示意圖Fig.1 Schematic diagram of redundant line segment merging

1.2 點云配準

1.2.1 配準基元和相似性測度

三維空間中，若要解算兩組點云的有效變換矩陣，至少需要兩對非平行直線。為了保證匹配的可靠性，本文針對上述優化處理的結果，進一步篩選有效的特征線對作為配準基元。若相鄰線段滿足以下條件，則該配準基元有效。

如圖2所示，d為相鄰線段最鄰近端點的距離，θ表示兩條相鄰線段的夾角。

圖2 配準基元示意圖Fig.2 Schematic diagram of registration primitive

而同名特征的判斷，以線對夾角和線段長度作為相似性測度。對于兩組點云p和q，L1表示線對中長線段的長度，L2表示線對中短線段的長度，dp和dq分別為兩組點云的平均點間距。如果兩組點云中的線對滿足式（4），則將其視為同名線對。

1.2.2 點云粗配準

根據相似性測度，在兩個待配準點集中尋找同名線對，并以線對的端點作為同名點，解算最終變換模型。為得到最優變換關系，本文采用如下方法迭代遍歷兩組點集中的線對，得到最佳的匹配結果：

1）基于兩組點集中的配準基元，利用相似性測度在兩組點集中查找匹配同名線對，并以線對端點坐標，采用四元數法［19］解算初始變換矩陣。

2）利用初始變換矩陣處理待配準點集中的線特征，將待配準點集轉換至目標點集中。

3）統計變換后的待配準點集與目標點集中同名線段的個數。

4）重復步驟1）～3），逐個遍歷點集中的配準基元，得到變換后的待配準點集與目標點集中同名線對的個數，取同名線對數目最多時的變換矩陣作為最優匹配結果。

5）為了使剛性變換矩陣解算結果更加準確，利用所有同名線段的端點坐標解算變換矩陣，并以此作為點云粗配準結果。

1.2.3 點云精配準

考慮到基于點云的特征線的提取會存在一定的誤差，因此本文在基于特征線匹配的基礎上，進一步采用ICP 算法進行兩組點集的迭代配準，以提高配準結果的精度，步驟如下：

1）對于粗配準點集P和Q，在點集P中尋找與Q對應的點，生成對應點對。2）通過四元數法計算旋轉平移的6個參數及變換矩陣R。3）對點集P使用上述變換矩陣R進行旋轉和平移，得到新的點集P'。

根據點集P'和Q中的對應點的平均距離來確定是否繼續迭代。因此，求解最佳變換矩陣的問題，可以轉化為計算使f(R，T)的值最小時的旋轉矩陣R和平移矩陣T；

4）若繼續迭代，更新待配準點云的位置，繼續步驟1）；否則結束迭代，得到最終的配準結果。

2 實驗與結果分析

為了驗證本文算法的有效性，采用了兩組具有不同重疊度的建筑物點云數據進行實驗。兩組數據均是利用地面激光雷達設備從不同角度采集的建筑物點云，為部分重疊點云，其中點集Ⅱ的重疊區域較小，受遮擋嚴重，點云渲染結果如圖3所示。兩組點云的統計信息如表1 所示，由表1 可以看出：點集Ⅰ的最大平均間距為0.053 m，點云密度較為稀疏，而點集Ⅱ的最大平均點間距為0.019 m，點云相對稠密。

圖3 實驗區域點云渲染效果圖Fig.3 Rendering effect diagrams of point clouds in experimental regions

表1 點云信息統計Tab.1 Statistical information of point clouds

圖4 是兩組點云的平面分割結果，為了便于說明，此處只針對每個數據集的左站點云處理結果進行展示分析。圖4中，圖（a）、（c）是直接基于點云法向一致性進行區域增長的結果，從圖中可以看出，很多共面區域被分成了多個小面片，由于該方法的區域增長范圍被限制在該平面初始種子點的周圍，因此提取得到的小平面呈現出以初始種子點為圓心的圓形區域，對此需要進行區域合并處理；圖（b）、（d）為基于平面法向的平面區域合并結果，可以看出，位于同一平面上的多個小平面已經被正確合并，形成較為完整的墻面，墻面結構更加清晰。

圖5 是兩組點集的直線段提取結果，其中：圖（a）、（c）是直接基于投影點集提取的直線段，圖（b）、（d）為優化后的直線段結果（Th_L=0.5，Th_θ=10，ε=0.05）。從圖5（a）、（c）中可以看出，兩組點云中均提取了豐富的結構信息，提取的結果能基本反映出建筑物表面的細節信息，但由于平面分割等因素，特征線中存在冗余線段；從圖5（b）、（d）優化結果可以看出，優化后冗余線段被有效合并，短線被正確剔除，特征線更加簡潔，能清晰表達建筑物屋頂及墻面特征。

基于特征線提取結果進行同名線段的匹配，匹配結果如表2 所示。從表2 中可以看出，數據集I 中大部分特征線得到有效匹配，而數據集Ⅱ由于重疊區域較少，雖然左右測站具有豐富的線特征，但尋找到的同名線段數目較少，只有23 對正確匹配的同名線段。

圖4 點云平面分割結果Fig.4 Plane segmentation results of cloud points

圖5 特征線段提取結果Fig.5 Extraction results of feature line segments

表2 線段提取及匹配結果統計Tab.2 Statistics of extraction and matching results of feature line segments

圖6 為建筑物點云配準結果圖，圖（a）為數據集Ⅰ的配準結果，圖（b）為數據集Ⅱ的配準結果。從圖6 中可以看出，兩組數據集重疊區域均正確地重疊在一起。

圖6 點云配準結果Fig.6 Registration results of point clouds

圖7 為配準結果局部剖面圖，從圖7 中可以更清楚地看出，不同測站的墻面點云較好地吻合在一起，表明實驗區域點云得到較好的配準。

圖7 配準結果局部剖面圖Fig.7 Part sectional drawings of registration results

為了進一步驗證方法的性能，將本文方法配準結果與經典ICP 算法結果進行對比分析。由于兩組數據集均為部分重疊，經典ICP 算法不能收斂到正確位置。本文以手動給定位置初值的ICP配準結果作為參照，分析經典ICP算法以及本文方法的配準結果，并統計配準結果對應點之間的最大距離誤差、平均距離誤差以及均方根誤差（Root Mean Square Error，RMSE）。RMSE計算式如下：

其中：g是點集數量；di是本文方法與手動配準結果的對應點的距離。

點云配準誤差統計分析結果如表3 所示。從表3 中可以看出，經典ICP 算法配準結果與手工初值的配準結果具有較大誤差，特別對于數據集Ⅱ，RMSE 達到0.245 m，表明對于部分重疊的建筑物點云，經典ICP 算法難以收斂到正確的位置；而本文方法結果與經典ICP 算法結果相比，配準精度有了明顯提高，兩組數據集的平均誤差分別為0.042 m 和0.044 m，表明基于特征的粗配準方法與手工給定初值的配準方法得到的結果精度相當，基于特征的粗配準能為ICP 配準提供有效的初值位置，提高ICP算法的穩定性。

表3 點云配準誤差統計分析 單位：mTab.3 Statistics and analysis of registration errors of point clouds unit：m

此外，對比點云信息統計表1以及點云重疊情況（見圖4）可以發現，在平均點間距方面，數據集Ⅰ大于數據集Ⅱ，但二者的RMSE 相當，分別為0.051 m 和0.053 m，分別為其點云最大平均點間距的0.96倍和2.79倍，表明點云配準精度不僅與點云密度相關，還受到點集重疊區域大小影響，點云密度越高，重疊度越大，配準結果的可靠性越高。

3 結語

地基建筑物點云配準對于獲取完整的建筑物信息、構建建筑物三維模型具有重要意義。本文在分析點云配準現狀的基礎上，根據優勢互補的思想，提出了一種基于線特征及ICP算法的地基建筑物點云配準方法。該方法在建筑物點云平面分割的基礎上，通過輪廓線檢測以及分裂擬合處理，得到建筑物豐富的特征線；然后，以特征線對作為配準基元，根據線段夾角及距離等相似性測度實現點云的粗匹配，在此基礎上利用ICP 算法完成建筑物點云精確配準。通過兩組實地數據進行實驗驗證，實驗結果表明，基于線特征的由粗到精的點云配準方法能改善ICP 算法對點云初值的依賴，特別是可以克服ICP 算法針對部分重疊區域點云易陷入局部最優的不足，提高了配準方法的穩定性。下一步研究將集中在地物其他特征的提取及匹配方面，以降低方法對線特征的依賴，提高其通用性。