ML Anthology

An O(N) Iterative Solution to the Poisson Equation in Low-Level Vision Problems

Shang-Hong Lai, Baba C. Vemuri
CVPR 1994 pp. 9-14
doi:10.1109/CVPR.1994.323804 /cvpr/1994/lai1994cvpr-o/

Abstract

In this paper, we present a novel iterative numerical solution to the Poisson equation whose solution is needed in a variety of low-level vision problems. Our algorithm is an O(N) (N being the number of discretization points) iterative technique and does not make any assumptions on the shape of the input domain unlike the polyhedral domain assumption in the proof of convergence of multigrid techniques. We present two major results namely, a generalized version of the capacitance matrix theorem and a theorem on O(N) convergence of the alternating direction implicit method (ADI) used in our algorithm. Using this generalized theorem, we express the linear system corresponding to the discretized Poisson equation as a Lyapunov and a capacitance matrix equation. The former is solved using the ADI method while the solution to the later is obtained using a modified bi-conjugate gradient algorithm. We demonstrate the algorithm performance on synthesized data for the surface reconstruction and the SFS problems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

CVPR Semantic Scholar

Cite

Text

Lai and Vemuri. "An O(N) Iterative Solution to the Poisson Equation in Low-Level Vision Problems." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1994. doi:10.1109/CVPR.1994.323804

Markdown

[Lai and Vemuri. "An O(N) Iterative Solution to the Poisson Equation in Low-Level Vision Problems." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1994.](https://mlanthology.org/cvpr/1994/lai1994cvpr-o/) doi:10.1109/CVPR.1994.323804

BibTeX

@inproceedings{lai1994cvpr-o,
  title     = {{An O(N) Iterative Solution to the Poisson Equation in Low-Level Vision Problems}},
  author    = {Lai, Shang-Hong and Vemuri, Baba C.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1994},
  pages     = {9-14},
  doi       = {10.1109/CVPR.1994.323804},
  url       = {https://mlanthology.org/cvpr/1994/lai1994cvpr-o/}
}