Image processing based on partial differential equations - Proceedings of the International Conference on PDE-Based Image Processing and Related Inverse Problems, CMA, Oslo, August 8-12, 2005

Error Analysis for H1 Based Wavelet Interpolations (p. 23)

Tony F. Chan, Hao-Min Zhou, and Tie Zhou

Summary.

We rigorously study the error bound for the H1 wavelet interpolation problem, which aims to recover missing wavelet coe.cients based on minimizing the H1 norm in physical space. Our analysis shows that the interpolation error is bounded by the second order of the local sizes of the interpolation regions in the wavelet domain.

1 Introduction

In this paper, we investigate the theoretical error estimates for variational wavelet interpolation models. The wavelet interpolation problem is to calculate unknown wavelet coe.- cients from given coeficients. It is similar to the standard function interpolations except the interpolation regions are defined in the wavelet domain. This is because many images are represented and stored by their wavelet coeficients due to the new image compression standard JPEG2000.

The wavelet interpolation is one of the essential problems of image processing and closely related to many tasks such as image compression, restoration, zooming, inpainting, and error concealment, even though the term "interpolation" does not appear very often in those applications. For instance, wavelet inpainting and error concealment are to fill in (interpolate) damaged wavelet coe.cients in given regions in the wavelet domain.

Wavelet zooming is to predict (extrapolate) wavelet coeficients on a finer scale from a given coarser scale coeficients. A major difference between wavelet interpolations and the standard function interpolations is that the applications of wavelet interpolations often impose regularity requirements of the interpolated images in the pixel domain, rather than the wavelet domain.

For example, natural images (not including textures) are often viewed as piecewise smooth functions in the pixel domain. This makes the wavelet interpolations more challenging as one usually cannot directly use wavelet coeficients to ensure the required regularity in the pixel domain. To overcome the difficulty, it seems natural that one can use optimization frameworks, such as variational principles, to combine the pixel domain regularity requirements together with the popular wavelet representations to accomplish wavelet interpolations.

A different reason for using variational based wavelet interpolations is from the recent success of partial differential equation (PDE) techniques in image processing, such as anisotropic difusion for image denoising (25), total variation (TV) restoration (26), Mumford-Shah and related active contour segmentation (23, 10), PDE or TV image inpainting (1, 8, 7), and many more that we do not list here. Very often these PDE techniques are derived from variational principles to ensure the regularity requirements in the pixel domain, which also motive the study of variational wavelet interpolation problems.

Many variational or PDE based wavelet models have been proposed. For instance, Laplace equations, derived from H1 semi-norm, has been used for wavelet error concealment (24), TV based models are used for compression (5, 12), noise removal (19), post-processing to remove Gibbs’ oscillations (16), zooming (22), wavelet thresholding (11), wavelet inpainting (9), l1 norm optimization for sparse signal recovery (3, 4), anisotropic wavelet filters for denoising (14), variational image decomposition (27).