基于近鄰搜索的激光點云數據孤立噪點濾波研究

張芳菲，梁玉斌，王 佳

(1.北京林業大學 精準林業北京市重點實驗室，北京 100083； 2.天津師范大學，天津 300387)

三維掃描儀具有精度高、速度快等優點，點云數據在三維實體中得到廣泛應用[1-4]。但獲取的點云數據受到儀器自身或是測量環境等因素的影響，數據中存在一些孤立噪聲點、離群點直接影響點云數據的質量和后期處理等問題。國內外研究者對于激光點云孤立噪聲點、離群噪聲點去除的研究可以分為兩類，針對有序點云、或者部分有序點云的處理應用較廣泛的算法有高斯濾波、均值濾波和中值濾波算法，以及維納濾波、最小二乘濾波、卡爾曼濾波[5]；對于無序的散亂點云,學者們也進行了很多研究,對于無序的散亂點云研究集中于Laplace算子、平均曲率流、移動最小二次曲面等方法，如武漢大學張小紅[6]提出的移動曲面擬合法，劉大峰、廖文和[7]等人提出應用似然估計函數，同時引入點的估計聚類的噪聲去除法，張毅[8]等人采用高斯函數來判斷一點對它鄰域內點的影響，進而去除離群點；王振[9]針對隨機噪聲點和大顆粒離群點提出統計分類法區分離群點和正常點的思想。Lange[10]提出通過建立偏微分方程逼近曲面的算法，能夠很好的去除小振幅噪聲，此外，在對無序點云統計分析的基礎上，文獻[11-12]以高程直方圖的方法剔除顯著的高位、低位粗差，但不適用于地表附近的孤立噪聲，但該方法簡便快速。上述已有的針對無序點云的孤立或者離群噪聲剔除方法往往是針對特定的數據，或者特定的濾波方法所設計的，都需要一些經驗參數，限定了其使用范圍。本文針對無序或散亂點云，以k-d tree[13]法組織和管理其空間數據，基于統計分析的方法自適應提取閾值并剔除孤立噪聲點。

1 基于k-d tree的孤立點云濾波基本原理

無序或者散亂點云的分布呈散亂無序狀態、沒有明顯規律性,檢索速度慢，因此必須建立數據點之間的空間拓撲關系[14]，使其有序化，進而搜索每個點的K-近鄰。目前，k-d tree法是一種常見的K-近鄰計算方法。設Q={p1,p2,…,pn}是未知的一個激光點云集,Q中與測點pi距離最近的k個測點稱為Pi的K-近鄰,記作Nb(p)。

1.1 k-d tree的創建和最近鄰查找

設Q={p1,p2,… ,pn}是未知的一個數據點集,Q中與待測點pi距離最近的k個測點稱為Pi的K-近鄰,記作Nb(p)。k-d tree的構建方法，如圖1所示。

1)讀入點集文件Q,將數據點存入一個n維數組中;

2)選擇一個方差最大的維度i(i=1,2,…,n)，然后在該維度中選擇中值m作為分割值對該數據集合進行劃分，這樣就得到兩個子集；與此同時創建一個樹結點，存儲；

3)對剛得到的兩個子集合重復1)的過程直到集合無法再分割，如果無法再分割，就將數據存入葉子結點。

圖1 k-d tree的構建

通過建立k-d tree，形成點與點之間的拓撲關系，實現點云數據的組織與管理，進而實現對每個點最近鄰點的查找，與最近鄰距離的存儲，如圖2所示，即：

1)從根結點開始，待查詢數據W與各個結點中的i(i=1,2,…,n)維度上的值m進行比較，如果W(k)>m，則進入右子樹，如果W(k)

2)進行回溯，找出在未訪問的結點中是否有比D更短的距離以及比P更近的點：如果Q與其父結點下未訪問的分支之間的距離小于D，則認為在該分支中有離P更近的點，進入該結點，重復1)的過程。如果找到了更近數據點，就更新P和D。相反，如果Q與其父結點下未訪問的分支之間的距離大于D，就認為不存在這樣的點，不必進入該結點。

圖2 最近鄰點的查找

1.2 基于k-d tree的激光點云孤立噪聲點濾除

如圖3所示，基于k-d tree的激光點云孤立噪聲點濾除的步驟包括基于k-d tree 組織激光點云、查找出k-近鄰點；其次，根據孤立噪聲點與其若干個k最近鄰點的距離的統計特性，濾除孤立噪聲。

