An Optimal Control Formulation and Related Numerical Methods for a Problem in Shape Reconstruction

The main problem considered in this paper is the construction of numerical methods and proofs of their convergence for the problem of "shape from shading." In the first part of the paper, it is assumed that the height function that describes the surface to be reconstructed is known at all local minima (or maxima). These points are a subset of the singular points, which are the brightest points in the image. A pair of optimal control problems are defined that provide representations for the height function. Numerical schemes based on these representations are then constructed. While both schemes lead to the same approximation, one yields a more efficient algorithm, while the other is more convenient in the convergence analysis. The proof of convergence is based on a representation of the approximation to the height as a functional of a controlled Markov chain. In a later part of the paper the assumption that the height must be known at all local minima (or maxima) is dropped. An extension of the algorithm is described that is capable of reconstruction without this information. Numerical experiments for both algorithms on synthetic and real data are included.