暑假研习系列

线、面SLAM从零入门

一、线特征及描述子

0. 点、线特征优缺点对比

线特征：优点在于具有天然的光照及视角不变性，同时更高级的特征也使追踪的鲁棒性和准确性有所提高。特别是在特定的人造场景（室内，走廊）等场景，能够克服无纹理或者不可靠纹理带来的干扰。缺点在于线段的检测及匹配耗时相对特征点更大。同时在后端也没有一个标准且通用的SLAM优化及回环模块。线特征匹配也是较为困难的，如线段易断裂，不具备强有力的几何约束（如极线几何约束），在纹理缺失处不具有较强的辨识度等。
点特征：优点最为普及和常用的特征，便于存储和匹配，速度较快。缺点在于在纹理重复，纹理缺失场景下容易误匹配，特征丢失等。

1. 端点检测与直线检测

端点检测在SLAM系统中是不可靠的，因为视角变化及相机视野的情况下并不能稳定的检测出来。因此，采用观测视角变换前后，直线是否观测到同一条直线，这一方法更加可靠。

2. 直线自由度问题

理论上直线应该有6个自由度，但是由于线绕着自身的方向轴旋转和移动，直线还是这个直线，所以自由度为4。

3. 线特征检测与特征提取问题

canny算子+霍夫直线检测：实时性不高，并且会产生误检。
LSD（a Line Segment Detector，线分割检测器）[4]：是一种能在线性时间内得到亚像素级精度的局部提取线段的算法。其核心思路是将梯度方向相近的像素点合，并进行误差控制。
- 优点该算法被设计成可以在任何数字图像上都无需参数调节。它可以自己控制误检的数量：平均而言，每张图有一个误检。它的速度比Hough要快。
- 缺点设置了每个点是否USED，因此每个点只能属于一条直线，若有相交必有至少一条直线被割裂为两条。又因为其基于梯度，直线交点梯度值往往又较小（不被检测为边缘点），因此很有可能相交的两条直线在交点处被割裂为四条线段；对于长线段被遮挡、局部模糊等原因经常割裂为多条直线。这些缺点在Hough变换中不存在。
- 整体流程如下（具体计算细节详见参考[2]）：
  - LSD首先计算对图像进行高斯下采样（s=0.8），目的是为了消除锯齿效应。
  - 计算图像每个像素点的梯度幅值与梯度方向。
  - 所有像素点的梯度构成梯度场【即，根据梯度值对所有点进行梯度从小到大的伪排序（pseudo-ordered），这里的排序也用了技巧来加速排序（将梯度值划分为1024个等级{bins}，这1024个等级涵盖了梯度由0~255的变化范围，以链表形式存储），能够在线性时间内完成。另建立状态列表，所有点设置为UNUSED，之后使用小梯度值抑制方法将梯度值小于ρ的点状态表中相应位置设置为USED】。
  - 接着合并梯度场里方向近化相同的像素点,构成一个区域,该区域被称为线段支持域（ line support regions）【即，取出列表中梯度最大（伪排列的首位）的点作为种子点（seed），状态列表中设为USED，然后以seed为起点，搜索周围UNUSED并且方向在阈值[ -t, t]范围内的点（一般取角度误差22.5），状态改为USED】。
  - 对线段支持域生成一个最小外接矩形，这个可以看做宽度为R的宽，长度为R的长的候选直线,统计最小外接矩形的主方向（矩阵最小特征值对应特征向量的角度）。若区域内某一像素点的梯度方向与主方向的角度差在设定阔值内,那么这个点被称作同性点（aligned pt）。对每个点进行设定时，将同步更新矩形框。
  - 利用最小外接矩巧内支持点的比例来判定这个线段支持域是否是一条线段【即，判断同性点密度是否满足阈值D（文章提供D=0.7），若不满足，截断R变为多个矩形框，直至满足】。
  - 利用NFA（the number of false alarms）公式计算拟合矩形精度误差。改变R使NFA的值更小直至NFA <= ε （文章中ε =1），R加入输出列表；如果改变了还不满足或者矩形区域太小，舍去。【关于NFA公式有a contrario approach and the Helmholtz principle两个准则（在完美噪声图像图像中不应该检测到目标和一个不会检测到目标的噪声图像），在[3]中直观的解释为：引入一个新的模型a contrario model，这个模型可以理解为一个完美噪声图像。如果目标图像矩形框内的aligned points个数小于了噪声图像矩形框内的aligned points个数，那么目标图像矩形框内的aligned points就有理由推断为是由图像噪声引起的，表明当前矩形与contrario model中相同位置越相似，就越不可能是真实框】
