这个博客是我对视觉的SLAM《十四讲》相关基础知识点的整理没有详细的推导过程，只相当于一个思维导图。同时，我在网上搜索了一些相关问题进行补充总结。我的水平有限。如果文章错了，请指出。

这是整个SLAM在系统的第一部分，首先提取特征，然后匹配特征，通过匹配特征来获得相关的变换矩阵，这里容易混淆的概念是特征提取，特征提取包括特征点和特征描述子，以ORB为例，ORB是由FAST特征点和BRIEF构成特征描述子。我们通常所说的Harris角点通常只指特征点，只有Harris角度不能匹配特征，需要通过向量对Harris特征描述(特征描述子)只能在两帧之间匹配。关于特征子的总结可以参考我的总结博客 视觉SLAM总结-视觉特征子综述(总结非常详细)

Harris角点：如下图所示，如果窗口中的灰度值发生剧烈变化，则窗口中心为角度。转换为数学描述是相关矩阵的两个特征值。 Harris特征描述子：Harris 角度描述子通常由周围图像素块的灰度值和用于比较的相关矩阵组成。图像的像素块由以像素点为中心的周围矩形部分组成 优点：计算简单；提取点均匀合理；稳定、稳定Harris算子对图像旋转、亮度变化、噪声影响和视觉变化不敏感。 缺点：对尺度非常敏感，没有尺度不变性；提取的角精度为像素级；需要设计角匹配算法

SUFT是对SIFT他们的想法是一致的，但他们使用不同的方法 SUFT特征点：基于Hessian矩阵构造金字塔尺度空间，利用箱式滤波器（box filter）简化二维高斯滤波 SUFT特征描述子：通过Haar小波特征设定特征点的主要方向，因此构建的特征描述子为64维 缺点：主方向阶段过于依赖局部区域像素的梯度方向；图像金字塔的层不够紧密也会导致尺度误差

Fast角点：如果一个像素与周围领域的像素有很大的不同，那么这个像素可能是一个角。直接的阈值判断可以加速角提取的简单和高效。 BRIEF特征描述子：BRIEF算法计算出二进制串的特征描述符。它选择n对像素点在特征点的邻域内pi、qi（i=1,2,…,n）。然后比较每个点对的灰度值。I(pi)> I(qi)，二进制串中生成1，否则为0。对比所有点，生成长度为n的二进制串。 优点：ORB算法的速度大约是SIFT的100倍，是SURF的10倍。 以上参考 https://zhuanlan.zhihu.com/p/36382429

特征匹配的方法有很多，这里就不赘述了，包括暴力匹配（Brute-Force Macher）、近似最近邻（FLANN）等，ORB SLAM二是词典加速匹配过程。

对极约束 x 2 T t ∧ R x 1 = 0 ( p 2 T K − T t ∧ R K − 1 p 1 = 0 ) \bm{x_2^T t^\wedge R x_1 = 0( p_2^T K^{-T} t^\wedge R K^{-1} p_1 = 0)} x2T​t∧Rx1​=0(p2T​K−Tt∧RK−1p1​=0) 本质矩阵E E = t ∧ R \bm{E=t^\wedge R} E=t∧R 基本矩阵F F = K − T E K − 1 \bm{F=K^{-T}EK^{-1}} F=K−TEK−1 其中， p 1 , p 2 p_1,p_2 p1​,p2​是像素坐标，对极约束描述的是空间中两个匹配点的空间位置关系，本质矩阵的奇异值必定是 [ δ , δ , 0 ] [\delta,\delta,0] [δ,δ,0],由于平移和旋转各三个自由度，因此本质矩阵有六个自由度。但通常采用八点法进行求解。由本质矩阵恢复 R , t R,t R,t的过程通过SVD分解完成。 当场景中所有特征点都落到一个平面上时就可以通过单应性来进行运动估计。通过这个关系可以推导得 p 2 = H p 1 \bm{p_2=Hp_1} p2​=Hp1​,其中 H H H就是单应矩阵。可以通过四对点求解。单应性的重要性在于，当相机发生纯旋转或者特征点共面时，基础矩阵的自由度会下降，就出现退化，这时候如果我们继续用八点法求基础矩阵，基础矩阵多余出来的自由度将主要由噪声决定。

PnP是求解3D到2D点对运动的方法，即问题描述为，我们的已知条件是n个3D空间点以及它们作为特征点的位置（以归一化平面齐次坐标表示），我们求解的是相机的位姿 R , t R,t R,t，如果3D空间点的位置是世界坐标系的位置，那么这个 R , t R,t R,t也是世界坐标系下的。特征点的3D位置可以通过三角化或者RGBD相机的深度图确定。

根据推导，一对特征点（一个3D点加一个2D点）可以提供两个线性约束，因此12维的齐次变换矩阵需要6对特征点。

