A new article is available in IPOL: http://www.ipol.im/pub/art/2018/228/
Matías Di Martino, and Gabriele Facciolo,
An Analysis and Implementation of Multigrid Poisson Solvers With
Verified Linear Complexity,
Image Processing On Line, 8 (2018), pp. 192–218.
https://doi.org/10.5201/ipol.2018.228
Abstract
The Poisson equation is the most studied partial differential equation,
and it allows to formulate many useful image processing methods in an
elegant and efficient mathematical framework. Using different variations
of data terms and boundary conditions, Poisson-like problems can be
developed, e.g., for local contrast enhancement, inpainting, or image
seamless cloning among many other applications. Multigrid solvers are
among the most efficient numerical solvers for discrete Poisson-like
equations. However, their correct implementation relies on: (i) the
proper definition of the discrete problem, (ii) the right choice of
interpolation and restriction operators, and (iii) the adequate
formulation of the problem across different scales and layers. In the
present work we address these aspects, and we provide a mathematical and
practical description of multigrid methods. In addition, we present an
alternative to the extended formulation of Poisson equation proposed in
2011 by Mainberger et al. The proposed formulation of the problem suits
better multigrid methods, in particular, because it has important
mathematical properties that can be exploited to define the problem at
different scales in a intuitive and natural way. In addition, common
iterative solvers and Poisson-like problems are empirically analyzed and
compared. For example, the complexity of problems is compared when the
topology of Dirichlet boundary conditions changes in the interior of the
regular domain of the image. The main contribution of this work is the
development and detailed description of an implementation of a multigrid
numerical solver which converges in linear time.
--
IPOL - Image Processing On Line - http://ipol.im/
contact e...@ipol.im - http://www.ipol.im/meta/contact/
news+feeds twitter @IPOL_journal - http://www.ipol.im/meta/feeds/
announces annou...@list.ipol.im - http://tools.ipol.im/mm/announce/
discussions discuss@list.ipol.im - http://tools.ipol.im/mm/discuss/
--
IPOL - Image Processing On Line - http://ipol.im/
contact e...@ipol.im - http://www.ipol.im/meta/contact/
news+feeds twitter @IPOL_journal - http://www.ipol.im/meta/feeds/
announces annou...@list.ipol.im - http://tools.ipol.im/mm/announce/
discussions discuss@list.ipol.im - http://tools.ipol.im/mm/discuss/
