Abstract
Input: A query image
Source: A point cloud reconstruction of a large scene (有一百多万3D点)
Result：pose
关键：an efficient and effective search method to establish matches between image features and scene points needed for pose estimation.
一个动态搜多额外匹配的框架，基于2D-to-3D and 3D-to-2D search.
一种采用两种方向优势，同时避免劣势的方法。
我们的方案有最好的registration表现，并且run-times和最快的方案媲美。
1. Introduction
如果需要更高的定位精度，一个3D point cloud is a more scene representation.
Using correspondences between 2D image features and 3D scene point, the full camera pose can be estimated with high precision.
在这个文章里，我们用离线的SfM获得的3D点云来表示一个场景。（对比我的，we represent a scene as a 3D point cloud obtained from an online Multi-view Stereo reconstruction），每一个3D点和一个描述子关联。
挑战的关键是在thousands of 2D query image features和百万的3D scene point之前建立关联。
然后可以用RANSAC来估计位姿，RANSAC的迭代次数和找到的匹配质量相关。
[11] 提出了一种简单的，tree-based approximate search，来获得不错的注册表现。但是，这种方案需要几秒来做一个搜寻。
我们提出一种和[11]的tree-based方案差不多表现的，但是is still one order of magnitude faster（快一个量级的）。而它的核心就是通过建立2D-to-3D correspondences来出发3D-to-2D匹配。
Related Work：。。。
2. The Image-Based Localization Problem
如上图所示，因为点云是SfM出的，所以每个点至少有两个SIFT描述子。
2D-to-3D vs. 3D-to-2D search 因为图像比点云有几个量级少的特征点 (an image contains several orders of magnitude fewer features than there are points in the model), 所以：
让match a single point against the features（3D-to-2D）是更有效的。
但是更慢的2D-to-3D有更高质量的匹配（？？？因为candidates更多，要经过ratio test就更难。如果有几个点都跟这个feature很接近，ratio test会拒绝ambiguous的feature）。In return,denser descriptor space也更有可能拒绝正确的匹配。
我们有一个组合两个策略优势的策略。
Prioritized Search 如果只考虑给部分的 特征/点做匹配就会更高效。这就需要一个prioritization scheme来先衡量最有希望的 特征/点。
对于3D-to-2D匹配，Li提供了一个只基于3D点的co-visiblity的优化方案。当一个点\(p\)的匹配被建立了，那么所有其他和\(p\)一同被看见的优先级就提升了。（这也make sense）。
对于2D-to-3D匹配，Sattler提供了一个只基于外观的方案 【11】.他们同时把点和特征assign给一组视觉单词（visual words）。因为处理一个特征的算力是基于 计算描述子距离来找到最近邻。这个计算数量和被assign给特征的visual word的点数量成比例。然后特征就会以一个逐渐需要更多算例的顺序来进行处理，因为会更偏向更具有外观区分度，只有更少数几个点能配上的特征。
我们会提出一种基于【11】然后基于外观和共视来排优先级的策略,它exploit 2D-to-3D and 3D-to-2D的the intrinsic similarity。
Bridging the Performance Gap ...
3. Active Correspondence Search
地图点会在一个离线的阶段被assign给visual words。
给定一张query图，它的SIFT特征会被映射到一个vocabulary。这样得到：每一个特征有一列表的候选点，然后特征们会以他们的列表的增序考虑。
对于每一个特征 \(f\),我们搜寻在这个word里所有的点，然后找到最近的两个邻居。两个点\(p_1, p_2\). 如果满足SIFT ratio test： $||f-p_1||_2 / ||f-p_2||_2 < 0.7 \(,那么一个匹配\)(f,p_1,||f-p_1||_2)$就建立了.
Active Correspondence Search
使用visual vocabulary诱导（induce）了数量效应（quantization effect)，限制了能被找到的匹配数。一个解决这个效应的简单方法是用软关联，把一个feature映射到多个visual words。我们用了active correspondence search —— 一个更高效的hierarchical approach。
当一个2D-to-3D匹配（\(f\)和\(p\))被找到，有很高的几率说在3D点\(p\)周围的区域的点也可以被query image看到。但是方案【11】就忽略了这个信息，继续做2D-to-3D的匹配。
而我们会动态的在\(p\)附近空间的点\(N_{3D}\)来找匹配。每一个这样的点\(p'\)会被插入到优先方案里，如果它被激活了（轮到处理它的意思？），我们就会在图像特征中寻找3D-to-2D的匹配。这组近似的特征可以再用visual vocabulary来identified。
因为我们需要一个更精细的vocabulary用于2D-to-3D匹配来限制搜索空间，我们需要一个更粗的vocabulary用于3D-to-2D搜索阶段来保证有足够的特征被考虑。
一个关键的观察是，一个coarser vocabulary可以通过使用vocabulary tree而不用任何的额外计算。
使用数中更粗糙的level的额外的好处就是可以恢复因为quantization effect导致的匹配。
注意active search只由2D-to-3D匹配而非3D-to-2D匹配。
Prioritization
高效的匹配搜索的关键就是优先次序（prioritization)。在我们的框架中，任何方向的匹配搜索都是找到在visual word存储的最近的两个neighbors。
在【11】中，优先次序的框架是基于找到最近邻的比较次数。。（blah blah，等看了【11】应该能懂。）我们是找到N个匹配之后中断搜索的。剩下的问题是，什么时候进行active search，是prefer基于appearance(2D-to-3D)还是covisibility(3D-to-2D)的信息。
- 当covisibility更重要，只要一个2D-to-3D匹配被找到了，direct prioritization strategy就可以执行active search。当\(N_{3D}\)的对于feature的匹配被昨晚，就可以恢复2D-to-3D匹配的行动。这个就会导致匹配只会蜷缩在图像中很小的区域，导致位姿的计算不稳定。
- 当appearance更被偏爱时，2D-to-3D匹配会率先被执行，然后执行active search和3D-to-2D匹配。这样的话可能只会从active search收益甚微。
所以我们提出了一种均衡两种方向的策略。当一个新的匹配被找到时，就会执行active search。然后用预测的搜寻cost来sort them into a common prioritization scheme for both directions。这个策略对于两种信息都平等对待，总会倾向更容易evaluate的那一侧。
Computational Complexity
给定一个点云有\(P\)个点，和一个vocabulary的大小是\(W\)，这样的花，一个单词的平均点数量就是\(P/W\)。如果考虑\(C+1\)个单词的话，那么一个特征的搜索cost是\(c\times P/W\). 这样的话，一个有\(F\)个特征的图的计算就是\(\mathcal{O}\left(c \cdot F \frac{P}{W}\right)\)。
相比较而言，active search最多会被触发\(N\)次.用kd-tree的话,\(N_{3D}\)个最个最近的点可以用\(\mathcal{O} \left(N_{3D} \log_2(P) \right)\)的时间. 使用一个更粗的vocabulary(size \(W\)), 这样的话,一个点会对应\(\frac{F}{W'}\)个特征. 因为\(N\)和\(N_{3D}\)是常量, active search的额外计算量是\(\mathcal{O} \left( \log_2(P) \frac{F}{W'} \right)\).
Comparison with Existing Methods
跟[11]比较的话,我们的方案能够恢复因为精细的单词表而丢失的匹配. 在Sec.6中体现了这些匹配的关键.
跟[10]比的话, 我们的active search是基于2D-to-3D的,会比基于3D-to-2D匹配的更可靠. 让我们的方案得到更好的表现,也更高效.
active search甚至比tree-based search好, 因为描述子空间的密度和3D点的个数相关, 而ratio test会移除很多正确的匹配(对于大的数据集而言).
4. Efficient Implementation
一个精细的视觉vocabulary, 有着100k个单词来用于2D-to-3D的匹配. 用[15]的approximate k-means来基于SIFT生成. 基于这个vocabulary,我们生成一个vocabuary tree(with branching factor 10).
Active search被包含在[11]里的2D-to-3D pipeline.
在找到\(N=100\)个匹配后, 我们用RANSAC-variant [22]来用6点DLT算法[16].
因为每一个点在重建的时候都是多帧观测的,所以一个候选点\(p'\)在3D-to-2D匹配的时候,都会有多个描述子\(D(p')\)存储在fine vocabulary不同的单词中. 定义了一组\(AW\)被在层级 \(l\) 被激活的视觉单词. 我们找到在\(AW\)所覆盖下和\(D(p')\)有最近距离的两个特征\(f_1, f_2\).
然后在Alg. 1中的两个for循环确认\(p'\)的搜寻cost. 我们要求\(f_1, f_2\)两个特征是有区分度的. 为了考虑3D-to-2D匹配的不确定性,3D-to-2D匹配不能代替2D-to-3D匹配. 被3D-to-2D匹配找到的特征,就不会再被考虑进2D-to-3D匹配.
层级 \(l\) 的选择直接控制了被分配的图像特征的个数和一个候选点\(p'\)的search cost. 因为一个query图一般有1k-20k个特征点(取决于它的精度),我们再有5k个特征的时候用level 2(100 words), 其他情况用level 3 (1000 words). 这样的话, 平均一个单词有5-50个特征. \(p'\)的search cost可以认为是常量.
5. Incorporating Additional Visibility Information
尽管比soft matching更高效, active search也需要额外的计算量. 在这个框架, 我们会讲如何加速定位的pipeline来补偿run-time increase.
这个提升在重建估计的时候图像用的观测,它近似于the set of viewpoints from which a point is visible. 它能够加速3D-to-2D匹配和RANSAC-based位姿估计(通过滤除不可能见到的地点). 因为approximative nature, 这个filter也会滤除正确的点. 我们提出一个简单的策略来恢复失去的表现.
这个滤除阶段可以表现为一个二分图(bipartite graph) \(G\), 由相机和3D点定义.
Filtering 3D points
3D空间中距离近(close proximity in 3D space)并不代表两点的co-visibiliy. 他们可能如图4.a一样是从不一样的位置被观测. 我们的point filter移除所有的在$ N_{3D}\(个最近邻点中不能直接观测(not directly visible)的点\)p$. 只有两个edge远的点才能被用作3D-to-2D匹配.
A RANSAC Pre-Filter (需要review)
如图4.c所示, 建立的匹配定义了子图(subgraph) \(G_c\) of \(G\). 我们的RANSAC pre-filter 在\(G_c\)中找到包含最后的3D点并且只能够连接到这个组成的组成. 这个加速了基于RANSAC的位姿估计算法, 因为外点被移除了. 注意这个filter对3D-to-2D匹配有一些影响,因为在一个错误的2D-to-3D匹配不太可能能找到further匹配.
Using Camera Sets (需要review)
这个filtering步骤可能太aggresive了. 如图b中的绿点. 通过融合相机, 我们希望找到更好的,更连续的点共视的估计. 对于每一张图\(I_j\), 我们定义类似图集 \(sim(I_j)\)为 \(k\) 个最近相机别切视角的差距和 \(I_j\)最多差\(60\)°. 这个集合包含问题(set cover problem)是用一个Greedy algorithm来解决的[10].
6. Experimental Evaluation
所有的query图的最大边上是1600个像素. 我们认为一个图如果最好的inlier数大于12,则被registered了.
Evaluation of Active Search
图5画了registered图的平均数和平均registration时间.
直接法的策略最先考虑visibility information,有最好的registration表现. 但是很容易找到匹配都集中在录像的一块, 导致不好的位姿精度.如table 2所示. 而我们的方案不会因为registration的表现而放弃定位精度.
Faster Registration using Filtering
尽管这个paper的专注点在registration表现, 我们还是对越快越好的定位方案感兴趣. point filter和RANSAC pre-filter也是为此设计的.
如预期的, 用filter会少量减少平均的registration表现. 我们发现filter对于不同数据集的表现不同.
RANSAC pre-filter对Vienna的影响最大, 因为它在数据集中有最少的描述子. 2D-to-3D的匹配更有可能找到错配. 既然错配是在整个模型中分布的, RANSAC pre-fitler可以移除他们中的大部分.
相对而言, filter们对于Rome的影响最小. 它有不同的landmark的重建, 有很多相似的视角. 这就会影响RANSAC pre-filter的效率. 而且, 更稠密的描述子空间让pre-filter很难移除错配.
Using Camera Sets
Comparison with State-of-the-Art
Table 3比较了我们的方案(\(N_{3D} =200, k = 10\))和其他方案.
\(P2F\) 表示3D-to-2D matching by Li.
\(P2F +F2P\) 会做2D-to-3D匹配,如果\(P2F\)失败了.
7. Conclusion & Future Work
组合2D-to-3D和3D-to-2D方案最好. 比tree-based方案快一个量级.