由圖4可知，當一維測量數據滿足正態分布時(用一般分布的頻數表繪制的直方圖，高峰在中間，左右基本對稱，當數據足夠多的時候組間距變得密集，越來越接近一條光滑曲線)，令μ代表平均值，σ代表標準差，則橫軸區間(μ-σ，μ+σ)內的數據統計面積達到68.26%；橫軸區間(μ-2σ，μ+2σ)內的數據統計面積達到95.44%；橫軸區間(μ-3σ，μ+3σ)內的面積則為99.74%。假設激光點的k個近鄰點的距離的中值近似滿足正態分布，那么99.74%的點都會落在(μ-3σ，μ+3σ)這個區域，就視這范圍內

圖3 基于k-d tree的點云去噪流程

的點為有效點，只有極少數不符合條件的點會落在范圍之外， 將這些點視為噪聲點去除。這樣設置閾值，能夠根據數據大小自動計算閾值，不用人工重復設定，提高效率和速度。

若任意激光點i(i=1,2…)的k個最近鄰點距離的平均值為Di，則

(1)

標準差s為

(2)

當μ-3σ≤Di≤μ+3σ時，為有效的激光點，否則為孤立噪聲點濾除。

2 實驗結果與分析

本實驗數據來自武漢大學理學樓，三維激光掃描儀應用Z+F IMAGER 5006i，見圖5。掃描儀的主要參數見表1。獲取數據采用 “super high”的掃描模式，即每掃描360°獲取20 000個點云數據，花費時間00:06:44。

圖5 實驗對象及掃描儀

最大測量距離/m最近測量距離/m分辨率/mm數據獲取率/pxl/sec50 m內誤差/mm79 0.4 0.1 ≤508 000 ≤1 垂直視野范圍/(°)水平視野范圍/(°)光束發散度/mrad垂直方向最大掃描速度/rps垂直方向一般掃描速度/rps3103600.22 ≤50 25

利用Cyclone軟件將點云數據導出為文本文件；其次，將掃描獲得的數據以5 cm進行重采樣，共1 333 099個點。根據圖3所示的點云去噪流程，利用 Visual studio 2012 C++開發環境編寫相關程序，濾除孤立噪聲點1 072個。統計所有點的k個最近鄰距離的平均值的直方圖(見圖6)，可以看出約132萬點近鄰距離分布在0～0.068之間；如圖6所示，132萬個激光點的k-近鄰平均距離分布直方圖中的第一個波峰在0.01處，低于0.01的近似均勻分布在兩側，(第二個較小的峰值屬于距離比較遠的地物，但也是有效點)；實驗計算得到的均值為0.014，計算得到的標準差為0.053，設定的孤立噪聲濾除閾值為0.174。

圖6 部分點近鄰距離分布

部分未濾除之前的點云數據和去除噪聲之后的點云數據分別導入到之前建好的數據庫中，并導入到Cyclone軟件中，其可視化顯示如圖7、圖8所示。

圖7 濾波前后的點云數據(主視圖)

圖8 濾波前后的點云數據(側視圖)

濾波前后的對比可以看出天空上的噪聲全部消失，樹木之間的雜亂噪聲也消失了，理學樓附近的墻與樓相連之間的噪聲也消失了大半，而有效點并沒有顯著地被誤刪，不影響后續的處理。實驗表明，所有點的近鄰距離確實近似于正態分布，激光點最近鄰距離近似正態分布的假設成立，說明閾值的設置合理，本算法能夠有效地去除噪聲點，保留有效點。本實驗中，每個激光點的最近鄰點的個數設定為10。

為了評價該算法去噪的效果，本文還將k-d tree去噪的結果與人工手動去噪的結果對比。人工去噪即將數據導入Cyclone軟件中通過目視發現、手動刪除噪聲點，人工去噪后有效點共1 331 929個；k-d tree去噪保留有效點為1 332 027個點，二者保留的有效點數目接近，精確率為99.9%。故說明k-d tree法與人工去噪效果近似，本算法能夠快速去噪且精確率高，閾值能夠自動計算不需人工設置，提高處理效率，尤其針對無序或散亂孤立噪聲點較多的數據效果突出。

3 結 論

本文提出一種基于統計分析的孤立噪聲點自動剔除的方法，該方法首先利用k-d tree組織地面建筑物的點云數據；其次，基于正態分布的原理，利用統計分析的方法，自動設置閾值，以濾除孤立噪聲點。通過實際獲取的地面建筑物的點云測試表明，地面采集的建筑物激光點數據服從正態分布，本文提出的孤立噪聲點剔除方法可處理無序或者散亂激光點云，且無需人工交互設定參數,快速、精確率高。今后的工作中，將通過調整近鄰點個數與離群點個數的幾何關系拓展本方法以剔除離群點噪聲。此外，本文的算法在計算效率上還有較大的上升空間，通過采用多核CPU并行算法或GPU并行算法可以進一步提高效率，減少計算的時間。