Rice University, L1-Related Optimization Project

::News      ::Courses      ::People      ::Papers and Reports      ::Software

FTVd: A Fast Algorithm for Total Variation based Deconvolution

Authors

Yilun Wang, Wotao Yin, Yin Zhang (Rice)

Paper / Software

[CAAM TR07-10] [Code] Version 1.0. Last Update: October 9, 2007. Copyright (c) 2007.

Introduction

FTVd is a fast algorithm for recovering a gray-scale image u0 from its blurry and noisy observation f by solving the model:

(1)
where ||.|| is the Euclidean norm and K is a point-spread function that blurs u.

The algorithm is based on splitting u into u and w, which approximates  \~/ u, and solving the following 2-norm penalty problem:

(2)
for a large penalty parameter b.

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 sub-problems is the so-called “w-subproblem” for a fixed u, the other is the so-called “u-subproblem” 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 b 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 b-value and gradually increases it until reaching a preset large value; during the process, the approximate solutions of (2) obtained for smaller b-values are used sequentially as the starting points in FTVd for computing those for larger b-values.

There are two approaches, isotropic and anisotropic ones, to discretize the total variation of u:

and
The current version of the code FTVd supports both isotropic and anisotropic discretizations for total variation.

Numerical Experiments

Our MATLAB-based 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 Fourier-Wavelet 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.


PIC
France: 512 by 512
PIC
Man: 1024 by 1024


PIC
Input Image (Medium Motion Blurring)
PIC
Input Image (Severe Motion Blurring)
PIC
ForWaRD Result (Medium Blurring)
PIC
ForWaRD Result (Severe Blurring)
PIC
FTVd result (Medium Blurring)
PIC
FTVd result (Severe Blurring)


PIC
Input Image (Medium Gaussian Blurring)
PIC
Input Image (Severe Gaussian Blurring)
PIC
ForWaRD Result (Medium Blurring)
PIC
ForWaRD Result (Severe Blurring)
PIC
FTVd Result (Medium Blurring)
PIC
FTVd Result (Severe Blurring)


Table 1Running Times in Seconds of LD and FTVd on a Linux Platform
Code Test 1Test 2Test 3 Test 4 Language
LD 167.6 1305.29304.943972.4 C++
FTVd 11.7 19.4 85.9 93.7 MATLAB
Ratio 14.3 67.3 108.3 469.3 Mean 164.8