基于特征恢复的离群点移除算法的研究

郭子选，谢晓尧，刘　嵩

(贵州师范大学 贵州省信息与计算科学重点实验室，贵州 贵阳　550001)



基于特征恢复的离群点移除算法的研究

郭子选，谢晓尧*，刘嵩

(贵州师范大学 贵州省信息与计算科学重点实验室，贵州 贵阳550001)

摘要：点云预处理是点云处理很重要的一个环节，在移除稀疏离群点的过程中，点云密度不均会造成有用信息的过度删除。针对这个问题，提出了一种基于特征恢复的离群点移除算法。首先使用传统基于统计的k邻域稀疏离群点移除算法移除稀疏离群点，然后针对过度删除的情况采用RANSAC算法对点云特征进行恢复。实验结果表明，经过恢复的点云数据，相对于单纯依靠传统离群点移除算法处理后的点云数据，过度删除现象有明显改善。由此得出，基于特征恢复的离群点移除算法可以有效删除稀疏离群点，减小对噪声阈值的依赖，同时有效抑制了由于密度不均匀导致的点云数据的过度删除。

关键词：三维激光扫描仪；稀疏离群点；kd-tree算法；k邻域；随机采样一致性算法

0引言

三维激光扫描仪可以快速获取高精度的物体表面点云数据。获取的激光点云不仅具有完整的三维空间信息，而且包含丰富的激光反射强度信息[1]。在文物保护与修复、建筑物变形检测、地形监测、影视制作等诸多领域均有广泛的应用。三维激光点云需要处理的工作包括: 点云去噪、点云平滑、点云编辑、点云分类、点云着色、目标识别、地物表面重构、影像与点云配准、基于影像与点云的单点测量、模型贴纹理等[2]。其中点云去噪是点云预处理阶段不可或缺的一步，稀疏离群点的移除是点云去噪的重要方面，移除效果的优劣直接影响点云后续的分析与建模。

激光扫描仪在对实体进行扫描的时候，由于外界因素干扰以及扫描仪本身误差，或多或少都会产生离群噪声点。目前关于离群噪声的处理前人们进行了很多研究。一种是传统基于k邻域的离群点移除算法，这种方法是根据单个点的k邻域距离，主要是靠人为经验设置阈值来删除离群点；第二种是R. B. Rusu, Z. C. Marton等人于2008年提出的基于统计的离群点删除算法[3]，这种算法对点云中所有的k邻域距离进行统计分析，计算所有点的k邻域平均距离的标准差，根据标准差设定合理阈值，进而删除稀疏离群点；第三种是基于密度的离群点去噪算法，通过计算离群程度，从而限制噪声并剔除离群点[4]，这种算法对于紧挨边界的离群点移除算法效果较好。第四种方法是朱俊峰等人提出的多尺度点云噪声监测的密度分析法[5]，对孤立噪声和簇状噪声都有较为效。

以上研究均对稀疏离群点的移除算法的发展起到了推动作用，但是对于密度分布不均的情况，均未找到较好的方法解决。研究采用目前广泛在点云去噪领域使用的基于统计的稀疏离群点对稀疏离群点移除，之后对移除的离群点进行二次处理，获得有特征的区域，对处理后的点云进行恢复，减小点云过度删除对后续处理带来的不利影响。

1稀疏离群点

在扫描海龙囤石质建筑时，由于关口年代久远，石质建筑已经风化，石头与石头之间存在较多的不规则缝隙，在缝隙之间会由稀疏的离群点噪声组成一条条的拖影。由于扫描角度、遮挡、扫描表面反射材质的不同，造成采集的点云密度总是不均匀的。因此拖影和扫描实体表面低密度区域的点云均呈现稀疏的状态。

