3
CVPR 2021 | 针对全局 SfM 的高效初始位姿图生成
source link: https://mp.weixin.qq.com/s/WmGVkt3OhsKZjOulyebNtA
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
CVPR 2021 | 针对全局 SfM 的高效初始位姿图生成
Original
chaochaoSEU
计算机视觉工坊
4 days ago
收录于话题
#位姿估计
计算机视觉工坊
专注于计算机视觉、VSLAM、目标检测、语义分割、自动驾驶、深度学习、AI芯片、产品落地等技术干货及前沿paper分享。这是一个由多个大厂算法研究人员和知名高校博士创立的平台,我们坚持工坊精神,做最有价值的事~
140篇原创内容
Official Account
在匹配图像集合时,最耗时的过程通常是局部描述符匹配 [21],也就是建立暂定对应关系。原因是它具有 O(n2) 复杂度,分别与局部特征的数量(即单个图像对)和图像的数量(即整个集合)有关。我们已经解决了第二个问题(参见第 1.1 节),但是匹配单个图像对仍然需要大量时间。加速特征匹配的常用方法是使用近似最近邻搜索,而不是精确搜索,例如使用 FLANN [29] 中实现的 kd-tree 算法。然而,即使是近似匹配仍然需要相当长的时间并降低相机姿势的准确性 [21]。我们提出了一种替代解决方案——利用来自当前姿势图中的步行的姿势来建立暂定的对应关系。通过仅检查与姿势一致的对应关系,这些姿势将用于使标准描述符匹配“轻量级”。Guided feature matching with pose. 让我们假设我们有一组关键点 Ki, Kj 分别在第 i 个和第 j 个图像中,以及从第 i 个图像到第 j 个图像的相对姿态 Pij = (tij, Rij)∈SE(3)。人们可以很容易地计算出基本矩阵 Eij = [tij]×Rij,并使用它通过 Sampson 距离或对称对极误差 [19] 来测量点对的距离。因此,目标是找到点对 (pi, pj),其中 pi ∈ Ki, pj ∈Kj 和 (pi, pj,Eij) 小于内点-离群点阈值。与使用 L2 范数在所有可能关键点的高维描述符向量上定义特征匹配的传统方法相比,我们建议使用基本矩阵选择一小部分候选匹配。因此,描述符匹配变得明显更快。由于在 2D 中进行匹配,该过程可以通过散列而不是蛮力或近似成对过程来完成。使用基本矩阵,在源图像中找到可能的点对降级为在目标点中找到相应的极线投影到正确位置的点,即,到源图像中的选定点上。因此,可以根据源图像中的极线将目标图像中的点放入 bin 中。一个直接的选择是在对极线的角度上定义 bin,如图 5 所示。我们在进一步的部分中称这种技术为对极散列 (EH)。请注意,即使内在相机参数未知,EH 也适用,因此,我们只有一个基本矩阵。图5 对极哈希。图像 C2中的点 p2 被分配给 C1(灰色区域)中对应的极线 l 选择的 bin。bin 定义在 C1 中对极线的角度上。对极是 e1 和 e2。让我们将第二个图像中的点(x,y)的第一个图像中对应的上极性线l的角度表示为α(x,y)∈[0;π)。由于上极性几何学的性质,某些α(x,y)角是不可能的。因此,我们定义了由有效角组成的间隔,因此,我们将用一些箱子覆盖为[a, b]:Point (0, 0) 是第二个图像的左上角,w2 是它的宽度,h2 是它的高度。散列点时,bin 的大小将为 (b−a)/( #bins)。这是实践中的一个重要步骤,因为有时对极点远在图像之外,因此角度范围 < 1。如果没有自适应 bin 大小计算,算法在这种情况下不会加速匹配。注意 [a, b] 是 [0, π) 当对极落在图像内时。在进行传统的描述符匹配时,我们只考虑那些位于相应 bin 中且 Sampson 距离低于用于确定姿势的阈值的匹配。执行引导后,对 2 到 30 个可能的候选对象而不是所有关键点进行描述符匹配。为了进一步清理它,我们应用具有自适应比率阈值的标准 SIFT 比率测试 [25, 21],这取决于最近邻居的数量——池越小,比率测试越严格。详细信息已添加到补充材料中。如果找到一个好的位姿,则在 A* 之后应用匹配过程。由于 A∗ 需要一组对应关系来确定位姿是否合理,因此我们使用来自当前图像可见的点轨迹的对应关系。当成功匹配新图像对时,将计算并更新多视图轨迹。由于全局和增量 SfM 算法都需要点跟踪,因此此步骤不会增加最终处理时间。4. 自适应对应关系排序在本节中,我们提出了一种策略,在大规模问题中进行成对相对位姿估计时,自适应地设置 PROSAC 采样 [10] 的点对应权重。PROSAC 利用点的先验预测内点概率等级,并从最有希望的点开始采样。逐渐地,抽取不太可能导致所寻求模型的样本。所提出算法的主要思想是基于这样一个事实,即在匹配图像集合时,在一张图像中检测到并与其他图像匹配的特征经常出现多次。因此,在 PROSAC 采样中将首先使用包含较早内点点的对应关系。相反,之前图像中的异常点应该稍后绘制。假设我们得到第 t 个图像对以匹配关键点 Ki、Kj 的集合。来自任一组的每个关键点 p 的得分为 s(t)p∈ [0, 1] 用于确定其在所有关键点中的异常值等级。在成功估计图像对的姿态 Pij 后,我们得到了 (p, q) 的概率 P ((p, q) | Pij) 是给定位姿 Pij 的异常值,其中 (p,q) 是一个暂定的对应关系,p ∈Ki,q ∈Kj。概率 P ((p, q) | Pij)可以计算,例如,在 MSAC [49]、MLESAC [49] 或 MAGSAC++ [6] 中,从假设正态或 χ2 分布的点到模型残差。由于我们不知道概率 P (p| Pij) 和 P (q| Pij) 如何相关,我们假设 p 和 q 与刚性重建一致是独立事件,因此, P((p, q)| Pij) = P(p|Pij)P(q|Pij)。为了能够分解概率 P ((p, q) | Pij),我们假设 P (p|Pij)=P (q| Pij) = sqrt(P ((p, q) | Pij))。然后在第 t 个图像对匹配为 s(t+1)p= s(t)pP (p| Pij) 和 s(t+1)q = s(t)q 之后,使用此概率更新分数 sp 和 sq。让我们设置 s(0)p = 1,因为所有关键点在开始时都可能是异常值。当使用 PROSAC 采样匹配第 (t + 1) 个图像对时,对应关系根据它们的离群点等级 s(0) p 逐渐排序,使得第一个最不可能是离群点。5. 实验旋转和平移误差(以角度为单位)和处理时间(以秒为单位)的累积分布函数如图 6 所示。我们在这里不包括 MST,因为它匹配的图像对(9922)比其他方法(402)少得多 130)。在准确性方面,基于 A* 的技术导致最准确的旋转矩阵,同时具有与基于广度优先和穷举匹配相似的平移误差。在处理时间方面,所提出的基于 A* 的技术导致比 EM 或 BF 更有效的姿势图生成。请注意,处理时间曲线中的断点是由将 RANSAC 迭代的最大次数设置为 5000 引起的。这是为了避免在内点比率较低时运行 RANSAC 时间过长。图 6 在 1DSfM 数据集的所有场景上,由不同初始化技术生成的姿态图的误差(以 ee 为单位)和处理时间(以秒为单位)的累积分布函数。所有算法都返回了 402 130 个姿势。成对姿态估计算法的平均、中值和总处理时间如表 1 所示。运行时间也包含这些情况,当 A* 或广度优先遍历没有找到有效姿态时,因此, GC-RANSAC 用于恢复姿势。A* 算法导致几乎一个数量级的加速,其中值时间约为 比GC-RANSAC低20倍。它验证了所提出的启发式算法,即广度优先算法明显慢于 A*。因此,所提出的启发式方法成功地指导了姿势图中的寻路。我们比较了使用或不使用由 A* 算法确定的姿势的特征匹配速度。在 FLANN 和蛮力匹配中,这意味着我们找到了所有导致对极误差小于内部异常阈值的候选匹配。然后通过基于描述符的匹配选择最佳候选者。运行时间在表 2 中报告。使用姿势显着加快了基于 FLANN 的算法和蛮力算法。与传统的基于 FLANN 的特征匹配相比,所提出的对极散列可实现 17 倍以上的加速。此外,通过对极散列,可以精确地找到邻居,而不是像 FLANN 那样进行近似。表 4 显示了对 PROSAC 使用不同对应排序技术的稳健估计的平均、中值和总处理时间(以秒为单位)。比较了三种方法:最初为 RANSAC 提出的均匀匹配(无序);PROSAC 当对应关系根据其 SIFT 比率排序时 [10];以及考虑来自早期估计的点的先验信息而提出的自适应重新排序。与均匀采样相比,根据其 SIFT 比率对对应项进行排序将估计速度提高了 10%,而所提出的自适应重新排序导致平均额外的 8% 加速。表 3 报告了由传统详尽匹配 (EM)、广度优先图遍历 (BF)、建议的基于 A* 的图遍历和使用最小生成树 (MST) 生成的姿势图初始化的 Theia 结果。虽然基于最小生成树的姿态图的生成速度非常快,但可以看出全局 SfM 算法不足以提供合理大小的重建。由 MST 初始化时重建的平均视图数量明显低于使用其他技术。可以看出,所提出的基于 A* 的方法导致与传统方法相似的视图数量和相似的错误。在图 7 中,A*traversal 访问的平均节点数(左)和获得的准确相对姿势的比率(右)被绘制为权重 λ 的函数。不同的曲线表示不同的最大深度。6.结论与初始姿态图生成相比,全局 SfM 算法的最终集束调整的时间需求可以忽略不计。为了将这一步加快近一个数量级,我们提出了三种新算法。用于估计来自 1D SfM 数据集的所有场景的位姿图的标准程序(即,FLANN 的特征匹配;类似 RANSAC 的稳健估计的姿势估计)在单个 CPU 上总共花费了 726 487 秒——大约 202 小时。通过使用所提出的算法集(即基于 A* 的姿态估计;用于匹配的对极散列;自适应重新排序),总运行时间减少到 105593 秒(29 小时)。在实验中,A* 在 93:8% 的图像对中找到了有效位姿。因此,由 RANSAC 进行的传统基于 FLANN 的特征匹配和姿态估计仅应用于 6:2 % 的图像对。备注:作者也是我们「3D视觉从入门到精通」特邀嘉宾:一个超干货的3D视觉学习社区
原创征稿
初衷3D视觉工坊是基于优质原创文章的自媒体平台,创始人和合伙人致力于发布3D视觉领域最干货的文章,然而少数人的力量毕竟有限,知识盲区和领域漏洞依然存在。为了能够更好地展示领域知识,现向全体粉丝以及阅读者征稿,如果您的文章是3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、硬件选型、求职分享等方向,欢迎砸稿过来~文章内容可以为paper reading、资源总结、项目实战总结等形式,公众号将会对每一个投稿者提供相应的稿费,我们支持知识有价!投稿方式
邮箱:[email protected] 或者加下方的小助理微信,另请注明原创投稿。▲长按加微信联系
▲长按关注公众号
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK