基于26KNN的机载点云去噪方法

李峰海

(山东铝业职业学院， 山东 淄博 255065)

随着三维激光扫描仪硬件性能的提高，3D扫描技术日趋成熟[1]，机载扫描系统(ALS, airborne lidar scanning)正迅速发展成为一种普遍的测量技术[2].从小型机械零件的质量检测，到获取考古遗址，再到整个城市的三维数据建模，三维激光扫描技术广泛应用于各个不同的领域[3-4].ALS具有高数据采集率、高精度和高空间数据密度的特点[5]，能获得最直接的空间和地理参考[6]，但扫描时产生数量巨大的散乱点云.ALS70机载扫描系统在抽稀后每平方公里扫描点数约为218.9万个，扫描50km2即可超过一亿个点.

虽然三维点云数据量庞大，但是受扫描环境的限制、扫描设备本身的精度限制以及被扫描物体的材料属性和仪器校准问题，往往产生大量的点云噪声[7-8].庞大的点云数据噪声会使待处理的原始数据尤其是在靠近物体表面边缘的数据产生虚假，而不能真实反映物体形态，在进行测量任务时也会出现测量伪影和异常数据点[9]，这些噪声点同时影响建筑物等的三维建模，使点云不能正确反映被测物体的位置，增大测量误差[10].

目前应用广泛的去噪方法是基于重复探测距离的K邻域法[8](KNN算法)，然而现有方法不适合点云去噪，巨大的ALS点云无法一次性调入计算机内存.在此基础上，本文提出了基于26邻域(26 k nearest neighbors,以下简称26KNN)的机载点云去噪方法，即对ALS超大点云按照图幅分块，去噪时将每个块分成小盒子，以每27个盒子为单位形成空间拓扑关系，以中心盒子构成26邻域进行点云数量运算.

1 26KNN算法综述

目前KNN算法有两种：传统的KNN算法[11]个改进的KNN算法.传统的KNN算法其基本思想是：找出待判定样本与训练样本集中与该样本距离最近的K 个样本，依据这K个样本所属的类别来判定新样本类别[12].改进的KNN算法则又有很多种，如Pandya等人提出的APF-KNN算法(用于滚动轴承的故障诊断)[13]，Li等[14]提出的用于监测网络入侵探测，Yu等[15]则提出了基于索引数据的KNN方法来用于高维数据处理等.无论是传统的还是改进的KNN算法，如果应用到ALS超大点云处理中都是不现实的，因为以上算法要重复计算点与点间的最近距离，受计算机内存限制而无法完成.本文提出的26KNN的算法则是主要针对地面以上的噪声点，对点云块来建立拓扑关系，而后统计邻域盒子中点云的密度，低于阈值则删除盒子，达到去噪的目的.

2 26KNN去噪原理

2.1 ALS超大点云分块

超大点云分块符合中大比例尺地形图分幅原则.根据测区大小实际和工程应用情况，一般按50cm×50cm标准分幅进行分块，如测绘1∶2 000大比例尺地形图时，首次分块大小为1 000m×1 000m，并且每一个块的点数不大于4000万.本次实验所分块大小为500m×500m.另外，首次分区的区个数不超过100万个，也就是说一次性处理点的个数不超过40亿个点.比例尺谱和对应分块谱见表1.

2.2 26NN去噪模型

如图1所示，在2.1将超大点云分成块后，将每块按照5m×5m×0.2m(0.3m)或3m×3m×0.2m(0.3m)的分辨率再分成若干个盒子，以每3×3×3个盒子构成一个立方体空间，以最中间的盒子为中心，根据邻域的26个盒子建立拓扑关系，并建立与点云的索引关系来统计所有邻域盒子中的总点数.记每个盒子行数为i(i=1,2,3)，盒子中点数为Xi，列数为j(j=1,2,3)，点数为Yi，层数为k(k=1,2,3),点数为Zi，则一组盒子中所有邻域的点总数S为：

(1)

如果S小于2，则认为此中心盒子中没有点或有孤点，进而将此盒子删除.循环运算即可删除整片点云噪声.

3 实验与分析

本实验所用数据来自常熟某地区机载扫描彩色点云，数量为1.9亿，存储格式为双精度型，占磁盘空间约为7.1G，整体形状如图2(a)所示.实验中所有计算通过IDL编程完成.现取超大点云分块后的其中一块(大小为4.2km×3.8km，点云数量为21971517个)为例，说明26KNN去噪方法的可行性.实验中，按照1∶500的图幅将本测区大致分为71个块，分别按照四种不同大小的盒子对每块点云逐个去噪，表2列出了不同盒子下去噪的时间.

盒子大小不同(即控制的去噪时的最小分辨率不同)，去噪所需的时间不同，分辨率小的盒子去噪时间稍长.实验表明，当盒子大小为5m×5m×0.2m或3m×3m×0.2m时，去噪效果更好，虽然比其他两种方案用时稍长，但几秒的时间差可以忽略.我们切取一块点云去噪结果中的一部分，去噪效果如图2所示.

4 结束语

本研究可得出如下结论.

(1) 用26KNN去噪方法处理ALS超大点云时，其中的分块技术解决了超大点云在计算机内存中无法运行的问题，普通的电脑就能实现去噪.

(2) 26KNN相比于KNN算法去噪，其计算量大大减少，速度有了数量级的提高，去噪效果好，能很好的去除上噪声点或体外噪声点.

点云噪声直接影响到点云拼接、城市建模、重叠区域混合点质量及应用精度.点云去噪是一个点云预处理中不可回避的问题，本实验实现了去除上噪声点，今后在去除下噪声点(倒影点)上会做进一步的研究.

[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] 杜娟,刘志刚,衣治安.一种适用于不均衡数据集分类的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.