Exact Simultaneous Recovery of Locations and Structure from Known Orientations and Corrupted Point Correspondences

摘要

Let and and consider the bipartite location recovery problem: given a subset of pairwise direction observations , where a constant fraction of these observations are arbitrarily corrupted, find and up to a global translation and scale. This task arises in the Structure from Motion problem from computer vision, which consists of recovering the three-dimensional structure of a scene from photographs at unknown vantage points. We study the recently introduced ShapeFit algorithm as a method for solving this bipartite location recovery problem. In this case, ShapeFit consists of a simple convex program over real variables. We prove that this program recovers a set of i.i.d. Gaussian locations exactly and with high probability if the observations are given by a bipartite ErdAs-R,nyi graph, d is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. This recovery theorem is based on a set of deterministic conditions that we prove are sufficient for exact recovery. Finally, we propose a modified pipeline for the Structure for Motion problem, based on this bipartite location recovery problem.