三维点云预处理之点云去噪

1.点云数据的去噪

   在测量数据的过程中，我们往往会不可避免的引入噪声点，点云数据预处理的一个步骤就是除去这些会对结果产生影响的错误的噪声点。

   点云数据的去噪方式有很多，不同的点云类型也可以通过分析其具体特征选择适合的去噪方法，如对于扫描线型的点云分布类型，通过拟合曲线求偏差可以很好的过滤掉噪点（可参考你做物理实验时对数据的处理方法）。而本文主要介绍通用的适合多数类型的去噪方法，其在处理点云时将点云视为一团在空间中杂乱分布的点，而不去刻意考虑点云的分布类型。

   其实参考物理实验对数据的处理方法，我们往往会默认不合群的数据为误差较大的点，因此去噪的核心就是找出这些不合群的点。这些点叫做**孤立点**，又叫**离群点**、**异常点**等。而所谓的离群可以指该点与其他点的距离大于一定值，复杂点的定义引入了孤立因子的概念等，因此离群一词虽然不好定义但又很十分形象。

补充：孤立点的分类：全局孤立点、集合孤立点等。

   很容易会想到可以通过求某一点与周围的点之间的距离来判断离群点（这也是目前比较常用的方法，其他也可通过统计、密度等方法判断，但很明显操作性和适用性会受到影响），可是对于大量无序的点来说，想要找到某一点其附近的点（即距离较近的点）并不容易，不同于肉眼一眼就能发现，计算机可能要求出该点到所有点的距离才能判断，这是一项非常耗时耗力的工作。因此对于大量无序的点，我们往往会考虑先将点数据按一定规则（空间索引方法）进行排列，这将会大大提高后续点云处理的速度。常见的排序方法有八叉树法、kd-tree法等。

补充：（1）八叉树：一种用于描述三维空间的树状数据结构，八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点（222）。

（2）kd-tree法：用于存储k维数据而提出的数据结构，是一种特殊的二叉树（指树中节点的度不大于2的有序树，其子节点数小于等于2）。其按照维度进行划分，每次划分替换一个维度，然后循环维度进行划分。（听起来有些复杂，其实对于三维来说就是按照进行点的划分，使每一个点都在节点上，直到分完每一个点。具体步骤如下：1.先将点按x坐标大小进行排序，将中间那个点放在第一个节点，剩下的自然而然分成两个部分，就有了两个子节点。2.每个部分再按y坐标大小进行排序，再将中间那个点放在刚刚的那两个节点上，又出现了2*2个部分和子节点。3.再按z坐标大小分，分完又按x坐标分。。。直到分完所有的点。）

   经过特定规律排列后，便包含了一定的点与点之间的位置信息，下面我们将考虑通过**平均邻域算法**来检测孤立点。平均邻域算法是一种基于距离的孤立点检测方法，通过计算点云数据中的点与其邻近点之间的距离的平均值是否超过定值来判断。

具体步骤如下：

（1）将点按照一定规律进行排列，这里我们采用kd-tree法；

（2）取三维点云数据的任一点，搜索该点的k近邻点；

补充：k邻点搜索方法：先通过二叉搜索找到一个当前的最近邻点（若该点存在于树中则即为该点），再以该节点进行正反向搜索判断k个距离最小的点（应按距离从小到大的顺序搜索）。

（3）计算该点与其k近邻点的平均距离并与设定值进行比较判断是否为孤立点。

补充：平均邻域算法的缺点是不好检测出紧挨点群的噪点，不过可以考虑进另一些判断因素，比如可以给距离的标准差设一个阈值，或者给该点与其k邻点的中心点之间的距离设一个阈值等，这就看你具体想要如何优化，提出你个人的观点了。