  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.
