Image analysis problems, posed mathematically as variational principles or as partial differential equations, are amenable to numerical solution by relaxation algorithms that are local, iterative, and often parallel. Although they are well suited structurally for implementation on massively parallel, locally-interconnected computational architectures, such distributed algorithms are seriously handicapped by an inherent inefficiency at propagating constraints between widely separated processing elements. Hence, they converge extremely slowly when confronted by the large representations necessary for low-level vision. Application of multigrid methods can overcome this drawback, as we established in previous work on 3-D surface reconstruction. In this paper, we develop efficient multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and we evaluate the performance of these algorithms on Synthetic images. The multigrid methodology that we describe is broadly applicable in low-level vision. Notably, it is an appealing strategy to use in conjunction with regularization analysis for the efficient solution of a wide range of ill-posed visual reconstruction problems.

Computational modules early in the human vision system typically generate sparse information about the shapes of visible surfaces in the scene. Moreover, visual processes such as stereopsis can provide such information at a number of levels spanning a range of resolutions. In this paper, we extend this multi-level structure to encompass the subsequent task of reconstructing full surface descriptions from the sparse information. The mathematical development proceeds in three steps. First, the surface most consistent with the sparse constraints is characterized as the solution to an equilibrium state of a thin flexible plate. Second, local, finite element representations of surfaces are introduced and, by applying the finite element method, the continuous variational principle is transformed into a discrete problem in the form of a large system of linear algebraic equations whose solution is computable by local-support, cooperative mechanisms. Third, to exploit the information available at each level of resolution, a hierarchy of discrete problems is formulated and a highly efficient multi-level algorithm, involving both intra-level relaxation processes and bi-directional inter-level algorithm, involving both intra-level relaxation processes and bidirectional inter-level local interpolation processes is applied to their simultaneous solution.. Examples of the generation of hierarchies of surface representations from stereo constraints are given. Finally, the basic surface approximation problem is revisited in a broader mathematical context whose implications are of relevance to vision.