1. Introduction
The shape from shading (SFS) problem [12], [26] is to recover the 3D shape of a surface from a single image, whose intensities are related to angles between surface normals and light source direction. SFS belongs to a wide class of problems in computer vision that involve embedding points in Euclidean space based on angles or distances information. These problems have natural formulations as systems of polynomial equations. Both exact methods, such as Gröbner basis and homotopy continuation, and convex relaxation techniques, have been applied to polynomial systems arising from diverse problems as structure from motion [5], [15], [24], camera calibration [7] and low-dimensional embedding [29], [38]. In this paper we apply similar techniques to the SFS problem, which traditionally was treated mostly as a general nonlinear PDE that is notoriously difficult to optimize. While the polynomial formulation is not new (e.g. [25]), only recently theory and software for polynomial systems became widely available.