李峰海

(山東鋁業(yè)職業(yè)學院， 山東 淄博 255065)

隨著三維激光掃描儀硬件性能的提高，3D掃描技術日趨成熟[1]，機載掃描系統(tǒng)(ALS, airborne lidar scanning)正迅速發(fā)展成為一種普遍的測量技術[2].從小型機械零件的質量檢測，到獲取考古遺址，再到整個城市的三維數(shù)據建模，三維激光掃描技術廣泛應用于各個不同的領域[3-4].ALS具有高數(shù)據采集率、高精度和高空間數(shù)據密度的特點[5]，能獲得最直接的空間和地理參考[6]，但掃描時產生數(shù)量巨大的散亂點云.ALS70機載掃描系統(tǒng)在抽稀后每平方公里掃描點數(shù)約為218.9萬個，掃描50km2即可超過一億個點.

雖然三維點云數(shù)據量龐大，但是受掃描環(huán)境的限制、掃描設備本身的精度限制以及被掃描物體的材料屬性和儀器校準問題，往往產生大量的點云噪聲[7-8].龐大的點云數(shù)據噪聲會使待處理的原始數(shù)據尤其是在靠近物體表面邊緣的數(shù)據產生虛假，而不能真實反映物體形態(tài)，在進行測量任務時也會出現(xiàn)測量偽影和異常數(shù)據點[9]，這些噪聲點同時影響建筑物等的三維建模，使點云不能正確反映被測物體的位置，增大測量誤差[10].

目前應用廣泛的去噪方法是基于重復探測距離的K鄰域法[8](KNN算法)，然而現(xiàn)有方法不適合點云去噪，巨大的ALS點云無法一次性調入計算機內存.在此基礎上，本文提出了基于26鄰域(26 k nearest neighbors,以下簡稱26KNN)的機載點云去噪方法，即對ALS超大點云按照圖幅分塊，去噪時將每個塊分成小盒子，以每27個盒子為單位形成空間拓撲關系，以中心盒子構成26鄰域進行點云數(shù)量運算.

1 26KNN算法綜述

目前KNN算法有兩種：傳統(tǒng)的KNN算法[11]個改進的KNN算法.傳統(tǒng)的KNN算法其基本思想是：找出待判定樣本與訓練樣本集中與該樣本距離最近的K 個樣本，依據這K個樣本所屬的類別來判定新樣本類別[12].改進的KNN算法則又有很多種，如Pandya等人提出的APF-KNN算法(用于滾動軸承的故障診斷)[13]，Li等[14]提出的用于監(jiān)測網絡入侵探測，Yu等[15]則提出了基于索引數(shù)據的KNN方法來用于高維數(shù)據處理等.無論是傳統(tǒng)的還是改進的KNN算法，如果應用到ALS超大點云處理中都是不現(xiàn)實的，因為以上算法要重復計算點與點間的最近距離，受計算機內存限制而無法完成.本文提出的26KNN的算法則是主要針對地面以上的噪聲點，對點云塊來建立拓撲關系，而后統(tǒng)計鄰域盒子中點云的密度，低于閾值則刪除盒子，達到去噪的目的.

2 26KNN去噪原理

2.1 ALS超大點云分塊

超大點云分塊符合中大比例尺地形圖分幅原則.根據測區(qū)大小實際和工程應用情況，一般按50cm×50cm標準分幅進行分塊，如測繪1∶2 000大比例尺地形圖時，首次分塊大小為1 000m×1 000m，并且每一個塊的點數(shù)不大于4000萬.本次實驗所分塊大小為500m×500m.另外，首次分區(qū)的區(qū)個數(shù)不超過100萬個，也就是說一次性處理點的個數(shù)不超過40億個點.比例尺譜和對應分塊譜見表1.

2.2 26NN去噪模型

如圖1所示，在2.1將超大點云分成塊后，將每塊按照5m×5m×0.2m(0.3m)或3m×3m×0.2m(0.3m)的分辨率再分成若干個盒子，以每3×3×3個盒子構成一個立方體空間，以最中間的盒子為中心，根據鄰域的26個盒子建立拓撲關系，并建立與點云的索引關系來統(tǒng)計所有鄰域盒子中的總點數(shù).記每個盒子行數(shù)為i(i=1,2,3)，盒子中點數(shù)為Xi，列數(shù)為j(j=1,2,3)，點數(shù)為Yi，層數(shù)為k(k=1,2,3),點數(shù)為Zi，則一組盒子中所有鄰域的點總數(shù)S為：

(1)

如果S小于2，則認為此中心盒子中沒有點或有孤點，進而將此盒子刪除.循環(huán)運算即可刪除整片點云噪聲.

3 實驗與分析

