A robust multigrid approach for variational image registration models

Variational registration models are non-rigid and deformable imaging techniques for accurate registration of two images. As with other models for inverse problems using the Tikhonov regularization, they must have a suitably chosen regularization term as well as a data fitting term. One distinct feature of registration models is that their fitting term is always highly nonlinear and this nonlinearity restricts the class of numerical methods that are applicable. This paper first reviews the current state-of-the-art numerical methods for such models and observes that the nonlinear fitting term is mostly ‘avoided’ in developing fast multigrid methods. It then proposes a unified approach for designing fixed point type smoothers for multigrid methods. The diffusion registration model (second-order equations) and a curvature model (fourth-order equations) are used to illustrate our robust methodology. Analysis of the proposed smoothers and comparisons to other methods are given. As expected of a multigrid method, being many orders of magnitude faster than the unilevel gradient descent approach, the proposed numerical approach delivers fast and accurate results for a range of synthetic and real test images.     

Homotopy method for a mean curvature-based denoising model

Variational image denoising models based on regularization of gradients have been extensively studied. The total variation model by Rudin, Osher, and Fatemi (1992) [38] can preserve edges well but for images without edges (jumps), the solution to this model has the undesirable staircasing effect. To overcome this, mean curvature-based energy minimization models offer one approach for restoring both smooth (no edges) and nonsmooth (with edges) images. As such models lead to fourth order (instead of the usual second order) nonlinear partial differential equations, development of fast solvers is a challenging task. Previously stabilized fixed point methods and their associated multigrid methods were developed but the underlying operators must be regularized by a relatively large parameter. In this paper, we first present a fixed point curvature method for solving such equations and then propose a homotopy approach for varying the regularized parameter so that the Newton type method becomes applicable in a predictor-corrector framework. Numerical experiments show that both of our methods are able to maintain all important information in the image, and at the same time to filter out noise.     

Multigrid second-order accurate solution of parabolic control-constrained problems

A mesh-independent and second-order accurate multigrid strategy to solve control-constrained parabolic optimal control problems is presented. The resulting algorithms appear to be robust with respect to change of values of the control parameters and have the ability to accommodate constraints on the control also in the limit case of bang-bang control. Central to the development of these multigrid schemes is the design of iterative smoothers which can be formulated as local semismooth Newton methods. The design of distributed controls is considered to drive nonlinear parabolic models to follow optimally a given trajectory or attain a final configuration. In both cases, results of numerical experiments and theoretical twogrid local Fourier analysis estimates demonstrate that the proposed schemes are able to solve parabolic optimality systems with textbook multigrid efficiency. Further results are presented to validate second-order accuracy and the possibility to track a trajectory over long time intervals by means of a receding-horizon approach.     

A full multigrid method for semilinear elliptic equation

A full multigrid finite element method is proposed for semilinear elliptic equations. The main idea is to transform the solution of the semilinear problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and semilinear problems on a very low dimensional space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient numerical methods can also serve as the linear solver for solving boundary value problems. The optimality of the computational work is also proved. Compared with the existing multigrid methods which need the bounded second order derivatives of the nonlinear term, the proposed method only needs the Lipschitz continuation in some sense of the nonlinear term.     

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.     

A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems

Summary In this paper we study a multi-grid method for the numerical solution of nonlinear systems of equations arising from the discretization of ill-posed problems, where the special eigensystem structure of the underlying operator equation makes it necessary to use special smoothers. We provide uniform contraction factor estimates and show that a nested multigrid iteration together with an a priori or a posteriori chosen stopping index defines a regularization method for the ill-posed problem, i.e., a stable solution method, that converges to an exact solution of the underlying infinite-dimensional problem as the data noise level goes to zero, with optimal rates under additional regularity conditions. Supported by the Fonds zur F?rderung der wissenschaftlichen Forschung under grant T 7-TEC and project F1308 within Spezialforschungsbereich 13     

Adaptive Segmentation Model for Images with Intensity Inhomogeneity based on Local Neighborhood Contrast

Segmentation of images with intensity inhomogeneity is a significant task in the field of image processing, especially in medical image processing and analysis. Some local region-based models work well on handling intensity inhomogeneity, but they are always sensitive to contour initialization and high noise. In this paper, we present an adaptive segmentation model for images with intensity inhomogeneity in the form of partial differential equation. Firstly, a global intensity fitting term and a local intensity fitting term are constructed by employing the global and local image information, respectively. Secondly, a tradeoff function is defined to adjust adaptively the weight between two fitting terms, which is based on the neighborhood contrast of image pixel. Finally, a weighted regularization term related to local entropy is used to ensure the smoothness of evolution curve. Meanwhile, a distance regularization term is added for stable level set evolution. Experimental results show that the proposed model without initial contour can segment inhomogeneous images stably and effectively, which thereby avoiding the influence of contour initialization on segmentation results. Besides, the proposed model works better on noise images comparing with two relevant segmentation models.     

