Global registration of multiple point clouds using semidefinite programming

DOI10.1137/130935458MaRDI QIDQ5252586zbMATH OpenOpenAlexFDO

Authors

Publication date 2 June 2015

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5226

zbMATH Keywords

convex relaxationspectral gapnoise stabilityexact recoveryrigidity theoryspectral relaxationsemidefinite program (SDP)global registrationrigid transforms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Semidefinite programming (90C22) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: Consider $N$ points in $mathbb{R}^d$ and $M$ local coordinate systems that are related through unknown rigid transforms. For each point we are given (possibly noisy) measurements of its local coordinates in some of the coordinate systems. Alternatively, for each coordinate system, we observe the coordinates of a subset of the points. The problem of estimating the global coordinates of the $N$ points (up to a rigid transform) from such measurements comes up in distributed approaches to molecular conformation and sensor network localization, and also in computer vision and graphics. The least-squares formulation of this problem, though non-convex, has a well known closed-form solution when $M=2$ (based on the singular value decomposition). However, no closed form solution is known for $Mgeq3$. In this paper, we demonstrate how the least-squares formulation can be relaxed into a convex program, namely a semidefinite program (SDP). By setting up connections between the uniqueness of this SDP and results from rigidity theory, we prove conditions for exact and stable recovery for the SDP relaxation. In particular, we prove that the SDP relaxation can guarantee recovery under more adversarial conditions compared to earlier proposed spectral relaxations, and derive error bounds for the registration error incurred by the SDP relaxation. We also present results of numerical experiments on simulated data to confirm the theoretical findings. We empirically demonstrate that (a) unlike the spectral relaxation, the relaxation gap is mostly zero for the semidefinite program (i.e., we are able to solve the original non-convex least-squares problem) up to a certain noise threshold, and (b) the semidefinite program performs significantly better than spectral and manifold-optimization methods, particularly at large noise levels.

Recommendations

• Stable camera motion estimation using convex programming
• Localization from incomplete noisy distance measurements
• Exact recovery with symmetries for procrustes matching
• Semidefinite Programming for Sensor Network and Graph Localization
• Globally optimal estimates for geometric reconstruction problems

Cites work

• scientific article; zbMATH DE number 2062578 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• An Interior-Point Method for Semidefinite Programming
• Angular synchronization by eigenvectors and semidefinite programming
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Block coordinate descent methods for semidefinite programming
• Characterizing generic global rigidity
• Characterizing the universal rigidity of generic frameworks
• Closest Unitary, Orthogonal and Hermitian Operators to a Given Operator
• Computing the Polar Decomposition—with Applications
• Conditions for Unique Graph Realizations
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Efficient rounding for the noncommutative Grothendieck inequality
• Eigenvector synchronization, graph rigidity and the molecule problem
• Exact and stable recovery of rotations for robust synchronization
• Exact matrix completion via convex optimization
• Geometry and convergence analysis of algorithms for registration of 3D shapes
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Localization from incomplete noisy distance measurements
• Low-rank optimization on the cone of positive semidefinite matrices
• Lx = b
• Manopt, a Matlab toolbox for optimization on manifolds
• Moment inequalities for sums of random matrices and their applications in optimization
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• New Perturbation Bounds for the Unitary Polar Factor
• On affine rigidity
• On the pseudo-inverse of the Laplacian of a bipartite graph
• Phase recovery, MaxCut and complex semidefinite programming
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Procrustes Problems
• Rigidity and energy
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• Semidefinite Programming
• Semidefinite programming for discrete optimization and matrix completion problems
• Semidefinite relaxation and nonconvex quadratic optimization
• Some Metric Inequalities in the Space of Matrices
• Spectral Properties of the Alignment Matrices in Manifold Learning
• Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
• Templates for convex cone problems with applications to sparse signal recovery
• The Geometry of Algorithms with Orthogonality Constraints
• Theory of semidefinite programming for sensor network localization
• Uniqueness of low-rank matrix completion by rigidity theory
• Universal Rigidity and Edge Sparsification for Sensor Network Localization
• Using a distributed SDP approach to solve simulated protein molecular conformation problems

Cited in

(18)

• Distributed methods for synchronization of orthogonal matrices over graphs
• Exact recovery with symmetries for procrustes matching
• The geometry of synchronization problems and learning group actions
• Orthogonal Trace-Sum Maximization: Tightness of the Semidefinite Relaxation and Guarantee of Locally Optimal Solutions
• On the tightness of semidefinite relaxations for rotation estimation
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Generalized orthogonal Procrustes problem under arbitrary adversaries
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Non-degenerate rigid alignment in a patch framework
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Gaussian Process Landmarking for Three-Dimensional Geometric Morphometrics
• Simultaneous Registration of Multiple Corresponding Point Sets
• Solving partial differential equations on manifolds from incomplete interpoint distance
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Stable camera motion estimation using convex programming
• Surface fitting and registration of point clouds using approximations of the unsigned distance function

Describes a project that uses

Uses Software

• PhaseLift
• TFOCS
• Manopt
• SNLSDP
• SDPLR
• CVX
• SDPT3

This page was built for publication: Global registration of multiple point clouds using semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5252586)