激光點云中典型地物分割方法

鄒紀偉, 劉德兒, 康 翔, 蘭小機, 楊 鵬, 劉靖鈺

(江西理工大學 土木與測繪工程學院, 江西 贛州 341000)

0 引 言

三維激光掃描技術自問世以來已被應用于各個領域, 如文物修復、建筑物的三維建模、智慧城市的建設和大面積的地形測量等[1]。地面激光掃描儀能夠快速高精度地獲取地物的表面信息, 相比于機載激光掃描儀和航空攝影測量, 其獲取的數據更加精細[2], 由于點云數據量龐大, 若直接對其進行操作, 工作量較大且耗時長, 因此需對源數據進一步處理, 點云分割作為數據處理的關鍵環節, 其分割精度直接影響到后續點云三維重建、特征提取、地物識別等操作。

常見的點云分割算法有RANSAC算法、歐氏聚類算法、區域增長算法、最小割算法等。RANSAC算法作為隨機參數的估計算法[3], 由Fishier等于1981年提出, 該算法在直線擬合、平面擬合、計算圖形方面應用廣泛, 在點云分割中, 該算法通常用于提取平面點云：李娜等[4]將RANSAC算法運用于點云的分割處理, 提取出了建筑物的特征立面；賀亦峰等[5]則通過設置不同閾值, 使用RANSAC算法將建筑立面中的墻面、窗戶、陽臺等要素單獨分割開來, 再通過歐氏聚類完成獨立個體的分割。基于歐氏聚類的點云分割是根據不同點間的歐氏距離來判斷是否屬于同類地物點：吳燕雄等[6]使用歐氏聚類加上平滑閾值的方法對地物實現分類提取, 能夠高效快速地達到分割效果, 但若地物種類過多, 閾值則較難設置, 易出現過分割或欠分割現象。區域增長算法[7-10]則是根據法向量及曲率實現不同地物分割：王競雪等[11]提出了一種對機載LiDAR數據中的建筑物提取, 通過區域生長算法與主成分分析相結合的方法實現高精度提取；李仁忠等[12]提出了通過將估算的曲率最小點設置為種子點的改進區域生長算法, 使分割的精確性及可靠性得到提高；孫金虎等[13]提出了基于最小生成樹(MST)改進的區域生長算法, 能夠得到平滑的分割邊界。

上述常見的點云分割算法, 若單獨應用于大型室外場景點云, 都存在一定的局限性, RANSAC算法適用于建筑立面細節特征的分割提取, 倘若建筑物結構較為復雜, 則需設置不同的平面模型參數進行分割, 操作較為繁瑣。歐氏聚類算法適用于相距較遠的不同地物點云分割, 若不同地物點云出現粘連問題, 則很難將其單獨分割開, 閾值設置恰當與否, 直接影響點云分割效果。區域增長算法因其根據法向量及曲率對散亂點云進行分類, 因此對樹、桿狀物分割效果良好。針對激光點云中的典型地物, 找到合適的融合分割算法對其進行分割, 將有效解決過分割或欠分割問題。

綜上, 本文提出基于區域增長與歐氏聚類相結合的點云分割算法：首先對數據預處理, 完成噪點去除及數據精簡, 采用漸近式形態學濾波去除地面點, 再通過區域增長算法將樹、桿狀物和建筑類地物單獨分割開, 最后用歐氏聚類實現對典型地物的有效分割, 解決傳統點云分割算法易出現過分割或欠分割問題, 為后續點云數據處理提供基礎。

1 數據預處理

通過地面激光掃描儀采集到的數據由于受環境因素的影響, 不可避免地產生噪聲, 影響后續實驗的分割效果, 因此本文在分割前先對源數據進行去噪處理。具體地，統計濾波通過對每個點的鄰域進行統計分析, 計算該點至其鄰域點的平均距離, 得到高斯分布圖, 將平均距離到標準范圍之外的點定義為離群點, 使用時僅需設置K近鄰搜索個數和標準差倍數就可將噪聲點從數據中去除。本文采集數據的噪聲符合這一特性, 因此采用該算法對噪聲點進行有效移除。經濾波后, 由于數據仍然過密, 影響后續分割算法的運行效率, 在保證數據特征信息的前提下, 采用八叉樹對數據進行精簡。該算法首先對點云創建一個八叉樹, 在樹中搜索并記錄真實的葉節點數據, 然后將節點數和對應的數據作為平均聚類算法K值和初始聚類中心, 最終計算出每個點的均方根曲率、所有點的均方根曲率均值、每個點到聚類中心的歐氏距離以及每個點到聚類中心的歐氏距離的平均值, 根據計算結果精簡點云數據。

