点云处理被广泛应用在三维重建、逆向工程、自动驾驶、 AOI检测等3d领域！此外，各类3d传感器直接扫描获得的原始数据都包含噪声，因此我们需要对原始数据进行预处理，才便于后续任务的执行。

图1 常见3d点云传感器

相关的行业应用：

图2 常见3d点云处理应用

点云实际应用阶段：

• 3d建模 ：例如最近非常火的黑神话悟空（虚幻5游戏引擎）渲染模型时，点云也要转化为三角模型，这样才便于进行物理碰撞、光线追踪等运算。
• 自动驾驶 ：语义分割、点云包围框计算，需要分割出每个车辆、人物、街景的点云。
• 点云测量 ：计算某些点云平面的的平面度、两个点之间的距离等（PolyWorks）。
• 逆向工程 ：分割出某些平面、曲面，将其进行参数化建模（Geomegic design）。

01 完整点云处理案例

在此之前，可能你并没有实际使用过一款三维扫描仪，在这里，我们 展示本节课涉及的点云处理任务的完整全过程。 在三维激光扫描的过程中，实际捕获的点云数据存在下述问题：

1. 遮挡、噪声： 常常会受到物体遮挡、光照不均匀等因素的影响，容易造成复杂形状物体的区域扫描盲点，形成孔洞。
2. 测量范围有限： 同时由于扫描测量范围有限，对于大尺寸物体或者大范围场景，不能一次性进行完整测量，必须多次扫描测量。

首先要对点云进行滤波，去除噪声点：

(a) 采集自激光雷达的点云滤波效果   （红色的为噪声点）	(b) 采集自3d结构光相机的点云滤波效果   （高反光引起的）
图3 点云滤波效果

1.2 点云降采样

在精度允许的前提下，我们必须减少点云数据，否则运算将会消耗大量时间。从实践来看， 这一步是非常必要的，否则写的程序很可能都在“转圈”阶段。 主要分为两种：

图4 点云降采样：体素滤波

1. 抽稀简化： 扫描的数据密度过大，数量过多，其中一部分数据对于后期建模用处不大，所以在满足一定精度以及保持被测物体几何特征的前提下，对数据进行精简。
2. 冗余数据： 是指在数据配准之后，其重复区域的数据，这部分数据的数据呈大，多为无用数据，对建模的速度以及质量有很大影响，对于这部分数据要予以去除。

1.3 点云配准

(a) 点云配准：鼠标	(b) 点云配准：叶片
图5 示范案例：点云配准

通常，无法一次性扫描完整个场景的点云，因此需要对点云进行配准，主要有：

1. 粗配准 ：在点云位姿完全未知的情况下对点云进行配准，为后续精配准提供初值。粗配准方法包括：

• 穷举搜索： 遍历整个变换空间，以选取：使误差函数最小化的变换关系，或者最多点对满足的变换关系，例如：RANSAC、四点一致集（4-Point Congruent, 4PCS）、Super4PCS算法。
• 特征匹配： 根据被测物、点云本身特点，构建点云之间的匹配关系。例如：FPFH特征的SAC-IA、FGR算法。SHOT特征的AO算法、线特征的ICL算法（当然，这些特征都比不过人工圆环特征精确）。

1.4 采样一致性

有时候，我们需要分割出一些规律形状（能用方程描述）的点云，用来计算某些指标。例如：平面点云计算平面度，对圆柱点云拟合直径，对球状点云拟合球的半径：

(a) 圆柱点云	(b) 球体点云
图6 RANSAC采样一致性

注：

• 采样一致性 （ RANSAC ）：分割规律点云（能用方程描述） 。
• 点云分割 ：根据距离、点云密度、区域生长、或深度学习方法对无规律点云进行分割。

1.5 点云分割

点云分割将点云数据划分为不同的部分或物体，以便更好地理解和分析它们。下面是课程中某节课，原始点云 vs 点云分割结果：

(a) 原始点云	(b) 分割点云
图7 点云分割结果

分割后的点云在多个领域中都有广泛的应用，‌包括但自动驾驶、‌城市规划与建筑设计、‌工业制造与智能制造、‌地质勘探与资源开发，‌以及智慧城市与环境监测等领域。

1.6 包围盒计算

包围盒计算经常用于自动驾驶或者6D姿态抓取：

(a) 自动驾驶	(b) 机械臂抓取
图8 包围盒应用

那么，怎么将它们串起来呢？本课程即从整体上讲解上述内容！

02 PCL点云库框架