- 修正算法[1]：解决一条直线被分割为多段的问题
  - 使用LSD提取线段特征，并计算所有线段特征对应的描述子（LBD）。
  - 对于任意两对线段，计算主方向差、点线距离、端点距离、描述子距离，小于阈值被认为是一条直线
  - 最小二乘拟合直线，实行合并
  - 检查长度是否大于合并前长度，大于保留，小于舍去。
LBD（line binary descriptor，线二进制描述符）[5]：描述了一种用于定义线段特征的描述符，并且基于该描述符可以对两幅图中的线段特征进行匹配操作。
- 它在MSLD的基础上进行改进提出了LBD描述子，在保留前者光照、旋转不变性及与长度无关的优点外，还引入了全局和局部的高斯权重系数。相比于MSLD，具有更优的匹配效果，计算速度更快，并在构建线段对关系图的时候，结合线段的局部外观和几何约束两种特征。
- 算法组成：
  - 特征提取部分：EDLines算法。
  - 特征描述部分：类似于Sift统计梯度直方图作为描述子，LBD采用了对像素梯度进行统计并计算统计量的平均向量与标准方差作为描述子。
- 整体流程如下[9]：
  - 构建高斯金字塔【即，用尺度因子scale factors和高斯模糊Gaussian blurring对原图进行下采样】。
  - 对金字塔中每一层的图片都进行一次EDLine算法的线特征提取。这里内容主要参考相关论文[6]，笔记对此进行了展开解说，详见下面一小节 “补充：EDLine算法内容”。通过EDLine算法，能在每一层空间里都能够获得一组线段。然后我们将尺度空间里的线进行重组，以发现对应线段。对于每一个从尺度空间里取出的线段，如果他们在图像中是相同的线段，但是在不同的尺度空间里，我们都安排一个唯一ID并将其存入到同一个LineVec变量中。换句话说，就是将不同尺度下的直线线段一一对应，减少了图匹配问题的维度。
  - 条带（Band）来表示线的支持域。首先在线段处建立一个矩形,该矩形称为线段支持域LSR（Line Support Region），并定义了方向 $d_L$ （线的方向）和方向 $d_丄$ （线的垂直方向)，两者用于区分具有相反梯度方向的平行线并使描述符旋转不变。该线的中点被选为这个局部坐标系的原点。LSR中的每个像素的梯度投影到这个局部框架。
    
    将LSR支持区域分割为一组条带 ${B_1,B_2,B_3……B_m}$ ，这些条带是LSR支持区域的子区域，并且它们与线段是平行的关系。LSR区域共分割为m个条带，每一个条带的像素宽度为w，如下图所示。
    
    通过全局高斯函数 $f_g$ 作用于LSR的每一列，降低距离线段较远的像素梯度对描述子的影响。通过局部高斯函数 $f_l$ 作用于相邻条带的每一列，降低条带间的边界效应。懒得手打公式了，直接上截图：
- 构造条带描述符：
  
  $BD_j$ 由 $BDM_j$ 矩阵的均值向量 $M_j$ ，标准方差 $S_j$ 得到：
  （说实话这点我没看懂说的是啥？）LBD的均值部分和标准方差部分由于其大小不同，分别进行归一化处理。此外，为减少非线性光照变化的影响，对LBD每个维度的进行抑制，使它小于一个阈值（0.4的是一个很好的值）。最后通过重新归一化约束向量得到单元的LBD。
