Multiview Registration Using Rank-Constrained Semide nite Programming

Abstract

We consider the problem of reconstructing a 3D surface from its multiview scans. Typically, the computational pipeline for this problem has two phases: (I) finding point-to-point correspondences between overlapping scans, and (II) registration of the scans based on the correspondences. The focus of this thesis is on phase II. In particular, we work with a global registration model, where the scans are registered in one-shot using rotations and translations. We consider a least-squares formulation of global registration, where the variables are the transforms associated with the scans. The present novelty is that we reduce this intrinsically nonconvex problem to an optimization over the positive semidefinite cone, where the objective is linear but the constraints are nevertheless nonconvex. We propose to solve this using variable splitting and the alternating direction methods of multipliers (ADMM). Due to the linear objective and the structure of constraints, the ADMM sub-problems turn out to be projections with closed-form solutions. In particular, for m scans, the per-iteration cost is the partial eigendecomposition of a 3m 3m matrix, and m����1 singular value decompositions of 3 3 matrices. We empirically show that for appropriate parameter settings, the proposed solver has a large convergence basin and is stable under perturbations. This is in keeping with recent empirical results on the effectiveness of ADMM for nonconvex problems (the convergence theory is still in its infancy though). We use the proposed ADMM algorithm to align 3D scans, where we determine the pairwise correspondences (in phase I) using the standard ICP algorithm. We present results on simulated and real datasets to demonstrate the effectiveness of our method. A remarkable feature of our method is that it can tolerate heavy amount of outliers in the correspondences. In particular, our method has better noise robustness than existing methods, where by “noise” we mean both perturbations in measurements and correspondences. An interesting open problem in this regard is establishing convergence (optimality) for the ADMM iterations; this is not covered by exisiting results.