基于26KNN的機(jī)載點(diǎn)云去噪方法

李峰海

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

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

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

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

1 26KNN算法綜述

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

2 26KNN去噪原理

2.1 ALS超大點(diǎn)云分塊

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

2.2 26NN去噪模型

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

(1)

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

3 實(shí)驗(yàn)與分析

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

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

4 結(jié)束語

本研究可得出如下結(jié)論.

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

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

點(diǎn)云噪聲直接影響到點(diǎn)云拼接、城市建模、重疊區(qū)域混合點(diǎn)質(zhì)量及應(yīng)用精度.點(diǎn)云去噪是一個(gè)點(diǎn)云預(yù)處理中不可回避的問題，本實(shí)驗(yàn)實(shí)現(xiàn)了去除上噪聲點(diǎn)，今后在去除下噪聲點(diǎn)(倒影點(diǎn))上會做進(jì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ù)據(jù)集分類的KNN 算法[J].科學(xué)技術(shù)與工程,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.