[论文阅读]Camera Pose Voting for Large-Scale Image-Based Localization - ICCV2015
这篇在组会上展示的文章是我在会议中重点分享的内容。当时是按照论文的论述方式来进行讲解的, 但结果发现难以让听众充分理解。于是, 现在计划采用个人的理解框架来重新阐述这篇文章, 并力求以最简洁明了的语言进行阐述。同时希望通过博客平台对文章内容进行整理与反思, 从而加深对知识体系的理解。
——致我的第一次组会报告
Image-Based Localization
让我们先了解一下什么是Image-Based Localization。值得强调的是，在结构光法中使用多张图片进行重构是关键。得益于计算机视觉的进步，在此背景下出现了许多先进的算法和技术。这些算法的核心在于从大量图片中提取并融合几何信息以恢复物体表面细节信息。值得注意的是，在实际应用中通常需要较大的计算资源才能满足实时性要求。
在实际应用中最常用的两种方法分别是双准尺法和双圆锥投影法这两种方法各有其特点和适用范围。双准尺法的基本思想是在同一平面上布置两个相互正交的直线准尺然后根据它们在不同视角下的投影关系来恢复空间坐标系进而实现三维重建目标。而双圆锥投影法则利用了物体表面呈现出双圆锥形特征这一特性通过匹配圆锥顶点来确定物体的空间参数进而完成重建过程。
基于图像定位系统则通过已知场景的三维模型进行推断从而确定拍摄这幅图像的相机在三维空间中的位置与朝向这一技术已被广泛应用于无人机航拍、机器人导航以及虚拟现实等领域并取得了显著的效果
图1. Imaged-based Localization Standard Pipeline
如图所示，在右侧可见场景的点云模型的一部分区域，在左上方可观察到查询图像。基于图像定位的关键在于确定对应的相机位置与姿态（在点云中以红色圆锥体的形式标识了相机的具体位置及指向方向）。
在该定位系统中,通常需要先离线构建场景中的三维点云模型.当进行定位操作时,在查询对象上首先提取其局部特征信息.其中一种常用的方法是SIFT算法.随后需要建立图像二维特征与三维点云模型之间的对应关系.当有足够的2D-3D匹配对被采集到时,通过运用RANSAC算法以及Pnp算法可以确定相机的姿态和平移参数.
这里的核心是如何实现2D-3D匹配关系的建立。点云模型中的每一个三维数据单元通常会包含被重建出与其相关联的所有二维图像特征信息。主要通过将三维数据单元中的二维特征与相关的二维特性进行匹配来获得相应的三维与二维特征对应关系。在实际操作中涉及多种思路与策略以确保匹配效果的优化。
Voting-Based Camera Pose Estimation
After explaining the concept of image-based localization, the subsequent paragraphs will delve into the positioning strategies discussed in the paper.
图2. Voting-based Localization System Overview
本文提出了一种定位流程图，在查询图像中首先获得每个特征与多个目标之间的对应关系，并通过几何滤波方法去除大部分不正确的对应关系；继而构建Voting Shape；当存在位置先验信息（如GPS数据）时，则可进一步限制Voting Shape的空间范围。对于每一个2D-3D对应关系都能生成一个Voting Shape；类似于Hough变换的方法进行区域投票；最终票数最高的区域即被认定为真实相机的姿态；随后基于RANSAC算法优化内点坐标，并通过PnP算法计算最终的姿态参数。
Find Reliable 2D-to-single-3D Matches VS Find Extended 2D-to-many-3D Matches
在传统的2D到3D匹配方法中，在数据库中存储了大量的二维特征描述子，并为每个查询图像提取其对应的二维特征描述子。为了实现该目的，在数据库2D描述子中寻找查询图像的2D描述子的最近邻通常会检索出多个候选匹配项（nearest neighbor和second nearest neighbor），然后通过Iowe's Ratio Test来评估这些候选匹配项的质量。该测试方法在计算机视觉领域得到了广泛应用，并且具有较高的准确性。
为此, 我将此策略命名为Find Reliable 2D-to-single-3D Matches, 并解释如下: 即通过获取一组二维特征, 确定一个可靠对应点, 建立二维到三维的对应关系. 由于在随后的姿态计算中采用的是RANSAC算法来进行随机采样, 因此当内点率不足时, RANSAC采样方法难以确保得到正确的结果.
但是ratio test也存在固有的局限性，在实际应用中随着应用场景规模不断扩大时，
具体来说，
数据库中的三维点和描述子数量将急剧上升，
从而导致描述子空间中单位体积内的描述子数量也随之增加。
图3. Correct Match is Rejected when Descriptor Space is Dense
如图所示，在数据中真实对应的红色球作为查询特征（红色五角星）时，在数据库中还存在许多其他与之高度相似的特征，则单纯依赖 ratio test 仍然无法获得理想的结果（即可能无法获得任何配对结果或得到明显错误的关系配对）。
Assumptions
首先，论文做出了一些必要的假设。
- 假设1：该三维场景模型与重力轴保持一致，并将地面平面作为近似处理。
- 假设2：基于摄像头内参数校准矩阵K以及重力方向信息。
- 假设3：用于查询的相机高度与地面平面之间的距离处于特定范围内。
假设2要求不仅需知相机的内参参数（intrinsic parameters），还需获取相机方向矢量（direction vector）。同样地，在假设2中，则需先确定重力方向（gravity direction），这样才能将模型坐标系与重力方向对齐（align）。地平面高度则可通过数据库中各相机位置信息进行插值（interpolation）获得。
这篇论文中所提出的这种模型之所以具有良好的工作性能，在很大程度上主要得益于它对于场景有着较强的先验知识，并且对用于查询的相机也施加了严格的限制条件。
Reformulate the Pose Estimation Problem
有了上面的假设了之后，就可以把相机姿态估计这个问题进行简化了。
在第一步之后获得了所有特征的一对多匹配结果（后续将介绍如何具体实现这一匹配关系）
目前已经建立了大量2D-3D匹配关系，并且各3D点在空间中的位置已知。为了简化问题起见，首先考虑最简单的情况：
假设相机的高度已知为 h ，并且相机的Z轴已与重力方向一致，则问题简化为要在空间中确定相机的一个二维位置以及绕重力轴的一个旋转角度；这样便能够实现各二维与三维点之间的匹配关系。对于每一对特定的二维与三维点匹配，则可以计算出对应的三维点到相机光心的距离d；也就是该三维点到相机光心的距离d。
图4. Camera Sees the 3D Point X
如图所示，在2D特征点图像中像素坐标为(x,y)的情况下，则基于摄像机的投影关系可推导出3D点深度d的具体计算公式为d = \frac{f(X_z - H_c)}{y}。
图5. The Possible Position of the Camera (Height is Known) When it Perceives the 3D Point X
那么假设该2D至3D匹配关系准确无误地建立起来后，在此条件下相机呈现出来的匹配关系将导致其可能出现的位置限定在一个特定区域内。具体而言，在xy平面内满足条件的所有可能位置构成了一个圆形区域，并且这个圆形区域的中心点即为对应三维空间中该点在其平面内的正交投影 X' ，而其半径值则直接对应于该点到平面的距离（深度）。
那么，在任意一个2D-3D匹配的情况下，总能在平面上找到这样一个圆来表明相机可能出现在 xy 平面上。
图6. The Position of the Camera (its height is known) Upon Seeing the 3D Point X1, X2, X3
根据图示信息, 假设存在三个正确的2D-3D对应关系, 则能够推导出三个圆, 而这些圆的交点位置即代表相机的空间位置。然而, 在实际应用中由于存在大量的错误配对, 因此需要采用类似于Hough变换算法的思想, 将图像区域划分为多个子区域, 并通过统计结果表明每个子区域内对应的票数大小来确定最终的相机位置。
Accounting for uncertainty
上一节假定相机的高度是精确已知的，并将其视为一种理想化的情况。然而实际情况是相机的高度未知，在假设2中我们仅假定相机的高度位于地平面附近的某个区间内。在2D与3D对应关系中需要注意的是，在反投影过程中其结果可能会引入一定的误差。因此必须将这些不确定性因素纳入考虑范围。
图7. 2D-3D Match is Correct when Reprojection Error is within r.
首先，对于一个2D-3D匹配关系，光心、2D像点、3D点并不能同时准确地在一条直线上，考虑到一定的误差，可以认为把3D点反投影到像平面上，会和2D像点的误差在 r个像素内。反过来看，通过连接光心和像平面上以像点为圆心、 为半径的圆上的点，可以得到一个圆锥，如图中下部分所示，圆锥无限延伸下去，那么在三维空间中对应的3D点就应该会落入到这个圆锥体中，把这个圆锥体称为 error cone。
图8.Error Cone is Intersected at height Intervals [h_{min} \space \space h_{max}]
注意这里的高度是在全局坐标系下描述的。如果相机的高度准确知道，那么可以进一步，把error cone 和 相对光心的高度为 X_z - H_c（X_z是3D点的高度，即Z轴坐标, H_c是相机光心的高度） 的水平面相交，会得到一个椭圆，3D点就会在这个椭圆平面上。因为相机的高度不确定，有一个变化的区间 ，那么3D点相对于光心的高度变化范围[h_l \space \space h_u]就是[X_z-h_{max} \space \space X_z-h_{min}]，这时3D点就会落在相对光心的高度为的两个平面截取error cone 所得到的立体中。如果把此时的立体和3D点都投影到水平面上，会得到上图中蓝色梯形所示区域，3D点也应该在蓝色梯形中。把蓝色区域表示的四边形称为error shape。
图9. Convert the Error Shape from Point Position to Camera Position
由于在空间中3D点的位置已经确定好了，则将上文所述的error shape转换到相机的位置上。这样相机可能的位置就不再局限于一个圆周上了，并且应该位于一个环形区域内（Error Ring），如图10所示。这种情况下高度不再是固定的值而是被限定在一个大致的区间内
图10. Error Circle: The Potential Position of the Camera while considering Uncertainty Factors
同样地，在处理每一个2D-3-D配对关系时
图11. Voting Shapes are Intersecting in the Most Likely Camera Position
掌握了几何学的基本概念后, 下一阶段的主要工作就是确定每个环形区域的具体位置。在划分平面区域时, 为每一个细分区域投下选票, 最终通过统计各选票数量后发现得票最高的区域即为目标相机所在位置。最后通过当前定位的内部参考点执行RACSAC+PnP算法进一步优化计算结果, 得到更为精确的空间定位和姿态信息。
Efficient Voting Shape Computation
为了计算所说的圆环，在此需要将整个过程分解成若干步骤来进行操作。第一步需要在 camera 坐标系下获取图 8 中蓝色区域所代表的 Error Shape；随后通过图 9 的方法将该 Error Shape移动至 camera 的位置上；接着将其进一步移动至 global 坐标系中；最后再考虑到旋转角度的影响因素后即可获得图 10 所展示的具体 Error Ring形状。
Local Error Shape Computation
图12. Voting Shape Computation
为了计算相机坐标系中Error Shape的具体表达式，可以使用一个四边形来进行近似拟合。通过这一过程，我们可以获得该误差形状相对于光心（即相机坐标系原点）的距离参数：最小值 d_n 和最大值 d_f；同时确定平面内的左侧边界线r_l和右侧边界线r_r。
图13. The Four Extreme Ray
我们现在研究一个图像中2D特征点对应的3D空间中像平面的反投影关系，在该关系中存在4个极致位置。这些极致位置分别位于垂直与水平方向上。将光心与这些极值位置相连即可得到4条射线，在图中标记为红色（r_n）、绿色（r_f）、蓝色（r_l）和黄色（r_r）。显然，在这些极端位置上相对于原始特征平面的位置偏移量均为相同数值r。
但必须考虑相机坐标系的轴不一定与重力方向一致，在这种情况下会引入一个旋转矩阵R_g将局部相机坐标系旋转至与重力方向对齐（即轴正方向垂直于地面并指向上方）。这样一来这四个极值点的位置也会随之发生变化下面将介绍具体的求解方法
这里我们引入前面说 error cone 的表达式：
令该式中v取值为1，则获得了图13所示，在像平面内的圆形轨迹；随后分别计算坐标y、z取得极值时对应的u值；进而确定了这四个极值点相对于光心的位置偏移量；从而得出这四个极值点与光心之间的连接线；最后运用拉格朗日乘子法（如上所述）来进行求解
对于射线r_n、r_f而言，在其分别与位于z = X_z - h_{\text{max}}}及z = X_z - h_{\text{min}}}位置的水平面相交的情况下（如图12(a)所示），即可求取Error Shape至相机中心点的距离参数d_n, d_f}.
对于射线r_l，r_r，让其夹角为angular resolution(2°)的一半。
另外需要注意的是还需考虑重力方向上的不确定度 因为重力方向是由垂直消隐线计算得出的 存在一定的不确定性 论文中3.1节对此展开了深入探讨 这里从略不再赘述 如需进一步了解可参考原文相关内容
Convert Local Error Shape into Global Camera Error Shape
通过成像设备获得了误差形状表达式，并且还需将其转换到整体坐标系中。
图14. 把不确定性转化到相机的位置
对于给定的一个二维到三维匹配关系m=(x,X)而言，请注意定义M为其对应的误差形状，并令\bar{M}代表该误差形状的中心位置。通过执行[Minkowski差运算]得到相机坐标系相对于世界坐标系的平移向量t'（即点X在平面内的正交投影），其中t'被定义为X'与\bar{M}之间的差值。由此可知，在世界坐标系中对应的Global Voting Shape即为V(m)=M_C + t’。
在计算过程中考虑到旋转角的影响后，则有以下关系式成立：V(m,\phi) = R_{\phi}M_C + t'_{\phi} = R_{\phi}M_C + X' - R_{\phi}\bar{M} ，这等价于\{X' - R_{\phi}p | p \in M \} 。即图10所示区域内的蓝色圆环区域。
此外，在处理多个匹配对时，我们都会按照相同的方式构建一个Voting Shape。所有这些Voting Shape的重叠区域即为相机最可能存在的位置。因为对每个匹配对我们只需进行一次操作即可完成匹配定位任务，因此该算法具有线性时间复杂度。
至此，应该说是把文中最重要的内容给介绍清楚了。
Filtering Based On Geometry Constraints
由于每个特征都与多个目标建立一对一的对应关系，在这种情况下会产生大量的一一对应关系。然而，在这些匹配结果中绝大多数是一些内部点。通过施加几何约束条件能够有效去除外部干扰数据。在论文中详细阐述了三种基于几何的过滤方法，具体包括...
1. Relative feature orientation。提取局部特征描述子的时候，会有一个方向信息，既然已经知道了重力方向，那么就可以得到所有特征的方向相对于重力方向的夹角。对于一个3D点包含的所有2D特征，描述子相对于重力方向的夹角应该比较一致，可以利用此信息滤波一些明显错误的匹配对。
2. 3D Point Visibility from SfM Model。同样，对于一个3D点，数据库中观测到这个点的相机的位置是已知的，那么查询相机如果也能看到这个3D点，那么视角应该也保持一定的一致性。这就是图11.出现的invisible area的原因，因为可以判断这些视角是不可能观测到该3D点的。
3. Feature Scale。论文中提出了scale of 3D point 这么一个概念，其实就是用投影的三角形比例关系，由2D特征的尺度，和焦距，深度来得到一个3D点的尺度，S_{3D}=S_I *d/f，同一个3D点计算出来的S_{3D}的分布也应该是保持一致性。
4. Positional Prior。另外，如果有GPS这种先验位置的信息，可以直接限制投票区域。
论文中称这些滤波器可以滤除掉85%的初始匹配对。可见效果还是挺好的。
Experiments and Results
之前提到对特征进行一一对多匹配的方法，请问具体的实现方式是怎样的？
该文中探讨了多种方案用于在近邻搜索过程中获取多个候选样本。
1. 该比值检验法适用于1:N匹配情况，并基于N+1个近邻进行计算。
2. 固定数量的最近邻居策略。
3. 绝对阈值化方法。
4. The variable radius search adapts to varying spatial distributions.
每个策略都可搭配 back-matching 机制进行反向验证，在该2D-3D配对关系下，意味着，在查询图像的特征空间中找到与该2D特征最接近的三维对象。
图15.实验数据
实验的主要数据来源是红色框内的两个样本。SF-0被视为一个大规模的城市街景数据集。接下来让我们深入探讨一下实验结果。
图16. 滤波操作和匹配策略的实验
通过查看图表可以看出,滤波操作展现出显著的效果,尤其是在95%的精度水平上,召回率得以提升至65%,甚至更高至70%(借助GPS技术).不同匹配策略的表现存在差异,可见在策略4(即变距搜索法)中取值N=3时表现最为优异.在此基础上展开后续实验采用了该配置方案.
图17. SF-0数据集实验结果
相机最终呈现的是6自由度的姿态，在与之前方法对比中显著提升了召回率；值得注意的是，在此过程中并未改善定位性能但可获得更为精确的姿态信息
图18.Dubrovnik数据集实验结果
在小规模数据集Dubrovnik上实现了最先进水平的表现。特别是在经过Bundle Adjustment优化后将相机位置误差中值降至0.47米并取得了显著提升
Reference
Zeisl et al., 2015. Camera pose estimation is employed for large-scale image-based localization using the proposed method. The approach leverages the voting mechanism to achieve robustness in determining camera poses across extensive image datasets.