Share Email Print

Proceedings Paper

Direct methods for Poisson problems in low-level computer vision
Author(s): Atul K. Chhabra; Timothy A. Grogan
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Several problems in low-level computer vision can be mathematically formulated as linear elliptic partial differential equations of the second order. A subset of these problems can be expressed in the form of a Poisson equation, Lu(x, y) = f(x, y). In this paper, fast direct methods for solving the Poisson equations of computer vision are developed. Until recently, iterative methods were used to solve these equations. Recently, direct Fourier techniques were suggested to speed up the computation. We present the Fourier Analysis and Cyclic Reduction (FACR) method which is faster than the Fourier method or the Cyclic Reduction method alone. For computation on an n x n grid, the operation count for the Fourier method is O(n2log2n), and that for the FACR method is O(n2log2log2n). The FACR method first reduces the system of equations into a smaller set using Cyclic Reduction. Next, the reduced system is solved by the Fourier method. The final solution is obtained by back-substituting the solution of the reduced system. With Neumann boundary conditions, a Poisson equation does not have a unique solution. We show how a physically meaningful solution can be obtained under such circumstances. Application of the FACR and other methods is discussed for two problems of low-level computer vision - lightness, or reflectance from brightness, and recovering height from surface gradient.

Paper Details

Date Published: 1 September 1990
PDF: 12 pages
Proc. SPIE 1295, Real-Time Image Processing II, (1 September 1990); doi: 10.1117/12.21218
Show Author Affiliations
Atul K. Chhabra, Univ. of Cincinnati (United States)
Timothy A. Grogan, Univ. of Cincinnati (United States)

Published in SPIE Proceedings Vol. 1295:
Real-Time Image Processing II
Richard D. Juday, Editor(s)

© SPIE. Terms of Use
Back to Top