A. 1.特征点检测与匹配
三维模型重建的流程：
三维点云获取——几何结构恢复——场景绘制
三维点云获取：
1.激光雷达
2.微软Kinect
有效距离比较短
3.单目多视角 ：几乎很难实时
4.双目立体视觉
基于图像的三维模型重建：
1.输入图像
2.基于图像的点云生成
3.点云到模型的重建
4.纹理图像的创建与编辑
5.纹理模型
相关商业软件：
Acute3D,Altizure,Agisoft PhotoScan
图像特征点应用：
1.相机标定
2.图像拼接
3.稠密重建
4.场景理解
图像特征点的检测方法：
图像特征点的基本要求：
1.差异性——可检测
特征点应该呈现出区别于非特征点的明显特征
2.重复性——可匹配
对应同一三维点的特征点应该在不同视角中被重复检测到
动机：特征点具有局部差异性
图像梯度
Harris矩阵
Harris矩阵H的特征值分析：
矩阵特征值反应了两个垂直方向的变化情况，一个事变化最快的方向，一个事变化最慢的方向
行列式值为特征值相乘，行列式的迹为特征值相加
在特征点附近，其他点的响应也比较大。
所以选取局部响应最大值，避免重复检测
算法流程
Harris角点检测一般用于快速检测，比如视频里面的跟踪
动机：Harris角点检测不具有尺度不变性
LoG算子：Lindeberg(1993)提出Laplacian of Gaussian
(LoG)函数的极值点对应着特征点
Lindeberg(1993)提出Laplacian of Gaussian
(LoG)函数的极值点对应着特征点
尺度空间：
对于一幅图像，用不同大小的滤波核进行滤波，一般用高斯滤波，得到一系列图像，这些图像就称之为尺度空间。然后把这些图像摞起来
LoG特征检测效果好，但是计算量比较大。
工程中也很少用。为了更好地利用LoG的性质，提出了一种近似的算法：基于DoG的特征检测子
LoG可以由DoG近似：
Lowe(2004)提出LoG近似等价于相邻尺度的高斯差分(DoG)
高斯空间：
高斯差分(DoG)
上图为3个Octive,每个octive的尺寸都会减小一半。
上图每个Octive中，左侧为高斯空间，相邻高斯空间做差得到DoG空间
特征点检测为在三维空间上做一个极值的比较，(三维空间为图像的二维空间+尺度的空间)，必须需要两个方向有极值。在高斯差分，边界上的两层是无效的，只有中间的红色区域是有效的。
在Octive,
if 每阶有效差分数 S =3，则高斯空间层数为N = S+3
特征点位置确定:
在位置和尺度空间组成的三维空间中寻找极值点
亚像素特征点位置确定：
除去边缘点：
DoG在边缘处值较大，需要避免检测到边缘点
通过统计梯度直方图的方法确定主方向，使算法具有旋转不变性
旋转 不变性、 尺度 不变性 、亮度 变化 不变性 ，对视角变化、 仿射 变换有一定程度的稳性
SIFT特征点非常稳定和鲁棒，但是计算量很大，对于要求稳定的图像建模可以采用。
针对实时要求比较高的应用提出了快速特征检测。
FAST特征点(Feature from Accelerated Segment Test)
通过检测局部像素灰度变化来确认特征点的位置
速度快，SIFT的一百倍，不具有尺度和旋转不变性
基于直方图的描述子
基于不变性的描述子
二进制描述子
以特征点为中心取一块区域，有圆形或者矩形，称之为特征支持区域
主方向：进行旋转并重新插值
特征尺度：影响支持区域的大小
用于微小运动的描述子
以特征点为中心的矩形区域内所有
像素的灰度值作为描述子,拉成一个向量，计算向量间距离
适用于微小变化的图像
对图像存在明显的旋转、尺度、光照和透视变换时不稳定
根据主方向对支持区域进行旋转，并通过双线性插值重构
减去均值再除以方差
图像归一化处理，去除光照变化
描述子形式：
描述向量由N个0或者1组成
N= 128，256,512
生成速度快，匹配效率高，不具有旋转不变性
最近邻搜索
最近邻距离比(lowe-ratio)
最近邻距离和次近邻距离比小于一定值
快速最近邻搜索
哈希表
多维Kd-tree
BFM(Bruce Force Mather)匹配ORB的结果
错误的匹配可以通过估计相机模型方式去除
估计 Homography Homography 矩阵之前最好的 50 对匹配对
B. 如何获取点云PointCloud数据
一：什么是点云数据
点云数据是指在一个三维坐标系统中的一组向量的集合。这些向量通常以X,Y,Z三维坐标的形式表示，而且一般主要用来代表一个物体的外表面形状。不经如此，除（X,Y,Z）代表的几何位置信息之外，点云数据还可以表示一个点的RGB颜色，灰度值，深度，分割结果等。
Eg..Pi={Xi, Yi, Zi,…….}表示空间中的一个点，
则Point Cloud={P1, P2, P3,…..Pn}表示一组点云数据。
二：点云数据的获得
大多数点云数据是由3D扫描设备产生的，例如激光雷达(2D/3D)，立体摄像头(stereo camera)，越渡时间相机(time-of-flight camera) 。这些设备用自动化的方式测量在物体表面的大量的点的信息，然后用某种数据文件输出点云数据。这些点云数据就是扫描设备所采集到的。
三：点云数据的用途
作为3D扫描的结果，点云数据有多方面的用途，包括为制造部件，质量检查，多元化视觉，卡通制作，三维制图和大众传播工具应用等创建3D CAD模型。
C. 提取平面点云的轮廓
一. 基于凸包的凹点挖掘算法：
1. 提取点云的凸包
2. 计算凸包每条边的顶点的点密度（即该点 K 个临近点到该点的距离平均值）
3. 如果顶点点密度大于所在边的长度的 X 倍，则删除该边，并从内部点中选择出一个满足夹角最大的点，插入边界边，形成两条新的边界边
4. 迭代 2 和 3，一直到全部边界边的 X 倍小于其端点的点密度，算法结束
二. 基于 Delaunay 三角网的轮廓提取算法：
A. 不使用辅助点：
1. 首先对点云进行 Delaunay 三角构网
2. 同上，判断每条网格边长度的X倍和其端点的点密度之间的大小关系，并删除长的网格边
3. 提取只属于一个三角形的边界，作为边界边
4. 分类排序，得到有顺序关系的内外轮廓
B. 使用辅助点：
1. 手动在点云的边界附近选点
2. Delaunay构网
3. 判断每个三角形，如果其中一个点是辅助点，而另外两个点是点云中的点，则连接这两个点做为边界边
4. 分类排序，得到有顺序关系的内外轮廓
总体来说，由于构网算法的时间复杂度较高，因此可以有选择的使用上面两种算法，比如只有在确定要提取内轮廓的情况下，可以选择第二种轮廓提取算法
D. 点云概念与点云处理
点云概念
点云与三维图像的关系 ：三维图像是一种特殊的信息表达形式，其特征是表达的空间中三个维度的数据，表现形式包括：深度图（以灰度表达物体与相机的距离），几何模型（由CAD软件建立），点云模型（所有逆向工程设备都将物体采样成点云）。和二维图像相比，三维图像借助第三个维度的信息，可以实现天然的物体——背景解耦。点云数据是最为常见也是最基础的三维模型。点云模型往往由测量直接得到，每个点对应一个测量点，未经过其他处理手段，故包含了最大的信息量。这些信息隐藏在点云中需要以其他提取手段将其萃取出来，提取点云中信息的过程则为三维图像处理。
点云的概念 ：点云是在同一空间参考系下表达目标空间分布和目标表面特性的海量点集合，在获取物体表面每个采样点的空间坐标后，得到的是点的集合，称之为“点云”（Point Cloud）。
点云的获取设备 ：RGBD设备是获取点云的设备，比如PrimeSense公司的PrimeSensor、微软的Kinect、华硕的XTionPRO。
点云的内容 ：根据激光测量原理得到的点云，包括三维坐标（XYZ）和激光反射强度（Intensity），强度信息与目标的表面材质、粗糙度、入射角方向，以及仪器的发射能量，激光波长有关。
根据摄影测量原理得到的点云，包括三维坐标（XYZ）和颜色信息（RGB）。
结合激光测量和摄影测量原理得到点云，包括三维坐标（XYZ）、激光反射强度（Intensity）和颜色信息（RGB）。
点云的属性 ：空间分辨率、点位精度、表面法向量等。
点云存储格式 ：*.pts; *.asc ; *.dat; .stl ; [1] .imw；.xyz； .las。LAS格式文件已成为LiDAR数据的工业标准格式，LAS文件按每条扫描线排列方式存放数据,包括激光点的三维坐标、多次回波信息、强度信息、扫描角度、分类信息、飞行航带信息、飞行姿态信息、项目信息、GPS信息、数据点颜色信息等。
C–class（所属类）
F一flight（航线号）
T一time（GPS时间）
I一intensity（回波强度）
R一return（第几次回波）
N一number of return（回波次数）
A一scan angle（扫描角）
RGB一red green blue（RGB颜色值）
点云的数据类型 ：
（1）pcl::PointCloudpcl::PointXYZ
PointXYZ 成员：float x，y，z;表示了xyz3D信息，可以通过points[i].data[0]或points[i].x访问点X的坐标值
（2）pcl::PointCloudpcl::PointXYZI
PointXYZI成员：float x, y, z, intensity; 表示XYZ信息加上强度信息的类型。
（3）pcl::PointCloudpcl::PointXYZRGB
PointXYZRGB 成员：float x,y,z,rgb; 表示XYZ信息加上RGB信息，RGB存储为一个float。
（4）pcl::PointCloudpcl::PointXYZRGBA
PointXYZRGBA 成员：float x , y, z; uint32_t rgba; 表示XYZ信息加上RGBA信息，RGBA用32bit的int型存储的。
（5） PointXY 成员：float x,y;简单的二维x-y点结构
（6）Normal结构体：表示给定点所在样本曲面上的法线方向，以及对应曲率的测量值，用第四个元素来占位，兼容SSE和高效计算。
点云的处理
点云处理的三个层次 ：Marr将图像处理分为三个层次，低层次包括图像强化，滤波，关键点/边缘检测等基本操作。中层次包括连通域标记（label），图像分割等操作。高层次包括物体识别，场景分析等操作。工程中的任务往往需要用到多个层次的图像处理手段。
PCL官网对点云处理方法给出了较为明晰的层次划分，如图所示。
此处的common指的是点云数据的类型，包括XYZ，XYZC，XYZN，XYZG等很多类型点云，归根结底，最重要的信息还是包含在pointpcl::point::xyz中。可以看出，低层次的点云处理主要包括滤波（filters），关键点（keypoints）/边缘检测。点云的中层次处理则是特征描述（feature），分割（segmention）与分类。高层次处理包括配准（registration），识别（recognition）。可见，点云在分割的难易程度上比图像处理更有优势，准确的分割也为识别打好了基础。
低层次处理方法:
①滤波方法：双边滤波、高斯滤波、条件滤波、直通滤波、随机采样一致性滤波。②关键点：ISS3D、Harris3D、NARF，SIFT3D
中层次处理方法：
①特征描述：法线和曲率的计算、特征值分析、SHOT、PFH、FPFH、3D Shape Context、Spin Image
②分割与分类：
分割：区域生长、Ransac线面提取、全局优化平面提取
K-Means、Normalize Cut（Context based）
3D Hough Transform(线、面提取)、连通分析
分类：基于点的分类，基于分割的分类，基于深度学习的分类（PointNet，OctNet）
高层次处理方法：
①配准：点云配准分为粗配准（Coarse Registration）和精配准（Fine Registration）两个阶段。
精配准的目的是在粗配准的基础上让点云之间的空间位置差别最小化。应用最为广泛的精配准算法应该是ICP以及ICP的各种变种（稳健ICP、point to plane ICP、Point to line ICP、MBICP、GICP、NICP）。
粗配准是指在点云相对位姿完全未知的情况下对点云进行配准，可以为精配准提供良好的初始值。当前较为普遍的点云自动粗配准算法包括基于穷举搜索的配准算法和基于特征匹配的配准算法。
基于穷举搜索的配准算法：遍历整个变换空间以选取使误差函数最小化的变换关系或者列举出使最多点对满足的变换关系。如RANSAC配准算法、四点一致集配准算法（4-Point Congruent Set, 4PCS）、Super4PCS算法等……
基于特征匹配的配准算法：通过被测物体本身所具备的形态特性构建点云间的匹配对应，然后采用相关算法对变换关系进行估计。如基于点FPFH特征的SAC-IA、FGR等算法、基于点SHOT特征的AO算法以及基于线特征的ICL等…
②SLAM图优化
Ceres（Google的最小二乘优化库，很强大）， g2o、LUM、ELCH、Toro、SPA
SLAM方法：ICP、MBICP、IDC、likehood Field、NDT
③三维重建
泊松重建、 Delaunay triangulations、表面重建，人体重建，建筑物重建，树木重建。结构化重建：不是简单的构建一个Mesh网格，而是为场景进行分割，为场景结构赋予语义信息。场景结构有层次之分，在几何层次就是点线面。实时重建：重建植被或者农作物的4D（3D+时间）生长态势；人体姿势识别；表情识别；
④点云数据管理：点云压缩，点云索引（KD、Octree），点云LOD（金字塔），海量点云的渲染
E. 激光点云预处理研究概述
3D点云数据的预处理是利用有效点云信息进行三维重建及障碍物感知的基础，是3D点云配准、3D点云拼接环节的前提。一般的 3D 点云预处理工作包括地面点云去除、点云滤波和点云分割。在三维点云数据处理过程中，点云数据离群点、噪声点的剔除以及点云数据的配准不仅是点云数据处理中的重要环节，也是后期对点云数据进行特征提取完成检测环节的基础。
在进行目标物体分割时，将离散的三维数据点聚类的判断依据为点与点之间距离是否接近，而在激光雷达点云数据中，有很大一部分数据属于地面点数据，并且地面点云呈现为纹理状，这对后续障碍物点云的分类，识别带来干扰，如果不将这些地面点数据去除，在进行目标物体分割时会导致分割算法失效，因此需要先进行过滤。所以，地面点云数据去除是减少数据量以及提高分割算法准确度的有效手段。
因此为了提高去除地面点云算法的准确性和鲁棒性，许多学者提出了大量研究方法，这些方法主要有以下两类：基于栅格图方法的地面去除研究、基于三维激光雷达原始扫描线数据的地面去除研究。
通过激光雷达扫描得到的点云包含大部分地面点，常用的栅格图方法地面滤除点云方法有栅格高度差法、法向量方法和高度法。栅格高度法首先根据栅格大小生成网格，计算每个网格最低点与最高点的高度差，比较h与预设高度差阈值大小，对网格进行分类，最后根据网格对网格内的点进行分类。法向量法是基于计算出地面法向量为竖直向下或向上的假设，即地面点法向量值为(0,0,1)或(0,0,-1)。方法过程是计算点法向量并设定点分类的法向量阈值。高度法去除地面点云，是最常用且耗时最小的方法。根据激光雷达安装位置与姿态，可以根据设定阈值直接将点云分为地面点和障碍物点。
基于栅格图的点云处理方式是通过将三维点云数据投影到地面，建立多个栅格单元，采用连通区域标记算法或者邻域膨胀策略对目标进行聚类，这类方法被广泛应用在激光雷达三维建模中。一是因为三维点云向二维平面投影过程极大地压缩了数据量，能够提高算法处理的实时性；二是因为点云向栅格图的映射，将复杂的三维点云处理问题转化为图像处理问题，可以使用成熟的图像处理相关算法，提高了算法处理的时间效率。栅格法简单可靠、计算效率高，但是栅格单元参数固定且往往凭经验确定，远距离目标点云较为稀疏往往会出现过分割，而近距离目标点云较为稠密又会出现欠分割，算法严重依赖于阈值参数的选择，且往往需要逐帧进行分析，必然损失部分实时性。
由于三维激光雷达的原始三维数据包含了详细的空间信息，所以也可以用来进行相关点云数据处理。激光扫描线在地面和障碍物形成的角度值存在显着的不同，可作为分离地面点的重要依据。激光雷达中的多个激光器水平扫描周围环境中的物体，在两个相邻物体之间形成的角度很小，而同一物体的角度值很大。这启示了我们可以充分利用这一特性，大于角度阈值可认为这两点是同一物体，较好地处理了相邻目标欠分割的问题。通过将非地面点云分割为不同物体，然后进行目标物体的识别，可以为无人车提供更加详细的车辆、行人等障碍物信息，在运动中避免与不同类型的障碍物发生碰撞并进行及时避让。地面点云欠分割会导致目标漏检，过分割又会对后续的识别等操作带来影响。利用激光雷达产生点云的几何特性，研究人员提出了多种特征构建的方法，基于三维激光雷达原始扫描线数据的地面去除研究属于其中较为常用的方法。
激光雷达在采集三维点云数据的过程中，会受到各类因素的影响，所以在获取数据时，就会出现一些噪声。其实在实际工作中除了自身测量的误差外，还会受到外界环境的影响如被测目标被遮挡，障碍物与被测目标表面材质等影响因素；另外，一些局部大尺度噪声由于距离目标点云较远，无法使用同一种方法对其进行滤波。
噪声就是与目标信息描述没有任何关联的点，对于后续整个三维场景的重建起不到任何用处的点。但是在实际的点云数据处理算法中，把噪声点和带有特征信息的目标点区别开来是很不容易的，去噪过程中由于许多外在因素总是不可避免的伴随着一些特征信息的丢失。一个好的点云滤波算法不仅实时性要求高，而且在去噪的同时也要很好的保留模型的特征信息[88]。就需要把点云数据的噪声点特征研究透彻，才能够提出效果更好的去噪算法。
点云数据是一种非结构化的数据格式，激光雷达扫描得到的点云数据受物体与雷达距离的影响，分布具有不均匀性，距离雷达近的物体点云数据分布密集，距离雷达远的物体点云数据分布稀疏。此外，点云数据具有无序和非对称的特征，这就导致点云数据在数据表征时缺乏明确统一的数据结构，加剧了后续点云的分割识别等处理的难度。神经网络作为一种端到端的网络结构，往往处理的数据是常规的输入数据，如序列、图像、视频和3D数据等，无法对点集这样的无序性数据直接进行处理，在用卷积操作处理点云数据时，卷积直接将点云的形状信息舍弃掉，只对点云的序列信息进行保留。
点云滤波是当前三维重建技术领域的研究热点，同时也是许多无人驾驶应用数据处理过程中至关重要的一步。3D点云滤波方法主要可以分为以下三类，主要包括基于统计滤波、基于邻域滤波以及基于投影滤波。
由于统计学概念特别符合点云的特性，因此，许多国内外学者都将统计学方法引用到点云滤波技术中，Kalogerakis 等人将一种稳健统计模型框架运用到点云滤波中，取得了非常好的滤波效果。在这个统计模型框架中，通过使用最小二乘迭代方法来估计曲率张量，并在每次迭代的时候根据每个点周围的领域来为样本分配权重，从而细化每个点周围的每一个邻域。然后利用计算获得的曲率以及统计权重来重新校正正态分布。通过全局能量的最小化并通过计算出的曲率和法线来把离群点去掉，并且能较好的保持点云的纹理特征。
基于邻域的点云滤波技术，就是通过使用一种相似性度量的方法来度量点和其他周围邻域对滤波效率与结果影响比较大点的相似性，从而来确定滤波点的位置。一般来说，可以通过点云的位置、法线和区域位置来度量其相似性。1998年，Tomasi等人将双边滤波器扩展到 3D 模型去噪，由于双边滤波器具有维持边缘平滑的特点，所以在除去点云数据噪声的同时也能较好的保持细节。但是，由于该方法是通过一个网格生成的过程来去噪的，而在生成网格的过程就会引入额外的噪声。相比较于规则格网、不规则三角网等数据结构，体元是真3D的结构并且隐含有邻域关系，能够有效的防止生成网格的过程中引入噪声，但该方法的需要设置的参数比较多，不能满足实际工业运用。
基于投影滤波技术通过不同的投影测量来调整点云中每个点的位置，从而实现噪声点云的去除。但是，如果输入的点云特别不均匀，经过局部最优投影处理后的点云将变得更散乱。孙渡等人提出了一种基于多回波及 Fisher 判别的滤波算法。首先结合格网划分思想划分点云网格，在每个网格内，通过点云数据的回波次数和强度进行划分，分出待定的样本；其次，利用Fisher判别的分析法将点云投影到一维空间内，通过判定临界值将植被点云与地面点云分离，实现陡坡点云的滤波，但是，该方法只针对点云中含有回波强度的属性才有效，对于不包含回波强度信息的点云，该方法失去作用。
为弥补点云本身的无序性、不对称性、非结构化和信息量不充分等缺陷，在对点云进行特征识别及语义分割等操作之前，需先对点云进行数据形式的变换操作。常用的点云形式变换方法有网格化点云、体素化点云、将点云进行球面映射等。
体素化是为了保持点云表面的特征点的同时滤除不具备特征的冗余的点云数据。由于常用的法向量计算取决于相邻点的数量，并且两个云点的分辨率也不同。所以具有相同体素大小的体素化就是为了在两个不同分辨率的点云中生成等效的局部区域。在实际进行点云配准算法的过程中，由于用于配准的源点云数据与目标点云数据的数量比较庞大、点云密集，并且这些原始点云数据中含有许多点云对于描述物体形状特征没有任何作用的点，如果使用算法直接对源点云与目标点云进行配置的话，整个过程将耗费大量时间，所以必须对点云进行下采样的同时仍保留住可以体现形状轮廓特征的那部分点云。
由于点云本身的稀疏性、无序性和非均匀分布的特点，在利用深度全卷积神经网络结构对激光雷达点云数据进行语义分割时，端到端的卷积神经网络无法直接对无序排布点云进行操作。为使端到端的神经网络在无序性分布的点云数据上具有通用性，需先对点云数据进行映射，常见的投影方式有基于平面的投影、基于圆柱面的投影以及基于球面的点云投影方式。
参考：
周天添等（基于深度神经网络的激光雷达点云语义分割算法研究）
李宏宇（激光雷达的点云数据处理研究）
范小辉（基于激光雷达的行人目标检测与识别）
F. 点云数据处理
三维计算视觉研究内容包括：
（1）三维匹配：两帧或者多帧点云数据之间的匹配，因为激光扫描光束受物体遮挡的原因，不可能通过一次扫描完成对整个物体的三维点云的获取。因此需要从不同的位置和角度对物体进行扫描。三维匹配的目的就是把相邻扫描的点云数据拼接在一起。三维匹配重点关注匹配算法，常用的算法有 最近点迭代算法 ICP 和各种全局匹配算法。
（2）多视图三维重建：计算机视觉中多视图一般利用图像信息，考虑多视几何的一些约束，相关研究目前很火，射影几何和多视图几何是视觉方法的基础。在摄影测量中类似的存在共线方程，光束平差法等研究。这里也将点云的多视匹配放在这里，比如人体的三维重建，点云的多视重建不仅强调逐帧的匹配，还需要考虑不同角度观测产生误差累积，因此也存在一个优化或者平差的过程在里面。通常是通过观测形成闭环进行整体平差实现，多视图重建强调整体优化。可以只使用图像，或者点云，也可以两者结合（深度图像）实现。重建的结果通常是Mesh网格。
（3）3D SLAM：点云匹配（最近点迭代算法 ICP、正态分布变换方法 NDT）+位姿图优化（ g2o 、LUM、ELCH、Toro、SPA）；实时3D SLAM算法 （LOAM）；Kalman滤波方法。3D SLAM通常产生3D点云，或者Octree Map。基于视觉（单目、双目、鱼眼相机、深度相机）方法的SLAM，比如orbSLAM，lsdSLAM...
（4）目标识别：无人驾驶汽车中基于激光数据检测场景中的行人、汽车、自行车、以及道路和道路附属设施（行道树、路灯、斑马线等）。
（5）形状检测与分类：点云技术在逆向工程中有很普遍的应用。构建大量的几何模型之后，如何有效的管理，检索是一个很困难的问题。需要对点云（Mesh）模型进行特征描述，分类。根据模型的特征信息进行模型的检索。同时包括如何从场景中检索某类特定的物体，这类方法关注的重点是模型。
（6）语义分类：获取场景点云之后，如何有效的利用点云信息，如何理解点云场景的内容，进行点云的分类很有必要，需要为每个点云进行Labeling。可以分为基于点的方法，基于分割的分类方法。从方法上可以分为基于监督分类的技术或者非监督分类技术，深度学习也是一个很有希望应用的技术。
（7）立体视觉与立体匹配 ZNCC
（8）SFM（运动恢复结构）
1、点云滤波方法（数据预处理）：
双边滤波、高斯滤波、条件滤波、直通滤波、随机采样一致性滤波。
VoxelGrid
2、关键点
ISS3D、Harris3D、NARF
SIFT3D、
3、特征和特征描述
法线和曲率计算 NormalEstimation 、特征值分析Eigen-Analysis、 EGI
PFH、FPFH、3D Shape Context、Spin Image
4、 点云匹配
ICP 、稳健ICP、point to plane ICP、Point to line ICP、MBICP、GICP
NDT 3D 、Multil-Layer NDT
FPCS、KFPCS、SAC-IA
Line Segment Matching 、ICL
5、点云分割与分类
分割：区域生长、Ransac线面提取、NDT-RANSAC、
K-Means、Normalize Cut（Context based）
3D Hough Transform(线、面提取)、连通分析、
分类：基于点的分类，基于分割的分类；监督分类与非监督分类
6、SLAM图优化
g2o 、LUM、ELCH、Toro、SPA
SLAM方法：ICP、MBICP、IDC、likehood Field、 Cross Correlation 、NDT
7、目标识别、检索
Hausdorff 距离计算（人脸识别）
8、变化检测
基于八叉树的变化检测
9. 三维重建
泊松重建、Delaunay triangulations
表面重建，人体重建，建筑物重建，树木重建。
实时重建：重建植被或者农作物的4D（3D+时间）生长态势；人体姿势识别；表情识别；
10.点云数据管理
点云压缩，点云索引（KD、Octree），点云LOD（金字塔），海量点云的渲染
点云驱动的计算机图形学主要研究应用
http://vcc.szu.e.cn/research/2015/Points/
G. CVPR 2020 论文阅读笔记（三维点云/三维重建）
论文地址： https://arxiv.org/abs/2003.00410
前置文章：10/16、10/17、10/18
本文提出了Point Fractal Network(PF-Net),旨在从不完整的点云数据中恢复点云，克服了之前方法修改现有数据点、引入噪声和产生几何损失的缺点。
由前置文章可知，之前的点云修复方法是输入不完整的点云，输出完整的点云，但这样会导致原有信息的缺失。这篇文章提出PF-Net，主要特点有三个：
网络的整体结构如下：
网络详细推理步骤如下：
损失函数使用完整性损失和对抗损失的加权平均，完整性损失使用L-GAN中提出的CD距离：
对抗损失使用GAN中常见的损失函数
感觉这篇文章对多尺度的运用非常极致，在编码器、解码器和CMLP中都应用了这种思想，最后的效果也非常不错，很值得借鉴。
论文地址： https://arxiv.org/abs/1612.00593
PointNet提出一种基础的网络结构，可以用于点云分类、部分分割和语义分割等多种任务。在这篇文章之前，点云数据的处理方式是将点云数据转换为多个二维的视图或三维的体素形式，然后应用2D/3D CNN进行处理，但这样引入了多余的体积，效率不高。本文是第一个直接使用点云数据的神经网络。（其实可以这样类比，在二维图像处理中，假设图像是二值化的，传统方法是将这个图像直接丢到CNN里面，但如果背景特别多会比较浪费资源。直接使用点云数据相当于直接将前景像素的坐标输入到神经网络里面，对稀疏数据会有比较好的性能，但因为以下三个问题导致直接使用坐标信息比较困难）
由于点云的排列是无序的（可以想象，点云中任意一点排在前面对点云的表达都是相同的）、点云之间是有相互作用的（相邻的点云才能构成形状）、点云在某些变换下具有不变性（比如旋转不会改变点云的类别）这些特性，要求神经网络既能处理无序的数据，又能捕捉全局的结构特征，同时对刚性变换不敏感。基于这些条件，作者提出了如下的网络结构：
可以简要分析一下网络的工作流程，以点云分类问题为例：
感觉网络的结构虽然简单，但是却很好地满足了点云数据自身特性对神经网络的要求。而且我觉得在图像处理中，也有时候必须用到坐标信息或者一些标量特征，这篇文章的方法对于怎样将这些特征融合进CNN里面也有一定的启发意义。
论文地址： http://proceedings.mlr.press/v80/achlioptas18a.html
这篇文章的主要工作是：
首先来看衡量两个点云相似程度的指标部分，作者首先给出了两个距离，EMD和CD：
在计算上，CD更为简便，而且EMD是不可导的。
基于这两种距离，作者引入了三种衡量两个点云相似程度的指标：JSD、Coverage和MMD：
定义了指标后，就可以实现自动编码器和生成模型了。作者提到了四种结构，分别是：
作者同时验证了AE的一些其他功能，比如如果给AE的编码器输入不完整的点云数据，即可训练得到点云复原的模型。使用SVM对低维表示进行分类，即可进行点云分类的任务，证明AE在点云数据形式中的潜在应用较为广泛。
论文地址： http://papers.nips.cc/paper/7095-pointnet-deep-hierarchical-feature-learning-on-point-se
PointNet++针对PointNet提取局部信息能力不强的弊端，提出了一种层次神经网络，可以更好地提取局部信息。其中心思想是将整个点云分割成若干个小部分来提取信息，然后将每个小部分整合成较大的部分，提取更高层次的信息。类似于CNN中卷积和下采样的思想。首先来看网络结构图：
网络大概可以分为两个部分，左边是层次的点云特征提取网络，右边是针对不同任务的解码网络。
特征提取分为若干个set abstraction模块，每个模块又分为采样层、分组层和特征提取层。
得到了较高层次的特征后，对不同的任务需要不同的解码网络。对分类网络来说比较简单，使用全连接即可。对分割网络来说，由于对每个点都需要输出数值，则需要类似上采样的操作。具体的实现作者使用了插值的方法，将较少的点插值到较多的点上去。首先找到插值的目标坐标，然后寻找K个距离最近的已知点，以距离的倒数作为权重，将K个点的特征做加权平均，作为这个点的特征。然后使用之前特征提取中得到的该点的特征与当前特征做一个拼接，即可得到最终特征（类似U-Net的skip connection）。公式如下：
感觉这篇文章和PF-Net的思想差不多，都是希望提取多尺度的特征。但是思路不一样，都值得借鉴。
H. 点云数据处理的5个步骤
1.点云滤波方法(数据预处理): 双边滤波、高斯滤波、条件滤波、直通滤波、随机采样一致性滤波。 VoxelGrid
2.关键点 ISS3D、Harris3D、NARF SIFT3D、
3.特征和特征描述 法线和曲率计算NormalEstimation、特征值分析Eigen-Analysis、EGI PFH、FPFH、3D Shape Context、Spin Image
4.点云匹配 ICP、稳健ICP、point to plane ICP、Point to line ICP、MBICP、GICP NDT 3D、Multil-Layer NDT FPCS、KFPCS
I. 标题 点云数据三种采集方法的优缺点
格点采样、均匀采样、几何采样。
1.格点采样：优点：效率非常高。采样点分布比较均匀，但是均匀性没有均价采样高，可以通过格点的尺寸控制点间距。缺点：不能精确控制采样点个数。
2.均匀采样：优点：采样点分布均匀。缺点：算法时间复杂度有些高，因为每次采样一个点，都要计算集合到集合之间的距离。
3.几何采样：优点：计算效率高，采样点局部分布是均匀的，稳定性高：通过几何特征区域的划分，使得采样结果抗噪性更强。
点云数据（point cloud data）是指在一个三维坐标系统中的一组向量的集合。扫描资料以点的形式记录，每一个点包含有三维坐标，有些可能含有颜色信息（RGB）或反射强度信息。
J. 密集点云细节好吗
密集点云细节好的。密集点云生成网络
名称：Dense 3D Point Cloud Reconstruction Using a Deep Pyramid Ne
摘要
本论文提出了一个叫做DensePCR的网络模型，一个对点云进行重建的深度金字塔网络。首先预测一个低分辨率的点云，然后通过聚合全局特征和局部特征，层次性的增加点云的密度。该模型的亮点之一是分阶段的处理点云，而以往的基于点云的重建方法，全都是在一个阶段预测点云，这就会导致两个问题：
这会显着增加模型的参数。
像EMD这样的损失函数，会极大的增加计算量。
且此论文解决了单视图重建的两个重要问题：
给一张2维图片，是否有足够的信息来预测密集点云？
如何上采样稀疏点云，来获取更加接近物体表面的稠密点云？
对于第一个问题，文章使用了深度金字塔结构的网络，首先预测一个低密度的稀疏点云，然后层次的增加点云的密度。对于第二个问题，提出了一种机制，该机制通过使用邻域地形信息和全局形状属性来“变形”围绕在每一个点的局部网格。
此论文的贡献归纳以下2点：
提出了进行点云重建的叫做DensePCR的深度金字塔网络模型，通过层次化的步骤来逐步的增加点云的密度。
此模型的参数相比于之前的网络模型，减少了3倍。
该模型的架构如图所示：
DensePCR的架构图。训练管道首先预测一个低分辨率的点云，然后层次化的增加点云密度。利用多尺度训练策略对每个中间结构加约束。中间点云（Xp）通过提取全局（Xg）和局部（Xl）点特征，并在每个点周围的坐标网格（Xc）上进行调节，以生成密集的预测，从而实现超分辨率。
接下来分别介绍Multi-Stage Training、Global Feature Learning、Local Feature Learning和Feature Aggregation and Grid Conditioning。
Multi-Stage Training
该网络是由多个训练阶段组成的，图片首先经过编码器-解码器（PointNet）来生成低密度的点云，然后再通过一个密度重建网络（Dense Reconstruction Network）来获得高密度的点云。而且在每个阶段所用的距离测量损失函数是不一样的。
如上图a所示，图片通过编码器-解码器结构的网络生成稀疏的点云 X^p 。因为点云是无序的(unordered)，所以设计出来的损失函数，一定要能够避免由于点云的无序性导致的结果不确定性，接下来介绍两种损失函数：Chamfer distance（CD）和Earth Mover's Distance（EMD）。
CD的定义如下：
Xp 是真实分布的点云。对于每一个预测的点，找到 Xp 中距离此点最小距离的那个点，然后算出最小距离，对所有的预测点都执行这种操作。反过来根据 Xp 中的每一个点，在预测的点云中找出距离此点的最小距离，对所有真实的点都执行这样的操作，最后把距离加起来，得到的最终距离，就是倒角距离（Chamfer Distance）。（注：虽然这种算法简单，计算快速，但是很明显倒角距离算法并不能保证两个点云分布之间的一致性。）
EMD的定义如下：
EMD可以缓解CD带来的问题，这里的 ϕ 是一个双射，由于它可以使一个点集映射到另一个点集，从而可以确保两个点集之间的一致性，但是EMD有一个显着的缺点，就是它的时间复杂度太大了。（CD和EMD另外写篇文章总结一下）鉴于此，文章分阶段的使用CD和EMD，首先是第一次产生稀疏点云之后，利用EMD既可以保持生成的点云和真实点云具有分布一致性，又可以减少了计算量。然后后续的密集点云全部采用CD来计算损失。
这里的稀疏点云的生成方法是一系列的卷积层、batchnorm层和relu层，以及后续的全连接层。稠密点云的生成方法等分析了后续的部件之后，再介绍。
Dense Reconstruction Network
稠密点云的生成，需要全局特征、局部特征、特征聚合以及网格坐标调整。
Global Feature Learning
众所周知，全局特征对于3d重建非常重要。为了提取全局特征，DensePCR采用了和PointNet一样的处理方式，采用MLP。
通过共享参数的感知机层，MLP可以从点云中提取出点云的全局特征。上图中的maxpool是一种对称操作。可以见的，虽然通过MLP+MAXPool的操作可以提取全局特征，但是由于maxpool的存在，无意中抹去了物体的局部过特征。
Local Feature Learning
局部特征在点云分割和点云分类领域是极其重要的，对于更好的重建物体的细节，点云的局部特征对于重建也非常重要。所以，DensePCR用PointNet++网络模型来提取物体的局部结构（PointNet++的介绍可以参考我的另一篇文章）。
具体来说，DensePCR在每一个点周围建造一个邻域球，在每一个邻域内运用MLP就可以获得这个邻域内的全局特征，相对于整个点云来说，也就是局部特征了。然后就可以得到 n×nl 的一个矩阵， n 是输入点云的个数， nl 是最后一层MLP的输出通道。
Feature Aggregation and Coordinate Grid Conditioning
此时的我们已经得到了全局特征和局部特征，此时就需要一个机制全局和局部特征，以及稀疏点云，来生成稠密点云。
为了实现这一任务，DensePCR提出了输出点对应的特征向量 ，分别由点坐标、全局特征和局部特征构成，表示为[Xp,Xg,Xl] ，其维度为 n×(3+ng+nl) 。
n个点是怎么变成4n个点的呐？
DensePCR利用上采样因子，把 n×(3+ng+nl) 平铺成 4n×(3+ng+nl) 。