Geometric multigrid for high-order regularizations of early vision problems (Q879515)

The surface estimation problem is used as a model to demonstrate a framework for solving early vision problems by high-order regularization with natural boundary conditions. Because the application of algebraic multigrid is usually constrained by an \(M\)-matrix condition which does not hold for discretizations of high-order problems, a geometric multigrid framework is developed for the efficient solution of the associated optimality systems. It is shown that the convergence criteria of \textit{W. Hackbusch} [Iterative solution of large sparse systems of equations, Springer (1991; Zbl 0729.65018)] are met, and in particular the general elliptic regularity required is proved. Further, the Galerkin formalism is used together with a multicolored ordering of unknowns to permit vectorization of a symmetric Gauss-Seidel relaxation in image processing systems. The implementation is analyzed computationally and inaccuracies are corrected by lumping and by proper floating point representations. Direct one-dimensional calculations are used to estimate the effect of regularization order, regularization strength, relaxation, and data support on the multigrid reduction factor. A finite difference formulation is ruled out in favor of a finite element formulation. A representative problem from magnetic resonance coil sensitivity estimation is solved using increasingly higher orders of regularization, and the results are compared in terms of accuracy and multigrid convergence.