通过观察点云，发现扫描得到的海龙囤点云数据中，拖影部分点云分布在墙体裂缝的后方，这些拖影点明显偏离了墙体表面，与扫描实体明显呈现不一致的状态。根据Hawkins的定义“一个离群点是一个观察点,它偏离其它观察点如此之大以至于引起怀疑是由不同机制生成的”[6]。因此这部分点云属于稀疏的离群点。这些点的存在不利于后期的点云处理和建模。而扫描实体表面的稀疏点云大部分是含有有用信息的稀疏点，不能删除。

这种稀疏离群点产生的原因是多方面的。首先，当激光照射到镜面和较湿的的表面时，会使激光扫描仪发射出去的激光经过一次或多次反射才被激光扫描仪接收到，由于激光反射时间的延长，会使点偏离物体的表面。其次，当激光打到物体边缘时，激光扫描仪的点会沿着物体表面的边缘延伸出去，形成一个拖尾，这种现象在使用相位式扫描仪扫描时会更加明显[7]。最后，激光扫描仪的精度以及稳定性会随着反射物表面的材质与粗糙度、空气湿度、仪器内部时间计器以及反射强度等的不同而受到不同程度的影响[8]。因海龙囤墙体处于野外，周围环境复杂多变，墙体易受周围环境的影响，而且墙面粗糙程度以及湿度不均匀，再加上裂缝较多，造成了这种现象在海龙囤石质建筑扫描的过程中是不可避免的。图1为海龙囤飞凤关墙面照片与点云俯视图，可以很明显的看出墙面后方有一段很长的拖尾。

图1　飞凤关墙面照片与点云俯视图Fig.1　Photo of Feifeng and the top-view of its point cloud

2基于特征恢复的离群点移除算法实现

2.1算法实现流程

算法实现的流程如图2所示：

图2　算法流程Fig.2　Algorithm flow

该算法主要分为两个部分，第一个部分是对原始点云进行稀疏离群点的删除；第二部分是针对过滤点云的特征对有信息区域进行恢复。

2.2基于统计的离群点移除算法

假设一个点云文件所包含的点云数量为m个。基于统计的离群点移除算法步骤如下：

步骤1在对点云处理之前，首先需要采用3d kd-tree来对无序点云进行组织。kd-tree是计算机科学中使用的一种数据结构，用来组织表示k维空间中的点的集合。它是一种带有其他约束条件的二分查找树，kd-tree对于区间和近邻搜索十分有用[9]。kd-tree是接下来对点云进行离群点移除与特征恢复的基础，其利用垂直于各个坐标轴的平面来逐级划分区域。经过组织后的点云，每个点都对应二叉树的一个结点。

步骤2然后计算每个点的k邻域平均距离。k邻域是指距离参考点欧式距离最近的k个点的集合。 由于点云中的每个点都变成了二叉树中的一个节点，通过遍历这棵二叉树可以很方便的查找点与点之间的欧氏距离以及k邻域。如公式(1)所示，(x0,y0,z0)为参考点，(xn,yn,zn)为参考点周围k邻域中的点。n为k邻域中的任一点索引，n∈[1,k]。μ为参考点的k邻域平均距离。

(1)

步骤3通过将每个点的k邻域平均距离相加再求平均值。如公式(2)所示，m为点云总个数，μi为当前参考点的k邻域平均距离。计算所有点的平均k邻域距离。

(2)

步骤4 计算所有点的k邻域距离标准差。如公式(3)所示，σ表示k邻域距离标准差。

(3)

2.3基于特征对有信息点云进行恢复

在基于统计的稀疏离群点移除算法的基础之上，采用RANSAC算法对删除点云的特征进行提取并恢复。RANSAC算法最早由Fischler和 Bolles于1981年提出，该算法是根据一组包含异常数据的样本数据集计算出数据的模型参数，从而得到有效样本[10]。经过使用RANSAC算法后的点云，可以为后续处理提供更为可靠的数据基础。

在点云处理的过程中，RANSAC算法可以提取出点云的平面、球面、圆柱面、锥面等特征信息。对于激光扫描仪扫描得到的无序点云而言，并不是点云所有部分都包含可恢复的特征信息，RANSAC算法作为移除稀疏离群点之后的辅助手段可以有效抑制有用点云数据的过度删除。

