| This thesis studies two inverse problems closely related two each other: The first problem is the estimation of n locations t1, t2, . . . , t n (up to global scale, translation and negation) in R d from noisy measurements of a subset of the pairwise lines that connect them, that is, from noisy measurements of +/- (ti - t j)/||ti - t j|| for some pairs (i,j), where the signs are unknown. For the second problem, we assume the availability of (measurements of) the signs, i.e., we consider the estimation of the locations ti (up to global scale and translation) from measurements of the pairwise directions (ti - tj)/||ti - tj|| for some pairs (i,j ). These inverse problems are at the core of the structure from motion (SfM) problem in computer vision, where the ti's represent camera locations in R3.;After introducing the inverse problems and providing a discussion of previous related works in Chapter 1, we continue with the characterization of well-posed problem instances in Chapter 2. The contents of Chapter 2 are based on the existing results of parallel rigidity theory, the significance of which was not previously recognized in the context of the camera location estimation problem. Basically, parallel rigidity theory studies the conditions of unique realizability of locations from exact (i.e., noiseless) pairwise lines and directions. We reiterate these results to identify a complete com- binatorial characterization of well-posed instances for the two inverse problems, and provide efficient algorithms to decide in the well-posedness of a given instance. In the absence of these conditions, we discuss how to identify maximal subsets of the pairwise measurements inducing well-posed sub-problems.;In Chapter 3, we study the inverse problem of location estimation from noisy pairwise line measurements. We firstly present a fundamental difficulty observed for the existing methods, that is, the tendency to produce spurious solutions that are clustered around a few locations. This is a well-known problem in SfM, especially for large, irregular collections of images. To overcome this difficulty, we introduce a semidefinite relaxation (SDR) method, specially tailored to exclude clustering solutions. For this formulation, we prove exact (in the noiseless case) and stable (in the presence of noisy lines) location recovery results. We also formulate an alternat- ing direction augmented Lagrangian method (ADM) to efficiently solve the resulting semidefinite program.;Chapter 4 investigates the second inverse problem, i.e. estimation of locations from noisy pairwise directions. For current methods in the literature, existence of outliers among the direction measurements typically induces large errors in the location estimates (especially for large, unordered image sets). To reduce the effect of outliers, we introduce two efficient convex programs for robust estimation of locations. As we observe in Chapter 7, compared to the existing alternatives, these methods provide highly accurate location estimates in the presence of outlier direction measurements. Provided with partially corrupted measurements (with sufficiently many noiseless directions), we empirically demonstrate that these programs can even recover the locations exactly. In Chapter 4, we also provide iteratively reweighted least squares (IRLS) solvers in order to efficiently solve these robust convex formulations.;To maintain the computational efficiency of the SDR formulation of Chapter 3 and the robust convex programs of Chapter 4 for large sets of locations, we introduce distributed formulations of these solvers in Chapter 5, based on spectral clustering and convex programming. We also show that these distributed methods induce well- posed distributed problem instances. In Chapter 6, we demonstrate how to formulate the camera location estimation problem in terms of the two inverse problems of location estimation (in R 3) from pairwise lines and directions, and also introduce a convex programming-based method to robustly estimate pairwise lines and directions. Lastly, we demonstrate the utility of our formulations through experiments on synthetic data and real images, in Chapter 7. |
