上篇文章说到从场景中提取特征点，并且对不同角度中的特征点进行匹配。这次要先介绍一个工具 —— 拟合。

拟合本质上是一个优化问题，对于优化问题，最基本的是线性最小二乘法。换言之，我们需要保证拟合误差最小。

1、最小二乘法拟合

基本的最小二乘法拟合解决的是 点 --- 模型 的拟合问题。以点到直线的拟合为例，按照拟合误差的建模，该问题可以分为两类。　

第一类以 因变量 误差作为优化目标，该类问题往往是自变量---因变量模式，xy的单位不同。

第二类以 距离 作为优化目标，该类问题xy的单位往往相同，直线不代表趋势，而是一种几何模型。

由于优化目标不同，故建模方式与解均不同，但是解法思路是一样的，都是讲求和化作向量的模。而向量又是矩阵的运算结果，最终化为奇异值分解问题。

2、RASAC拟合　　

RanSaC算法（随机采样一致）原本是用于数据处理的一种经典算法，其作用是在大量噪声情况下，提取物体中特定的成分。下图是对RanSaC算法效果的说明。图中有一些点显然是满足某条直线的，另外有一团点是纯噪声。目的是在大量噪声的情况下找到直线方程，此时噪声数据量是直线的3倍。

如果用最小二乘法是无法得到这样的效果的，直线大约会在图中直线偏上一点。关于随机采样一致性算法的原理，在wiki百科上讲的很清楚，甚至给出了伪代码和matlab,C代码，想换一个不那么严肃或者说不那么学术的方式来解释这个算法。

实际上这个算法就是从一堆数据里挑出自己最心仪的数据。所谓心仪当然是有个标准（目标的形式:满足直线方程？满足圆方程？以及能容忍的误差e）。平面中确定一条直线需要2点，确定一个圆则需要3点。随机采样算法，其实就和小女生找男朋友差不多。

1. 从人群中随便找个男生，看看他条件怎么样，然后和他谈恋爱，（平面中随机找两个点，拟合一条直线，并计算在容忍误差e中有多少点满足这条直线）

2. 第二天，再重新找个男生，看看他条件怎么样，和男朋友比比，如果更好就换新的（重新随机选两点，拟合直线，看看这条直线是不是能容忍更多的点，如果是则记此直线为结果）

3. 第三天，重复第二天的行为（循环迭代）

4. 终于到了某个年龄，和现在的男朋友结婚（迭代结束，记录当前结果）

显然，如果一个女生按照上面的方法找男朋友，最后一定会嫁一个好的（我们会得到心仪的分割结果）。只要这个模型在直观上存在，该算法就一定有机会把它找到。优点是噪声可以分布的任意广，噪声可以远大于模型信息。

这个算法有两个缺点，第一，必须先指定一个合适的容忍误差e。第二，必须指定迭代次数作为收敛条件。

综合以上特性，本算法非常适合从杂乱点云中检测某些具有特殊外形的物体。

3、非线性拟合

线性最小二乘法已经有了很好的解释。但是生活总是如此不易，能化成上述标准矩阵形式的问题毕竟还是少数，大部分情况下，我们面对的不是min(||Ax - b||)，而是 min(||f(x)-b||) !!!

在三维重建中，如果我们有2个以上视角，那么三条线很可能是不交于一点的。原因是我们选择的旋转矩阵有精度表达问题，位姿估计也存在误差。使用奇异值分解的方法是求得到三条线距离最小的点，还有一种合适的估计，是使得该点在三个相机上的重复投影误差最小。同时,R,T,P(X,Y,Z)进行估计，最终保证Reprojection err 最小的方法————the state of the art BUNDLE ADJUST.

先回到最原始的问题，如何求解非线性最小二乘法。

由线性最小二乘法，我们可以得到非线性最小二乘法矩阵表达形式。如果要求得其局部最小值，则对 x 求导后，导数应为 0。

然而，这个东西并不好解，我们考虑使用梯度下降迭代的方式。这里使用的是单纯的梯度。

这里有个非常不好理解的地方，其假设detaX非常小，故表示成上述形式，以保证 f(x + deta_X)<f(x) ， 只要依次迭代 x 就能保证每次都向着f(x)减小的方向移动。实际上，这个解应该由HESSIAN矩阵给出。

以信标定位为例。讲道理，两个信标为圆心画圆应该给出位置的两个解析解。但是如果有很多信标，那么信标就会画出一块区域........这是SLAM里的经典问题了，后面会有博客专门讲BUNDLE ADJUST.

今天小编就介绍到这里，感谢您的持续关注，更多内容，欢迎进入交流群探讨。