FTVd: A Fast Algorithm for Total Variation based Deconvolution
Authors
Yilun Wang, Wotao Yin, Yin Zhang (Rice)
Paper / Software
[CAAM TR0710] [Code] Version 1.0. Last Update: October 9, 2007. Copyright (c) 2007.
Introduction
FTVd is a fast algorithm for recovering a grayscale image u^{0} from its blurry and noisy observation f by solving the model:
The algorithm is based on splitting u into u and w, which approximates u, and solving the following 2norm penalty problem:
FTVd makes use of the splitting technique and takes an iterative process of alternately minimizing (2) with respect to u or w while fixing the other; one of the two subproblems is the socalled “wsubproblem” for a fixed u, the other is the socalled “usubproblem” for a fixed w. Minimizing (2) with respect to w can be further divided into problems on each component of w (see Eq. (16) in the paper). The main computation of minimizing (2) with respect to u boils down to three Fast Fourier Transforms (FFTs) (see Eq. (17) in the paper) applied to quantities of the image size, and our approach can be easily extended to using other transforms such as discrete cosine transforms (DCTs).
It may be tempting to set to a fixed and very large value to force solution of (2) to be an accurate approximation to that of (1). However, FTVd uses a continuation strategy to accelerate convergence: it starts with a small value and gradually increases it until reaching a preset large value; during the process, the approximate solutions of (2) obtained for smaller values are used sequentially as the starting points in FTVd for computing those for larger values.
There are two approaches, isotropic and anisotropic ones, to discretize the total variation of u:
Numerical Experiments
Our MATLABbased code FTVd was compared with two existing C++ codes for image deblurring: lagged diffusivity (LD, developed by Rodríguez and Wohlberg at Los Alamos National Lab) and FourierWavelet Regularized Deconvolution (ForWaRD, developed by Neelamani, Choi and Baraniuk with the Rice DSP group). While FTVd and LD produce visually indistinguishable outputs, which contain less artifacts than those produced by ForWaRD, FTVd and ForWaRD are both faster than LD.



