【泡泡一分钟】GraphMatch： SfM 系统中如何高效构建帧之间的匹配关系图（3DV-2）

每天一分钟，带你读遍机器人顶级会议文章

标题：GraphMatch: Efficient Large-Scale Graph Construction for Structure from Motion

作者：Cui Q, Fragoso V, Sweeney C, et al.

来源：3DV 2017

编译：鲁涛

播音员：刘畅

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

 

摘要

        大家好，今天为大家带来的文章是"GraphMatch: Efficient Large-Scale Graph Construction for Structure from Motion"——为大规模SfM任务高效构建图像帧之间的匹配关系图，该文章选自3DV 2017。

        本文提出了GraphMatch，可在构建大规模SfM系统（运动恢复结构）时快速寻找图片之间的匹配关系。现代的SfM系统常用词汇树来快速构建匹配图，而本文的GraphMatch利用两个先验知识来预测匹配的图像对，这样不仅省去了离线构建词汇树的开销，同时还使得SfM系统中图像匹配的步骤更加高效。其中，第一个先验是通过计算图像对之间的Fisher向量距离得到的分数，第二个先验来自于潜在的匹配图中节点之间的距离。GraphMatch把这两个先验结合到类似于PatchMatch的“采样-传递”的策略中­­­­——采样阶段，用Fisher向量距离来指导获得匹配的图像对，传递阶段通过探索匹配的图像对的相邻节点来寻找新的匹配关系。

图1. （a）是经典方法的流程图，（b）为本文思路。

  详细来说，全文共分为两个部分。

 

• 首先是预处理部分。作者提取了每张图像的SIFT特征点，并分别生成Fisher向量，然后根据这些向量为每张图片生成一个相似度列表，列表中从高到低列举了哪些图片有可能跟当前图片相似。这个列表主要是给后续的搜索提供个方向，避免盲目随机搜索。

 

• 然后是算法的主体部分，采样和传递迭代进行：

1. 在采样环节中，利用前面的列表信息，每轮迭代时，从列表中抽取固定数量的候选图片，用于测试。当然，这里会特意选取那些相邻节点数量少于特定值的节点。测试成功之后，会更新关系图和列表信息。

2. 传递环节中，作者主要是考虑，如果两个节点能匹配上的话，那么它们的相邻节点很可能也能匹配上。这一步会查询关系图中所有存在相连关系的节点。具体来说，假设节点A和B之间存在一条边，则检测A评分最高的一批相邻节点跟B是否可以相连，以此类推。

图2. 实验效果图

 

        以上，就建立了SfM系统中的图像匹配关系图。实验表明，与其余有竞争力的近似方法相比，GraphMatch 找出了最多的匹配图像对，同时也是最高效的。 

        今天的泡泡一分钟就到这里了，如果你觉得有收获，欢迎转发到朋友圈，让更多人一起学习机器人顶级会议文章。

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号。

回复关键字“GraphMatch”，即可获取本文下载链接。

---

泡泡机器人SLAM的原创内容均由泡泡机器人的成员花费大量心血制作而成，希望大家珍惜我们的劳动成果，转载请务必注明出自【泡泡机器人SLAM】微信公众号，否则侵权必究！同时，我们也欢迎各位转载到自己的朋友圈，让更多的人能进入到SLAM这个领域中，让我们共同为推进中国的SLAM事业而努力！

商业合作及转载请联系liufuqiang_robot@hotmail.com