本文實驗數據通過RIEGL VZ-1000掃描儀獲取, 其中源數據點個數為1 133 991, 通過對數據進行去噪及精簡, 同時手動對無效點進行移除, 最終得到的結果見圖1, 其中統計濾波K近鄰搜索個數設置為6, 標準差倍數設置為1.0, 而精簡點云細分級別設置成10, 去噪后點個數為1 115 968(圖1b)，精簡及手動去除無效點后點個數為109 130(圖1c), 可見預處理后的點云噪點被較好地移除, 地物更加清晰, 便于分割處理, 且數據精簡后將更好地提高算法的運行效率。

圖1 數據預處理

2 點云分割算法

2.1 地面點移除

由于采集數據時不可避免夾雜地面點云, 為了確保點云分割的質量, 需要對該區域點云進行有效去除。本文研究數據為室外大型場景點云, 雖然地形較為平坦, 但仍夾雜地形起伏較大區域, 因而采用漸近式形態學濾波去除地面點。

形態學濾波的主要操作為腐蝕與膨脹, 該濾波算法在二維圖像中運用較為廣泛, 其中先腐蝕后膨脹稱為開運算, 該操作可對小區域噪聲進行去除, 同時可對圖像進行平滑處理; 而先膨脹后腐蝕稱為閉運算, 該操作對圖像細小空洞有較強的修復能力。在激光點云中, 通過腐蝕運算可獲得指定區域點的最小高程值, 而膨脹操作則獲得該區域內點的最大高程值。借助不斷增長的濾波窗口, 通過開運算操作, 漸近式形態學濾波即可實現地面點與非地面點的分離, 該濾波操作主要通過高差閾值Δhi判斷[14]

(1)

其中:h0為最小高差閾值,s為研究區域的平均地形坡度,c為格網大小,hmax為最大高差閾值, 而wi為運行到i次時濾波窗口的大小。當前后格網內的高程差小于高差閾值Δhi時, 將當前格網內的點歸為地面點類格網, 標記為0; 而對于大于高差閾值的, 將該格網歸為非地面點類格網, 標記為1。通過遍歷所有點云數據, 即可將地面點與非地面點分離開來。

2.2 基于區域增長與歐氏聚類相結合的點云分割

歐氏聚類算法是應用于測繪領域的一種重要的點云分割算法。它利用KD樹搜索近鄰域點, 計算鄰域點到該點的歐氏距離, 將在閾值范圍內的點聚為一類, 通過反復迭代, 直到沒有新點加入為止。

(2)

其中:pi,qi∈Q,Q是一個點云集。具體的實現步驟為: ①對于空間中的某點p1, 利用KD樹搜索找到其近鄰點, 計算這n個點到p1的距離, 將距離小于閾值的點p3、p4、p5…放到點集A中, 將點集A中的點從原始點云中移除; ②依次遍歷點集A中的所有點, 重復步驟①, 更新點集A; ③當A中無新點加入時, 該類聚類完成; ④新建點集B, 對剩余點執行步驟①操作; ⑤所有點都遍歷完成, 運行結束。

通過歐氏聚類進行分割的效果主要由設置的距離閾值決定: 當設置的閾值過大時, 會出現過分割現象, 建筑物與周邊較近的地物歸為一類,當建筑物與樹木及地面周邊點粘連時, 無法通過歐氏聚類分割(圖2a、2b); 反之, 則出現欠分割情形, 在圖2c、2d中, 由于閾值設置過小, 建筑物出現缺失現象。針對此問題并結合上述分析, 本文提出基于區域增長與歐氏聚類相結合的點云分割算法。

圖2 欠分割及過分割現象

區域增長算法是將點云的法向量進行比較, 將滿足平滑約束條件的相鄰點歸為一類, 其工作原理為先利用KD樹對散亂點建立拓撲關系, 計算各點平均曲率值, 再將各點按曲率值從小到大進行排序, 將曲率值最小的點設置為種子節點, 由于曲率最小的點位于平坦區域, 從該區域進行增長可以減少區域的總數, 避免重復分割, 最后將滿足條件的不同地物聚為一類。

(3)