在说PCL之前，不得不提另外一个最新的点云处理库：Open3D。两种库有各自适应的范围，并没有优劣之比，个人使用下来总结对比如下：

1. Open3D对Python的支持性更好！深度学习框架大多使用Open3D进行点云处理。
2. PCL对QT的支持更好，例如可以直接嵌入QT版本，工业上使用较多。
3. PCL依赖于各个库，例如VTK、Boost、并且需要自己编译，还是比较费劲的。
4. PCL各个版本代码的兼容性较差，一些算法在某些特定版下使用会报错。

PCL（Point Cloud Library）实现了大量点云相关的通用算法和高效数据结构，涉及到点云获取、滤波、分割、配准、检索、特征提取、识别、追踪、曲面重建、可视化等功能。整体框架如下：

图9 PCL整体软件框架

PCL点云库：基于Boost、Eigen、FLANN、VTK、CUDA、OpenNI、Qhull等开源库，广泛应用于机器人、人机交互、虚拟现实、激光遥感测绘、逆向工程等领域。兼容多个操作系统和硬件平台。包含的模块包括： IO输入模块、八叉树、Kd树、滤波、配准 等等模块 的大型C++点云处理库。下面我们对这些模块，按照它们的功能不同，分开介绍。

图10 点云处理主要流程框架

PCL的模块和工作流程如图10所示：

01 数据结构与算法

1. kd-tree： 二叉搜索树，用于解决K维空间的** 最近邻搜素问题 **。最近邻搜索在特征匹配、描述子计算、邻域检测等算法中都有广泛应用。
2. 八叉树： 八叉树是一种将空间分为8个子空间的数据结构，可以用来执行碰撞检测、邻域检测、空间变换检测、快速对三维目标进行交、并、补、差等集合运算。
3. Search： 定义了大量搜索算法，包括：KD树、八叉树、FLANN等快速搜索算法。
4. Common模块：
1. 点云数据结构： PointCloud类，用于表示点、曲面、法向量、特征描述
2. 公共工具方法： 计算距离、均值、协方差、角度转换等方法。

注：kd-tree和八叉树都是非常重要的数据结构，之后很多算法，都是基于它们基础之上的，因此需要着重了

02 点云获取

1. 输入、输出IO： 点云数据的读取、保存功能。
2. 点云格式转换： 删除冗余数据，保留点云处理所需要的XYZ、RGB信息，转化为统一数据格式，方便后续处理。

03 点云预处理

1. 滤波Filters： 因为测量误差的原因，直接扫描获得的点云含有大量噪声，我们需要对点云进行去噪声和离群值。另外，数据量也可能过大，这就需要降采样模块。
2. 特征提取：
1. 特征Features： 提取特征描述子，包含从点云数据计算3d特征的数据结构和机制。三维特征是空间中某一三维点的表示形式，它可以根据该点周围的可用信息来描述。
2. 关键点Keypoints： 比较有特色、突出的点，可以用来计算关键信息。

关键点 ：一些比较突出的关键点，比如说颜色突出点、曲率突出点等；

特征库 ：计算某些点周围点云的特征描述，将关键点建立对应关系，对多片点云进行配准或分割等任务。

示范 ：某个点云配准任务，直接ICP配准计算量太大，先计算关键点，然后对这些关键点计算特征，进行点云粗配准。

:::

(a) 点云滤波	(b) 特征提取	(c) 关键点：keypoints
	局部点云	整体点云
(d) 点云配准	(e) 表面重建
图11 PCL不同模块展示（一）

04 三维重建技术

1. 点云配准： 为无序、有序点云提供大量的配准算法，关键点：确定点云数据集之间的对应点，使得每个点之间的距离最小。
2. 表面重建： 点云存在噪声，直接重建的点云表面较为粗糙，多片点云对齐后也需要进行重采样，然后表面进行光滑，得到最终的点云表面。并且三角化为后续应用做铺垫。

(a) 采样一致性	(b) 点云分割
图12 PCL不同模块展示(二)

05 点云感知技术

1. 采样一致性： 用于圆柱、平面等规则几何体的拟合、分割任务，包括：
1. 线：平行线、条、杆状物体
2. 面：垂直于指定轴向、法向约束的平面。
3. 圆：平面、空间上的圆、球、圆柱、圆锥、球体等。
2. 点云分割： 将点云分割为多个簇的点云，例如自动驾驶中自动分割路面、路杆、行人等。

注：在PCL实现中，分割模块也包含前面的采样一致性模块。

3. 点云识别： 物体点云识别应用算法，类似于将2d模板应用到3d点云上。

:::

03 课程大纲