HyperSfM

We propose a novel algorithm that solves the Structure from Motion problem in a divide and conquer manner by exploiting its bipartite graph structure. Recursive partitioning has a rich history, stemming from sparse linear algebra and finite element methods, and are also appealing for solving large-scale SfM problems. However, an important and less explored question is how to generate good partitionings for SfM that divide the problem into fully-constrained sub-problems. Here we introduce HyperSfM, a principled way to recursively divide an SfM problem using a hyper graph representation, in which finding edge separators yields the desired "nested-dissection" style tree of nonlinear sub-problems. After partitioning, a bottom-up computation pass solves the SfM problem robustly (by having fully constrained sub-problems) and efficiently (because most nonlinear error is removed at lower levels of the tree). The performance of the algorithm is demonstrated for various indoor and outdoor standard data-sets.