P3P的作用是将利用三对特征点，讲空间点在世界坐标系下的坐标，转换到像极坐标系中的坐标，将PnP问题转化为ICP问题，推导过程是利用三角形特征完成的。

其本质是一个最小化重投影误差的问题，公式如下： 即理解为调整相机的位姿使得重投影误差变小，而最小的重投影误差就对应着实际的位姿。需要求这里要注意的是这里仅仅是采用了BA的方法，但是实际做BA优化的时候，是同时优化位姿和路点位置，因此有两个相关的雅克比矩阵，但这里仅仅优化位姿，因此所求的雅克比矩阵仅仅和位姿有关，可以直接求取 J J J如下，然后就可以进行求解 δ ξ \delta \xi δξ进行迭代

其本质就是确定两个点集之间的匹配关系。

其问题构建为： 求解过程是先对每个点进行去质心坐标，然后根据优化问题计算旋转矩阵 R R R（这里会用到SVD），最后求 t t t

其问题构建为： 这里的推导和PnP的类似，即求位姿导数。

光流法的基本假设是灰度不变假设，即同一个空间点的像素灰度值，在各个图像中是固定不变的 在LK光流中假设某一窗口内的像素具有相同的运动，因此 w × w w×w w×w大小的窗口内有 w 2 w^2 w2个像素，即构成 w 2 w^2 w2个方程，然后构成关于 d x d t \frac{dx}{dt} dtdx​, d y d t \frac{dy}{dt} dtdy​的超定线性方程，求其最小二乘解。LK光流是得到特征点之间的对应关系，如同描述子的匹配，之后还是需要通过对极几何、PnP等求解相机位姿。

直接法之所以称为直接法是因为它是直接获得相机位姿，而不需要通过匹配、求解矩阵等过程，直接法的思路是根据当前相机的位姿估计值,来寻找 p 2 p_2 p2​ 的位置。但若相机位姿不够好, p 2 p_2 p2​的外观和 p 1 p_1 p1​会有明显差别, 然后通过优化光度误差来优化相机位姿。 非常快的框架SVO就是结合了直接法和特征点法，SVO采用的是提取稀疏特征点（类似特征点法），帧间VO用图像对齐（类似于直接法）。 直接法的缺点：1. 非凸性；2. 单个像素没有区分度；3. 灰度值不变是很强的假设

我后来对后端进行了一个非常全面的总结，参考博客视觉SLAM总结——后端总结 首先注意目标函数如下： 其中 F i j F_{ij} Fij​为整个代价函数在当前状态下对相机姿态的偏导数， E i j E_{ij} Eij​表示该函数对路标点位置的偏导数。因此在非线性优化过程中获得的 H H H矩阵为 H矩阵最重要的一个特性就是它的稀疏性，其中左上角和右下角为对角阵且一般左上角较小右下角较大。左下角和右上角可能稀疏也可能稠密，矩阵的非对角线上的非零矩阵块,表示了该处对应的两个相机变量之间存在着共同观测的路标点,有时候称为共视(Co-visibility)。其对应关系如下： 其求解 H Δ x = g \bm{H\Delta x=g} HΔx=g的过程中消元的过程即Marginalization（边缘化），首先消元结果如下： 先求解 将解得的 Δ x c \Delta \bm x_c Δxc​带入原方程，再求解 Δ x p \Delta \bm x_p Δxp​，其优势在于：

1. 在消元过程中,由于 C \bm C C为对角块,所以 C − 1 \bm {C^{-1}} C−1容易解得。
2. 求解了 Δ x c \bm{\Delta x_c} Δxc​ 之后,路标部分的增量方程由 Δ x p = C − 1 ( w − E T Δ x c ) \bm{\Delta x_p = C^{-1}(w-E^T\Delta x_c)} Δxp​=C−1(w−ETΔxc​)给出。这依然用到了 C − 1 \bm{C^{-1}} C−1易于求解的特性。

从概率角度来看,我们称这一步为边缘化，是因为我们实际上把求 ( Δ x c \Delta \bm x_c Δxc​ , Δ x p \Delta \bm x_p Δxp​) 的问题,转化成先求 Δ x c \Delta \bm x_c Δxc​ ,再求 Δ x p \Delta \bm x_p Δxp​的过程。这一步相当于做了条件概率展开: 所谓鲁棒核函数就是减小误匹配带来的误差，如Huber核，其实就是改变一下目标函数的定义: 当误差 e e e大于某个阈值 δ \delta δ后,函数增长由二次形式变成了一次形式,相当于限制了梯度的最大值.

这一部分之前并没有花很多时间去研究，主要是知道目前SLAM中用的比较多的方法是词袋模型，词袋模型中涉及到字典的生成和使用的问题，这一部分和机器学习的只是挂钩比较深。 字典的生成问题就是非监督聚类问题，可以采用K-means对特征点进行聚类，然后通过K叉树进行表达，相似度判断采用是TD-IDF的方法。

我将更多的问题总结到了视觉SLAM面试题汇总中