Multigrid method for solving convection-diffusion problems with dominant convection

A modification of the multigrid method for the solution of linear algebraic equation systems with a strongly nonsymmetric matrix obtained after difference approximation of the convection-diffusion equation with dominant convection is proposed. Specially created triangular iterative methods have been used as the smoothers of the multigrid method. Some theoretical and numerical results are presented.     

Local Fourier analysis for multigrid with overlapping smoothers applied to systems of PDEs

Since their popularization in the late 1970s and early 1980s, multigrid methods have been a central tool in the numerical solution of the linear and nonlinear systems that arise from the discretization of many PDEs. In this paper, we present a local Fourier analysis (LFA, or local mode analysis) framework for analyzing the complementarity between relaxation and coarse‐grid correction within multigrid solvers for systems of PDEs. Important features of this analysis framework include the treatment of arbitrary finite‐element approximation subspaces, leading to discretizations with staggered grids, and overlapping multiplicative Schwarz smoothers. The resulting tools are demonstrated for the Stokes, curl–curl, and grad–div equations. Copyright © 2011 John Wiley & Sons, Ltd.     

Increasing Accuracy and Efficiency for Regularized Navier-Stokes Equations

In this article, a finite element scheme for the family of time relaxation models, that represent a regularization of Navier-Stokes equations, is developed, analyzed and numerically tested. The proposed finite element scheme combines three ideas: (i) the use of an incompressible filter, for better consistency outside the periodic domains, (ii) a second order accurate linearization for the nonlinear term, that allows to solve only one linear system per time step, and (iii) a stabilization in time term that compliments well the linearization. A complete numerical analysis of the scheme, that includes the computability of its numerical solutions, its stability, and velocity error estimates, is given. This is followed by numerical experiments that confirm the theoretical convergence rates and show the advantage of the proposed scheme.     

A Crank-Nicolson scheme for the Landau-Lifshitz equation without damping

An accurate and efficient numerical approach, based on a finite difference method with Crank-Nicolson time stepping, is proposed for the Landau-Lifshitz equation without damping. The phenomenological Landau-Lifshitz equation describes the dynamics of ferromagnetism. The Crank-Nicolson method is very popular in the numerical schemes for parabolic equations since it is second-order accurate in time. Although widely used, the method does not always produce accurate results when it is applied to the Landau-Lifshitz equation. The objective of this article is to enumerate the problems and then to propose an accurate and robust numerical solution algorithm. A discrete scheme and a numerical solution algorithm for the Landau-Lifshitz equation are described. A nonlinear multigrid method is used for handling the nonlinearities of the resulting discrete system of equations at each time step. We show numerically that the proposed scheme has a second-order convergence in space and time.     

Convergence analysis of HSS-multigrid methods for second-order nonselfadjoint elliptic problems

In this paper, the multigrid methods using Hermitian/skew-Hermitian splitting (HSS) iteration as smoothers are investigated. These smoothers also include the modified additive and multiplicative smoothers which result from subspace decomposition. Without full elliptic regularity assumption, it is shown that the multigrid methods with these smoothers converge uniformly for second-order nonselfadjoint elliptic boundary value problems if the mesh size of the coarsest grid is sufficiently small (but independent of the number of the multigrid levels). Numerical results are reported to confirm the theoretical analysis.     

On constrained Newton linearization and multigrid for variational inequalities

Summary. We consider the fast solution of a class of large, piecewise smooth minimization problems. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with constrained Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give polylogarithmic upper bounds for the asymptotic convergence rates. Efficiency is illustrated by numerical experiments. Received March 22, 1999 / Revised version received February 24, 2001 / Published online October 17, 2001     

MgNet: A unified framework of multigrid and convolutional neural network

We develop a unified model, known as MgNet, that simultaneously recovers some convolutional neural networks(CNN) for image classification and multigrid(MG) methods for solving discretized partial differential equations(PDEs). This model is based on close connections that we have observed and uncovered between the CNN and MG methodologies. For example, pooling operation and feature extraction in CNN correspond directly to restriction operation and iterative smoothers in MG, respectively. As the solution space is often the dual of the data space in PDEs, the analogous concept of feature space and data space(which are dual to each other) is introduced in CNN. With such connections and new concept in the unified model, the function of various convolution operations and pooling used in CNN can be better understood. As a result,modified CNN models(with fewer weights and hyperparameters) are developed that exhibit competitive and sometimes better performance in comparison with existing CNN models when applied to both CIFAR-10 and CIFAR-100 data sets.     

