Constrained & unconstrained

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).

Preconditioners
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.

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)

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.

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.