...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Image Processing On Line >An Analysis and Implementation of Multigrid Poisson Solvers With Verified Linear Complexity
【24h】

An Analysis and Implementation of Multigrid Poisson Solvers With Verified Linear Complexity

机译：验证线性复杂度的多重网格泊松求解器的分析和实现

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：泊松方程是研究最多的偏微分方程，它允许在一个优雅而有效的数学框架中公式化许多有用的图像处理方法。使用数据项和边界条件的不同变化，可以开发类似泊松的问题，例如，在许多其他应用程序中用于局部对比度增强，修复或图像无缝克隆。对于离散型泊松方程，多重网格求解器是最有效的数值求解器。但是，它们的正确实现依赖于：（i）离散问题的正确定义，（ii）插值和限制算子的正确选择，以及（iii）在不同规模和层级上对问题的适当表述。在本工作中，我们着眼于这些方面，并提供了多网格方法的数学和实践描述。此外，我们提出了Mainberger等人在2011年提出的泊松方程扩展公式的替代方案。提出的问题表述特别适合于更好的多网格方法，因为它具有重要的数学特性，可以利用这些数学特性以直观自然的方式在不同范围内定义问题。另外，经验地分析和比较了常见的迭代求解器和类泊松问题。例如，当Dirichlet边界条件的拓扑在图像的规则域内部变化时，比较了问题的复杂性。这项工作的主要贡献是开发和详细描述了在线性时间收敛的多网格数值求解器的实现。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号