Wavelet approximation methods in image and signal compression

REVISTA DE LA ´ ´ UNION MATEMATICA ARGENTINA Volumen 45, N´ mero 1, 2004, P´ginas 25–41 u a

WAVELET APPROXIMATION METHODS IN IMAGE AND SIGNAL COMPRESSION
´ ´ GUSTAVO GARRIGOS AND EUGENIO HERNANDEZ ∗

Abstract. The material in this paper comes from various conferences given by the authors. We start with a brief survey of harmonic analysis methods in linear and non-linear approximationrelated to signal compression. Special emphasis is made on wavelet-based methods and some of the mathematical theory of wavelets behind them. We also present recent results of the authors concerning nonlinear approximation in sequence spaces and the validity of Jackson and Bernstein inequalities in general smoothness spaces.

1. Introduction Real world images can be mathematically described in variousways [1]. A particularly simple model considers (analog) images as non-negative functions of two variables f (x, y) supported in the unit square [0, 1]2 , which physically may be interpreted as light intensity fields upon a given screen. Precise mathematical expressions of images are sometimes known (e.g. in fractal type designs), although often this is not the case (as in most pictures from thereal world). Analog images must be “digitized” in order to be stored and manipulated by computers. We briefly describe how to produce a digital version of f (x, y) (we follow [4, p. 324]): a measuring device (a photometer) averages the light intensity over small squares (of side length 2−M ) distributed dyadically along the picture frame [0, 1]2 . So if M is large (typically, M ≥ 8), we can codifythe image as a sequence of 22M coefficients: p k = pk
(M )

=

1 |IM,k |
IM,k

f (x, y) dxdy,

0 ≤ k1 , k2 < 2M ,

(1.1)

k2 k1 1 +1 2 +1 where IM,k denotes the dyadic square [ 2M , k2M ] × [ 2M , k2M ]. These squares are usually called pixels (or picture elements) located at positions 2−M k, and correspond in practice to the number of “dots” that form a computer screen. To each of themwe associate a single number pk (typically a rounded integer between 0 and 28 ),

The material in this paper was presented by the authors at the International Workshop in Classical Analysis and Applications held in Yaound´ (Cameroon) in December 2001, and the VII e Encuentro Nacional de Analistas “Alberto P. Calder´n”y Primera Reuni´n Hispano-Argentina de o o An´lisis held in Villa de Merlo(Argentina) in August 2004. The authors thank the people and instia tutions promoting and supporting these conferences. Authors supported by the European Network “HARP 2002-2006” and the Spanish project “MTM2004-0678, MEC, (Spain)”. First author also supported by Programa Ram´n y Cajal, MCyT (Spain). o 2000 Mathematical Subject Classification: 42A16, 42C40, 41A15. Key words and phrases: linearapproximation, non-linear approximation, wavelet, Sobolev spaces, Besov spaces.

∗

25

26

´ ´ G. GARRIGOS, E. HERNANDEZ

which represents the “color level” of the picture at that point. In this way we have converted f (x, y) into a “digital image” {pk }, a sequence of “bits” which can be stored and processed by computers. For the mathematical model, this process may be reversed. Given asequence of bits {pk }, we construct a so-called observed image f (o) (x, y) by: f (o) (x, y) =
k

pk φM,k (x, y),

(1.2)

where φM,k (x) = φ(2M x − k) and the function φ may be simply chosen as χ[0,1]2 or replaced by smoother versions such as splines or wavelet-type scaling functions. In general, when M is sufficiently large, f (o) (x, y) is an almost indistinguishable copy of f (x, y), and thuscan be identified for mathematical purposes with the original image. The compression problem then consists in representing f (o) (x, y) with much less than 22M coefficients without loosing the visual resemblance with the original image. With this example in mind, we can describe a general mathematical setting for compression problems, which is based in classical approximation theory. We are given...