Direct methods for Poisson problems in low-level computer vision

Atul K. Chhabra; Timothy A. Grogan

doi:10.1117/12.21218

1 September 1990 Direct methods for Poisson problems in low-level computer vision

Atul K. Chhabra, Timothy A. Grogan

Proceedings Volume 1295, Real-Time Image Processing II; (1990) https://doi.org/10.1117/12.21218
Event: 1990 Technical Symposium on Optics, Electro-Optics, and Sensors, 1990, Orlando, FL, United States

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.

Citation Download Citation

Atul K. Chhabra and Timothy A. Grogan "Direct methods for Poisson problems in low-level computer vision", Proc. SPIE 1295, Real-Time Image Processing II, (1 September 1990); https://doi.org/10.1117/12.21218

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Computer vision technology

Machine vision

Direct methods

Reflectivity

Image restoration

Image processing

Fourier transforms

Show All Keywords

Keywords/Phrases

Search In:

Publication Years