基于近鄰搜索的激光點(diǎn)云數(shù)據(jù)孤立噪點(diǎn)濾波研究

張芳菲，梁玉斌，王 佳

(1.北京林業(yè)大學(xué) 精準(zhǔn)林業(yè)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100083； 2.天津師范大學(xué)，天津 300387)

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

1 基于k-d tree的孤立點(diǎn)云濾波基本原理

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

1.1 k-d tree的創(chuàng)建和最近鄰查找

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

1)讀入點(diǎn)集文件Q,將數(shù)據(jù)點(diǎn)存入一個(gè)n維數(shù)組中;

2)選擇一個(gè)方差最大的維度i(i=1,2,…,n)，然后在該維度中選擇中值m作為分割值對(duì)該數(shù)據(jù)集合進(jìn)行劃分，這樣就得到兩個(gè)子集；與此同時(shí)創(chuàng)建一個(gè)樹結(jié)點(diǎn)，存儲(chǔ)；

3)對(duì)剛得到的兩個(gè)子集合重復(fù)1)的過程直到集合無法再分割，如果無法再分割，就將數(shù)據(jù)存入葉子結(jié)點(diǎn)。

圖1 k-d tree的構(gòu)建

通過建立k-d tree，形成點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系，實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的組織與管理，進(jìn)而實(shí)現(xiàn)對(duì)每個(gè)點(diǎn)最近鄰點(diǎn)的查找，與最近鄰距離的存儲(chǔ)，如圖2所示，即：

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

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

圖2 最近鄰點(diǎn)的查找

1.2 基于k-d tree的激光點(diǎn)云孤立噪聲點(diǎn)濾除

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

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

圖3 基于k-d tree的點(diǎn)云去噪流程

的點(diǎn)為有效點(diǎn)，只有極少數(shù)不符合條件的點(diǎn)會(huì)落在范圍之外， 將這些點(diǎn)視為噪聲點(diǎn)去除。這樣設(shè)置閾值，能夠根據(jù)數(shù)據(jù)大小自動(dòng)計(jì)算閾值，不用人工重復(fù)設(shè)定，提高效率和速度。

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

(1)

標(biāo)準(zhǔn)差s為

(2)

當(dāng)μ-3σ≤Di≤μ+3σ時(shí)，為有效的激光點(diǎn)，否則為孤立噪聲點(diǎn)濾除。

2 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)數(shù)據(jù)來自武漢大學(xué)理學(xué)樓，三維激光掃描儀應(yīng)用Z+F IMAGER 5006i，見圖5。掃描儀的主要參數(shù)見表1。獲取數(shù)據(jù)采用 “super high”的掃描模式，即每掃描360°獲取20 000個(gè)點(diǎn)云數(shù)據(jù)，花費(fèi)時(shí)間00:06:44。

圖5 實(shí)驗(yàn)對(duì)象及掃描儀

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

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

圖6 部分點(diǎn)近鄰距離分布

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

圖7 濾波前后的點(diǎn)云數(shù)據(jù)(主視圖)

圖8 濾波前后的點(diǎn)云數(shù)據(jù)(側(cè)視圖)

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

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

3 結(jié) 論

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