问题及部分回答来源： https://www.cnblogs.com/xtl9/p/8053331.html https://zhuanlan.zhihu.com/p/46694678 http://www.voidcn.com/article/p-ngqfdzqe-ot.html https://zhuanlan.zhihu.com/p/28565563

1. 构建图像金字塔，SIFT特征利用不同尺寸的图像与高斯差分滤波器卷积；SURF特征利用原图片与不同尺寸的方框滤波器卷积。
2. 特征描述子，SIFT特征有4×4×8=128维描述子，SURF特征有4×4×4=64维描述子
3. 特征点检测方法，SIFT特征先进行非极大抑制，再去除低对比度的点，再通过Hessian矩阵去除边缘响应过大的点；SURF特征先利用Hessian矩阵确定候选点，然后进行非极大抑制
4. 特征点主方向，SIFT特征在正方形区域内统计梯度幅值的直方图，直方图最大值对应主方向，可以有多个主方向；SURF特征在圆形区域内计算各个扇形范围内x、y方向的haar小波响应，模最大的扇形方向作为主方向

等距变换：相当于是平移变换（t）和旋转变换（R）的复合，等距变换前后长度，面积，线线之间的角度都不变。自由度为6（3+3） 相似变换：等距变换和均匀缩放（S）的一个复合，类似相似三角形，体积比不变。自由度为7（6+1） 仿射变换：一个平移变换（t）和一个非均匀变换（A）的复合，A是可逆矩阵，并不要求是正交矩阵，仿射变换的不变量是:平行线，平行线的长度的比例，面积的比例。自由度为12（9+3） 隐射变换：当图像中的点的齐次坐标的一般非奇异线性变换，射影变换就是把理想点（平行直线在无穷远处相交）变换到图像上，射影变换的不变量是:重合关系、长度的交比。自由度为15（16-1） 参考：https://blog.csdn.net/try_again_later/article/details/81281688

Homography Matrix可以将一个二维射影空间的点变换该另一个二维射影空间的点，如下图所示，在不加任何限制的情况下，仅仅考虑二维射影空间中的变换，一个单应矩阵 H H H可由9个参数确定，减去scale的一个自由度，自由度为8。 Fundamental Matrix对两幅图像中任何一对对应点 x \bm x x和 x ′ \bm x' x′基础矩阵 F \bm F F都满足条件： x T F x ′ = 0 \bm{x^T F x' = 0} xTFx′=0，秩只有2，因此F的自由度为7。它自由度比本质矩阵多的原因是多了两个内参矩阵。 Essential matrix：本质矩是归一化图像坐标下的基本矩阵的特殊形式，其参数由运动的位姿决定，与相机内参无关，其自由度为6，考虑scale的话自由度为5。

在相机完成校正后，则有 d / b = f / z d/b=f/z d/b=f/z,其中 d d d 表示视差， b b b 表示基线， f f f 是焦距， z z z 是深度

已知空间点世界坐标系坐标和其像素投影，公式如下 目前一共有两种解法，直接线性变换方法（一对点能够构造两个线性约束，因此12个自由度一共需要6对匹配点），另外一种就是非线性优化的方法，假设空间坐标点准确，根据最小重投影误差优化相机位姿。 目前有两个主要场景场景，其一是求解相机相对于某2维图像/3维物体的位姿；其二就是SLAM算法中估计相机位姿时通常需要PnP给出相机初始位姿。 在场景1中，我们通常输入的是物体在世界坐标系下的3D点以及这些3D点在图像上投影的2D点，因此求得的是相机坐标系相对于世界坐标系(Twc)的位姿 在场景2中，通常输入的是上一帧中的3D点（在上一帧的相机坐标系下表示的点）和这些3D点在当前帧中的投影得到的2D点，所以它求得的是当前帧相对于上一帧的位姿变换

本人知道的现在常用的就是利用词袋模型进行闭环检测，也有利用深度学习进行闭环检测的方法，暂时没有去了解过

这个之后单独写一篇博客来研究这个好了，二值图的连通域应该是用基于图论的深度优先或者广度优先的方法，后来还接触过基于图的分割方法，采用的是并查集的数据结构，之后再作细致对比研究。

在BA优化、PnP、直接法里面都有接触到非线性优化问题，上面几种方法都是针对对非线性优化问题提出的方法，将非线性最优化问题作如下展开，就可以获得梯度下降法和牛顿法 梯度下降法是一个一阶最优化算法，通常也称为最速下降法。 要使用梯度下降法找到一个函数的局部极小值，必须向函数上当前点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。因此指保留一阶梯度信息。缺点是过于贪心，容易走出锯齿路线。 牛顿法是一个二阶最优化算法，基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似。因此保留二阶梯度信息。缺点是需要计算 H \bm H H矩阵，计算量太大。 Δ x ∗ = − J T ( x ) / H \Delta \bm x^* = -\bm {J^T}(\bm x)/\bm H Δx