機載LiDAR數據建筑物頂面點云分割方法研究

于海洋,余鵬磊,謝秋平, 李 寧,盧小平

(1. 河南理工大學 礦山空間信息技術國家測繪地理信息局重點實驗室，河南 焦作 454000； 2. 河南理工大學 礦山空間信息技術河南省重點實驗室，河南 焦作 454000)

一、引 言

機載激光雷達(airborne light detection and ranging，LiDAR)能夠快速、精確地獲取建筑物的頂面信息，為建筑物三維模型重建提供了有效的數據支持。在模型構建過程中，對建筑物頂面進行精確分割，進而通過擬合建筑物中各個部分來獲得最可靠的多面體模型，可實現建筑物的精確、快速重建。

目前，建筑物頂面分割算法主要有隨機抽樣一致性(random sampling consensus，RANSAC) 算法、聚類算法、區域增長算法、3D 霍夫變換(3D-Hough transform)等[1]。RANSAC 算法通過迭代方法抑制點云噪聲，但其模型參數的確定存在困難[2]。對于大范圍建筑物的提取，建筑物形式各異，面片大小不同，難以采用統一的參數對所有建筑物進行面片分割處理，同時迭代運算計算量大[3]。聚類算法需要建(構) 筑物模型先驗知識，往往難以獲得，導致模式聚類中心不穩定，且算法過于復雜[4]。3D 霍夫變換頂面分割方法是將傳統的二維圖像霍夫變換拓展到三維點云參數空間，生成所有可能的平面，統計平面中點的個數來確定分割平面，此方法易產生偽平面，計算量大，速度慢[2]。區域增長算法復雜度低，計算速度快，但該方法對種子點選取及特征參數的設置要求較高。本文通過點云數據法向量的分析建立了一種建筑物頂面區域增長分割種子點選取和特征參數的設置方法。

二、點云法線與曲率計算

表面法線是幾何體表面的重要屬性，在計算機圖形學等眾多領域應用廣泛。對于一個已知的幾何體表面，獲取的點云數據集表現為一組特定樣本，根據垂直于點表面的矢量推斷表面某一點的法線方向方法較多[5]，一般分為兩大類：一是使用曲面重建技術，從獲取的點云數據集中擬合采樣點對應的曲面，然后從曲面模型中計算表面法線；二是直接從點云數據集中近似推斷表面法線。本文擬采用第二種方法，已知一個點云數據集，在其中的每個點處直接近似計算表面法線[6]。該方法估計一個點的表面法線時，首先需要從周圍支持這個點的鄰近點搜索著手，確定某點的鄰域點集，以此為基礎采用主成分分析法計算法線和曲率。

1. 鄰域點集的確定

本文選用了近似快速最近鄰搜索算法FLANN[7]。FLANN算法采用分層K均值樹和多重隨機k-d樹實現，并能根據用戶輸入的高維數據和設定的準確度自動選取最優搜索算法和參數。

在實際應用中確定查詢點pq的鄰域點集Pk主要有兩種途徑：一是確定與查詢點最鄰近的k個點，即k_search算法；第二種是確定與查詢點距離在半徑r之內的所有k個點，即r_search算法。

LiDAR點云數據空間分布不均勻，密度變化較大(如植被點云)，r_search算法計算結果不穩定，k_search算法固定搜索一定數量鄰近點，法向量計算結果較優。

2. 法線計算

確定表面某點法線的問題近似于估計表面的一個相切面法線的問題，因此可轉化為一個在鄰域點集Pk中最小二乘平面擬合問題[5]。平面可采用點x及該點法向量n表示，點pi∈Pk到平面的距離為

di=(pi-x)·n

x和n采用最小二乘法計算，因此di=0。x定義為點集Pk擬合平面的中心，即

估計表面法向量n的問題可采用主成分分析法來解決。通過計算一個協方差矩陣C∈R3×3的特征矢量和特征值來獲得n，這個協方差矩陣從查詢點的鄰近點集Pk中創建。對于每一個點pi,對應的協方差矩陣C為

式中，ξi表示pi的權重，一般設定為1；vj是第j個特征向量；λj是協方差矩陣的第j個特征值。C是對稱、半正定的矩陣，其特征值λj為實數，正交標架下的特征向量vj對應著Pk的主成分[5]。如果0≤λ0≤λ1≤λ2，最小特征值λ0的特征向量v0即近似于+n={nx,ny,nz}或-n。另外，n也可表示為球面坐標系統中的一對角度(φ,θ)，即

協方差矩陣C的計算受噪聲的影響較大，可采用基于最優擬合面的協方差矩陣C來消除噪聲的影響[6]，即不再采用最小二乘擬合切平面，而是尋找最優平面模型，根據點到最優平面的距離di將鄰域Pk中的點分為內部點(di≤dmax)和外部點(di>dmax)，在計算協方差矩陣C時，內部點和外部點采用不同的權重ξi

圖1 LiDAR數據法線計算

3. 曲率估計

主成分特征分析既可以用于表面法線估計，也可以用于給定點pq的表面曲率的推算。該方法采用協方差矩陣C特征值λ作為p點曲面變化度的近似。如果λ0=min(λi)，p點沿曲面法線n的變化度可表示為

