GraphMatch: Efficient Large-Scale Graph Construction for Structure from Motion
This addresses a bottleneck in SfM pipelines for computer vision applications, though it is incremental as it builds on existing approximate methods like PatchMatch.
The paper tackles the problem of efficiently constructing matching graphs for large-scale structure-from-motion by introducing GraphMatch, which uses Fisher vector distances and graph distance priors in a sample-and-propagate scheme, resulting in finding the most image pairs while being the most efficient compared to approximate methods.
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 PatchMatch 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.