We propose a novel multi-grid method for solving total variation models. This type of models arises frequently in image processing tasks such as de-noising and segmentation. It is usually proposed as minimizing a nonlinear functional containing a total variation term, and the computational domain is either rectangle in 2D or rectangular cuboid in 3D. A usual multi-level decomposition of the domain is performed over the whole domain. The resulted subdomains are marked by four colors (in 2D case) in the interlacing formation, such that subdomains of the same color are non-overlapping. At each level, the solution for the minimizer of the nonlinear functional is updated in parallel on the subdomains of the same color, while the solution on each subdomain is updated by the same constant. This process is carried out in a Gauss-Seidel manner over the four colors for a few iterations. Unlike the usually multi-grid method that loops over all levels in V-cycle or W-cycles, the proposed approach sequentially updates the solution from coarsest level to finest, and repeat the procedure until convergence. The numerical tests demonstrate the linear scalability of the proposed algorithm and shows a potential for improvement in parallel computing.

This presentation is part of Minisymposium “MS49 - Image Restoration, Enhancement and Related Algorithms (4 parts)”
organized by: Weihong Guo (Case Western Reserve University) , Ke Chen (University of Liverpool) , Xue-Cheng Tai (Hong Kong Baptist University) , Guohui Song (Clarkson University) .

Authors:

Ke Yin (Huazhong Univeristy of Science and Technology)

Keywords:

computer vision, image representation, nonlinear optimization, partial differential equation models