有特征的墙面信息因为密度较小，超出了正常阈值的范围，于是被删除了，致使墙面的信息遭到了破坏。在删除的离群点中，有特征区域相对于无特征区域的点云相对集中，密度相对较大。RANSAC算法是根据局内点数量的多少来确定拟合平面的，因其可以在密度大的区域获得较多的内点，于是密度大的区域就会有更大的概率优先拟合。被删除的特征区域正好符合以上条件，因此就可以利用RANSAC算法提取特征区域进行恢复。

以下是RANSAC算法提取平面特征的步骤：

步骤1首先是对平面进行建模， 平面方程的一般形式为ax+by+cz+d=0。共有4个参数。其中(a,b,c)为平面的法向量，d为一个常数。

步骤2在样本中选择一个子集，计算模型的参数，从而建立代表这个子集的具体的平面模型。

步骤3设置其他点到平面模型的距离阈值。点到平面模型的距离小于该阈值即设为局内点，大于该阈值设为局外点。由于海龙囤石质建筑风化严重，此处选用了0.1 m作为阈值，如果点云面比较平整，阈值在0.05 m以下较为合适。

步骤4计算局内点与局外点的比值，并与之前计算结果对比，如果比值大于之前计算结果，则将其保留。

步骤5查看是否超过最大迭代次数，则返回2重新计算。迭代次数计k由以下公式(4)得到：

1-p=(1-wn)k

(4)

其中p为迭代过程中随机选取数据集中的点为局内点的概率，w表示局内点数据与数据集数目的比值。wn是所有n个点均为局内点的概率，1-wn是n个点中至少有一个点为局外点的概率。由公式(4)可知p越大迭代次数越高。对上式两边取对数，得到计算迭代次数k的公式(5)：

(5)

一般情况下，为了避免迭代次数过少，导致拟合平面不理想，往往需要在k的基础上乘以一个系数，来增加拟合成功的概率。

步骤6将得到的拟合平面与经过基于统计的离群点删除算法处理后的点云合并，并输出最终点云。

2.4实例分析与算法比较

2.4.1实例分析

扫描数据来源于海龙囤飞凤关墙面的一部分，实际照片与点云如图3所示。

图3　飞凤关墙面Fig.3　Part of the wall of Feifeng

海龙屯石质建筑存在较多的稀疏离群点，以此墙面为例，首先运用基于统计的稀疏离群点移除算法对原始数据进行处理。表1为计算所得到的关键数据。图4为飞凤关墙面点云数据使用该算法处理后的点云效果图。

表1　算法关键参数

图4　稀疏离群点移除后点云效果Fig.4　Rusult of removing sparse outliers

由图4可知，由于墙面数据密度不均，导致墙面有用信息被误删除，所有删除的点如图5所示。

图5　删除的点云Fig.5　Point cloud of removed

对图5中的点使用RANSAC算法提取平面特征，并将提取出的特征点恢复至之前的点云中。最终结果如图5所示。将图6与图4对比可知，最终点云的墙面信息较之前有了很大的改善，同时墙面后的稀疏离群点也得到了有效的抑制。

图6　最终点云数据的正面与侧面图Fig.6　Front view and top view of final point cloud

2.4.2算法比较

为了验证基于特征恢复的稀疏离群点在点云稀疏离群点移除方面的优势，对点云使用基于统计的稀疏离群点移除算法，同时使用基于特征恢复的稀疏离群点移除算法处理点云，对比两种算法处理效果。

如图7所示，分别取阈值为σ、1.5σ、2σ，其中σ为k邻域平均距离的标准差。左侧为经过基于统计的稀疏离群点移除算法处理后的点云正面图像，右侧为经RANSAC算法对点云进行恢复后的点云正面图像。通过对比可得，基于特征恢复的离群点移除算法减小了对先验知识的依赖，在表面信息移除较多的情况下，恢复的效果也比较好。

