基于近邻搜索的激光点云数据孤立噪点滤波研究

张芳菲，梁玉斌，王 佳

(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并行算法可以进一步提高效率，减少计算的时间。