Robust Synchronization and its Applications in 3D Computer Vision

University of Minnesota Ph.D. dissertation. August 2020. Major: Mathematics. Advisor: Gilad Lerman. 1 computer file (PDF); xv, 198 pages.This dissertation includes five works of my Ph.D. research. It starts with an introduction to 3D reconstruction and its associated synchronization problems, followed by the robust synchronization algorithms and their theoretical guarantees. Common 3D reconstruction tasks rely on accurate estimation of camera rotations and locations. These estimation problems are often solved by using graph optimization methods and can be mathematically formulated as synchronization problems. The synchronization problems ask to find the absolute states (e.g. rotations, locations) of graph nodes from the given noisy and corrupted relative states among pairs of nodes. The most common synchronization problem is group synchronization, where the states of nodes are elements of certain mathematical group. It asks to find the underlying group elements (e.g. absolute rotations) for each node from the given noisy and corrupted group ratios (e.g. relative rotations) among pairs of nodes. HASH(0x40ca7b0) In order to solve this problem, we first propose cycle-edge message passing (CEMP) framework that estimates the corruption levels of group ratios for any compact group. We establish the exact recovery and linear convergence guarantees with adversarial corruption and its stability to sub-Gaussian noise. We further show that under a uniform corruption model, the recovery results are sharp in terms of an information-theoretic bound. HASH(0x40c9e18) We next extend the idea of CEMP and develop message passing least squares (MPLS) framework for directly solving group elements under both high corruption and noise. We carefully refine the framework for specific applications of rotation and permutation synchronization in 3D computer vision. Both applications demonstrate the superior performance of MPLS over the state-of-the-art methods. HASH(0x40cb050) Finally, we discuss camera location estimation problem which can be viewed as a variant of group synchronization problem on the noncompact group R^3. We present and prove an exact recovery theory for the state-of-the-art least unsquared deviations (LUD) solver under adversarial corruption. We then develop the all-about-that-base (AAB) preprocessing step for detecting corrupted edges. We demonstrate that the application of AAB significantly improves the performance of common camera location solvers on both synthetic and real data