点云处理算法整理（超详细教程）

目录

一. 线性回归_最小二乘法、梯度下降法

二. 线性回归_最小二乘法、RANSAC算法

三. 最近点迭代_ICP算法

四. 常见三角网格划分_voronoi图和Delaunay三角剖分

五. PCL曲面聚类分割算法优缺点分析

六. 区域增长算法、欧几里得聚类算法

七. PCL AABB和OBB包围盒算法

一. 线性回归_最小二乘法、梯度下降法

https://www.cnblogs.com/armysheng/p/3422923.html

最小二乘法（适用范围：线性回归方程：直线、圆、椭圆；）

最小二乘法（又称最小平方法）是一种数学优化技术。

它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达

最小二乘法与梯度下降法：梯度下降法可以使用tensorflow模块

最小二乘法跟梯度下降法都是通过求导来求损失函数的最小值，那它们有什么区别呢。

相同　：

　1.本质相同：两种方法都是在给定已知数据（independent & dependent variables）的前提下对dependent variables算出出一个一般性的估值函数。然后对给定新数据的dependent variables进行估算。　

　2.目标相同：都是在已知数据的框架内，使得估算值与实际值的总平方差尽量更小（事实上未必一定要使用平方），估算值与实际值的总平方差的公式为：左上角
其中为 xi第i组数据的independent variable，yi为第i组数据的dependent variable，β为系数向量。

不同：

　　1.实现方法和结果不同：最小二乘法是直接对求导找出全局最小，是非迭代法。而梯度下降法是一种迭代法，先给定一个，然后向下降最快的方向调整，在若干次迭代之后找到局部最小。梯度下降法的缺点是到最小点的时候收敛速度变慢，并且对初始点的选择极为敏感，其改进大多是在这两方面下功夫。

二. 线性回归_最小二乘法、RANSAC算法

https://blog.csdn.net/qq_18941713/article/details/84647887

RANSAC算法（适用范围：线性回归方程：直线、圆、椭圆；）
RANSAC为Random Sample Consensus的缩写，它是根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，得到有效样本数据的算法。

RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声。这些异常数据可能是由于错误的测量、错误的假设、错误的计算等产生的。同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法。

最小二乘法与ransac的区别: （最小二乘法根据全部点进行计算，ransac根据用户设置的阈值进行计算)
在拟合平面（地面）这一需求上，平面的凹凸点（小的坑洼）是有效数据，但对所需平面来说有一定的偏移。而大的凹凸，比如地面上的障碍物、地面的深坑，这些都是偏移量过大的无效数据。

最小二乘拟合，旨在照顾所有人的想法，对所有数据进行拟合，在无效数据多且偏移量大的情况下，拟合效果不好。
而RANSAC拟合，旨在照顾多数人的意愿，对主体数据进行拟合，手动设置一个阈值，同拟合平面的距离超过阈值的点，就被判定为无效数据。

随机拟合多个平面，选取平面内数据点最多的平面，或者说，无效数据最少的平面，作为拟合出的结果。
根据如上思路，RANSAC在拟合平面这一需求上，可以得到更准确的结果。

三. 最近点迭代_ICP算法

https://blog.csdn.net/kksc1099054857/article/details/80280964

ICP算法（适用范围：点云配准；）
点云数据能够以较小的存储成本获得物体准确的拓扑结构和几何结构，为了获得被测物体的完整几何信息，就需要将不同视角即不同参考坐标下的两组或者多组点云统一到统一坐标系下，进行点云的配准。在配准算法中，研究者使用最多的是ICP算法。

ICP算法的原理与步骤：（请参照左下角网站）

ICP算法的基本原理是：分别在带匹配的目标点云P和源点云Q中，按照一定的约束条件，找到最邻近点（pi，qi），然后计算出最优匹配参数R和t，使得误差函数最小。误差函数为E（R，t）为：左上角

其中n为最邻近点对的个数，pi为目标点云 P 中的一点，qi 为源点云 Q 中与pi对应的最近点，R 为旋转矩阵，t为平移向量。
ICP算法步骤、ICP算法关键，左下角网站有详细说明

