这篇博客会介绍点云的基本知识，重点介绍最近两年发表的部分经典论文，有什么建议欢迎留言！
点云基本介绍
点云是某个坐标系下的点的数据集，包含了丰富的信息，可以是三维坐标X，Y，Z、颜色、强度值、时间等等。下面两张图分别展示了点云在三维空间可视化以后的效果和数据格式。点云的数据获取方式有很多种，比较常见的是三维激光扫描仪进行数据采集，它有三大类：
- 星载（星载LiDAR采用卫星平台，运行轨道高、观测视野广，基本可以测量到地球的每一个角落，为三维控制点和数字高程模型的获取提供了新的途径，有些星载激光雷达还具有观察整个天体的能力）
- 机载：机载主要借助无人机（UAV/UAS）进行大规模的点云数据采集。
- 地面分为三小种：地上三维激光扫描、车载MMS、手持激光扫描。
兔子形状的点云
三维点云的数据示例
从上面的数据示例可以看出，点云本质上是一长串点（Nx3矩阵，其中n是点数），这带来两个问题。第一，在几何上，点的顺序不影响它在空间中对整体形状的表示，例如，相同的点云可以由两个完全不同的矩阵表示，如下图所示。我们希望不论点云顺序怎样，模型可以从中得到相同的特征。第二，点云在空间中经过刚性变换后，如旋转或者平移，点云的坐标会变。有时我们为了方便对点云做处理（如分类等），需要将其旋转到正面或者侧面（做旋转），此时，模型得到的点云数据（N*3矩阵）将会完全不同。我们希望点云做变换之后不会影响模型的结果。
传统的点云处理方式包括两大类：
- 将点云数据投影到二维平面。此种方式不直接处理三维的点云数据，而是先将点云投影到某些特定视角再处理，如前视视角和鸟瞰视角。同时，也可以融合使用来自相机的图像信息。通过将这些不同视角的数据相结合，来实现点云数据的认知任务。比较典型的算法有MV3D和AVOD。
- 将点云数据划分到有空间依赖关系的体素（voxel）。此种方式通过分割三维空间，引入空间依赖关系到点云数据中，再使用3D卷积等方式来进行处理。这种方法的精度依赖于三维空间的分割细腻度，而且3D卷积的运算复杂度也较高。
接下来我们会介绍从17年至今比较经典的关于点云的论文，包括PointNet，PointNet++，GeoNet，Kd-Net、SO-Net以及做数据上采样的PU-Net。
PointNet
此处是PointNet的位置
PointNet++
此处是PointNet++的位置
GeoNet
- 论文名 GeoNet: Deep Geodesic Networks for Point Cloud Analysis
- 作者 Tong He，Haibin Huang，Li Yi等
GeoNet是一种基于测地距离的点云分析深度网络，发表在2019年的CVPR上。论文贡献包括两个：开发了一种数据表示以及提出了如何将其运用到下游任务中的方法。为了方便理解论文内容，我们首先来介绍一下测地距离这个概念。
测地距离
我们先从点云的研究任务说起。点云的形状分析是点云的重要任务之一，主要包括三个方面的特征，集合特征、统计特征和拓扑特征。集合特征主要有法向量、曲率等，统计特征主要包括模型顶点间的集合关系、顶点的曲率分布等，拓扑特征主要有突出的特征点、临界点、骨架、Reeb图等，其中骨架是对点云主要特征的一种可视化描述，符合人类的视觉特征。
从目前已有的工作来看，拓扑特征是点云的重要特征之一，对点云的分类、简化、检索等研究有重要的作用。寻找提取点云拓扑特征的简单、有效、快速的方法对点云的形状分析与理解具有重要的意义，测地线就是其中的一种。
测地线是连接曲面上给定的两点之间的最短路径，测地线的长度就是这两点之间的测地距离。根据计算结果的精确性，三维模型的测地距离的计算方法可以分为两大类：精确的方法和近似的方法。可以看做是图论上计算两个点之间的最短路径的计算方法，采用dijkstra等。
GeoNet计算测地距离
GeoNet其实就是利用网络来计算测地距离。我们假设\(\chi = \{ x_{i} \}\)表示点云，每个点的维度为3 。那么我们可以为点\(x_{i}\)定义它的邻居节点为\(B_{r}(x_{i})=\{ x_{j}|d_{E}(x_{i},x_{j}) \le r\}\) 。其中\(d_{E}(x_{i},x_{j})\)表示两个节点之间的欧式距离。也就是说将\(x_{i}\)为球心，半径为r内的节点划为它的邻居节点。这是GeoNet关于邻域的定义。基于此我们继续定义\(G_{r}(x_{i})=\{ g_{i,j}=d_{G}(x_{i},x_{j})|x_{j} \in B_{r}(x_{i}) \}\)，其中\(d_{G}表示测地距离\)，即\(G_{r}(x_{i})\)表示 \(x_{i}\)到邻域内每个点的测地距离的集合。GeoNet的目标是利用神经网络拟合映射关系：\(f:x_{i} \to G_{r}(x_{i})\)，它的网络结构如下图所示。
如图所示，GeoNet由两个模块组成：特征提取模块以及测量匹配模块。其中特征提取模块利用PointNet++提取点云的局部特征，再将其输入解码器，同时还将原始的点云输入解码器（skip connection），这样解码器可以对点云的局部特征和总体特征做处理。测量匹配模块利用特征抽取模块得到的特征向量为每个节点计算其邻域测地距离。但该模块的目的并不是计算出准确的测地距离，而是在模型不断拟合测地距离的过程中，其参数矩阵会隐含的提取出一些特征。（笔者私以为，GeoNet的作用就是进行特征提取，在训练模型计算测地距离的过程中，模型的参数包含了点云的一些特征）
论文中还详细介绍了GeoNet如何与下游任务：分类、分割等做融合，并给出了示例。
Kd-Net
- 论文名 Escape from Cells: Deep Kd-Networks for the Recognition of 3D Point Cloud Models
- 作者
Kd-Net是一种基于Kd-tree的网络，我们先对Kd-tree加以介绍。
Kd-tree
KD树是从二叉搜索树发展来的，是一种高维索引树形数据结构，常用于大规模高维数据密集的查找比对的使用场景中，主要是最近邻查找以及近似最近邻查找，在CV中主要是图像检索和识别的高维特征向量的查找和比对。
我们举例讲述如何构建一个三维的KD树。我们可以在第一层选择用节点的第一维数据作为分类依据，第二层用第二维数据，第三层用第三维数据，第四层用第一维数据，以此类推。用图中的数据来说明：
- 根节点为（3，1，4），分类依据为3。
- 拿到第二个数据（2，3，7），先与根节点（3，1，4）比较，第一层节点的分类维度为一，（2，3，7）的第一维数据小于根节点的第一维数据，所以下一步与根节点的左节点做比较，发现左节点为空，将（2，3，7）放在左节点。
-
拿到第三个数据（2，1，3），先与根节点（3，1，4）比较，第一层节点的分类维度为一，（2，1，3）的第一维数据小于根节点的第一维数据，所以下一步与根节点的左节点做比较。左节点为（2，3，7），第二层节点的分类维度为二，（2，1，3）的第二维数据比（2，3，7）的第二维数据小，下一步与其左节点作比较。左节点为空，将（2，1，3）插入该点。
KD树构建过程
二维KD树的表示方法利用Kd_tree构建Kd-net
了解了如何构建Kd-tree后，我们来看如何根据点云构建Kd-tree进一步组成Kd-net。
下图左边是建好的Kd-tree，编号为8-15的是8个数据点。可以看到紫色的是第一次切割，蓝色和红色是第二层，绿色和橙色（或红色？）是第三层。该示意图用二维展示了三维点云的kd-tree，在三维空间中，切割的方向是x,y,z轴。为了将点云向量化，作者先用预训练好的数据将叶子节点（8、9、12、13、14、15）向量化，然后根据公式逐层向上计算每个节点的向量表示，直到所有的节点都被向量化。
图中的右半部分是Kd-net的结构图，其中灰色的条表示网络的节点，中间的圆圈是网络的参数，第一层是所有数据点的向量表示。网络经过一次前向传播得到一个特征向量，即图中标号为1的节点，该节点提取了所有数据的特征。标号为1的特征向量经过一个全连接层得到节点0，即分类结果。其中，相同颜色的圆圈表示网络中的共享参数。节点之间共享参数的条件为：在Kd-tree中是同一层，且分割的方向都相同。可以看到节点8、9、12、13、14、15在同一层且分割的方向都相同：平行于y轴。
kd-tree和kd-net
kd-tree向量化公式
持续更新...