An Iterative Multigrid Regularization Method for Toeplitz Discrete Ill-Posed Problems

Iterative regularization multigrid methods have been successfully applied to signal/image deblurring problems. When zero-Dirichlet boundary conditions are imposed the deblurring matrix has a Toeplitz structure and it is potentially full. A crucial task of a multilevel strategy is to preserve the Toeplitz structure at the coarse levels which can be exploited to obtain fast computations. The smoother has to be an iterative regularization method. The grid transfer operator should preserve the regularization property of the smoother. This paper improves the iterative multigrid method proposed in [11] introducing a wavelet soft-thresholding denoising post-smoother. Such post-smoother avoids the noise amplification that is the cause of the semi-convergence of iterative regularization methods and reduces ringing effects. The resulting iterative multigrid regularization method stabilizes the iterations so that the imprecise (over) estimate of the stopping iteration does not have a deleterious effect on the computed solution. Numerical examples of signal and image deblurring problems confirm the effectiveness of the proposed method.     

Newton-Multigrid for Biological Reaction-Diffusion Problems with Random Coefficients

An algebraic Newton-multigrid method is proposed in order to efficiently solve systems of nonlinear reaction-diffusion problems with stochastic coefficients. These problems model the conversion of starch into sugars in growing apples. The stochastic system is first converted into a large coupled system of deterministic equations by applying a stochastic Galerkin finite element discretization. This method leads to high-order accurate stochastic solutions. A stable and high-order time discretization is obtained by applying a fully implicit Runge-Kutta method. After Newton linearization, a point-based algebraic multigrid solution method is applied. In order to decrease the computational cost, alternative multigrid preconditioners are presented. Numerical results demonstrate the convergence properties, robustness and efficiency of the proposed multigrid methods.     

Improved variational image registration model and a fast algorithm for its numerical approximation

In a multimodal image registration scenario, where two given images have similar features, but noncomparable intensity variations, the sum of squared differences is not suitable for inferring image similarities. In this article, we first propose a new variational model based on combining intensity and geometric transformations, as an alternative to use mutual information and an improvement to the work by Modersitzki and Wirtz (Modersitzki and Wirtz, Lect Notes Comput Sci 4057 (2006), 257–263), and then develop a fast multigrid (MG) algorithm for solving the underlying system of fourth‐order and nonlinear partial differential equations. We can demonstrate the effective smoothing property of the adopted primal‐dual smoother by a local Fourier analysis. Numerical tests will be presented to show both the improvements achieved in image registration quality and MG efficiency. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Robust Estimation for Generalized Additive Models

This article studies M-type estimators for fitting robust generalized additive models in the presence of anomalous data. A new theoretical construct is developed to connect the costly M-type estimation with least-squares type calculations. Its asymptotic properties are studied and used to motivate a computational algorithm. The main idea is to decompose the overall M-type estimation problem into a sequence of well-studied conventional additive model fittings. The resulting algorithm is fast and stable, can be paired with different nonparametric smoothers, and can also be applied to cases with multiple covariates. As another contribution of this article, automatic methods for smoothing parameter selection are proposed. These methods are designed to be resistant to outliers. The empirical performance of the proposed methodology is illustrated via both simulation experiments and real data analysis. Supplementary materials are available online.     

修正的TV-Stokes模型的新快速算法

基于Tai等人的前期工作,本文研究修正的TV-Stokes图像去噪模型,提出一些新的求解该两步模型的快速算法.我们利用对偶形式和多重网格方法得到一个求解第1步的快速算法.给出另外一种新的求解光滑的切向量场的保不可压性质的算法.在第2步中,我们提出一类有效的全新算法:首先通过计算Poisson方程得到具有光滑法向量场的函数g,然后利用Jia和Zhao的方法得到恢复的图像.新算法的运算速度非常快,用于图像恢复的CPU时间少于0.1 s.数值结果显示新的快速算法是有效的和稳定的,恢复图像的质量也超过了一般去噪方法.     

Multigrid Solution of a Lavrentiev-Regularized State-Constrained Parabolic Control Problem

A mesh-independent, robust, and accurate multigrid scheme to solve a linear state-constrained parabolic optimal control problem is presented. We first consider a Lavrentiev regularization of the state-constrained optimization problem. Then, a multigrid scheme is designed for the numerical solution of the regularized optimality system. Central to this scheme is the construction of an iterative pointwise smoother which can be formulated as a local semismooth Newton iteration. Results of numerical experiments and theoretical two-grid local Fourier analysis estimates demonstrate that the proposed scheme is able to solve parabolic state-constrained optimality systems with textbook multigrid efficiency.