四. 常见三角网格划分_voronoi图和Delaunay三角剖分

https://blog.csdn.net/tuibianyanzi/article/details/51886916

Voronoi图的定义：

Voronoi图:计算几何里的一种基于距离的平面划分方法。在平面上有n个不重合种子点（节点），把平面分为n个区域，使得每个区域内的点到它所在区域的种子点（节点）的距离比到其它区域种子点（节点）的距离近。每个区域称为该种子点（节点）的Voronoi区域。Voronoi图是Delaunay三角剖分的对偶图。Voronoi图的每条边是由相邻种子点（节点）的垂直平分线构成，在边上的点到两个种子点（节点）的距离相等。

Delaunay三角剖分的定义：

定义1：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：

1.除了端点，平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面，且所有三角面的合集就是点集V的凸包。

定义2：Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边。存在一个圆经过a,b两点，圆内不含点集V中任何的点，这一特性又称空圆特性。
定义3：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分

Voronoi图和Delaunay三角剖分的对偶关系：Voronoi图的一个顶点同时属于三个Voronoi多边形，每个Voronoi多边形内有且仅有一个节点（种子点）。连接三个共点的Voronoi多边形分别对应的三个节点（种子点）则形成一个Delaunay三角形，所有这样的三角形的集合就是著名的Delaunay三角剖分如右图所示。

Voronoi图的定义

Delaunay三角剖分定义

五. PCL曲面聚类分割算法优缺点分析

三种数据分割方法的比较：

1）基于模型拟合的方法 常见的有：Hough变换法，RANSAN法（直接建立Ax+By+Cz+D=0的关系式，然后使用最小二乘法进行参数确定）
优点：主要用于3D点云分割，不受噪声和异常数据干扰 
缺点：分割质量受像素点特征影响较大，不适于大量数据的分

 2）基于区域增长的方法
优点：广泛应用在3D点云分割中，执行简单 
缺点：鲁棒性不是很好，受分割的多种评判标准的影响，计算时间长

3）基于聚类特征的方法 
优点：鲁棒性较好，不需要查找点或查找区域 
缺点：大数据量的分割计算量很大，无法检测连续的边界点，分割后需细化处理

六. 区域增长算法、欧几里得聚类算法

https://blog.csdn.net/qq_29462849/article/details/85112847

区域蔓延分割

区域生长分割算法广泛应用于图像分割中，二维图像常常采取区域生长分割算法实现图像分割，由于其分割的高效性，现已被应用于3D分割中，PCL中的类pcl::RegionGrowing用来实现点云的区域生长分割。区域生长分割是基于点云法线的分割算法，算法的主要思路如下：

（1）根据点的曲率值对点云进行排序，曲率最小的点叫做初始种子点，区域生长算法从曲率最小的种子点开始生长，初始种子点所在区域为最平滑区域，从初始种子点所在的区域开始生长可减小分割片段的总数，从而提高算法的效率。

（2）设置一空的聚类区域Ｃ和空的种子点序列Ｑ，选好初始种子点，将其加入种子点序列，并搜索该种子点的领域点，计算每一个领域点法线与种子点法线之间的夹角，小于设定的平滑阀值时，将领域点加入到Ｃ中，同时判断该领域点的曲率值是否小于曲率阀值，将小于曲率阔值的领域点加入种子点序列Ｑ中，在Ｑ中重新选择新的种子点重复上述步骤，直到Ｑ中序列为空，算法结束。

基于欧几里德距离的分割算法

具体的实现方法大致是：

找到空间中某点p10，有kdTree找到离他最近的n个点，判断这n个点到p的距离。将距离小于阈值r的点p11,p12,p13…放在类Q里。
2. 在 Q\p10 里找到一点p11,重复1。
3. 在 Q\p10,p11 中找到一点，重复1，找到p12,p13,p14…全部放进Q里。
4. 当 Q 再也不能有新点加入了，则完成搜索了

七. PCL AABB和OBB包围盒算法

https://blog.csdn.net/qing101hua/article/details/53100112

OBB包围盒算法