Computational Techniques

* The Digital TV Filter
* Preconditioners
* Iterative Methods
* Modular Solvers
* Total Variation Image Restoration : Numerical Methods and Extensions

The Digital TV Filter

Motivated by the classical TV (total variation) restoration model, we propose a new nonlinear digital filter -- the TV filter for denoising and enhancing digital images, or more generally, data living on graphs. The digital TV filter is a data dependent lowpass filter, capable of denoising data without blurring jumps or edges. In iterations, it solves a global total variation (or L1) optimization problem, which differs from most statistical filters. Applications are given in the restoration of 1-D signals, 2-D data with irregular structures, gray scale and color images, and non-flat image features such as chromaticity. The digital TV filter intrinsically combines edge detection and an automatic modification of the filter coefficients, and thus is much simpler than the edge-detection-edge-adaptive filter invented by Lev, Zucker, and Rosenfeld (IEEE Trans. Sys. Man Cybern., SMC-7(6), 1977). The digital TV filter also outperforms the most popular median filter, and its recent generalization --- VDF (vector directional filter) invented by Trahanias, et al. (IEEE Trans. Image Process., 2(4), 1993; 5(6), 1996). Report by Chan, Osher, and Shen. (Updated version is coming soon. Click the image to see more details.)


Image reconstruction is a mathematically ill-posed problem and regularization methods must often be used in order to obtain a reasonable solution. Recently the total variation regularization has become very popular for this purpose. In a typical iterative solution of the nonlinear regularization problem, such as the fixed point iteration of Vogel or Newton's method, one has to invert linear operators consisting of the sum of two distinct parts. One part corresponds to the blurring operator and is often a convolution; the other part corresponds to the TV regularization and resembles an elliptic operator with highly varying coefficients. (from CAM 97-44 Abstract, Sep. 97) (IEEE Trans.Image Process.) Reports on Preconditioners .

Iterative Methods

Iterations are needed for solving the nonlinear problem, as well as for the linear problems which arise at each step. Analogous to the situation for solving large discretized PDEs in several dimensions, the size of the problems are large enough that direct solution methods are too costly and iterative methods can be more efficient. (from CAM 96-38 Introduction, Nov. 97) [SIAM J. Num. Anal. Vol 36 1999] Reports on Iterative Methods .

Modular Solvers

Many Problems in image restoration can be formulated either as unconstrained nonlinear optimization problem or as a noise constrained problem. In Practice, it is much easier to develop algorithms for the unconstrained problem, and not always obvious how to adapt such methods to solve the corresponding constrained problem.

We present a new method which can make use of any existing convergent method for the unconstrained problem to solve the constrained one. The new method is based on a Newton iteration applied to an extended system of nonlinear equations, which couples the constraint and the regularized problem. The existing solver is used in a block elimination algorithm. The new modular solver enables us to easily solve the constrained image restoration problem; the solver automatically identifies the regularization parameter during the iterative solution process. (from CAM 97-52 Abstract, Nov. 97) (IEEE Trans.Image Process.) Report on Modular Solvers .

Total Variation Image Restoration : Numerical Methods and Extensions

We describe some numerical techniques for Total Variation image restoration methods, namely a primal-dual linearization for the Euler-Lagrange equations and some preconditioning issues. We highlight the extension of this technique to color images, blind deconvolution and the starcasing effect. (from CAM 97-50 Abstract, Nov. 97) [IEEE image proc : Proc. of the 1997 IEEE Int. Conf. on Image Proc.] Reports on Total Variation .

Reports on Image Restorations
Reports on Computational Techniques

Tony Chan , Stanley Osher , Jianhong Shen , Michael Leonard , Joseph R. Shinnerl , David Strong , Pep Mulet, Peter Blomgren , C. K. Wong, Jamylle Carter