课程笔记-三维点云处理04 ——Model Fitting
本系列笔记是对深蓝学院所开设的课程：《三维点云处理》的笔记
课程每周更新，我也会努力将每周的知识点进行总结，并且整理成笔记发上来，欢迎各位多多交流&批评指正！！
本文主要为课程第四章的笔记！
课程链接：
正式内容:
####################################################
本节课大纲：
- 首先继续将谱聚类 上节课只讲了步骤没有讲原理
- 介绍三个模型拟合的算法： 最小二乘法、霍夫变换、RANSAC
上节课回顾
讲了三种聚类算法 Kmeans GMM 和谱聚类
前两种都是基于欧式距离的 谱聚类更多参考数据的密集程度，并且能够自确定K的数量
Spectral Clustering
谱聚类构建步骤：
- 建立相似矩阵
- 用拉普拉斯矩阵L对矩阵进行计算
- 特征值分解，求对应于最小的K个特征值的特征向量
- 将特征向量组成一个v矩阵
- 对v矩阵的每一行都做一个Kmeans
- 对每一个点所在的类进行Kmeans分类
谱聚类原理
相当于将点按照无向图的原理做链接。
可以将谱聚类问题转化为图切割问题
但是图切割会遇到问题：理想的分割应该切到红色和蓝色之间，但是事实上可能切到最边上这两个点，因为这样也能满足条件另损失函数很小
解决方法：可以加一个限制条件，使切出来的每一块都不至于太小
表示A分区大小的有两种该方法 一个是按照其中元素个数划分 另一个是按照连接疏密的程度（权重划分）
分别对应两种切割的方法：RatioCut 和 NormalizedCut
一般都是偏向于用有归一化的谱聚类，因此也用对应的 normalized cut 算法
谱聚类证明
直观证明：
要用到拉普拉斯矩阵
有几个分区，就能够在矩阵中找到几个特征值为0的向量
拉普拉斯矩阵可以把聚类的结果直接体现在特征向量上，所以比较方便。
特性
1。 拉普拉斯矩阵的特性
具体证明如下：
性质2： 有多少个连通域就有多少个特征值为0
证明如下：
具体推导过程忽略
证明
总结
一般用normalize的
谱聚类可以用图切割的思想去理解
总结 谱聚类的优点、缺点、复杂度
优点：在所有数据集上都比较好用
缺点：计算量比较复杂
meanshift & dbscan
这一节介绍一些轻松简单的聚类方法，跟谱聚类相比比较易于理解与计算 只做介绍不做推导
两种方法在实际应用场景中都会常见
mean shift
引入：一个点云图里有一个圆，找出一个点使得以他为圆心的点最多
方法：类似于一个爬山的思想，先寻找一个圆，根据圆里面点的分布求位置坐标，然后根据分布求平均坐标作为圆心将圆移动，从而将圆的位置改变，进入下一个圆
如何将meanshift应用在聚类中？
- 先将一个圆按照密度的方法移动到一个使他不再动的位置为止 （前三步）
- 重新找一个圆，同样让其按照meanshift方法移动 （重复多次）
- 将重叠的圆 取里面包含数量最多的圆，其他的圆去掉，剩下多少圆就说明有多少类别。
有些像进化算法
总结：
因为还是最邻近的，所以对高纬度的数据处理性能不佳
DBSCAN
跟meanshift相比效果更好，但复杂度却没有更高
类似于漫水算法
从一个点出发 找到离自己最近的点往前走
算法步骤：
- 随便选一个没有经过过的点 即为P 然后找一个半径圆 统计圆内数量，如果达到要求就可以记为一类
- 如果没有达到要求，就扔掉 视为噪声
- 访问圆中的每一个点，并且标记为已经访问，并归类
- 重复上面的做法 进行分类
一个点有两个标签 ：一个是类标签 决定了是哪一类的 ；另一个是性质标签，分为核心点；边界点；噪声
只要是核心点都进行搜索 边界点不进行搜索但进行归类 噪声点不进行归类
总结：
对噪声比较稳定 比较简单
但是比较吃 最小周围点数 设置的数值（数值的选取和设置影响对性能影响比较大
而且在处理比较稠密的点（或者距离区间比较相近的点时表现没有那么好）
聚类算法总结
一共讲了上面这几种例子，针对不同的数据分类方式的表现各异。
主要分两类 一类是基于距离的 另一类是基于连接的 各有优劣 。
通过上图可以看出 谱聚类在每一个场景下都有不错的发挥，属于鲁棒性比较强的算法。
模型拟合部分 model fitting
以如何拟合一条二维的直线为例进行讲解
- 如果知道所有的点都是内联值，可以用最小二乘直接拟合
- 如果有离群值，但不是特别的多 可以用加强最小二乘 霍夫变换 RANSAC （对噪声更加鲁棒）
- 如果大部分是噪声点 只能用 霍夫变换 RANSAC
Robust Least Square 鲁棒最小二乘
最小二乘
把问题变成平方和的模式
最小二乘的标量表示
用矩阵形式表示如下：
用A矩阵的最小特征向量去解就可以
一般对于最小二乘有三种写法：
最小二乘法对于噪声比较敏感，所以要提出加强最小二乘
Robust Least Square
用绝对值等一些对极端值反应较小的处理方法 来代替平方数 ，以此减小平方数对其的冲击
如何解通用的最小二乘方法：
梯度下降法
高斯牛顿法
等一些其他的方法
总结：
有点：简单 快速
缺点 ：抵抗噪声能力差
霍夫变换
霍夫变换在图像当中最广泛的应用就是求线
核心思想是：原始空间的点可以转化成参数空间中的线或线转点
将数据点翻转 做霍夫投票
两个点可以取平均点
用一个 θ角来表示空间中的直线
然后进行霍夫投票
需要进行区域的划分 （结合速度和精度综合考量）
如果是三维空间坐标下 可以用r 和 θ 的坐标 进行求解
用这个方法可以求出三维空间中的圆锥
然后再通过霍夫变换得到参数：
总结：
好处： 因为是基于投票的方法 ，所以对噪声干扰强 而且可以针对不完整的形状进行补充
劣势： 参数不能过高，因为每一个参数都是一维空间 所以一般只用在2维和3维的情况下
RANSAC
因为霍夫变换的模型参数一般小于三个，所以针对三维点云一般用RANSAC算法
步骤：
- 选定一个sample 即对于直线模型来说只需随机选取两个点
- 求解 直线的方程
- 计算其他点是否支持这个方案——求每个点到这个直线的距离 进行统计
4. 重复上述的步骤 当重复次数足够多时候进行比较
5.选出投票最多的模型
参数设置：1. τ 应该以经验或者实验设置 （一般是符合 X方分布）
2. 设置迭代的参数 n 标准：做n次迭代得到一个好的标准的置信度要大于0.99（或0.9
一些比较实用的tricks：
- 找到一条达到预期的线就可以提前终止
- 模型选出来之后 实用LSQ重新优化一下 所得数据更加准确
总结：
作业
- 选一个KITTI数据集 把地面去掉
- 对于剩下的点 聚类
- 把地面标记成蓝色 不同聚类物体用不同颜色表达 （前景聚类）
- 并将结果可视化