We study the problem of 3D shape reconstruction from 2D landmarks extracted
in a single image. We adopt the 3D deformable shape model and formulate the
reconstruction as a joint optimization of the camera pose and the linear shape
parameters. Our first contribution is to apply Lasserre's hierarchy of convex
Sums-of-Squares (SOS) relaxations to solve the shape reconstruction problem and
show that the SOS relaxation of minimum order 2 empirically solves the original
non-convex problem exactly. Our second contribution is to exploit the structure
of the polynomial in the objective function and find a reduced set of basis
monomials for the SOS relaxation that significantly decreases the size of the
resulting semidefinite program (SDP) without compromising its accuracy. These
two contributions, to the best of our knowledge, lead to the first certifiably
optimal solver for 3D shape reconstruction, that we name Shape*. Our third
contribution is to add an outlier rejection layer to Shape* using a truncated
least squares (TLS) robust cost function and leveraging graduated non-convexity
to solve TLS without initialization. The result is a robust reconstruction
algorithm, named Shape#, that tolerates a large amount of outlier measurements.
We evaluate the performance of Shape* and Shape# in both simulated and real
experiments, showing that Shape* outperforms local optimization and previous
convex relaxation techniques, while Shape# achieves state-of-the-art
performance and is robust against 70% outliers in the FG3DCar dataset.

该研究通过采用三维可变形形状模型，将三维形状重建问题转化为相机姿态和线性形状参数的联合优化，使用 Lasserre 的 SOS 松弛层次来解决问题，并通过添加一个异常值剔除层和使用新的 TLS robust 代价函数来解决 TLS 问题，研发出一个鲁棒的三维形状重建算法 Shape#，可以容忍 70% 的异常值，达到了最先进的性能。

完美形状：从 2D 标志点中可证明的最优 3D 形状重建

In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D  Landmarks

Semidefinite Programming (SDP) and Sums-of-Squares (SOS) relaxations have led
to certifiably optimal non-minimal solvers for several robotics and computer
vision problems. However, most non-minimal solvers rely on least-squares
formulations, and, as a result, are brittle against outliers. While a standard
approach to regain robustness against outliers is to use robust cost functions,
the latter typically introduce other non-convexities, preventing the use of
existing non-minimal solvers. In this paper, we enable the simultaneous use of
non-minimal solvers and robust estimation by providing a general-purpose
approach for robust global estimation, which can be applied to any problem
where a non-minimal solver is available for the outlier-free case. To this end,
we leverage the Black-Rangarajan duality between robust estimation and outlier
processes (which has been traditionally applied to early vision problems), and
show that graduated non-convexity (GNC) can be used in conjunction with
non-minimal solvers to compute robust solutions, without requiring an initial
guess. Although GNC's global optimality cannot be guaranteed, we demonstrate
the empirical robustness of the resulting robust non-minimal solvers in
applications, including point cloud and mesh registration, pose graph
optimization, and image-based object pose estimation (also called shape
alignment). Our solvers are robust to 70-80% of outliers, outperform RANSAC,
are more accurate than specialized local solvers, and faster than specialized
global solvers. We also propose the first certifiably optimal non-minimal
solver for shape alignment using SOS relaxation.

本研究提出了一种可应用于任何非最小化求解器的鲁棒全局估计通用方法，该方法利用了鲁棒估计与异常值处理之间的 Black-Rangarajan 对偶并结合逐步非凸性与 SDP 解法求解，解决了常规稳健代价函数导致的非凸性问题；本方法应用于点云和网格登记，位姿图优化和基于图像的形状算法中，具有 70-80％异常值鲁棒性，并且比专门的局部求解器更准确和更快。