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

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

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

0 引 言

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

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

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

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

1 數(shù)據(jù)預處理

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

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

圖1 數(shù)據(jù)預處理

2 點云分割算法

2.1 地面點移除

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

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

(1)

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

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

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

(2)

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

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

圖2 欠分割及過分割現(xiàn)象

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

(3)

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

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

圖3 典型地物分割流程圖

3 實驗與分析

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

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

圖4 地面點去除

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

圖5 區(qū)域增長分割

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

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

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

圖8 樹及桿狀物分割

圖9 建筑物分割

4 結 論

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