舜宇智能光学开发者论坛
 找回密码
 立即注册
上篇文章说到从场景中提取特征点,并且对不同角度中的特征点进行匹配。这次要先介绍一个工具 —— 拟合。

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

1、最小二乘法拟合

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




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

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

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


2、RASAC拟合  

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


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

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

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

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

  • 第三天,重复第二天的行为(循环迭代)

  • 终于到了某个年龄,和现在的男朋友结婚(迭代结束,记录当前结果)

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

这个算法有两个缺点,第一,必须先指定一个合适的容忍误差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矩阵给出。


  
以信标定位为例。讲道理,两个信标为圆心画圆应该给出位置的两个解析解。但是如果有很多信标,那么信标就会画出一块区域......



------------------扩展链接-------------------

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
分享至 : QQ空间
收藏
欢迎大家来到舜宇智能光学开发者论坛!

0 个回复

您需要登录后才可以回帖 登录 | 立即注册