目前机器人SLAM问题是一个非常值得研究的方向,在未知环境中,首先要通过SLAM技术获得环境的地图,然后才能进行导航。这个方向是近几年比较新的研究方向,相关的机器人公司以及研究机器人的大厂也很需要SLAM方向的人才,比如大疆、美团、旷视科技等已经在这个行业有了一定的产品应用。在SLAM方向的面试中,总结的面试题如下:
1.重定位和回环检测的区别是什么?
2.单应矩阵H和基础矩阵F的区别是什么?
3.视觉SLAM方法的分类和对应的特点分析。
4.关键帧的作用是什么?
- 如何选择关键帧?
6.相机传感器的分类及其优缺点是什么?
7.ROS中rosrun和roslaunch的区别是什么?
8.请描述视觉SLAM的框架以及各个模块的作用是什么?
9.SLAM中的绑架问题是什么?
10.在视觉SLAM中可能用到有关的边缘检测算子有哪些?
11.在SLAM中,如何对匹配好的点做进一步的处理,更好保证匹配效果?
12.SLAM后端有滤波方法和非线性优化方法,这两种方法的优缺点是什么?
13.什么是BA优化?
14.描述一下RANSAC算法。
15.相似变换、仿射变换、射影变换的区别是什么?
16.ICP算法的原理是什么?简要叙述一下。
17.四元数的相关概念是什么,请解释一下。
18.激光SLAM中的具体方法有什么?请解释一下每种方法的特点。
19.说明UKF,EKF和PF之间的关系。
20.点云配准算法目前有哪些?
建议大家先自己答题,再对照参考答案噢~
参考答案
1.重定位和回环检测的区别是什么?
重定位是跟丢以后重新找回当前的姿态,通过当前帧和关键帧之间的特征匹配,定位当前帧的相机位姿。重定位就是重新定位,当前图像因为和最近的图像或者局部地图之间缺乏足够的匹配,导致机器人无法确定自己的位姿,此时处于当前状态的机器人不再知道其在地图中的位置,也叫做机器人被“绑架”,就说的是人质被蒙上双眼带到未知地方,蒙罩去掉后完全不知道自己在哪里,这时候就需要充分利用之前建好的地图或者存好的数据库。此时机器人需要观察周围环境,并且从已有地图中寻找可靠的匹配关系,一般是关键帧信息,这样就可以根据已有信息“重新”估计机器人的姿态。
回环检测是为了解决位置估计随时间漂移的问题。主要是通过识别曾经到过的场景,将其与当前帧对应,优化整个地图信息,包括3D路标点、相机位姿和相对尺度信息。回环的主要目的是降低机器人随时间增加,轨迹中累积的漂移,一般发生在建图过程中。这是因为基于运动传感器或者视觉信息的里程计容易出错,使估计的轨迹偏离其实际真实的情况。通过回环,优化整个地图信息,包括3D路标点、相机位姿和相对尺度信息。回环检测提供了回环帧与所有历史帧的关系,可以极大减少误差。回环主要是纠正机器人/相机轨迹,而重新定位再从未知状态找回姿态。两者都需要当前图像预先访问过之前的位置附近,本质上都是一个图像识别问题。
重定位和回环检测的区别:
重定位主要为了恢复姿态估计,而回环是为了解决漂移,提高全局精度。二者容易混淆的原因是重定位通常也需要找到与之前帧的对应关系求解出姿态,而这可以通过回环来完成,很多算法是可以共享的。
2.单应矩阵H和基础矩阵F的区别是什么?
(1)基础矩阵F和单应矩阵H所求相机获取图像状态不同而选择不同的矩阵。
(2)本质矩阵E和基础矩阵F之间相差相机内参K的运算。
(3)只旋转不平移求出F并分解出的R,T和真实差距大不准确,能求H并分解得R。
3.视觉SLAM方法的分类和对应的特点分析。
视觉SLAM可以分为特征点法和直接法。特征点法是根据提取、匹配特征点来估计相机运动,优化的是重投影误差,对光照变化不敏感,是比较成熟的方案,常见的开源方法有ORB-SLAM等。
特征点法的优点:
(1)特征点本身对光照、运动、旋转比较不敏感,因此稳定性更好。
(2)相机运动较快,也能跟踪成功,鲁棒性较好。
(3)研究时间较久,方案比较成熟。
特征点法的缺点:
(1)关键点提取、描述子匹配时间长。
(2)特征点丢失的场景无法使用。
(3)只能构建稀疏地图。
直接法根据相机的亮度信息估计相机的运动,可以不需要计算关键点和描述子,优化的是光度误差,根据使用像素可分为稀疏、半稠密、稠密三种,常见的方案是SVO、LSD-SLAM等。
直接法的优点:
(1)速度快,可以省去计算特征点和描述子时间。
(2)可以在特征缺失的场合,特征点法在该情况下会急速变差。
(3)可以构建半稠密乃至稠密地图。
直接法的缺点:
(1)因为假设了灰度不变,所以易受光照变化影响。
(2)要求相机运动较慢或采样频率较高。
(3)单个像素或像素块区分度不强,采用的是数量代替质量的策略。
4.关键帧的作用是什么?
关键帧目前是一种非常常用的方法,可以减少待优化的帧数,并且可以代表其附近的帧。
5. 如何选择关键帧?
选取关键帧的指标:
(1)距离上一关键帧的帧数是否足够多(时间)。运动很慢的时候,就会选择大量相似的关键帧,冗余、运动快的时候又丢失了很多重要的帧。
(2)距离最近关键帧的距离是否足够远(空间)运动。相邻帧根据姿态计算运动的相对大小,可以是位移,也可以是旋转,或者二者都考虑了。
(3)跟踪质量(主要根据跟踪过程中搜索到的点数和搜索的点数比例)/共视特征点。这种方法记录了当前视角下的特征点数或者视角,当相机离开当前场景时才会新建关键帧,避免了上一种方法存在的问题,缺点是比较复杂。
6.相机传感器的分类及其优缺点是什么?
视觉SLAM常用的相机包括单目相机、双目相机和深度相机。
单目相机的优点:
(1)应用最广,成本可以做到非常低。
(2)体积小,标定简单,硬件搭建也简单。
(3)在有适合光照的情况下,可以适用于室内和室外环境。
单目相机的缺点:
(1)具有纯视觉传感器的通病:在光照变化大,纹理特征缺失、快速运动导致模糊的情况下无法使用。
(2)SLAM过程中使用单目相机具有尺度不确定性,需要专门的初始化。
(3)必须通过运动才能估计深度,帧间匹配三角化。
双目相机一般有Indemind、小觅和ZED等。
双目相机的优点:
(1)相比于单目相机,在静止时就可以根据左右相机视差图计算深度。
(2)测量距离可以根据基线调节。基线距离越大,测量距离越远。
(3)在有适合光照的情况下,可以适用于室内和室外。
双目相机的缺点:
(1)双目相机标定相对复杂。
(2)用视差计算深度比较消耗资源。
(3)具有纯视觉传感器的通病:在光照变化较大、纹理特征缺失、快速运动导致模糊的情况下无法使用。
深度相机一般有Kinect系列、Realsense系列、Orbbec和Pico等。
深度相机的优点:
(1)使用物理测距方法测量深度,避免了纯视觉方法的通病,适用于没有光照和快速运动的情况。
(2)相对双目相机,输出帧率较高,更适合运动场景。
(3)输出深度值比较准,结合RGB信息,容易实现手势识别、人体姿态估计等应用。
深度相机的缺点:
(1)测量范围窄,容易受光照影响,通常只能用于室内场景。
(2)在遇到投射材料、反光表面、黑色物体情况下表现不好,造成深度图确实。
(3)通常分辨率无法做到很高,目前主流的分辨率是640×480.
(4)标定比较复杂。
7.ROS中rosrun和roslaunch的区别是什么?
rosrun允许在任意软件包中运行可执行文件,而无需先在其中进行cd或roscd。
Roslaunch可以通过ssh在本地和远程轻松启动多个ros节点,以及在参数服务器上设置参数。它包括自动重生已经死掉的进程的选项。roslaunch接收一个或多个XML配置文件,这些文件指定要设置的参数和要启动的节点以及应在其上运行的计算机。
rosrun只能运行一个节点,如果要运行多个节点,就需要多次使用rosrun命令,而roslaunch可以采用xml格式描述运行的节点,同时运行多个节点。
8.请描述视觉SLAM的框架以及各个模块的作用是什么?
(1)传感器信息读取。在视觉SLAM中主要是相机图像信息的读取和预处理,在机器人中,还会有码盘、惯性传感器等信息的读取和同步。
(2)视觉里程计就是前端,其任务是估算相邻图像间相机运动,以及局部地图的样子。
(3)后端优化。后端接受不同时刻视觉里程计测量的相机位姿,以及回环检测的信息,对它们进行优化,得到全局一致的轨迹和地图。
(4)回环检测。判断机器人是否到达过去先前的位置,如果检测到回环,它会把信息提供给后端进行检测。
(5)建图。根据估计的轨迹,建立与任务要求对应的地图。
9.SLAM中的绑架问题是什么?
绑架问题就是重定位,指的是机器人缺少先前位置信息的情况下确定当前位姿。比如机器人在一个已经构建好地图的环境中,但它并不知道自己在地图中的相对位置,或者在移动过程中,由于传感器的暂时性功能故障或者相机的快速移动,导致先前的位置信息丢失,因此得重新确定机器人的位置。初始化绑架是一个通常状况的初始化问题,可以使用粒子滤波方法,重新分散例子到三维空间,被里程信息和随机扰动不断更新,初始化粒子收敛到可解释观察结果的区域。追踪丢失状态绑架,即在绑架发生之前,系统已经保存当前状态,则可以使用除视觉传感器之外的其他的传感器作为候补测量设备。
10.在视觉SLAM中可能用到有关的边缘检测算子有哪些?
在边缘检测一般分为滤波、增强和检测三个步骤,其基本原理是用高斯滤波器进行去噪,之后再用卷积内核寻找像素梯度。边缘检测算子:
(1)canny算子:一种完善的边缘检测算法,抗噪能力强,用高斯滤波平滑图像,用一阶偏导的有限差分计算梯度的幅值和方向,对梯度幅值进行非极大值抑制,采用双阈值检测和连接边缘。
(2)sobel算子:一阶导数算子,引入局部平均运算,对噪声具有平滑作用,抗噪声能力强,计算量较大,但定位精度不高,得到的边缘比较粗,适用于精度要求不高的场合。
(3)laplacian算子:二阶微分算子,具有旋转不变性,容易受噪声影响,不能检测边缘的方向,一般不直接用于检测边缘,而是判断明暗变化。
11.在SLAM中,如何对匹配好的点做进一步的处理,更好保证匹配效果?
(1)确定匹配最大距离,汉明距离小于最小距离的两倍。
(2)使用KNN-matching算法,在这里设置K为2,每个匹配得到两个最接近的描述子,然后计算最接近距离和次接近距离之间的比值,当比值大于既定值时,才作为最终匹配。
(3)使用RANSAC算法找到最佳单应性矩阵,该函数使用的特征点同时包含正确和错误匹配点,因此计算的单应性矩阵依赖于二次投影的准确性。
12.SLAM后端有滤波方法和非线性优化方法,这两种方法的优缺点是什么?
滤波方法的优点:在当前计算资源受限、待估计量比较简单的情况下,EKF为代表的滤波方法非常有效,经常用在激光SLAM中。
滤波方法的缺点:存储量和状态量是平方增长关系,因为存储的是协方差矩阵,因此不适合大型场景。但是现在视觉SLAM的方案中特征点的数据很大,滤波方法效率是很低的。
非线性优化方法一般以图优化为代表,在图优化中BA是核心,而包含大量特征点和相机位姿的BA计算量很大,无法实时。在后续的研究中,人们研究了SBA和硬件加速等先进方法,实现了实时的基于图优化的视觉SLAM方法。
13.什么是BA优化?
BA的全称是Bundle Adjustment优化,指的是从视觉重建中提炼出最优的三维模型和相机参数,包括内参和外参。从特征点反射出来的几束光线,在调整相机姿态和特征点空间位置后,最后收束到相机光心的过程。BA优化和冲投影的区别在于,对多段相机的位姿和位姿下的路标点的空间坐标进行优化。
将误差表示为:
也就是:
可以计算出误差对位姿和路标坐标的偏导:
对于特征点位置p和m个位姿以及n个特征点,表示为:
上式中的右边简写为:
然后,将优化的目标函数表示为:
目标函数也可以表示为:
对于线性增量方程:
这里的
将雅克比矩阵分块为:
则:
14.描述一下RANSAC算法。
RANSAC算法是随机采样一致算法,从一组含有“外点”的数据中正确估计数学模型参数的迭代算法。“外点”一般指的是数据中的噪声,比如匹配中的误匹配和估计曲线中的离群点。因此,RANSAC算法是一种“外点”检测算法,也是一种不确定的算法,只能在一种概率下产生结果,并且这个概率会随着迭代次数的增加而加大。RANSAC主要解决样本中的外点问题,最多可以处理50%的外点情况。
RANSAC主要通过反复选择数据中的一组随机子集来达成目标,被选取的子集假设为局内点,验证步骤如下:
(1)一个模型适用于假设的局内点,也就是说所有的未知参数都能从假设的局内点计算得到。
(2)使用(1)中得到的模型测试所有其他数据,如果某个点适用于估计的模型,认为它也是局内点。
(3)如果有足够多的点被归类为假设的局内点,则估计的模型就足够合理。
(4)使用假设的局内点重新估计模型,因为它仅仅被初始的假设局内点估计。
(5)最终,通过估计局内点和模型的错误率估计模型。
15.相似变换、仿射变换、射影变换的区别是什么?
相似变换相当于等距变换和均匀缩放的一个复合,用S表示变换矩阵,S为3×3矩阵,
左上角2×2矩阵为旋转部分,tx和ty为平移因子,具有4个自由度,即旋转、x方向平移、y方向平移和缩放因子s。相似变换前后长度比,夹角,虚圆点I,J保持不变。
仿射变换相当于一个平移变换和一个非均匀变换的复合,用A矩阵表示,A为3×3矩阵,
其中A可以分解为:
其中
左上角2×2矩阵为旋转部分,tx和ty为平移因子,它有6个自由度,即旋转4个,x方向平移,y方向平移。它能保持平移性,不能保持垂直性,图像中各部分变换前后面积比保持不变,共线线段或者平行线段的长度比保持不变,矢量的线性组合不变。
射影变换由有限次中心射影的面积定义的两条直线间的对应变换称为一维射影变换,由有限次中心射影的面积定义的两个平面之间的对应变换称为二维射影变换。射影变换是最一般的线性变换,有8个自由度,保持重合关系和交比不变,但不会保持平行性。
16.ICP算法的原理是什么?简要叙述一下。
ICP算法的核心是最小化目标函数:
目标函数是指是对所有对应点之间的欧式距离的平方和。
17.四元数的相关概念是什么,请解释一下。
四元数在程序中使用很广泛,但在SLAM中四元数的概念比较难理解。四元数是Hamilton找到的一种扩展复数,四元数具有一个实部和三个虚部:
其中i,j,k是四元数的三个虚部,满足下式:
也可以使用标量和向量来表示四元数:
在上式中,标量s是四元数的实部,向量v是虚部。
四元数可以表示三维空间中任意一个旋转,与旋转矩阵类似,假设某个旋转是围绕单位向量
进行了角度为θ的旋转,则该旋转的四元数形式为:
上式实质上是模长为1的四元数,也就是单位四元数。反之,也可以通过任意长度为1的四元数计算对应旋转轴和夹角:
如果某个四元数的长度不为1,可以通过归一化转化为模长为1的四元数。
对四元数的θ加上2π,就可以得到相同旋转,但对应的四元数变为-q。因此,在四元数中,任意的旋转都可以由两个互为相反数的四元数表示。如果θ为0的话,则得到一个没有任何旋转的四元数:
18.激光SLAM中的具体方法有什么?请解释一下每种方法的特点。
激光雷达分为单线和多线两种,单线雷达一般应用在平面运动场景,多线雷达应用在三维运动场景。
(1)单线雷达构建二维地图的SLAM算法称为2D lidar SLAM,包括Gmapping、hector、karto和cartographer算法,在二维平面内运动,扫描平面与运动平面平行。
Gmapping是一种基于粒子滤波的2D激光雷达SLAM,构建二维栅格地图。融合里程计信息,没有回环检测。优点是在小场景中,计算量小,速度较快。 缺点是每个粒子都携带一幅地图,无法应对大场景(内存和计算量巨大);如果里程不准或标定参数不准,在长回廊等环境中容易把图建歪。
hector SLAM是完全基于scan-matching的,使用迭代优化的方法来求匹配的最佳位置,为避免陷入局部极值,也采用多分辨率的地图匹配。 由于完全依赖于scan matching,要求雷达的测量精度较高、角度范围大,扫描速度较高(或移动速度慢)。噪声多、边角特征点少的场景就很容易失败。 原文所提出方法的特点还在于,加入IMU,使用EKF估计整体的6DoF位姿,并根据roll, pitch角将激光扫描数据投影到XY平面,因而支持激光雷达有一定程度的倾斜,比如手持或机器人运动在不是很平整的地面上。
karto是基于scan-matching,回环检测和图优化SLAM算法,采用SPA(Sparse Pose Adjustment)进行优化。
cartographer是谷歌开源的激光SLAM框架,主要特点在于: 1.引入submap,scan to submap matching,新到的一帧数据与最近的submap匹配,放到最优位置上。如果不再有新的scan更新到最近的submap,再封存该submap,再去创建新的submap。 2.回环检测和优化。利用submap和当前scan作回环检测,如果当前scan与已经创建的submap在距离上足够近,则进行回环检测。检测到回环之后用ceres进行优化,调整submap之间的相对位姿。为了加快回环检测,采用分枝定界法。
(2)3D lidar SLAM算法是针对多线雷达的SLAM方法,包括LOAM、Lego-LOAM和LOAM-livox等。
LOAM是针对多线激光雷达的SLAM算法,主要特点在于:1) 前端抽取平面点和边缘点,然后利用scan-to-scan的匹配来计算帧间位姿,也就形成了里程计;2) 由估计的帧间运动,对scan中的每一个点进行运动补偿;3) 生成map时,利用里程计的信息作为submap-to-map的初始估计,再在利用submap和map之间的匹配做一次优化。 LOAM提出的年代较早(2014),还没有加入回环优化。
LeGO-LOAM在LOAM的基础上主要改进:1) 地面点分割,点云聚类去噪;2)添加了ICP回环检测和gtsam优化。
LOAM_livox是大疆2019年公布的面向小FOV Lidar的LOAM算法。相比LOAM,做了一些改动。算法的特点: 1.添加策略提取更鲁棒的特征点:a) 忽略视角边缘有畸变的区域; b) 剔除反射强度过大或过小的点 ; c) 剔除射线方向与所在平台夹角过小的点; d) 部分被遮挡的点 2.与LOAM一样,有运动补偿 3.里程计中剔除相对位姿解算后匹配度不高的点(比如运动物体)之后,再优化一次求解相对位姿。
19.说明UKF,EKF和PF之间的关系。
从精度的角度来看,所有高精度都是通过增加计算量来换来的,如果UKF通过加权减少Sigma点的方法来降低计算负载,那么精度在一定程度上会低于一阶泰勒展开的EKF线性化。除了EKF和UKF之间的时间复杂性问题外,我们还需要检查它们的理论性能。从以往的一些研究中中,我们知道UKF可以将状态估计和误差协方差预测到4阶精度,而EKF只能预测状态估计的2阶和误差协方差的4阶。但是,只有在状态误差分布中的峰度和高阶矩很明显的情况下,UKF才能进行更准确的估计。在我们的应用中,四元数分量协方差的大小显着小于统一性,这意味着峰度和更高阶矩非常小。这一事实说明了为什么UKF的性能不比EKF好。
另外,采样率也是另外一个拉小UKF与EKF差距的因素,对许多动态模型(有论文提到四元数动态)随着采样间隔的缩短,模型愈发趋近准线性化,那么越小的步长,积分步长把(四元数)传播到单位球面的偏差就越小。因此最小化了线性化误差。
最后,也是最根本的在选取EKF和UKF最直观的因素,UKF不用进行雅可比矩阵计算,但是,许多模型的求导是极为简单的,在最根本的地方UKF没有提供更优的解决方案。这也使得,状态模型的雅可比计算的简单性允许我们在计算EKF和UKF用相同的方法计算过程误差协方差。
UKF并不是万能的,也不是一定比EKF优秀,很多时候需要根据情况选择特定的滤波。
20.点云配准算法目前有哪些?
点云配准算法目前有ICP、KC、RPM、形状描述符配准和UPF/UKF。
(1)ICP
ICP算法简单且计算复杂度度低,使它成为最受欢迎的刚性点云配准方法。ICP算法以最近距离标准为基础迭代地分配对应关系,并且获得关于两个点云的刚性变换最小二乘。然后重新决定对应关系并继续迭代知道到达最小值。目前有很多点云配追算法都是基于ICP的改进或者变形,主要改进了点云选择、配准到最小控制策略算法的各个阶段。ICP算法虽然因为简单而被广泛应用。但是它易于陷入局部最大值。ICP算法严重依赖初始配准位置,它要求两个点云的初始位置必须足够近,并且当存在噪声点、外点时可能导致配准失败。
(2)KC
KC算法应用了稳健统计和测量方法。Tsin和Kanade应用核密度估计,将点云表示成概率密度,提出了核心相关(Kernel Correlation,简称KC)算法。这种计算最优配准的方法通过设置两个点云间的相似度测量来减小它们的距离。对全局目标函数执行最优化算法,使目标函数值减小到收敛域。因为一个点云中的点必须和另一个点云中的所有点进行比较,所以这种方法的算法复杂度很高。
(3)RPM
为了克服ICP算法对初始位置的局限性,基于概率论的方法被研究出来。Gold提出了鲁棒点匹配(Robust Point Matching,简称RPM)算法,以及其改进算法。这种方法应用了退货算法减小穷举搜索时间。RPM算法既可以用于刚性配准,也可以用于非刚性配准。对于RPM算法,在存在噪声点或者某些结构缺失时,配准可能失败。
(4)形状描述符配准
形状描述符配准在初始位置很差的情况下也能大体上很好的实现配准。它配准的前提是假设了一个点云密度,在没有这个特殊假设的情况下,如果将一个系数的点云匹配到一个稠密的点云,这种匹配方法将失败。
(5)UPF/UKF
尽管UPF算法能够精确的配准较小的数据集,但是它需要大量的粒子来实现精确配准。由于存在巨大的计算复杂度,这种方法不能用于大型点云数据的配准。为了解决这个问题,UKF算法被提出来,这种方法收到了状态向量是单峰假设的限制,因此,对于多峰分布的情况,这种方法会配准失败。
版权归原作者 深蓝学院 所有, 如有侵权,请联系我们删除。