3D structure recovery from a collection of 2D images is a classical problem in computer vision that requires the estimation of the camera orientations and locations, i.e. the camera motion. For large, irregular collections of images, high quality camera location estimation turns out to be a complex, ill-conditioned problem.
In our work, we firstly identify well-posed instances of the camera location estimation problem, by demonstrating its relation to the existing theory of parallel rigidity. For robust location estimation from noisy pairwise measurements, we formulate a semidefinite programming relaxation, and a second-order cone programming relaxation. We prove stable location recovery results for our methods, and also provide efficient algorithms (scalable to large image collections) to solve the resulting convex programs. Lastly, we demonstrate the utility of our formulations through experiments on Internet photo collections. This is a joint work with Amit Singer (Princeton University) and Ronen Basri (Weizmann Institute of Science).