Direct Analytical Methods for Solving Poisson Equations in Computer Vision Problems

The need to solve one or more Poisson equations of the general form: Δu=f arises in several computer vision problems such as shape from shading, lightness, and optical flow problems. The currently used methods for solving these Poisson equations are iterative. In this paper we first discuss direct analytical methods for solving these equations on a rectangular domain. We then describe some embedding techniques that may be useful when boundary conditions (obtained from stereo and occluding boundary) are defined on arbitrary contours. The suggested algorithms are computationally efficient owing to the use of fast orthogonal transforms. Applications to shape from shading, lightness, and optical flow problems are also discussed. The algorithm resulting from the direct analytical methods for the computation of optical flow is new. A proof for the existence and convergence of the flow estimates is also given. Experiments using synthetic images indicate that results comparable to multigrid can be obtained in a very small number of iterations.