前言:视觉SLAM涉及比较多的数学理论知识,比如刚体变换涉及的四元数和李群,此部分主要看十四讲即可。还有前端和后端非线性优化,涉及到比较多的概率论和矩阵理论方面知识,虽然有些本科和硕士期间都学过,但也忘的差不多了,十四讲比较基础的也没有过多解释。于是主要把SLAM涉及到的不太理解的知识,重新网上检索看了下,汇总于此,引用参考文章均在标题注入了链接。
左乘一个矩阵就代表对右边的向量做一次变换,向量代表的是一条有方向的直线,变换的结果其实就是对这条直线进行各种运动,包括:平移、旋转、伸缩、投影(高维到低维)、映射等,其中,映射是对一个向量作升维或降维(也可以在同一空间中)的操作 R n →R m ,所以广义上,映射的意思等同于变换.
另外一个经常提到的词是“线性变换”,线性变换保证了输入的直线(向量)在变换过程中不会产生弯曲,即输入是直线,输出也是直线。因为 矩阵变换都是线性变换,所以我们这里说的“变换”其实就是“线性变换”。
先举个简单的例子,假如我们要将直线OB变换到直线OB’,也就是逆时针旋转θ ,那么我们怎么求变换矩阵A?
根据变换的定义,也就求一个矩阵A ,使得:[x′ y′]=A[x y]
正交变换
在各种变换中,有一种变换拥有良好的特性——它能使变换后的向量长度,向量之间的内积、距离、夹角等很多性质都不变,这种变换,我们称为正交变换,用于实施这种变换的矩阵,我们称为正交矩阵,这种变换的特性,我们称为正交变换的不变性。
假如有m个向量,我们把向量都看作点,那么这m点就会构成一个具有一定几何结构的空间(图形),我们对这m个点进行正交变换,其结果直观来说就是,正交变换不会对图形进行拉伸、压缩,它能够使变换后的图形保持原来图形的几何形状,如下图所示,ABC构成的空间正交变换到A’B’C’,其大小和形状都不会改变。
正交矩阵
正交矩阵是在欧几里得空间里的叫法,在酉空间里叫酉矩阵。
酉空间: 设V是复数域C上的线性空间,在V上任意两向量x、y按某一确定法则对应于唯一确定是的复数,称为内积,记为(x,y),满足以下性质: 共轭对称性(x,y)= ; 可加性(x+y,z)=(x,z)+(y,z); 齐次性(k x,y)=k(x,y),k为任意复数; 非负性(x,x)≥ 0,当且仅当x=0时有(x,x)= 0. 定义了内积的复线性空间V,叫复内积空间即酉空间(有限维或无限维)。
酉空间和欧式空间统称为内积空间。
上面的正交变换是从变换的结果来进行直观的解释,可以看到这种变换拥有良好的性质——能够保持空间的不变性,保证不会对原空间产生压缩拉伸,往深了说,就是这种变换不会损失信息,因为它保持了原空间的内部结构,这在工程上是很有用的
那么产生这种变换的矩阵——正交矩阵是什么样的,有什么性质?下面给出正交矩阵的定义:
如果矩阵A AA满足: A A T = A T A = E ,则A为正交矩阵。由上述定义,我们可以很容易得到正交矩阵的如下性质:A T = A − 1等式两边取行列式,可以得到 ∣ A ∣ = ± 1 列(行)两两相乘相同为1,不同为0(与自身转置乘的意义),可以得到A 的各列(行)都是单位向量且两两正交
对角矩阵(diagonal matrix)是一个主对角线之外的元素皆为0的矩阵
2.旋转矩阵
参考:双目立视觉:一(坐标系变换、左乘右乘、旋转矩阵
左右乘,以及我们的旋转平移,都是建立在我们的旋转矩阵规定之上的。
逆时针为正 且有下面公式
左乘:回退 右乘:前进
例如:
矩阵A旋转30°变换到了矩阵B,那么矩阵B坐标系下的点就可以左乘变换矩阵,回退到矩阵A时,坐标点的大小。
矩阵B旋转30°到了矩阵A,那么矩阵B上的点右乘旋转矩阵,就可以在矩阵A上面进行表示了。
欧拉角与旋转矩阵之间的转化公式及原理_loongkingwhat的博客-CSDN博客_旋转矩阵转欧拉角blog.csdn.net/loongkingwhat/article/details/82765388.
坐标变换与基变换到底哪个左乘,哪个右乘??_ALexander_Monster的博客-CSDN博客_坐标变换左乘和右乘的关系blog.csdn.net/ALexander_Monster/article/details/104963801
坐标变换就把一个点(或一个向量)从一个坐标系转换到另一个坐标系去。举个栗子:东北天坐标下点B坐标为(1, 2, 3),通过坐标变换到北西天坐标系,在北西天坐标系下B点坐标是(x, x, x)。 上面那点就是说,同一个点(或向量)在不同坐标系下的坐标分别是什么? 注意,坐标变换,是左乘的。过渡矩阵A是乘在左边的。(在这里A和A-1均只表示一个象征作用,象征变换阵,下同)
3.矩阵的秩
「秩」是图像经过矩阵变换之后的空间维度
「秩」是列空间的维度
因此,此矩阵的「秩」为2。
因此,此矩阵的「秩」为1。
3. AX*XB求解
包括: 1、三角分解(LU分解) 2、LDLT分解与LLT分解(Cholesky分解) 3、QR分解 4、奇异值分解(SVD分解) 5、特征值分解
线性方程和非线性方程
线性方程:代数方程,如y =2 x +7,其中任一个变量都为一次幂。 这种方程的图形为一直线,所以称为线性方程。
所谓非线性方程,就是因变量与自变量之间的关系不是线性的关系,这类方程很多,例如平方关系、对数关系、指数关系、三角函数关系等等。 求解此类方程往往很难得到精确解,经常需要求近似解问题。
4.最小二乘法
概念:所谓“二乘”就是平方的意思,又称最小平方法,通过最小化误差的平方,寻找数据的最佳函数匹配。用最小二乘法可以简便的求得未知的数据,并使得求得的数据与实际数据之间误差的平方和为最小。
观测矩阵,指实际上是我们在测量时,得到的真实数据。
最小二乘法的几何意义就是求解 b 在A的列向量空间中的投影。
如何找到我需求的B呢?
线性回归因为比较简单,可以直接推导出解析解,而且许多非线性的问题也可以转化为线性问题来解决,所以得到了广泛的应用。甚至许多人认为最小二乘法指的就是线性回归,其实并不是,最小二乘法就是一种思想,它可以拟合任意函数,线性回归只是其中一个比较简单而且也很常用的函数,所以讲最小二乘法基本都会以它为例。
穷举法,算出最小残差平方和时的B………………这个最初是这样做的,但是有点太浪费计算资源了,速度比较慢。
还有其他方法:(梯度下降法、牛顿法、拟牛顿法、共轭梯度法等)如何求逆,是矩阵求最小二乘的精华。
4.1 非线性最小二乘
最小二乘又可以分为线性和非线性两种,分别对应fi(x)的线性形式与非线性形式,线性最小二乘很好求解,可以将公式(1)变换为矩阵方程(公式2),最后直接求解矩阵方程即可,不需要迭代,这种解被称为“解析解”。非线性最小二乘问题则不然,它要复杂得多,没有办法变换为矩阵方程形式,以至于它必须将问题化简为每一步均为可以直接求解的子问题,整个求解过程是迭代的。
1.对原问题中的每一个函数fi(x)在x0处进行一阶泰勒展开,因为一阶泰勒展开属于线性函数(公式3),于是通过这种手段,就可以将非线性最小二乘问题简化为线性最小二乘问题来求解。
2.对得到的线性最小二乘问题,进行直接求解。这里面涉及到两个矩阵,一个是雅克比矩阵(公式4),一个是赫森矩阵(公式5)。
3.得到子问题的解析解xk+1之后(公式2),xk+1与xk之间便自然地建立了等式关系(公式6)。
4.更新参数xk(k=k+1, k=1....n),回到步骤1,直到满足收敛条件,得到最优解x*
几个注意事项:
第一:步骤1中,一定要一阶泰勒展开,不能采用二阶以上,因为只有一阶泰勒展开才是线性函数,才能转换为线性最小二乘问题来直接求解。
第二:步骤2中,雅克比矩阵和赫森矩阵都是属于子问题的,不是原问题的。
第三:步骤3中,是为了得到新求解的参数xk+1与之前参数xk之间的关系,形成一种“链式反应”,也就是迭代了。
第四:步骤4中,收敛条件一般有1.梯度近乎为0。2.变量变化很小。3.目标函数值变化很小等。
第五:许多优化算法,都可以用于解决非线性最小二乘问题。例如我之前讲过的LM算法与信赖域算法(参考2与参考3),对应的matlab代码已给出。
第六:函数fi(x)往往都是如下形式(公式7),千万别以为fi(x)就是hi(x),我之前犯过类似的错误,调代码调的很惨。
4.2 非线性最小二乘求解推导
我们先考虑一个最小二乘问题 是一个任意的非线性函数。如果 是个数学形式上很简单的函数,那问题也许可以用解析形式来求。令目标函数导数为0,求解最优值,就和求一个二元函数的极值一样:
解此方程,就得到了导数为0的极值。它们可能是极大,极小或者鞍点值,只要挨个比较它们的函数值即可。但是,这个方程是否容易解取决于 f导函数的形式。 有可能是一个非常复杂的非线性方程。通常对于不方便求解的最小二层问题,我们可以用迭代的方式,从一个初始值出发,不断更新当前的优化变量,使目标函数下降。具体的步骤可列写如下:
这让求解导函数为零的问题,变成了一个不断寻找梯度并下降的过程。直到某个时刻的增量非常小,无法再使函数下降。此时算法收敛,目标达到了一个极小,我们完成了寻找极小值的过程。在这个过程中,我们只要找到迭代点的梯度方向即可,而无需寻找全局导数为0的情况。
5. 范数
范数主要是对矩阵和向量的一种描述,有了描述那么“大小就可以比较了”,从字面理解一种比较构成规范的数。有了统一的规范,就可以比较了。
例如:1比2小我们一目了然,可是(3,5,3)和(6,1,2)哪个大?不太好比吧 2范数比:根号(43)比根号(41)大,因此2范数对比中(3,5,3)大 无穷范数比:5比6小,因此无穷范数对比中(6,1,2)大矩阵范数:描述矩阵引起变化的大小,AX=B,矩阵X变化了A个量级,然后成为了B。
向量范数:描述向量在空间中的大小。 更一般地可以认为范数可以描述两个量之间的距离关系。向量范数的通用公式为L-P范数
记住该公式其他公式都是该公式的引申。 L-0范数:用来统计向量中非零元素的个数。 L-1范数:向量中所有元素的绝对值之和。可用于优化中去除没有取值的信息,又称稀疏规则算子。 L-2范数:典型应用——欧式距离。可用于优化正则化项,避免过拟合。 L-∞范数:计算向量中的最大值。
欧式距离
欧式距离就是所谓的向量的二范式
余弦距离
弦相似度经常被用来衡量两个向量的相似度
6. 在拟合的时候进行应用-LM算法——列文伯格-马夸尔特算法(最速下降法,牛顿法,高斯牛顿法)
什么是拟合?你有一堆数据点,我有一个函数,但是这个函数的很多参数是未知的,我只知道你的这些数据点都在我的函数上,因此我可以用你的数据点来求我的函数的未知参数。
拟合我们可以认为是一种试探性的方法,这种方法在计算机出来以前很多情况下是不可能实现的,为什么,因为公式涉及了大量的迭代过程,也就是我想要通过数据点求函数的参数,没有解析解能够直接代入数据求得参数,而是通过一点一点的摸索尝试,最终得到最小误差也就是最好拟合。最具有代表性的就是暴风法,把所有可能的结果都带进去,找到最好的拟合。然后聪明的人类不想这么鲁莽,并且这么无目的地寻找,于是人们开始研究参数向什么方向迭代是最好的,于是便出现了梯度方向等一系列方法。
有最速下降法、Newton 法、GaussNewton(GN)法、Levenberg-Marquardt(LM)算法等。
沿着导数方向,我们的函数值是逐渐增大的
我们行进的方向和我们的我们行进的方向和我们的梯度方向一致时,函数增长最快,方向相反时,函数下降最快。
补充知识:
雅克比Jacobian 矩阵是函数的一阶偏导数以一定方式排列成的矩阵。W当一个函数的输入和输出都是向量的函数,把它所有的偏导数放入一个矩阵,把包含所有这样偏导数的矩阵称为Jacobian 矩阵。
Hessian矩阵等价于 梯度 的Jacobian矩阵。雅克比矩阵(Jacobian Matrix)在正运动学中的应用海森 Hessian 矩阵是一个由多变量实值函数的所有二阶偏导数组成的方块矩阵
在图像中应用:
对于可导函数,当一阶导数为 0,二阶导数不为 0 时,说明是极值点。
二阶导数大于 0,是极小值点;二阶导数小于 0,是极大值点。边缘到底有什么特征呢?如下图所示,一个二维平面上的一条直线,图像的特征具体可以描述为:沿着直线方向,亮度变化极小,垂直于直线方向,亮度由暗变亮,再由亮变暗,沿着这个方向,亮度变化很大。我们可以将边缘图像分布特征与二次型函数图形进行类比,是不是发现很相似,我们可以找到两个方向,一个方向图像梯度变化最慢,另一个方向图像梯度变化最快。那么图像中的边缘特征就与二次型函数的图像对应起来了,其实二次型函数中的hessian矩阵,也是通过对二次型函数进行二阶偏导得到的(可以自己求偏导测试下),这就是我们为什么可以使用hessian矩阵来对边缘进行检测以及进行边缘响应消除,我想大家应该明白其中的缘由了。还是那句话,数学模型其实就是一种反映图像特征的模型。
所以Hessian matrix实际上就是多变量情形下的二阶导数,他描述了各方向上灰度梯度变化,这句话应该很好理解了吧。我们在使用对应点的hessian矩阵求取的特征向量以及对应的特征值,较大特征值所对应的特征向量是垂直于直线的,较小特征值对应的特征向量是沿着直线方向的。对于SIFT算法中的边缘响应的消除可以根据hessian矩阵进行判定。
参考链接:https://zhuanlan.zhihu.com/p/56598915
7. 特征值
如果说一个向量v是方阵A的特征向量,将一定可以表示成下面的形式:
这时候λ就被称为特征向量v对应的特征值,一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式:
其中Q是这个矩阵A的特征向量组成的矩阵,Σ是一个对角阵,每一个对角线上的元素就是一个特征值。
特征值分解可以得到特征值与特征向量,特征值表示的是这个特征到底有多重要,而特征向量表示这个特征是什么,可以将每一个特征向量理解为一个线性的子空间,我们可以利用这些线性的子空间干很多的事情。不过,特征值分解也有很多的局限,比如说变换的矩阵必须是方阵。
几何意义:变换会将对应本征向量方向的向量进行缩放,缩放的倍数就是本征值。
8. 奇异分解
特征值分解是一个提取矩阵特征很不错的方法,但是它只是对方阵而言的,在现实的世界中,我们看到的大部分矩阵都不是方阵,比如说有N个学生,每个学生有M科成绩,这样形成的一个N * M的矩阵就不可能是方阵,我们怎样才能描述这样普通的矩阵呢的重要特征呢?
奇异值分解可以用来干这个事情,奇异值分解是一个能适用于任意的矩阵的一种分解的方法:
假设A是一个N * M的矩阵,那么得到的U是一个N * N的方阵(里面的向量是正交的,U里面的向量称为左奇异向量),Σ是一个N * M的矩阵(除了对角线的元素都是0,对角线上的元素称为奇异值),V’(V的转置)是一个N * N的矩阵,里面的向量也是正交的,V里面的向量称为右奇异向量)
假设M是一个m×n阶矩阵,其中的元素全部属于域K,也就是实数域或复数域。如此则存在一个分解
使得其中U是m×m阶酉矩阵;Σ是m×n阶非负实数对角矩阵;而V**,即V的共轭转置,是n×n阶酉矩阵。这样的分解就称作M的奇异值分解。Σ对角线上的元素Σi,i即为M*的奇异值。
酉矩阵(又译作幺正矩阵,英语:unitary matrix)是一个 n×n 复数方块矩阵 U,其满足以下性质:其中 *U** 是 U 的共轭转置,In 是 n×n 单位矩阵。
Mvi= λivi
里的 λi 是拉伸尺度(scalar)。从几何上看,*M* 对向量 V*i* 进行了拉伸,映射变换。V*i* 称作矩阵 M 的特征向量(eigenvector),λi 称作为矩阵*M* 特征值(eigenvalue)。这里有一个非常重要的定理,对称矩阵*M* 的特征向量是相互正交的。
它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示,这些小矩阵描述的是矩阵的重要的特性。
奇异值分解的几何含义为:对于任何的一个矩阵,我们要找到一组两两正交单位向量序列,使得矩阵作用在此向量序列上后得到新的向量序列保持两两正交。
奇异值的计算是一个难题,是一个O(N^3)的算法。在单机的情况下当然是没问题的,matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值,但是当矩阵的规模增长的时候,计算的复杂度呈3次方增长,就需要并行计算参与了。
奇异值的直观应用
图片压缩
图片实际上对应着一个矩阵,矩阵的大小就是像素大小,比如这张图对应的矩阵阶数就是450*333,矩阵上每个元素的数值对应着像素值。我们记这个像素矩阵为A 现在我们对矩阵A进行奇异值分解。直观上,奇异值分解将矩阵分解成若干个秩一矩阵之和,用公式表示就是
如果只保留大的奇异值,舍去较小的奇异值,这样(1)式里的等式自然不再成立,那会得到怎样的矩阵——也就是图像?
奇异值往往对应着矩阵中隐含的重要信息,且其重要性和奇异值大小正相关。每个矩阵A都可以表示为一系列秩为1的“小矩阵”之和,而奇异值则衡量了这些“小矩阵”对于A的权重。
图像去噪
在图像处理领域,奇异值不仅可以应用在数据压缩上,还可以对图像去噪。如果一副图像包含噪声,我们有理由相信那些较小的奇异值就是由于噪声引起的。当我们强行令这些较小的奇异值为0时,就可以去除图片中的噪声。异值分解还广泛的用于主成分分析(Principle Component Analysis,简称PCA)和推荐系统(如Netflex的电影推荐系统)等。在这些应用领域,奇异值也有相应的意义.
可以说奇异值分解将一个矩阵原本混合在一起的三种作用效果,分解出来了。矩阵可以认为是一种线性变换,一个线性变换的作用可以包含旋转、缩放和投影三种类型的效应。奇异值分解正是对线性变换这三种效应的一个析构。而特征值分解其实是对旋转缩放两种效应的归并。(有投影效应的矩阵不是方阵,没有特征值)
6. 图像偏导数
图像就是一个复杂的曲面,我们要想得到曲面点的梯度,就需要对该点求偏导。 求偏导的输入:附近点的灰度值 求偏导的输出:一个数用窗操作,卷积操作(我不想提卷积操作,因为事实就是一个简单的相乘相加的数学公式) 对x求导
联系客服