图7　算法效果对比Fig.7　Comparative effects of two algorithms

3结束语

利用基于统计的离群点删除算法，较好的删除了稀疏的离群点，并针对密度不均匀的点云，利用点云特征对有信息区域进行恢复。在删除稀疏离群点的同时，保留了密度较低的特征区域点云。目前的研究对象是海龙囤石质建筑，相对于现代规则建筑，其表面较为复杂。虽然提取特征较为困难，但是实验结果表明，该算法可以提取这种石质建筑复杂的表面信息并将其恢复，并有显著的效果。为古建筑的后期修复提供了较为完整可靠的资料，也为其后期分析、建模提供了更为有效的数据基础。

参考文献：

[1] 张毅,闫利.地面激光点云强度噪声的三维扩散滤波方法[J].测绘学报,2013，42(4):568-573.

[2] 龚书林.三维激光点云处理软件的若干关键技术[J].测绘通报,2014(6):135-136.

[3] RUSU R B,MARTON ZC,BLODOW N,et al.Towards 3D Point Cloud Based Object Maps for Household Environments[J].Robotics and Autonomous Systems,2008,56(1):927-941.

[4] 张毅,刘旭敏,关永.基于密度的离群噪声点检测[J].计算机应用,2010，30(3):802-805.

[5] 朱俊锋,胡翔云,张祖勋,等.多尺度点云噪声检测的密度分析法[J].测绘学报,2015，44(3):282-291.

[6] HAWKINS D.Identification of Outliers[M].London:Chapman and Hall,1980.

[7] JACOBS G.Accuracy of scan points[J].Professional Surveyor Magazine,2009,29(8):1-3.

[8] 施贵刚,程效军,官云兰,等.地面三维激光扫描点云配准的最佳距离[J].江苏大学学报(自然科学版),2009，30(2):197-200.

[9] 朱德海.点云库PCL学习教程[M].北京：北京航空航天大学出版社,2012：10.

[10]胡伟,卢小平,李珵,等.基于改进RANSAC算法的屋顶激光点云面片分割方法[J].测绘通报,2012(11):31-34.

文章编号：1004—5570(2016)01-0088-05

收稿日期：2015-09-24

基金项目：贵州省科技厅工业攻关项目(黔科合GZ字[2012]3017)；贵州省科学技术基金资助项目(黔科合J字LKS[2011] 9号)；贵州省经济和信息化委员会资助项目(1158)；贵州省科技厅攻关项目：海龙屯申报世界文化遗产关键性技术研究(黔科合SY字[2014]3072号)

作者简介：郭子选(1989-)，男，硕士研究生，研究方向：计算视觉，E-mail：313984057@qq.com. *通讯作者：谢晓尧(1952-)，男，教授，博导，博士，研究方向：网络与信息安全、计算数学，E-mali：xyx@gznu.edu.cn.

中图分类号：TP391

文献标识码：A

Sparse outlier removal algorithm based on resuming features

GUO Zixuan，XIE Xiaoyao*，LIU Song

(Key Laboratory of Information and Computing Science Guizhou Province, Guizhou Normal University, Guiyang， Guizhou 550001, China)

Abstract:The point cloud pre-processing is very important part of point cloud processing. In the process of removing the sparse outliers , the uneven point density of the point cloud can cause excessive deleted of useful information. In order to solve this problem, Sparse outlier removal algorithm based on resuming features is proposed. Firstly, using the traditional k neighborhood sparse outliers removal to processing the original cloud point. For the case of excessive deleted, using the RANSAC algorithm to recovery feature point.The experimental results show that the sparse outlier removal algorithm based on resuming features is better than traditional methods. It makes a significant improvement in sparse outliers removed. The conclusion is that the algorithm can effectively remove the sparse outlier and reduce dependence on the noise threshold. Meanwhile, the algorithm can effectively suppress excessive deleted caused by uneven density.

Key words:3D laser scanner; sparse outliers; k-dimensional tree; k neighborhood; random sample consensus algorithm