最小特征值和所有特征值總和的比值可近似表示以點p為中心的鄰域Pk的曲率變化大小，并且該比值具有尺度不變性[8]。較小的σp值意味著鄰域Pk中的所有點位于表面的切平面上，因此在建筑物頂面分割區域增長算法中選取具有最小曲率的點作為種子點。

三、區域增長分割算法實現

1. 區域增長分割

區域增長分割算法實現流程如圖2所示。首先，按照點云曲率的大小對點云進行排序。具有最小曲率的點最有可能位于平面上，因此可選作區域增長算法的種子點。具體區域增長算法實現過程如下。

1) 選取未處理點云中具有最小曲率的點作為種子點。

2) 搜索種子點鄰近點云，對比每個鄰近點與種子點的法向量和強度值差，如果兩者之間的角度差φ和強度值差I小于設定閾值，則將該鄰近點添加到該區域中。

圖2 區域增長分割算法流程

3) 檢測鄰近點的曲率值，如果小于設定閾值則將該點添加到種子點集中，同時將已經處理過的種子點從點集中刪除。如果種子點集中的點全部處理完畢，則說明該區域增長已經結束,統計點集數量并判斷是否符合最小數量閾值要求。

對于未處理的點云數據重復進行上述操作，即可完成區域生長分割過程。

2. 面片鄰接點云處理

面片與面片鄰接處，法線計算會受到鄰接點云的影響，導致部分鄰接點不能正確分割。本研究中依據未分割鄰近點到分割點集擬合面的距離，將未分割鄰近點進行正確分割。點A到平面α距離d計算采用向量法

式中，A是平面α外的一點；P是α內與A鄰近的一點；n是α的法向量。

四、試驗分析

試驗區位于鄭州市鄭東新區，LiDAR數據由ALS60機載LiDAR系統獲取，獲取時間為2011年9月20日，試驗區數據點云密度為2.19個/m2。原始數據已經過濾波分類處理分離地面點，建筑物頂部一般高度在1.5 m以上，試驗數據只保留距離地面1.5 m以上的點云，主要由建筑物房頂和植被等構成，具體處理方法如圖3所示。

圖3 LiDAR點云數據預處理

試驗中法向量計算時k取值8，區域增長算法角度差閾值φ取值0.04π，強度值差I取值10，曲率閾值取值0.2，構成面片點云數量最小閾值取值20。

試驗區建筑物類型包括各種人字形頂面、穹頂、平頂等，區域增長分割算法均能較好地進行分割，部分房頂周邊有植被覆蓋，分割算法均能有效區分(如圖4所示)。處理結果中紅色點云為噪聲點，主要由植被構成，其他顏色點云構成分割面片。根據點到面距離對鄰接點進行處理，去除植被噪聲點。面片與面片鄰接處，法線計算會受到鄰接點云的影響，少量點未能正確分割，根據鄰近點到擬合面的距離進行分割(如圖5所示)。

圖4 不同類型建筑物頂面分割結果

圖5 面片鄰接點云處理分割結果

五、結束語

本文分析了LiDAR點云的法線和曲率的計算方法，采用曲率最小點作為種子點，以點云法向量角度差和灰度值差作為生長條件，構建區域增長算法,實現了建筑物頂面點云分割。試驗結果表明， 本文提出的算法能準確地分割建筑物頂面，不受建筑物形狀、結構等因素影響，并能夠有效分離植被，可為建筑物三維模型的構建提供技術支持。

參考文獻：

[1] 胡偉,盧小平,李珵，等. 基于改進 RANSAC 算法的屋頂激光點云面片分割方法[J].測繪通報, 2012(11):31-34.

[2] TARSHAKURDI F, LANDES T, GRUSSENMEYER P. Hough-transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from LiDAR Data[C]∥Proceedings of ISPRS Workshop on Laser and Silvilaser 2007. Espoo: ISPRS, 2007: 407-412.

[3] 王植, 李慧盈, 吳立新，等.基于RANSAC模型的機載LiDAR數據中建筑輪廓提取算法[J].東北大學學報：自然科學版，2012,33(2): 271-275.

[4] 李云帆, 馬洪超. 從LiDAR 數據中提取建筑物平面目標的新方法[J]. 計算機工程與應用,2011,47(10): 5-7.

[5] KLASING K, ALTHOFF D, WOLLHERR D, et al. Comparison of Surface Normal Estimation Methods for Range Sensing Applications[C] ∥Proceedings of the IEEE International Conference on Robotics and Automation. Kobe: ICRA, 2009: 12-17.

[6] RUSU R B, COUSINS S. 3D is Here: Point Cloud Library [C]∥Proceedings of the IEEE International Conference on Robotics and Automation. Shanghai: ICRA,2011: 9-13.

[7] MARIUS M, LOWE D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[C]∥Proceedings of the International Conference on Computer Vision Theory and Applications. Lisbon: VISAPP, 2009.

[8] PAULY M, GROSS M, KOBBELT L. Efficient Simplification of Point Sampled Surfaces[C]∥Proceedings of IEEE Visualization. Washington D.C.: IEEE Computer Society Press, 2002:163-170.