TY - JOUR
T1 - An analysis and implementation of multigrid poisson solvers with verified linear complexity
AU - Di Martino, J. Matías
AU - Facciolo, Gabriele
N1 - Publisher Copyright:
© 2018 IPOL & the authors.
PY - 2018/7/26
Y1 - 2018/7/26
N2 - 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.
AB - 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.
KW - Laplace equation
KW - Multigrid
KW - Poisson editing
KW - Poisson equation
UR - http://www.scopus.com/inward/record.url?scp=85055745297&partnerID=8YFLogxK
U2 - 10.5201/ipol.2018.228
DO - 10.5201/ipol.2018.228
M3 - Artículo
AN - SCOPUS:85055745297
SN - 2105-1232
VL - 8
SP - 192
EP - 218
JO - Image Processing On Line
JF - Image Processing On Line
ER -