【泡泡一分钟】GraphMatch:一种应用于SFM的、高效的大规模图片构建算法（3dv-47）

会员服务 ·

【泡泡一分钟】GraphMatch:一种应用于SFM的、高效的大规模图片构建算法（3dv-47）

2018 年 2 月 26 日 泡泡机器人SLAM 泡泡一分钟

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

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

作者：Qiaodong Cui, Victor Fragoso, Chris Sweeney, Pradeep Sen

来源：3dv 2017 ( International Conference on 3D Vision）

播音员：水蘸墨

编译：杨雨生

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

摘要

作者提出的GraphMatch算法，是一种应用于大规模SFM问题的，近似但有效的图匹配算法。现在的SFM算法通常采用词汇树来快速构建匹配图，从而避免在相匹配的图片中，进行暴力搜索。与传统方法不同，GraphMatch算法不需要提前花费大量时间构建词汇树，而是通过两个先验信息来预测哪一个图片对更可能相匹配，因此使SFM的匹配过程更加高效。第一个是根据任意两幅图片的Fisher vector之间的距离计算出来的分数。第二个是基于基础匹配图（一种图结构，顶点为图像，如果两幅图像之间有足够的匹配，则之间存在一条边）的顶点之间的图像距离。GraphMatch将这样两种信息带入类似于图像块匹配算法的“采样和增殖”迭代过程。算法的采样过程利用Fisher 相似性来查找相互匹配的图片，增殖的过程中，通过搜索相匹配的图片的相邻图片，从而使新发现的图片与原来的图片具有较高的相似度。作者的试验证明，与其他的方法相比，在同样的时间内，GraphMatch能够匹配更多的图片，效率是最高的。

PS：上图中a为现在比较流行的SFM算法，通过构建词汇树，来加速图像之间匹配的速度。但是这种方法要求，需要对数据集中的很多图片的特征进行聚类，构建离线的词典。而且需要对所有的图片进行编号，也会占据比较大的内存。b 为作者提出的GraphMatch算法，与传统方法相比，不需要构建词汇树，因此节省出了离线训练的步骤。在计算图片相似度的时候，通过Fisher距离来计算图片之间的相似性。作者发现，相比于词汇树的相似度评分，这样可以查找到更好的匹配。然后算法进行“采样和增殖”迭代，在采样过程中找到合适的匹配图片后，再增殖过程中，根据当前的匹配图和相似性，查找新的匹配。

作者利用GraphMatch算法，对三个包含较多图片的数据集进行了重构，其结果如上图所示。并且重构的时间，相对于传统算法，显著减少。

Abstract

We present GraphMatch, an approximate yet efficient method for building the matching graph for large-scale structure-from-motion (SfM) pipelines. Unlike modern SfM pipelines that use vocabulary (Voc.) trees to quickly build the matching graph and avoid a costly brute-force search of matching image pairs, GraphMatch does not require an expensive offline pre-processing phase to construct a Voc. tree. Instead, GraphMatch leverages two priors that can predict which image pairs are likely to match, thereby making the matching process for SfM much more efficient. The first is a score computed from the distance between the Fisher vectors of any two images. The second prior is based on the graph distance between vertices in the underlying matching graph. GraphMatch combines these two priors into an iterative “sample-and-propagate” scheme similar to the Patch-Match algorithm. Its sampling stage uses Fisher similarity priors to guide the search for matching image pairs, while its propagation stage explores neighbors of matched pairs to find new ones with a high image similarity score. Our experiments show that GraphMatch finds the most image pairs as compared to competing, approximate methods while at the same time being the most efficient.

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

在【泡泡机器人SLAM】公众号（paopaorobot_slam）中回复关键字“3dv-47”，即可获取本文下载链接。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/forums/