On Some Iterative Concepts for Image Restoration

Ingrid Daubechies1; Gerd Teschke2; Luminita Vese3    1 Princeton University, PACM, Washington Road, Princeton, NJ 08544-1000, USA
2 Konrad-Zuse Institute Berlin, Takustr. 7, D-14195 Berlin-Dahlem, Germany
3 Department of Mathematics, UCLA, 405 Hilgard Avenue, Los Angeles, CA 90095-1555, USA

I INTRODUCTION

This chapter discusses several iterative strategies for solving inverse problems in the context of signal and image processing. We essentially focus on problems for which it is reasonable to assume that the solution has a sparse expansion with respect to a wavelet basis or frame. In each case, we consider a variational formulation of the problem and construct an iteration scheme for which the iterates approximate the solution. To this end, we apply surrogate functionals; the corresponding strategy was shown to converge in norm and to regularize the problem (see Daubechies et al., 2004). We discuss special cases and generalizations.

The surrogate functional method in its initial setup as described in Daubechies et al. (2004) amounts to a combination of Landweber's method and a shrinkage operation, applied in each iteration step. The shrinkage is due to the presence of the 1-penalization term in the functional. Recent developments in the field of signal and image processing have shown the importance of sparse representations for various tasks in inverse problems (such as compression, denoising, deblurring, decomposition, texture analysis); 1-constraints select for such sparsity. Here we limit ourselves to illustrating a small number of concrete inverse problems for which we show in detail the variational formulations and the resulting expressions for the iteration. For all cases we discuss convergence and give detailed numerical illustrations. In addition to these case studies, we also present strategies for more general constraints.

We begin with the concrete problem of simultaneously denoising, decomposing, and deblurring a given image. The associated variational formulation of the problem contains terms that promote sparsity and smoothness. We show how to transform the problem such that the basic method of Daubechies et al. (2004) applies. In a second example, we discuss a natural extension to vector-valued inverse problems. Potential applications include seismic or astrophysical data decomposition/reconstruction and color image reconstruction. The illustration presented here contains audio data coding. After these two case studies, we turn to more general formulations. We allow the constraint to be some other positive, homogeneous, and convex functional than the 1-norm. In the linear case, and under fairly general assumptions on the constraint, we prove that weak convergence of the iterative scheme always holds. In certain cases (i.e., for special families of convex constraints) this weak convergence implies norm convergence. The presented technique covers a wide range of problems. Here we discuss in greater detail image restoration problems in which Besov- or bounded variation (BV) constraints are involved. We close with sketching the design of hybrid wavelet-partial differential equation (PDE) image restoration schemes (i.e., with variational problems that contain wavelet and BV constraints).

II SIMULTANEOUS DECOMPOSITION, DEBLURRING, AND DENOISING OF IMAGES BY MEANS OF WAVELETS

This section is devoted to wavelet-based treatments of variational problems in the field of image processing. In particular, we follow approaches presented in Meyer (2002), Vese and Osher (2003, 2004), and Osher et al. (2003) and discuss a special class of variational functionals that induce a decomposition of images into oscillating and cartoon components and possibly an appropriate “noise” component. In the setting of Vese and Osher (2003) and Osher et al. (2003), the cartoon component of an image is modeled by a BV function; the corresponding incorporation of BV penalty terms in the variational functional leads to PDE schemes that are numerically intensive. By replacing the BV penalty term by a 11(L1) term (which amounts to a slightly stronger constraint on the minimizer) and writing the problem in a wavelet framework, elegant and numerically efficient schemes are obtained with results very similar to those obtained in Osher et al. (2003) and superior to those from Rudin et al. (1992). This approach allows incorporating bounded linear blur operators into the problem so that the minimization leads to a simultaneous decomposition, deblurring, and denoising.

A Wavelet-Based Reformulation of the Variational Problem

As mentioned previously, we focus on a special class of variational problems that induce a decomposition of images into “texture” and “cartoon” components. Ideally, the cartoon part is piecewise smooth with possibly abrupt edges and contours; the texture part fills in the smooth regions in the cartoon with typically oscillating features. Inspired by Meyer (2002), Vese and Osher (2003) and Osher et al. (2003) propose to model the cartoon component by the space BV; this induces a penalty term that allows edges and contours in the reconstructed cartoon images, leading to a numerically intensive PDE-based scheme.

Our main goal is to provide a computationally thriftier algorithm by using a wavelet-based scheme that solves not the same but a very similar variational problem, in which the BV constraint, which cannot easily be expressed in the wavelet domain, is replaced by a 11(L1)-term (i.e., a slightly stricter constraint, since 11(L1)⊂BV in two dimensions). Moreover, we can easily incorporate the action of linear bounded blur operators; we also show convergence of the proposed scheme.

To provide a brief description of the underlying variational problems, recall the methods proposed in Vese and Osher (2003) and Osher et al. (2003). They follow the idea of Meyer (2002), proposed as an improvement on the total variation framework of Rudin et al. (1992). In principle, the models can be understood as a decomposition of an image f into =u+v, where u represents the cartoon part and v the texture part. In the model by Vese and Osher (2003, 2004), the decomposition is induced by solving

u,g1,g2Gp(u,g1,g2),whereGp(u,g1,g2)=∫Ω|∇u|+λ‖f−(u+divg)‖L2(Ω)2+μ‖|g|‖Lp(Ω),

with ∈L2(Ω), ⊂R2, and =divg=div(g1,g2). The first term is the total variation of u. If ∈L1 and ∇u| is a finite measure on Ω, then ∈BV(Ω). This space allows discontinuities; therefore edges and contours generally appear in u. The second term represents the restoration discrepancy; to penalize v, the third term approximates (by taking p finite) the norm of the space G of oscillating functions introduced by Meyer (with =∞), which is in some sense dual to (Ω). (For details, refer to Meyer, 2002.) Setting...