式中:Ki為曲面中點的平均曲率近鄰點；n為法向量;P為該點周圍無限小的區域; diam(P)為這個區域的直徑;為該點的梯度算子。該算法具體的步驟如下: ①將散亂點云按照曲率值進行排序, 找到曲率最小的點, 將其設置成種子節點，②計算該種子點與鄰近點的法線差值, 若小于設置的閾值, 且曲率值也小于設定的閾值, 則將該點添加到種子點集, 即歸為一類; ③將通過兩次檢驗的點從原始點云中去除; ④設置最小和最大聚類的點數; ⑤重復步驟①～③, 算法會將滿足條件的不同地物聚類為一類, 并用不同的顏色加以區分; ⑥當剩余的點云數小于最小聚類點數時, 則停止工作。

在大規模場景點云中, 建筑物等地物點云的曲率變化明顯要小于樹木等桿狀地物, 由于區域增長算法是按法線差值與曲率變化進行分割的, 可將曲率變化較大的樹木及桿狀地物通過該算法分割出來, 歸為一類, 將剩余地物點云劃分為另一類, 再分別對兩類點云執行歐氏聚類分割, 最終完成對典型地物的分割, 其分割流程見圖3。

圖3 典型地物分割流程圖

3 實驗與分析

采用RIEGL VZ-1000掃描儀獲取的該數據，包含建筑物、周邊低矮樹木、路燈、旗桿等典型地物, 地物種類較多, 場景較為復雜。實驗軟硬件環境:Windows 10專業版、處理器為Intel(R)Core(TM)i5-4200M CPU @2.50 GHz、內存為8 GB; 本研究的實驗算法是在Microsoft Visual Studio 2017編譯環境下, 結合PCL方法庫編程實現。

通過預處理后, 采用漸近形態學濾波算法移除地面點, 濾波窗口設置為20 m, 坡度設置為1.0, 最小高差閾值設置為0.5 m, 最大高差閾值設置為0.8 m, 得到的結果如圖4所示。濾波后, 大量地面點都得以去除, 建筑物底部點及階梯處點未因該操作而受影響, 較好地保證了地物點的完整性。

圖4 地面點去除

經形態學濾波后, 再對非地面點采用區域增長算法進行分割, 法線差值設置為0.05, 曲率閾值設置為1.0。從圖5a可以看出, 由于樹及桿狀物曲率變化較大, 而建筑物點云分布較為平整, 因此樹及桿狀物聚類后呈現紅色, 而其余地物顏色與該類地物顏色不同；基于此，可將樹木及桿狀物點云簇分為一類(圖5b)；其余地物歸為另一類(圖5c)。接著，分別對上述兩類點云簇進行歐氏聚類分割: 將典型地物個體單獨分離出來, 樹及桿狀物距離閾值設置成1.0 m, 最小聚類簇點數為50, 最大聚類簇點數為300 000, 最終生成的聚類簇數為53個(圖6)；而對于建筑物等點云簇, 其距離閾值設置為2.0 m, 最小聚類簇點云為50, 最大聚類簇點數為300 000, 最后生成的聚類簇數為7個(圖7)。

圖5 區域增長分割

圖6 樹及桿狀物歐氏聚類分割結果

圖7 建筑地物歐氏聚類結果

從圖8及圖9可以看出, 通過本文算法, 可將建筑物、樹、旗桿等典型地物單獨分割開來, 較好地解決了建筑物與地面、建筑物與樹桿、樹桿與地面等不同地物點云間因粘連問題而出現的過分割現象, 且本文將不同地物歸為兩類, 即樹及桿狀物點云簇和建筑物點云簇, 通過分別對其進行歐氏聚類, 較好地解決了雙方對閾值設置的沖突, 避免出現地物欠分割現象。

圖8 樹及桿狀物分割

圖9 建筑物分割

4 結 論

以TLS獲取的大規模場景點云數據作為研究對象, 通過統計濾波與八叉樹精簡對源數據作預處理, 降低了噪聲點的干擾, 提高了點云分割的運行效率。由于受地物形態特征、空間位置、地面點等因素影響, 在對典型地物進行分割時，常會出現過分割或欠分割現象, 因此，本文提出基于區域增長與歐氏聚類相結合的分割算法, 首先通過形態學濾波去除地面點, 然后通過區域增長算法, 將典型地物分為樹桿類及建筑物兩大類, 最后分別對這兩類地物通過歐氏聚類完成獨立個體的有效分割。本文方法有效解決了點云分割中易出現的過分割或欠分割問題, 在對樹、桿狀物及建筑物等典型地物的點云分割中有較強的實用性。然而, 本文算法的閾值需要人工調試, 如何自動獲取合適的閾值, 將是下階段的研究重點, 雖然本文事先對數據作了預處理, 提高了運行效率, 但若數據量很大時, 其運行時間將成倍增長, 如何改進算法, 加入并行策略, 減少分割時間, 將是下一步的工作重點。