Solutions for simplified versions of this problem have been proposed by Sugihara for the case of polyhedra, and by Horn et al for the case of a single smooth surface patch given the surface orientation on the patch boundary. This work presents the first solution for the general case.
A variational formulation of line drawing and shading constraints in a common framework is developed. Finding the 3-D shape which best satisfies these constraints is a difficult global optimization problem. The problem is made tractable by precomputing line labels at junctions using the algorithm developed in [Malik '85]. The global constraints are partitioned into constraint sets corresponding to the faces, edges and vertices in the scene. For a face the constraints are given by Horn's image irradiance equation. We develop a variational formulation of the constraints at an edge -- both from the known direction of the image curve corresponding to the edge and shading. The associated Euler-Lagrange differential equation completely captures the local information. At a vertex, the constraints are modelled by a system of non-linear equations.
An algorithm has been developed to solve this system of constraints. We are now studying various refinements intended to make the algorithm robust in the presence of image noise.