Rice University, L1-Related Optimization Project

Authors

Yilun Wang, Wotao Yin, Yin Zhang (Rice)

Paper / Software

Introduction

FTVd is a fast algorithm for recovering a gray-scale image u⁰ 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

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 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:

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.

France: 512 by 512

Man: 1024 by 1024

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

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