The total variation (TV) denoising method is a PDE-based technique that preserves edges well but has the sometimes undesirable staircase effect, namely, the transformation of smooth regions ( ramps) into piecewise constant regions ( stairs). In this paper we present an improved model, constructed by adding a nonlinear fourth order diffusive term to the Euler--Lagrange equations of the variational TV model. Our technique substantially reduces the staircase effect, while preserving sharp jump discontinuities (edges). We show numerical evidence of the power of resolution of this novel model with respect to the TV model in some 1D and 2D numerical examples.

We present a new method for solving total variation (TV) minimization problems in image restoration. The main idea is to remove some of the singularity caused by the nondifferentiability of the quantity $|\nabla u|$ in the definition of the TV-norm before we apply a linearization technique such as Newton's method. This is accomplished by introducing an additional variable for the flux quantity appearing in the gradient of the objective function, which can be interpreted as the normal vector to the level sets of the image u. Our method can be viewed as a primal-dual method as proposed by Conn and Overton [ A Primal-Dual Interior Point Method for Minimizing a Sum of Euclidean Norms, preprint, 1994] and Andersen [Ph.D. thesis, Odense University, Denmark, 1995] for the minimization of a sum of Euclidean norms. In addition to possessing local quadratic convergence, experimental results show that the new method seems to be globally convergent.

In this paper we show that the lagged diffusivity fixed point algorithm introduced by Vogel and Oman in [SIAM J. Sci. Comput., 17 (1996), pp. 227--238] to solve the problem of total variation denoising, proposed by Rudin, Osher, and Fatemi in [Phys. D, 60 (1992), pp. 259--268], is a particular instance of a class of algorithms introduced by Voss and Eckhardt in [Computing, 25 (1980), pp. 243--251], whose origins can be traced back to Weiszfeld's original work for minimizing a sum of Euclidean lengths [Tôhoku Math. J., 43 (1937), pp. 355--386]. There have recently appeared several proofs for the convergence of this algorithm [G. Aubert et al., Technical report 94-01, Informatique, Signaux et Systèmes de Sophia Antipolis, 1994], [A. Chambolle and P.-L. Lions, Technical report 9509, CEREMADE, 1995], and [D. C. Dobson and C. R. Vogel, SIAM J. Numer. Anal., 34 (1997), pp. 1779--1791]. Here we present a proof of the global and linear convergence using the framework introduced in [H. Voss and U. Eckhart, Computing, 25 (1980), pp. 243--251] and give a bound for the convergence rate of the fixed point iteration that agrees with our experimental results. These results are also valid for suitable generalizations of the fixed point algorithm.

Liu, Osher, and Chan introduced weighted essentially nonoscillatory (WENO) reconstructions in [X.-D. Liu, S. Osher, and T. Chan, J. Comput. Phys., 115 (1994), pp. 200–212] to improve the order of accuracy of essentially nonoscillatory (ENO) reconstructions [A. Harten et al., J. Comput. Phys., 71 (1987), pp. 231–303]. In [G.-S. Jiang and C.-W. Shu, J. Comput. Phys., 126 (1996), pp. 202–228], the authors proposed smoothness indicators to obtain a WENO fifth order reconstruction from third order ENO reconstructions. With these smoothness indicators, Balsara and Shu [J. Comput. Phys., 160 (2000), pp. 405–452] and, later, [G. A. Gerolymos, D. Sénéchal, and I. Vallet, J. Comput. Phys., 228 (2009), pp. 8481–8524] obtained $(2r-1)$th order WENO reconstructions from rth order ENO reconstructions for $4\leq r\leq 6$, resp., $7\leq r\leq 9$. In [A. K. Henrick, T. D. Aslam, and J. M. Powers, J. Comput. Phys., 207 (2005), pp. 542–567], the authors noticed that these reconstructions do not attain the optimal order $2r-1$ at extrema and they proposed a fix for the problem. Other authors [R. Borges et al., J. Comput. Phys., 227 (2008), pp. 3191–3211; N. K. Yamaleev and M. H. Carpenter, J. Comput. Phys., 228 (2009), pp. 4248–4272] have addressed this problem with different weight designs for Jiang–Shu smoothness indicators. In this paper we exploit the special structure of Jiang–Shu smoothness indicators and analyze the role of a parameter appearing in the weight definition to avoid division by zero to obtain for any $r\geq 2$, by standard approximation properties of Lagrange interpolation, that the order of the WENO reconstruction is $2r-1$ at smooth regions, regardless of neighboring extrema, whilst this order is r, as ENO reconstructions have, when the function has a discontinuity in the stencil of $2r-1$ points but it is smooth in at least one of the substencils of r points. The optimal weights are also obtained in closed form.

We describe some numerical techniques for the total variation image restoration method, namely a primal-dual linearization for the Euler-Lagrange equations and some preconditioning issues. We also highlight extension of this technique to color images, blind deconvolution and the staircasing effect.