补充：Edge Drawing algorithm（ED算法）[7],[8]
- 使用5×5高斯核， $\sigma=1$ 的滤波器来平滑图像；
- 计算每个像素梯度的幅值和边缘方向（gradient magnitude and edge direction maps），梯度算子如Prewitt, Sobel, Scharr, 等可用于这一步，梯度幅值计算可以是 G = |Gx| + |Gy|，梯度方向判断依赖于是否有可能通过水平线或者垂直线：如果x梯度梯度更大与y方向梯度, i.e., |Gx| >= |Gy|, 就极有可能通过一个近似垂直的直线。否则，则可能通过一条近似水平的直线。仅使梯度角为0度或90度两种角度，因为实验表明，使用两个梯度角足以巧妙地锚定连接过程。增加梯度角的数目只是增加了计算时间而不帮助连接过程。。之后，对梯度图进行阈值化，并消除那些像素的梯度幅度小于用户定义的阈值的像素（文中Sobel算子，阈值36 ）。注意，到目前为止，上述计算步骤与正统边缘提取算法没有什么区别。
- 提取锚点：理论上锚点的设计根据应用情况可以选择不同的选点策略，如角点，关键点等。本文中作者采用的局部梯度极值方法，这样可以一定的降低计算量。直观上理解，由于局部梯度极值为锚点，通常对应边缘，然后使用智能路径将其连接起来。通过改变AnchorThresh可以定性的改变锚点数量，锚点扫描间隔也可采用不同的策略（追求细节每行/列，对象边界的骨架的话每两行/列，这个有点像降采样）。算法的具体流程如下，即：对于水平边缘，比较上下像素；对于垂直边缘，比较左和右像素（利用上一步的梯度方向属性加速计算）
- 计算启发式智能路径算法：首先初始选择一个锚点作为起始点(x,y)，当水平边缘通过该点时，通过比(x,y+1)，(x,y)，(x,y-1)三点处的像素梯度值，将最大点定义为锚点(X,Y)；若水平边缘通过该点(X,Y)，则比较(X-1,Y+1)，(X-1,Y)，(X-1,Y-1)处的像素梯度值，选择最大值，与(X,Y)相连，直到点 $(X_i , Y_i)$ 不是边缘像素，或者与已选点冲突。注意，此时并不是所有锚点都被连接。当边缘长度后者经过的锚点小于一定阈值时，边缘将会被舍弃。
补充：EDLine算法[6]

EDLines运行速度对比LSD，对给定的图像快约10倍的速度。它能够检测基本所有主要线段，并极少有误报情况。此外，ED not only produces a binary edge map similar to other edge detectors, but it also produces a set of edge segments, which are connected chains of pixels corresponding to object boundaries（即不像其他边缘检测器那样生成二值边缘映射，而是连续的像素链）。

算法流程如下：
- 运行边缘绘制（ED）算法（详见上一章节），产生一套干净的，像素相邻的链，称之为边缘。边缘线段直观地反应对象的边界。
- 然后，利用直线度准则，即最小二乘直线拟合法，从生成的像素链中提取线段。【详细来说，首先用最小二乘拟合初始生成直线（the ﬁrst while loop）；再用增加像素的方法扩展直线（the second while loop），即遍历像素链的剩余像素，当像素到当前拟合线的距离小于一定误差（一个像素大小）后添加该部分为直线，直到转向或者方向改变】
- 最后，Similar to Desolneux et al. (2000) and LSD (Grompone von Gioi et al., 2008b, 2010)，验证Helmholtz principle，用来消除虚假线段。这里详见LSD的误差控制部分，不再赘述。

4. 实验部分

待续

参考：

[1] 谢晓佳. 基于点线综合特征的双目视觉 SLAM 方法[D]. 浙江大学, 2017.

[2] 博客：https://www.cnblogs.com/Jessica-jie/p/7510931.html，及这位博主的相关笔记

[3] 博客：https://blog.****.net/wuliyanyan/article/details/103233264

[4] Von Gioi R G, Jakubowicz J, Morel J M, et al. LSD: a line segment detector[J]. Image Processing On Line, 2012, 2: 35-55.

[5] Zhang L, Koch R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency[J]. Journal of Visual Communication and Image Representation, 2013, 24(7): 794-805.

[6] Akinlar C, Topal C. EDLines: A real-time line segment detector with a false detection control[J]. Pattern Recognition Letters, 2011, 32(13): 1633-1642.

[7] C. Topal, C. Akinlar, Edge Drawing: A Combined Real-Time Edge and Segment Detector,” Journal of Visual Communication and Image Representation, 23(6), 862-872, 2012.

[8] C. Topal, C. Akinlar, and Y. Genc, Edge Drawing: A Heuristic Approach to Robust Real-Time Edge Detection, Proceedings of the ICPR, pp. 2424-2427, August 2010.

[9] Zhang L, Koch R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency[J]. Journal of Visual Communication and Image Representation, 2013, 24(7): 794-805.

暑期研习系列：线、面SLAM从零入门（持续更新中）