本實驗所用數(shù)據來自常熟某地區(qū)機載掃描彩色點云，數(shù)量為1.9億，存儲格式為雙精度型，占磁盤空間約為7.1G，整體形狀如圖2(a)所示.實驗中所有計算通過IDL編程完成.現(xiàn)取超大點云分塊后的其中一塊(大小為4.2km×3.8km，點云數(shù)量為21971517個)為例，說明26KNN去噪方法的可行性.實驗中，按照1∶500的圖幅將本測區(qū)大致分為71個塊，分別按照四種不同大小的盒子對每塊點云逐個去噪，表2列出了不同盒子下去噪的時間.

盒子大小不同(即控制的去噪時的最小分辨率不同)，去噪所需的時間不同，分辨率小的盒子去噪時間稍長.實驗表明，當盒子大小為5m×5m×0.2m或3m×3m×0.2m時，去噪效果更好，雖然比其他兩種方案用時稍長，但幾秒的時間差可以忽略.我們切取一塊點云去噪結果中的一部分，去噪效果如圖2所示.

4 結束語

本研究可得出如下結論.

(1) 用26KNN去噪方法處理ALS超大點云時，其中的分塊技術解決了超大點云在計算機內存中無法運行的問題，普通的電腦就能實現(xiàn)去噪.

(2) 26KNN相比于KNN算法去噪，其計算量大大減少，速度有了數(shù)量級的提高，去噪效果好，能很好的去除上噪聲點或體外噪聲點.

點云噪聲直接影響到點云拼接、城市建模、重疊區(qū)域混合點質量及應用精度.點云去噪是一個點云預處理中不可回避的問題，本實驗實現(xiàn)了去除上噪聲點，今后在去除下噪聲點(倒影點)上會做進一步的研究.

[1]Michael W,Alexander B, Martin B,etal. Processing and interactive editing of huge point clouds from 3D scanners[J]. Computers and Graphics 2008,32(2):204-220.

[2] Josep M B, José L L.Unsupervised robust planar segmentation of terrestrial laser scanner point clouds based on fuzzy clustering methods[J].ISPRS Journal of Photogrammetry and Remote Sensing, 2008, 63:84-98.

[3] Akbarzadeh A, Frahm J M, Mordohai P,etal. Towards urban 3D reconstruction from video[C]//3D Data Processing, Visualization, and Transmission, Third International Symposium on. IEEE, 2006:1-8.

[4] Vosselman G, Kessels P, Gorte B. The utilisation of airborne laser scanning for mapping[J]. International Journal of Applied Earth Observation and Geoinformation, 2005, 6(3):177-186.

[5] Ergun B. A novel 3D geometric object filtering function for application in indoor area with terrestrial laser scanning data[J]. Optics and Laser Technology, 2010, 42(5):799-804.

[6] Kumari P, Carter W E, Shrestha R L. Adjustment of systematic errors in ALS data through surface matching[J]. Advances in Space Research, 2011, 47(10):1851-1864.

[7] Marcon M, Piccarreta L, Sarti A,etal. Fast PDE approach to surface reconstruction from large cloud of points[J]. Computer Vision and Image Understanding, 2008, 112(3):274-285.

[8] Sankaranarayanan J, Samet H, Varshney A. A fast all nearest neighbor algorithm for applications involving large point-clouds[J]. Computers and Graphics, 2007, 31(2):157-174.

[9]Cheng N L P, Sutton M A, McNeill S R.Three-dimensional point cloud registration by matching surface features with relaxation labeling method[J]. Experimental Mechanics,2005, 45(1):71-82.

[10] Zhang X C, Xi J T, Yan J Q. A methodology for smoothing of point cloud data based on anisotropic heat conduction theory[J]. The International Journal of Advanced Manufacturing Technology, 2006, 30(1-2):70-75.

[11] Cover T, Hart P. Nearest neighbor pattern classification[J]. Information Theory, IEEE Transactions on, 1967, 13(1):21-27.

[12] 杜娟,劉志剛,衣治安.一種適用于不均衡數(shù)據集分類的KNN 算法[J].科學技術與工程,2011,11(12):2680-2685.

[13] Pandya D H, Upadhyay S H, Harsha S P. Fault diagnosis of rolling element bearing with intrinsic mode function of acoustic emission data using APF-KNN[J]. Expert Systems with Applications, 2013,40:4137-4145.

[14] Li Y, Guo L. An active learning based TCM-KNN algorithm for supervised network intrusion detection[J]. Computers and Security, 2007, 26(7):459-467.

[15] Yu C, Cui B, Wang S,etal. Efficient index-based KNN join processing for high-dimensional data[J]. Information and Software Technology, 2007, 49(4): 332-344.