自动驾驶定位面试以及参考答案_定位算法面试

作者：木道寻08 | 2024-07-30 21:59:35

踩

定位算法面试

一、惯性导航方向

IMU测量方程是什么？噪声模型是什么？
中值积分情况下，imu的测量方程为
1)姿态解算
a.基于旋转矩阵
IMU的随机误差一般包括以下几类，各类误差项及其原理如下(以陀螺仪为例)( 1）量化噪声
量化噪声是数字传感器必然出现的噪声，我们通过AD采集把连续时间信号采集成离散信号，在这个过程中，精度就会损失，损失的精度大小和AD采样的精度有关(这里具体指的是模数转换时，AD器件的位数，位数越高采样越精确），精度越高，量化噪声越小。
( 2）角度随机游走
陀螺敏感角速率并输出时是有噪声的，这个噪声里面的白噪声成分叫宽带角速率白噪声，我们计算姿态时，本质上是对角速率做积分，这必然会对噪声也做了积分。白噪声的积分并不是白噪声，而是一个马尔可夫过程，即这一次的误差是在上一次误差的基础上累加一个随机白噪声得到的。角度误差所包含的这种马尔可夫性质的误差就叫做角度随机游走。
( 3)角速率随机游走
从理解上和角度随机游走一样，角速率里面并不全是白噪声，它也有马尔可夫性质的误差成分，而这个误差是由宽带角加速率白噪声累积的结果。
(4）零偏不稳定性噪声
这应该是大家再熟悉不过的一个误差项了，如果一个陀螺只让你用一个指标来体现精度，那必然就是它了。但是这个指标的理解上却不像前几个参数那样直白。
我们可以先把它理解为零偏随时间的缓慢变化，假设在刚开始时零偏大小是某个值，那么过一段时间之后，零偏便发生了变化，具体变化成了多少，无法预估，所以就要给他一个概率区间，来描述它有多大的可能性落在这个区间内，时间越长，区间越大。
实际上，如果你真的测的时间足够长，会发现它也不会无限制增长下去，所以，这个对概率区间的描述只是近似有效，或者一定时间内有效，由于这个有效时间比较长，所以我们一般仍然使用这种方式来描述，只是在理解上要知道这一点的存在。
( 5）速率斜坡
看到斜坡这种描述词，我们一般会想它是不是一种趋势项。实际上，它确实是趋势性误差，而不是随机误差。所谓随机误差，是指你无法用确定性模型去拟合并消除它，最多只能用概率模型去描述它，这样得到的预测结果也是概率性质的。而趋势性误差是可以直接拟合消除的，在陀螺里，这种误差最常见的原因是温度引起零位变化，可以通过温补来消除。
加速度计同样具有这5项误差，而且原理一致，因此不再重复
惯导误差模型是怎么来的？比如15维的卡尔曼滤波模型。
可参考博客文章< https://zhuanlan.zhihu.com/p/135230133>
或参考英文文献
GPS双天线安装偏角是怎么标定的？
通过车辆前行得到航迹角，同时双天线自己可以计算出一个航向角，两者之差为安装偏角，具体拟合方法可以通过最小二乘或滤波算出。
多传感器之间是怎么对时的？
激光雷达∶大多数雷达如VLP-16等都提供基于pps脉冲和GPRMC信号的输入接口,PPS和GPRMC信号可以由GNSS或IMU提供，或者由外部时钟源提供。少数激光雷达还支持
NTP/PTP同步，PTP的精度一般来说比NTP要高，这两个信号都需要由外部时钟源设备提供。相机:需要支持外部触发曝光的型号，因为相机帧周期包括曝光时间和readout时间（整帧像素点读出），一般来说readout时间是固定的，可以补偿这个时间，相机的时间戳选择为曝光的中间时间。
GNSS : GNSS可以从卫星获得高精度的时钟信号，而且通常的GNSS都支持PPS脉冲以及GPRMC信号。
(1 )使用GNSS作为时钟源，将GNSS的PPS信号提供给LiDAR和一个开发板，开发板将给相机同时提供一个曝光的脉冲信号。CAMVOX采用这种方案。
(2)使用外部时钟源，这种时钟源通常支持PPS信号输入，将GNSS的PPS传给外部时钟源，同时外部时钟源可以使用PTP/NTP/PPS给LiDAR做时间同步，同时触发相机开始曝光。外部时钟源同时也可以使用PTP/NTP对主机进行时间同步。
GPS到来时是有延时的，而IMU给出的加速度和角速度是实时的，这种情况下怎么处理延时？怎么做的融合？
先通过imu积分计算实时的轨迹，同时把imu数据缓存下来，当GPS到来时，再根据GPS的时间戳去修正历史时刻的数据，然后重新积分该时刻后的imu。
DR递推的原理是什么？大概怎么去做？
DR，也叫航位推算，是在知道当前时刻位置的条件下，通过测量移动的距离和方位，推算下一时刻位置的方法。可以根据上一时刻位置速度角度，通过imu加速度二次积分得到平移量，角速度积分得到旋转量来进行DR，也可以通过轮速计和车辆运动模型来进行DR。
组合导航卡尔曼滤波过程噪声是如何调参的?
先通过GPS和imu的性能参数和频率确定一个米级单位下的噪声。之后在该噪声参数下得到融合的轨迹，然后分别对两个噪声增大缩小分成几组进行调节，观察轨迹。最终选最平滑的一组轨迹的噪声参数，或者选跟真值比精度最高的一组的噪声参数。

二、点云算法方向

最近邻问题有哪几种典型解法？
( 1 )Ⅰ暴力搜索:计算每个点对与其他点之间的距离，取最小。
( 2 ) I KDTree :建立KDtree，依次在不同维度上划分数据，加快搜索速度，可以适用于任何维度的数据。
( 3 )I八叉树:将空间逐级分为8个区域来划分数据，故称为8叉树，适用于3维数据。同理还有二叉树、四叉树等等…
怎么对KdTree进行插入操作？怎么确定一个节点的分类面？
(1 )Ⅰ插入操作∶直接寻找其对应的叶子节点，将其加入其中，如果叶子节点中点的数量多于了设定值，则再对叶子节点划分。但是这样插入的点多了会影响KDtree相对平衡的树深度。因此当插入的点过多时，可以直接重构一个KDtree。(不一定对)
( 2)l节点的分类面:
n依次对不同维度进行划分，划分的依据是此节点这个维度上数值的中位数/平均数，本节点划分的维度取决于本节点轮到了哪个维度。
n检查当前节点上所有数据在所有维度上的标准差/方差，动态的选择方差最大的维度进行划分，同样使用中位数/平均数进行划分。这样可以提高KDTree的搜索速度。
怎么对KdTree进行Search By Range和Search By KNN操作？
( 1 ) n KNN:维护一个长度为K的距离序列，将当前搜索过的距离最小的K个点的序号纳入其中，同时记录一个worst_dist。搜索从query所在的最小的分区开始，依次向上遍历。当搜索点与当前分区的分割轴的距离大于worst_dist时，可以跳过对此分割轴另一边的搜索，以大幅加快搜索速度。
( 2) Range :同理，直接将上述worst_dist设定为搜索半径R，将满足条件的点需要全部append到列表中即可。
举出除了KdTree以外的近邻计算方法（栅格、B树、R树、四叉、八叉树等）。
4.举出除了KdTree以外的近邻计算方法(栅格、B树、R树、四叉、八叉树等)。【参考回答】
( 1 ) B树:在B-树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1…Kn查找给定的关键字(可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功;否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。
( 2 ) R树:R树是用来做空间数据存储的树状数据结构。1.除根结点之外，所有非根结点包含有m至M个记录索引(条目)。根结点的记录个数可以少于m。通常，m=M/2。2.对于所有叶子中存储的记录(条目），l是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意∶此处所说的“矩形”是可以扩展到高维空间的)。3.对于所有非叶子结点上的记录(条目），i是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质2)。4.所有叶子结点都位于同一层，因此R树为平衡树。
( 3 ) 四叉树:四叉树数据结构是一种对栅格数据的压缩编码方法。其基本思想是将一幅栅格数据层或图像等分为4部分，逐块检查其格网属性值（或灰度）;如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区分割为四个子区;这样依次分割，直到每个子块都只含有相同的属性值或灰度为止;查找时，过远的节点可以不用展开。
( 4 ) 八叉树:八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心;左:递回子切分一个立方体为多个卦限.右:对应的八叉树。查找时，过远的节点可以不用展开。
给定一组点，如何计算其拟合平面？如何计算其拟合直线？解释其方法的意义。
l通过最小二乘法可以实现对其平面和直线的拟合，两者方法并无本质的区别，只是形式分别为AX+BY+CZ+D=O以及AX+BY+C=0。具体最小二乘法的解法可以使用系数矩阵的特征值和特征向量求解，也可以通过系数矩阵的左逆方法求解。
举出常见的点云的registration方法。
lterative Closest Point (ICP)和Normal Distribution Transform(NDT )
说明ICP的详细过程，要求说明代数解法和匹配问题解法。

( 1 ) ICP的代数解法如上，对于两组点集，通过最近邻找到可能的匹配对，并根据变换后距
离欧式最小的原则求得一组R，t的解。按照这种方法不断迭代，直到R,t收敛。
( 2 ) ICP问题最好有一组较好的初始解，这样可以加快算法的收敛速度，提高算法收敛的质量。这一组初始解可以通过相对可靠的匹配点获得。一般这样的匹配点通过特征点搜索和特征点描述子来得到，即使用FPFH,SHOT或其他3D特征描述子来进行特征点匹配，建立特征点匹配对。之后使用RANSAC方法来在这些特征点之间建立最合理的ICP解，再作为初值，带入上述的ICP算法求解。
说明NDT的详细过程，Normal distribution的含义是什么。

Normal Distribution 代表正态分布。NDT算法找到每一个点对应的一个cell，将其中的点分布视为一个正态分布，计算其均值和方差。这样就可以得到一个点在其对应的cell中的似然概率。NDT算法就是以这样一种思想出发，目的是将source中的点进行一个变换，使其变换到target点云中，并且每个点在其对应的cell里的似然概率最大，即负对数似然最小，如下。
具体的最优化方法可以使用简单的一阶方法，梯度下降法或者二阶方法，牛顿法。上述算法表格中使用的是牛顿法。
匹配问题除了最近邻还有什么解法？说明匈牙利算法、最大流/最小割、谱方法等其中一种。
匈牙利算法同样用于求解两个结合之间的最大匹配问题，匹配有两个要点:( 1 ）匹配是边的合集
( 2）这个合集中，任意两条边不能有共同的顶点
对于一个二部图，我们可以先给出满足上述条件的随意的一个匹配，之后，在这个已经确定的匹配前提下，去寻找增广路径。每找到一个增广路径，就意味着目前的匹配中可以再增加一条边。当图中再也找不到增广路径时，就意味着已经完成了二部图的最大匹配任务。这就是匈牙利算法的思想。
解释混合高斯模型含义。解释EM算法的原理。
混合高斯模型即由多个高斯分布混合而成的分布，其中的数据以不同的概率屋于不同的高斯分布，在其属于的分布中服从普通的具有不同参数的高斯分布。如下图所示

在这里插入图片描述
EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步(E步），另一个为极大步(M步），所以算法被称为EM算法( Expectation-MaximizationAlgorithm )。

在这里插入图片描述

总体步骤如下：
在这里插入图片描述

三、状态估计方向

从贝叶斯滤波器角度推出卡尔曼滤波器方程。
从增益最优化角度推出卡尔曼滤波器方程。
从Cholesky方程推出卡尔曼滤波器方程。
解释KF中的噪声矩阵含义。运动方程中估计噪声是变大还是变小？修正方程中估计噪声是变大还是变小？
RTS与KF之间的联系？
将卡尔曼滤波器推广至EKF。
解释数值矩阵求逆的几种做法（QR、Cholesky、SVD）。
什么是Moore-Penrose逆？如何计算Moore-Penrose逆？
SVD是什么？SVD是如何求解的？
特征值是什么？如何计算矩阵的特征值与特征向量？什么样的矩阵必然能对角化？不能对角化的矩阵的标准形式是什么？什么是Jordan标准形？
如何求解线性最小二乘解？如何求解零空间解？说明特征值方法和奇异值方法之间的联系。
描述图优化和最小二乘之间联系。画出VIO中常用的图优化模型。
稀疏图优化的稀疏性体现在哪里？要求答出稀疏Schur和稀疏Cholesky之一。
描述滤波器与最小二乘之间的联系？说明为什么卡尔曼滤波器可以看成两个时刻间的最小二乘。
说明UKF、EKF和PF之间的关系。
解释UKF中的Sigma采样点关系。
解释PF中的重要性重采样的过程是如何做的。解释轮盘赌原理。
解释李群李代数在三维状态估计中的作用。
流形是怎么定义的？流形在局部与R3同胚是什么含义？为什么说SO3是一个流形？
解释SO3, SE3中的Exp和Log的原理。解释BCH的原理和作用。
分别使用左右扰动模型，求解几个常见的雅可比：
解释四元数的更新与SO3的更新方式有何异同。
说明四元数运动模型与SO3运动模型之间的联系。
解释高斯推断和概率学中边缘化之间的关系。解释边缘化与卡尔曼滤波器之间的关系。
什么是M估计？说明M估计与核函数之间的关系？

四、计算机视觉/VIO方向

单应矩阵、基础矩阵、本质矩阵的定义？
相机内参和外参的含义？如果将图像放大两倍，内外参如何变化？
相机内参的意义会随着相机几何模型的选择的而异;相机的几何模型通常可分为投影模型与畸变模型，譬如投影模型包括针孔模型、全向模型、双球面模型等，畸变模型包括径向-切向模型、等距模型、等积模型、多项式拟合模型等，根据不同的组合可得到不同的相机模型。相机模型决定了相机内参，即相机投影模型参数和相机畸变模型参数。相机内参数是与相机自身特性相关的参数，比如相机的焦距、像素大小、畸变参数等，SLAM中通常使用K内参矩阵表示相机投影模型，如
径向和切向畸变模型含义，鱼眼模型含义（回答等距投影模型即可）？
( 1)径向畸变︰光线在远离透镜中心的地方比靠近中心的地方更加弯曲。
( 2)切向畸变∶透镜不完全平行于图像平面，即sensor装配时与镜头间的角度不准。
( 3)鱼眼模型:等距投影模型中，成像点位置和入射角成正比。
极线是什么？对极约束是什么？描述了什么几何关系？
如果两个相机在不同位置拍摄同一个物体，或者一个运动的相机在不同时刻拍摄同一物体，我们有理由相信两张图片中匹配的特征点之间存在着某种几何关系，这种关系可以用对极几何来描述。对极几何描述了两帧图像中各像素的射影关系(或者说是各匹配点的几何关系)，其与外部的场景本身无关，只与相机的内参以及两图像的拍摄位置有关。
八点法原理与过程。
在对极几何中，F是一个3×3的矩阵，有九个未知量，但是F存在尺度等价性、不满秩两个约束，F矩阵的自由度为7。由于每对点能提供一个约束，因此理论上仅需要7对点便可求解F矩阵，然而该结果可能给出F的3个实数解，且所有3个解都要通过检验来选择。因此通常会选择8对点，构建超定方程，然后通过最小二乘、并添加强迫约束来求解。
具体步骤如下：
预积分相比于传统积分的差异在哪里？
传统的积分方式在IMU积分的过程中，每一次姿态的更新都需要依赖上一次的积分结果，这会导致如果关键帧的位姿进行了优化，对优化后的关键帧的下一帧位姿的IMU预测的结果需要重新计算积分过程，这会造成计算资源的浪费。预积分重新推导了积分的过程，将积分的基准坐标系确定为IMU坐标系，使得积分的过程不受积分起始位姿的影响，当关键帧的位姿发生改变后，将预积分的结果直接加到优化后的位姿上，就可以得到目标关键帧的IMU预测的位姿。预积分的主要差异在于积分的基准坐标系，有点world-centric robo-centric的意思﹔;带来的结果是优化迭代过程中，不会重复计算;这个是优化中使用预积分的原因。
预积分的测量模型和噪声模型是什么？预积分对零偏是怎么处理的？为什么要这样处理？
说明预积分的图优化模型。
解释重投影模型和BA的原理。
说明PnP问题的解法。
说明RANSAC原理，讨论存在的问题。
随机采样一致性(RANSAC )是一种根据含有外点的数据拟合参数模型的迭代方法。外点( outlier ）是“不符合”模型的测量，内点( inlier )是“符合”模型的测量。RANSAC是一种概率算法，只有花费足够时间去搜索，才能确保（提高）找到合理答案的概率。
RANSAC以迭代的方式进行。在基础版本中，每个迭代包括以下五个步骤︰
( 1 )在原始数据中随机选取一个子集作为假设的内点（例如，如果根据数据拟合一条二维直线，则选择两个点)。
(2)根据假设的内点拟合一个模型（例，根据两个点拟合直线)。
( 3 )判断剩余的原始数据是否符合拟合的模型，并将其分为内点和外点。如果内点太少，则该次迭代被标记为无效并中止。
(4)根据假设的内点和上一步中划分出的内点重新拟合模型。( 5）计算所有内点的残差，根据残差和评估模型。
迭代上述步骤，把具有最小残差和的模型作为最佳模型。
RANSAC的优点是它能鲁棒的估计模型参数，它能从包含大量outlier的数据集中估计出高精度的参数。RANSAC的缺点是它计算参数的迭代次数没有上限，如果设置迭代次数的上限，得到的结果可能不是最优的结果，甚至可能得到错误的结果;RANSAC只有一定的概率得到可信的模型，概率与迭代次数成正比;RANSAC只能从特定的数据集中估计出一个模型，如果存在两个(或多个）模型，RANSAC不能找到别的模型。
解释单目VIO的初始化过程。需要估计哪些量？重力方向和尺度如何估计？
由于相机与IMU是两个不同的传感器，各自都可以进行位姿的估算，如何将两个传感器各自估算得到的位姿关联起来，是单目VIO初始化的主要目的。这个过程主要是为了求出重力方向和估计相机与IMU之间的尺度关系。我们以VINS的初始化过程为例进行介绍。
为什么单目VSLAM会有尺度漂移？如何解释这种尺度漂移？现实当中有没有解决办法？
因为对于新的图像帧，都是先计算其R,t，再利用该R,t三角化与之前图像帧匹配的点。但如果初始化时算的R,t有误差，那么三角化的三维点的深度就存在误差，也就是说其深度会存在一个缩放。后续PnP的每一帧，都会有这样的问题。如果没有回环检测，那么这个缩放的误差会一直存在并被传递与叠加，导致后面三角化的点的尺度与第一幅图的点不一致。这就是尺度漂移。
现实中可以通过添加一些先验信息，如已知长度的物体作为观测，或融合其他传感器解决。
举出几种光流方法（LK，HS等）。说明LK光流的建模方式。
光流是—种描述像素随着时间，在图像之间运动的方法。
LK光流中，即使物体发生了运动，物体上同一个点在图像中的灰度是不变的。因此可以将图像看作是时间的函数，并利用灰度不变假设:

五、C++方向

C++函数指针有哪几类？函数指针、lambda、仿函数对象分别是什么？
C++成员函数指针，静态函数指针，全局函数指针。
( 1 )函数指针︰指针指向普通的函数对象;
( 2 ) Lambda : C++11后支持的匿名函数对象，可捕获函数域外的变量;( 3 )仿函数对象︰重载了“0”运算符的类对象。
如何利用谓词对给定容器进行自定义排序？
使用标准泛型函数算法stdsort(),传入容器的begin()和end()，再传入一个可调用对象（谓词），该谓词输入两个容器的类型变量，返回一个bool值反映这两个元素的排序。
传递引用和传递值的区别？传递常引用和传递引用之间的区别？传递右值引用和传递引用之间的区别？
传引用类似于传指针，对传入对象的修改就是对原对象的修改;而传值涉及对象的拷贝。传引用只能传递某一具体对象的引用，常值引用可以传递常数(本质上是因为常引用可以引用右值)。传递右值引用涉及到对象所有权的转移，或传递临时对象。
函数对象应该通过什么传递？
如果要改变传递对象的内容，可以传引用或指针，如果不改变，传const引用或指针。
什么是万能引用？用途是什么？
万能引用是类型推导时的概念，例救auto&&即为万能引用，它会根据被引用的类型自动变为左引用和右引用类型，若在模板中则形式类似于T&&，T为类型模板参数，万能引用的本质是引用折叠，它可以简化模板函数设计，使模板函数可以同时处理左值和右值。
什么是完美转发？用途是什么？
这是一个模板概念，将模板中的万能引用T&& a通过T还原为a原本的类型，假定现在有某一对象A要通过模板函数tf(参数为万能引用)以引用的形式传入函数f中，为了保证A传入tf的引用方式与tf中A传入f的引用类型相同需要使用stdforward进行完美转发
std::unorded_map和std::map之间的差异是什么？
前者容器无序，插入或删除速度很快;后者容器内容有序，每次插入时会对容器内元素进行排序。unordere_map内部用哈希表实现，适合查找，map为红黑树实现，适合对顺序有要求的应用。
虚函数、虚表的原理？
虚函数的地址存放于虚函数表之中，而类的对象内部会有指向类内部的虚表地址的指针。运行期虚函数的多态调用会被编译器转换为对虚函数表的访问。
如何在c++中创建线程？如何在线程间同步？
最简单的方式就是直接构建一个std::thread对象。使用互斥锁，条件变量进行线程间的同步
互斥锁是什么？用途是什么？条件变量又是什么？为什么要用条件变量？
互斥量(mutex)从本质上说是一把锁，在访问共享资源前对互斥量进行加锁，在访问完成后释放互斥量上的锁。对互斥量进行加锁以后，任何其他试图再次对互斥锁加锁的线程将会阻塞直到当前线程释放该互斥锁。
条件变量(cond)是在多线程程序中用来实现"等待à唤醒"逻辑常用的方法。条件变量利用线程间共享的全局变量进行同步的一种机制。
互斥锁和条件变量所解决的，是不同的问题，不同的场景。其中条件变量必须与互斥量配合使用，它可以以无竞争的方式访问资源，即，条件变量本身会预防死锁的产生。
智能指针和祼指针之间的差异？为什么要用指针的引用计数？
智能指针可认为是裸指针的封装，其增加了引用计数的机制，会在引用计数为降为0时自动回收所指向的对象的内存。
智能指针分哪几种？std::unique_ptr, std::shared_ptr, std::weak_ptr各有何用途？
C++11标准中就这三种。
( 1 ) unique_ptr:独占语义。在任何时间点，资源只能唯一地被一个unique_ptr占有。当unique_ptr离开作用域，所包含的资源被释放。如果资源被其它资源重写了，之前拥有的资源将被释放。所以它保证了他所关联的资源总是能被释放。
( 2 ) shared_ptr:共享占有语义。shared_ptr的目标非常简单:多个共享指针可以同时指向—个对象，当最后一个shared_ptr离开作用域时，内存才会自动释放。
( 3 ) weak _ptr:共享非占有语义。通常与shared_ptr配对使用，其弱引用计数可以解决shared_ptr循环引用的问题。
悬挂指针会导致什么问题？如何避免？
使用悬挂指针的结果是未定义的，通常会导致程序崩溃。使用指针前判断是否为空，当回收指针资源时，将指针的值设为nullptr;另外使用智能指针避免这些问题。
traits是什么？什么时候用traits？
总结起来就是特性萃取，一般在两种情况下会使用。一是提升性能，利用traits将运行期判断提升到编译期;二是实现数据和通用实现的解耦合。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/905561