Signal and Image Multiresolution Analysis E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 360

Veröffentlichungsjahr: 2012

Beschreibung

Multiresolution analysis using the wavelet transform has received considerable attention in recent years by researchers in various fields. It is a powerful tool for efficiently representing signals and images at multiple levels of detail with many inherent advantages, including compression, level-of-detail display, progressive transmission, level-of-detail editing, filtering, modeling, fractals and multifractals, etc.
This book aims to provide a simple formalization and new clarity on multiresolution analysis, rendering accessible obscure techniques, and merging, unifying or completing the technique with encoding, feature extraction, compressive sensing, multifractal analysis and texture analysis. It is aimed at industrial engineers, medical researchers, university lab attendants, lecturer-researchers and researchers from various specializations. It is also intended to contribute to the studies of graduate students in engineering, particularly in the fields of medical imaging, intelligent instrumentation, telecommunications, and signal and image processing.
Given the diversity of the problems posed and addressed, this book paves the way for the development of new research themes, such as brain–computer interface (BCI), compressive sensing, functional magnetic resonance imaging (fMRI), tissue characterization (bones, skin, etc.) and the analysis of complex phenomena in general. Throughout the chapters, informative illustrations assist the uninitiated reader in better conceptualizing certain concepts, taking the form of numerous figures and recent applications in biomedical engineering, communication, multimedia, finance, etc.

Leseprobe

Table of Contents

Introduction

Abdeldjalil OUAHABI

Chapter 1. Introduction to Multiresolution Analysis

Abdeldjalil OUAHABI

1.1. Introduction

1.2. Wavelet transforms: an introductory review

1.3. Multiresolution

1.4. Which wavelets to choose?

1.5. Multiresolution analysis and biorthogonal wavelet bases

1.6. Wavelet choice at a glance

1.7. Worked examples

1.8. Some applications

1.9. Bibliography

Chapter 2. Discrete Wavelet Transform-Based Multifractal Analysis

Abdeldjalil OUAHABI

2.1. Introduction

2.2. Fractality, variability and complexity

2.3. Multifractal analysis

2.4. Multifractal formalism

2.5. Algorithm and performances

2.6. Applications

2.7. Conclusion

2.8. Bibliography

Chapter 3. Multimodal Compression Using JPEG 2000:Supervised Insertion Approach

Régis FOURNIER and Amine NAÏT-ALI

3.1. Introduction

3.2. The JPEG 2000 standard

3.3. Multimodal compression by unsupervised insertion

3.4. Multimodal compression by supervised insertion

3.5. Criteria for quality evaluation

3.6. Some preliminary results

3.7. Conclusion

3.8. Bibliography

Chapter 4. Cerebral Microembolism Synchronous Detectionwith Wavelet Packets

Jean-Marc GIRAULT

4.1. Issue and stakes

4.2. Prior information research

4.3. Doppler ultrasound blood emboli signal modeling

4.4. Energy detection

4.5. Wavelet packet energy detection

4.6. Results and discussions

4.7. Conclusion

First published 2012 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

John Wiley & Sons, Inc. 111 River Street Hoboken, NJ 07030 USAwww.wiley.com

ISTE Ltd 27-37 St George's Road London SW19 4EU UKwww.iste.co.uk

© ISTE Ltd 2012

The rights of Abdeldjalil Ouahabi to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2012947123

British Library Cataloguing-in-Publication Data

Introduction1

Wavelet-based multiresolution analysis can be applied for analysis, processing and synthesis of mono- or multidimensional signals at different levels of resolution, by decomposing them into (orthonormal) “scaling” and (orthonormal) “wavelet” functions. Therefore, multiresolution analysis provides a family of orthonormal wavelets, and reduces any redundancy to nil.

In practice, on the one hand, the field of activity awaited the work of Mallat and Daubechies, which focused on implementation adapted to the pyramidal algorithms of Burt and Adelson, for a concrete use of the wavelets to be generated, using the fast wavelet transform. On the other hand, multiresolution analysis was also contingent on the benefits of sub-band coding, introduced in 1977 by Esteban and Galand.

The concept of multiresolution analysis provides a framework for the decomposition (and reconstruction) of a signal in the form of a series of approximations of decreasing scale, completed by a series of details.

To illustrate this idea, let us take the case of an image constructed of a succession of approximations; details improve this image. Therefore, coarse vision becomes finer and more precise.

In fact, in multiresolution analysis, fast wavelet transform is achieved without wavelets or scaling functions! All that is required are the coefficients of a low-pass filter h (and of a high-pass filter derived from h). That is the wonder of Mallat’s fast wavelet transform. In practice, such filters are directly linked to the chosen wavelet.

Researchers, engineers and practitioners of a diverse range of disciplines (multimedia, telecommunications, medicine and biology, signal and image processing, fracture and fluid mechanics, thermodynamics, astrophysics, finance, etc.) are confronted daily with increasingly challenging technological problems at multiple levels of analysis, such as in classification, segmentation, detection (of contours or parameters of interest), reduction or even elimination of noise, compression in preparation for transmission or storage, synthesis and reconstruction.

The concept of multiresolution analysis constitutes an efficient tool, often without a priori knowledge, that is universally applicable to the domains noted above. This tool, sometimes described as miraculous, produces an immediate and readily interpretable and exploitable result. However, for specific applications that require the extraction of targeted information, it is amply clear that it will be necessary to develop and “merge” advanced methods that use existing techniques or optimize analyses (for example, in compression) by taking into account edges or borders, using third-generation waveforms such as ridgelets, curvelets, and strips. In effect, these anisotropic wavelets are automatically oriented and expanded by unifying the geometry of a potential edge.

Since the concept of multiresolution analysis has been well-known for two decades, it is now appropriate to question the utility of further work.

This book aims to provide a simple formalization and new clarity for multiresolution analysis, rendering accessible obscure techniques, and merging, unifying or completing the technique with encoding, feature extraction, compressive sensing, multifractal analysis and texture analysis.

This book is aimed at industrial engineers, medical researchers, university lab attendants, lecturer-researchers and researchers from various specialisms. It is also intended to contribute to the studies of graduate students in engineering, particularly in medical imaging, intelligent instrumentation, telecommunications, and signal and image processing. Given the diversity of the problems posed and addressed, this book paves the way for the development of new research themes, such as brain—computer interface (BCI), compressive sensing, functional magnetic resonance imaging (fMRI), tissue characterization (bones, skin, etc.) and the analysis of complex phenomena in general.

Throughout the chapters, informative illustrations assist the uninitiated reader in better conceptualizing certain concepts, taking the form of numerous figures and recent applications in biomedical engineering, communication, multimedia, finance, etc.

The first chapter of this book briefly recounts the story of the discovery of wavelets, and simply and informatively summarizes the principal themes of multiresolution analysis in one or two dimensions. Abdeldjalil Ouahabi illustrates the interest of the concept of “multiresolution analysis” through several recent applications in feature extraction and classification, adaptive compression, masking encoding and image transmission errors, and suppression of correlated noise, the most notable of which come from the medical (ECG, EEG, BCI and fMRI), telecommunications and multimedia domains.

In Chapter 2, Abdeldjalil Ouahabi introduces the notion of complexity in the context of “multifractal” modeling and analysis of complex, nonlinear and irregular phenomena involving a large hierarchy of scales.

Historically, multifractal analysis was developed in the 1980s to understand and analyze complex phenomena in which regularity varies significantly from one point to another. It also aims to extract new quantitative parameters or multifractal attributes to be used in the more general tasks of analysis of complex phenomena, for example in classification or characterization.

It is interesting to note that multifractal analysis and wavelet transforms are two initially distinct concepts, but were born in the same period at the beginning of the 1980s, and address common concepts: oscillation of localized functions, the concept of scale and localization of singularities. The use of wavelets, and more particularly multiresolution analysis, since the first work in multifractal analysis of turbulent signals, has since facilitated the refining of the practice of multifractal analysis.

After suggesting some practical tools and their related algorithms, Abdeldjalil Ouahabi revisits the “multifractal formalism” based on multiresolution analysis, with an emphasis on algorithm and statistical validation. He illustrates the topic with several applications of signal processing to the analysis of turbulent high-speed signals, financial data, Internet traffic, food quality, medical images, in particular in BCI, fMRI, bone density (osteoporosis) and in ultrasonic tissue characterization (melanoma).

Chapter 3 is devoted to multimodal compression. It consists of joint compression of several signals of different modalities using a unique encoder (here, the JPEG 2000 standard). The supervised insertion approach presented by Réegis Fournier and Amine Naït-Ali in this chapter is based on quasi-optimal insertion of one signal into another (that is the insertion of a signal into an image) by exploiting the oversampled characteristics of certain zones, known as insertion zones. The future of this novel approach seems promising, notably for signals particularly rich in potential insertion zones such as high-definition (HD) images.

Chapter 4 details the use of multiresolution analysis via wavelet packets in the medical domain, and specifically in the detection of microembolisms.

Migration of these microembolisms can result in a cerebral artery aneurysm, disrupting circulation; this can cause an ischemic stroke, cerebrovascular accident (CVA). The number of CVAs is increasing and presents a serious problem in public health. Therefore, their timely detection is particularly important due to their correlation with an increased risk of accidents.

Rather than immediately presenting the best multiresolution analysis-based microembolism detector, Jean-Marc Girault first explains and justifies the entire process involved in the implementation of a detector: from analysis to the modeling of ultrasonic Doppler blood processes, via existing research and data extraction. Such synchronous detectors based on multiresolution analysis by wavelet packets are compared with other detectors, from the most recent to more classic systems, in the case of synthetic signals and audio recording from clinical investigations.

The reliable performance of such detectors offers today’s medical practitioner a new “offline” tool for revealing hitherto undetectable microembolisms. However, detection of these “inaudible” microembolisms raises the question of the validity of the current gold standard.

1 Introduction written by Abdeldjalil OUAHABI.

Chapter 1

Introduction to Multiresolution Analysis1

1.1. Introduction

The concept of wavelet analysis can be introduced in two ways: one is the continuous wavelet transform and the other is multiresolution analysis (MRA).

Continuous wavelet transform is calculated on the basis of the scale factor s and the time position u in the set of real numbers (the time-scale plane is therefore continuously traversed), which renders it extremely redundant. In the reconstruction of a signal by continuous inverse transform, this redundancy is extreme in the sense that all the expanded and translated wavelets are used such that they are linearly dependent, therefore reflecting existing signal information without adding new information.

To profit from a non-redundant signal representation while ensuring a perfect reconstruction from its decomposition, an extremely effective tool, i.e. MRA, was defined by Mallat [MAL 99] and Meyer [MEY 90].

Wavelet multiresolution analysis includes the analysis, processing and synthesis of mono- or multidimensional signals at different levels of resolution, by decomposing them into (orthonormal) “scaling” basis functions and (orthonormal) “wavelet” basis functions. MRA, therefore, provides a family of orthonormal wavelets, which reduces any redundancy to zero.

This powerful concept allows numerical implementation of wavelet decomposition; the definition of the discrete wavelet transform thus necessarily underpins that of the MRA. This chapter concerns wavelet-based MRA.

The introduction of wavelets is closely related to multiresolution. Grasping the concept of wavelets, is therefore, the key to understanding this type of analysis.

Arising from the insight of the geophysicist Jean Morlet of Elf Aquitaine (which became Total following a merger with TotalFina), and formalized jointly by the physicist Alex Grossmann [GRO 84] in 1983, wavelets constitute a powerful tool for signal and image processing for the simultaneous description at multiple scales and for the local properties of complex signals such as non-stationarities, irregularities and rapid transitions, as in image contours. From this perspective, they constitute a “mathematical zoom”, providing accurate analysis and a remarkable synthesis of signals and images.

Wavelets1 have also been extremely useful in the analysis of transients of different durations, in noise reduction (denoising), image compression (JPEG 2000 standard), pattern recognition, data mining and progressive data transmission, and in numerical analysis (solving partial differential equations), computer vision, etc.

The orthonormal wavelet basis was first discovered by mathematician Yves Meyer in 1986 [MEY 90]. At the end of the 1980s, physicist and mathematician Ingrid Daubechies [DAU 92] constructed a family of compactly supported orthonormal wavelet bases (Daubechies wavelets have a support of minimum size). In addition, due to the concept of MRA, algorithms for rapid analysis and reconstruction [MAL 99, MEY 90, BEY 91] based on this have been developed, their implementation requiring only a small number of operations: in the order of N operations for a signal of size N.

The concept of MRA, therefore, provides a framework for signal decomposition in the form of a series of approximations of decreasing resolution together with a set of details.

To illustrate this idea, take the case of an image constructed out of a succession of approximations; the details (see section 1.3) come to sharpen this image. Therefore, coarse vision becomes finer and more precise.

The effervescent enthusiasm for the world of wavelets and their application has existed for almost three decades; it prompted the publication of a number of influential books and scientific journals on its theoretical foundations and development. In this chapter, the first objective is to introduce the “wavelet” tool via MRA to make it accessible to the widest possible range of users from the academic world (students, early career researchers or non-specialists in the field) as well as from the socioeconomic world. The second objective of the chapter is to provide the reader with the basics through which he/she can approach the concepts of the other chapters in the book. Therefore, it provides keys with which we can unlock the concepts that, due to their roots in applied mathematics, may at first seem obtuse to those who are involved in information processing.

This introductory chapter refers to a rich bibliography. We recommend that readers wishing to deepen their understanding of wavelets and their transforms refer to the primary references cited in the bibliography. We also thank our colleagues Stéphane Mallat and Gabriel Peyré for their kind permission to reproduce several figures found on the website htttp://www.ceremade.dauphine.fr/peyre/wavelet-tours/. The simulations presented in this chapter can be reproduced using either Matlab® or Scilab the free multiplatform software for numerical calculation.

After briefly recounting the discovery of wavelets, this chapter focuses on the concept of MRA and the equivalence of orthonormal wavelet bases and filter banks, leading to the rapid, linearly complex algorithms used for the calculation of a wavelet transform.

Throughout the chapter, several comments are included to clarify, add necessary depth, draw the reader's attention to undiscussed topics or highlight areas of possible confusion. The multiresolution analysis and the criteria for choosing a wavelet provided underpin the chapter, highlighting the take-home message of the problems discussed (MRA and the criteria for choosing a wavelet). Finally, informative illustrations help the uninitiated reader to better conceptualize certain ideas, manifested in particular applications (biomedical engineering and communication) and frequently accompanied by the corresponding Matlab® code.

1.2. Wavelet transforms: an introductory review

1.2.1. Brief history

At the beginning of the 19th Century (between 1807 and 1822), Joseph Fourier discovered that all signals could be decomposed into a set of sine waves (often called waves, see Figure 1.1) of different frequencies. The idea of this decomposition is to weigh (by judicious choice of amplitudes) these sine waves and modify their phases by shifting them such that they become additive or subtractive.

Figure 1.1.Wave: sine wave Fourier basis

Mathematical rigor came from Lejeune Dirichlet in 1829 (proof of theorem), and later it was consolidated by Camille Jordan in 1881 (extension to certain functions and convergence criteria).

In practice, Fourier analysis is equally as applicable to periodic signals, better known by the term “Fourier series”, as to transients (signals that rapidly decrease to zero) known in this case as “Fourier transforms”. Today, in the digital age and due to the fast Fourier transform (FFT), there is no operational difference between Fourier series and Fourier transforms.

The Fourier approach can also be seen as the decomposition of a signal into its frequency components or visualization (or representation) in the frequency or spectral domain of information initially described in the temporal domain. Such transformations are reversible and no information is lost in the conversion from one domain to the other.

These simple ideas provoked astonishment and even hostility from Fourier's contemporaries, such as Lagrange, Laplace, Monge and Lacroix.

To illustrate the “insufficiencies or limitations” of the Fourier concept, take the case of music: each note is literally “noted” on the score so that it can be read and interpreted by the musician. The shape of the note represents its duration, and its position on the staff determines its pitch or its (fundamental) frequency. Clearly, without information about duration (time) and frequency (as well as intensity of the note), it is impossible to perform a piece of music. The central critique of the Fourier approach, therefore, is that information is “hidden” in time. In effect, Fourier is informative about frequency contents (number, value and intensity of the frequencies) but remains silent with respect to the moment of transmission and the duration of each frequency. However, temporal information is not, in fact, lost: the original signal can be “reconstructed” using an inverse Fourier transform (addition of weighted sine waves).

From 1975 onward, Jean Morlet strived to find an alternative to Fourier analysis under the umbrella of petroleum prospecting via seismic reflection. Toward the end of the 1970s and the beginning of the 1980s, Jean Morlet discovered highly temporal localized waves, which he named wavelets (Figure 1.2). These wavelets serve as the mathematical microscope in adapting automatically to the various components of a given signal: they are compressed for the analysis of high-frequency transients, increasing the microscope's magnification to examine the finer details, and expanded for the analysis of long-term, low-frequency components. These wavelets are translated along the time axis in order to “scan” the entire signal.

Figure 1.2.Morlet wavelet: a perfectly localized finite energy function

In 1984, the physicist Alex Grossman collaborated with Jean Morlet at the advent of the wavelet era, demonstrating the robustness of the wavelet transform and its property of conservation of energy. Shortly afterward, in 1986, the mathematician Yves Meyer added the finishing touches to this formidable saga, created through the insight of Jean Morlet an engineer at Elf Aquitaine, which gave him the recognition he deserves.

Some years later, Stéphane Mallat provided the information processing community with a “filter” approach in which the principal role is played by a scaling function, sometimes called the “father wavelet”. The concept of MRA is materialized by the decomposition of a signal by a cascade of filters: a pair of mirror filters for each level of resolution, with a low-pass filter associated with the scaling function to provide approximations and a high-pass filter associated with the wavelet to encode details.

Because of her tenacity and dedication, in 1988, Ingrid Daubechies made a significant contribution to the saga with her proposal of readily exploitable, iteratively constructed wavelets, with qualities such as orthogonality, compact support, regularity and the existence of vanishing moments (properties that we discuss in the following paragraphs).

A fast algorithm applicable to signals and images was born, bringing the world of wavelets great acclaim at the end of the 1980s.

NOTE 1.1.- Before finishing this brief history, it seems appropriate to cite the work of the mathematician Alfred Haar who in 1910 proposed the only orthogonal, symmetrical and compactly supported wavelet for signal decomposition. It is well-known that during this period, the term “wavelets” was not well-known, although today it is known by the term “Haar wavelet” and corresponds to a first-order Daubechies wavelet.

1.2.2. Continuous wavelet transforms

The analysis of transitions of different durations requires a transform capable of acting simultaneously on a range of temporal resolutions: wavelet transforms perform this function by decomposing a signal via a family of translated and dilated wavelets.

Called a wavelet (or mother wavelet), a finite energy function2 contains n vanishing moments (or n ∈ ), that is, satisfying:

[1.1]

Expression [1.1] indicates that wavelet analyzes a signal with the following qualities:

– oscillation (by taking positive and negative values), that is the number n controls the oscillations of ; the more n increases, the more oscillates;

The continuous wavelet transform of a signal X ∈ L2() at time u and scale s is defined by:

[1.2]

where W refers to the wavelet and * denotes the complex conjugate of .

Expression [1.2] represents the scalar product of X and the set of wavelets u,s associated with .

WX(u, s) characterizes the “fluctuations” of the signal X(t) in the neighborhood of position u at scale s (see Figure 1.5; here u takes the specific value t0).

By examining expressions [1.1] and [1.2], it is clear that WX(u, s) will be insensitive to the signal's most regular behaviors and more flexible than polynomials with a degree that is less than n (the number of vanishing moments of ). Conversely, WX(u, s) takes into account the irregular behavior of polynomial trends. This important property plays a role in the detection of signal singularities (see Chapter 2).

Figure 1.3.“Mexican hat” wavelet: a) 2D and b) ID

Figure 1.4.Example of an expanded and translated wavelet

Figure 1.5.The process of a wavelet transform

WX(u, s) can also be interpreted as a linear filter operation:

[1.3]

where * denotes the product of convolution, with in which the Fourier transform, , is identified as the transfer function of a band-pass filter [MAL 07]. Expression [1.3] states that wavelet transforms can be calculated by expanded band-pass filters (with variable s).

1.2.2.1. Wavelet transform modulus maxima

Singularities or contours [OUA 07, OUA 09] can be detected by using the maxima of the continuous wavelet transform.

The underlying assumption is that wavelet has n vanishing moments and that it has Cn rapidly decreasing derivatives.

Therefore, according to the Hwang-Mallat theorem [MAL 92], X; can only be singular at point t0 if there is a sequence of wavelet maxima with coordinates (up, sp)p∈ converging to t0 in small (or fine) scales:

[1.4]

with

If the wavelet has only a single vanishing moment, the WTMM are the maxima of the first derivative of X smoothed by . These multiscale modulus maxima are used in the localization of singularities, and contours in an image. If the wavelet has two vanishing moments, modulus maxima correspond to large curves.

NOTE 1.3.- Conversely, if WX(u, s) does not have a small-scale maximum, X is locally regular.

NOTE 1.4.- In general, nothing guarantees that a modulus maximal situated at [u0,s0] belongs to a series of maxima that extends at small (or fine) scales. However, in the case where θ is Gaussian, modulus maxima of WX(u, s) belong to related curves that are not disrupted as the scale decreases.

NOTE 1.5.-In the case of an image, contour points are distributed on the plane of the image that often corresponds to the borders of principal structures. Individual maximal wavelet packets are therefore convolved to generate a curve in which the maxima could follow that contour.

Effectively, in the case of an image denoted by X, we consider two wavelets, partially derived with respect to t1 and t2, of the smooth function :

The corresponding wavelet transform is:

[1.5]

where ∇ denotes the gradient operator and * is the convolution product operator.

Two-dimensional wavelet transforms, therefore define the gradient field of X(t) smoothed by the angle between the velocity vector of RBC number. Note that the gradient gives the direction of maximum variation of X at the smoothing scale s and that the orthogonal direction is often called the direction of maximal regularity.

Therefore, in the spirit of Canny contour detection, the maxima of the wavelet packet transform are defined by points u, where is locally maximum in the direction of the gradient given by the angle . These points form chains, called maxima chains, where the gradient vector locally indicates the direction in which the signal varies most strongly at the given smoothing scale s.

Numerical calculation of the gradient requires us to find an approximation of the derivative of a numeric signal. The derivation is performed by the optimization of certain criteria (here, by Canny detection). The extraction of contours in images is generally performed in three stages as described in Figure 1.7.

The skeleton of a wavelet transform consists of lines of maxima that converge to a point in plane (t1, t2) within the limits of s → 0 . This skeleton takes a space-scale position that contains a priori all the information with respect to fluctuations in the local regularity of X.

Figure 1.8, available at http://cas.ensmp.fr/~chaplais/, shows that singularities create large amplitude coefficients in their cone of influence. WTMM efficiently detect singularities; furthermore, the order of the singularity of X(t) at any given time can be estimated by representing the WTMM as a function of scale s. The slope of the curve (assuming linearity), for example in log-log coordinates, obtained at a given time provides an estimate of the (Hölder) coefficient of singularity.

Figure 1.7.Stages of contour extraction in the Lena image

Figure 1.8.a) Signal X(t) displays singularities and b) the (modulus of the) wavelet transform including maxima lines

1.2.2.2. Reconstruction

The inverse of a continuous wavelet transform in L2 is provided by the wavelet admissibility condition:

[1.6]

where is the Fourier transform of (t).

In order for this integral to be finite, it is necessary to ensure that , which is the reason why wavelets must have a mean of zero . This condition is almost sufficient. If with continuously differentiable , the admissibility condition is satisfied.

In practice, choosing a wavelet with a zero mean (and highly localized in time and in frequency) is sufficient.

In this case, it is possible to synthesize or reconstruct signal X(t) by inversing the wavelet transform, following:

[1.7]

This reconstruction uses all scales, and as such it is highly redundant.

NOTE 1.6.- Continuous wavelet transforms allow the detection of isolated singularities as well as their order of singularity. Regular parts of the signal are represented in the coarsest resolution. It is, therefore, possible to attempt to reconstruct the signal from this coarse resolution and the WTMM. However, constraints must be put in place with respect to the non-uniqueness of the solution to this problem.

Analyzing the wavelet transform modulus facilitates the detection of singularities in the signal interpretable as contours. It is possible to reconstitute an image (visually) close to the original image from its contours (see Figure 1.9).

1.2.3. Discrete wavelet transforms

As previously described, continuous wavelet transforms are highly redundant: WX(u, s) is the 2D (plane (u,s)) representation of a signal X(t) in 1D.

This redundancy can be reduced using one of the innumerable family of wavelets .

Figure 1.9.Reconstruction of the Lena image using WTMM (contours)

The time-scale plane (u, s) is converted into a “dyadic mesh” (or in base 2), as shown in Figure 1.10:

Therefore, discrete wavelet transforms are written as follows:

[1.8]

Clearly, to reduce or eliminate the redundancy, the family must constitute an orthonormal basis of L2(). The conditions under which this basis becomes orthonormal and thus provide a “highly economical” wavelet transform are related to the concept of MRA.

Figure 1.10.Discretization process: a) continuous wavelet transform, b) discretization of plane (u, s), and c) discrete wavelet transform

1.3. Multiresolution

The idea of MRA of a signal consists of its representation as a limit of its successive approximations, where each approximation is a smoothed version of the preceding approximation. Successive approximations are presented at different resolutions, hence the term “multiresolution”. When resolution increases, successive images approximate the signal increasingly closely, and on the contrary, when resolution decreases, the amount of information contained in an image also decreases, eventually to zero. The wavelet coefficients encode the difference in information between two successive images, that is the details acquired by an image when its resolution doubles.

This conceptualization of MRA is comparable to that of a camera, which moves closer to a subject or uses a zoom to distinguish its details and which moves away to capture larger structures — the famous concept of the mathematical microscope.

The rest of this section presents the classic mathematical formulation of MRA.

1.3.1. Multiresolution analysis and wavelet bases

1.3.1.1. Approximation spaces

MRA approximates a signal at multiple resolutions by orthogonal projection onto a family of spaces . Such multiresolution approximations are entirely characterized by a particular discrete filter that determines the loss of information between resolutions. These filters allow simple construction of orthogonal wavelet bases.

In effect, the approximation of signal of resolution 2−j is defined as its orthogonal projection on the space . Space Vj regroups all possible approximations of resolution 2−j.

The MRA is constructed using subspaces Vj nested one inside the other such that the passage from one space to another will result from a change in scale3(mathematical zoom).

The following sections present the mathematical properties of an MRA, providing meaningful examples for each condition.

An MRA of L2() is a family . of nested vectors with the following properties [1.9] to [1.13]:

– is a series of approximation spaces, that is:

[1.9] Vj is a closed subspace of L2

This property ensures the existence of the orthogonal projections of X on each of the spaces Vj, the projection approaching X. In other words, the approximation of a signal of resolution 2−j is defined as its orthogonal projection on the space .

[1.10]

This property reflects the nested property of the spaces and the improvement of the approximation as j decreases. This inclusion is a causal property, simply meaning that an approximation of resolution 2−j contains all the information necessary to calculate an approximation of a coarser resolution 2−j−1.

[1.11a]

[1.11b]

Expression [1.11b] also4 assures that series {Vj} converges to L2() as a whole (we say -∪j∈ Vj is compact in L2()) and therefore the series of projections converges toward X. In other words, on one hand, when resolution 2−j tends toward 0, property [1.11a] implies that all details of X are lost. On the other hand, when resolution 2−j tends toward +∞, property [1.11b] also results in the convergence of the approximation to the signal X.

– All spaces Vj are obtained by the expansion or dyadic contraction or expansion of functions of a unique space. These spaces are all deducted from the central space V0 by contraction (for j < 0 ) or by expansion (for j > 0), that is:

[1.12]

This property characterizes the multiresolution aspects of series {Vj} and plays a crucial role in the construction of wavelet bases. In fact, expansion by two of signals Vj enlarges details by a factor of 2, and [1.12] therefore guarantees an approximation with the coarser resolution 2−j−1.

– A final property of which the intuitive interpretation means that Vj is invariant by any translation of length proportional to scale 2j :

[1.13]

Finally, there is a function θ of V0 such that {θ(t − k)}k∈ is a Riesz basis of V0

Recall that {θ(t − k)}k∈ is a Riesz base of V0 if A > 0 and B > 0 such that X∈V0 is decomposed uniquely by:

[1.14]

with

[1.15]

Energy equivalence guarantees that the development of signals on {θ(t − k)}k∈ is numerically stable. Therefore, due to the properties of expansion [1.12] and development [1.14], it is possible to verify that the family is a Riesz basis of Vj with the same Riesz bounds A and at all scales 2j.

Under these conditions ([1.9] and [1.13]), and from θ, it is possible to show [MAL 99] that there is a function called the scaling function, which, by dilation and translation, generates an orthonormal basis of Vj :

[1.16]

The scaling function can be considered the “potential” that allows the construction of a mother wavelet via MRA.

1.3.1.2. Detail spaces

From the family of spaces {Vj}, a second family of subspaces denoted by {Wj} is defined, where Wj is the orthogonal complement of Vj in Vj−1, represented by the following expression:

[1.17]

As opposed to the spaces {Vj}, which are approximation spaces, the spaces {Wj} are detail spaces. Thus, expression [1.17] means that an element of the approximation space of level (j − 1) decomposes in the approximation of level j, which is coarser, and the details of level j.

This results in the following series of nested spaces:

Figure 1.11 shows this decomposition. Subspaces are symbolically represented by rectangles.

Figure 1.1.Principles of multiresolution alysis

Diverse properties of the subspaces {Wj}j∈. can be formalized, notably:

[1.18]

which indicates that an element L2 can be written in the form of an orthogonal sum of a coarse approximation and an infinity of finer details, and the relationship

[1.19]

explains the fact that the entirety of signal L2 is an infinite sum of orthogonal details.

Figure 1.12.Decomposition of a signal on multiple levels

It can be demonstrated, by dilation and translation, that wavelet Ψ generates an orthonormal base of Wj and therefore of :

[1.20]

1.3.2. Multiresolution analysis: points to remember

Clearly, the idea of MRA can be summarized as follows: it concerns the representation of a signal in the form of a coarse approximation and a series of “corrections” of decreasing amplitude. A true MRA provides a seductive algorithmic element (see the Mallat algorithm in section 1.3.3.2) that paves the way for some impressive applications, notably in compression, denoising, image restoration, smoothing, computer graphics, vision, etc.

From a formal perspective, the MRA of signal X consists of the realization of successive orthogonal projections of the signal on the spaces Vj, which leads to increasingly coarse approximations of X as j increases. The difference between two successive approximations shows the detail information lost during the transition from one resolution to another. This detail information is contained in the subspace Wj orthogonal to Vj.

Thus, signal X belonging to a space Vj is projected on a subspace Vj+1 and a subspace Wj+1 with the aim of reducing the resolution by half. Therefore, there are:

– a scaling function (t) that generates an orthonormal basis of Vj+1 via expansion and translation;

– a wavelet function (t) that generates an orthonormal base of Wj+1 via dilation and translation.

The projection of signal X on the space Vj+1 is denoted by:

[1.21]

The projection of signal X on space Wj+1 is denoted by:

[1.22]

1.3.3. Decomposition and reconstruction

1.3.3.1. Calculation of coefficients

The following calculation demonstrates that any scaling function can be determined by a numerical filter called a conjugate mirror filter.

In effect, {(t − k))} being an orthonormal basis of V0, it is therefore possible to establish the decomposition:

[1.23]

The kth component (or the coefficient) h(k) is given by the scalar product

[1.24]

Equation [1.23] expresses the dilation of by 2 as a function of its entire translation. Series h(k) is interpreted as the coefficients of a discrete filter.

The approach is identical for :

[1.25]

where

[1.26]

Thus, there is a relationship between h(k) and g(k):

[1.27]

This mirror filter plays a fundamental role in rapid algorithms for wavelet transforms.

Mallat [MAL 99] shows that the coefficients of the decomposition of a signal on an orthonormal wavelet basis are calculated by a rapid algorithm that cascades in discrete convolutions with h and g of which the outputs are subsampled.

NOTE 1.8.- The following notation will be adopted:

and

1.3.3.2. Implementation of MRA: Mallat algorithm

Upon decomposition, we have:

[1.28]

[1.29]

and upon reconstruction, we have

[1.30]

[1.31]

where * is the convolution product operator.

According to expressions [1.28] and [1.29], the decomposition of a signal into wavelet bases involves a succession of discrete convolutions with the impulse response low-pass filter and the high-pass impulse response filter as shown in Figure 1.13.

Figure 1.13.Fast wavelet transform or Decomposition of a signal on multiple levels

aj+1 and dj+1 are calculated by taking every other sample from the convolutions of aj- with and , respectively, and so on.

The symbol at the left (used in Figure 1.13) represents the decimation by a factor of 2; in other words, keep one of every two samples.

Fast wavelet transforms are therefore calculated by the cascade of filterings by and followed by subsampling (or decimation) by a factor of 2.

The initialization of the algorithm can present certain difficulties; however, it is possible to assimilate the sampled values of signal X with the coefficients a0. The complexity of this algorithm is of the order of N when signal X is of size N.

Reconstruction or synthesis consists of an interpolation that inserts zeros into series aj +1 and dj+1 to double their length, followed by a filter, as shown in Figure 1.14.

Figure 1.14.Fast inverse wavelet transform or Reconstruction (synthesis)

The symbol to the left (used in Figure 1.14) represents an interpolation that inserts zeros between the samples of aj+1 and dj+1.

NOTE 1.9.-The Mallat algorithm is the key point to remember in MRA. It allows the rapid calculation of a discrete orthogonal wavelet transform (decomposition) and, inversely, permits reconstruction or synthesis of a signal (in ID or 2D) from the wavelet coefficients.

The checklist shown in Table 1.1 helps memorize the fundamental elements of an MRA.

Table 1.1.Multiresolution analysis: checklist

NOTE 1.10.- In this brief introduction, we will examine neither the properties of the low-pass filter h and high-pass filter g used in this algorithm nor the conditions of their use and even less so their extension to M-band decomposition (M ≠ 2). A large body of work is dedicated to them elsewhere, notably in the works of Vetterli [VET 86, VET 95], and also Akansu [AKA 00], Strang [STR 96] and Vaidyanathan [VAI 93].

1.3.3.3. Extension to images

In 2D, the decomposition into a separable wavelet basis is achieved by an extension of the Mallat algorithm. Therefore, for an image, the ID algorithm is applied, first, to each row and then to each column, as shown in Figure 1.15.

Figure 1.15.The Mallat algorithm: decomposition of an image

The Mallat algorithm is based on the pyramidal description of MRA. Wavelet and scaling function are therefore applied to images by rows and columns separately. The dilation of the wavelet and the scaling function is obtained by subsampling the original image. The first approximation contains all levels of a size bigger than half of that of the original image. The three images of the wavelet coefficients contain levels between the resolution of the original image and that of the first image of approximation in the diagonal, vertical and horizontal directions. Effectively, the original image is analyzed by the application of two filters along the rows, one being high-pass g and the other being low-pass h, the coefficients of these filters being unique to the chosen wavelet. Next, every other column is taken, and in the same way a high-pass filter and a low-pass filter are applied, and finally every other row is treated in the same way.

At the first level of decomposition, four reduced-size images are thus obtained:

– Image A1 is obtained after double low-pass filtering (and decimation), constituting a low-resolution approximation of the image.

– After low-pass then high-pass filtering (and decimation), an image H1 is obtained, which captures the horizontal detail of the original image.

– After high-pass then low-pass filtering (and decimation), an image V1 is obtained, which captures the vertical detail of the original image.

– After double high-pass filtering (and decimation), image D1 captures the diagonal detail of the original image.

The same decomposition is also applied to the approximation of the image at the first level of approximation — that is A1 — and so on, until each level of the approximation image Ak is decomposed as shown in the diagram in Figure 1.16.

Figure 1.16.Successive decomposition of an image on three levels. Pyramidal arrangement of the coefficients (subbands) of approximation Ak of level k and coefficients (subbands) of horizontal detail Hk, vertical detail Vk and diagonal detail Dk

This principle is often represented by a pyramid with different stages. Figure 1.17 shows a pyramid of images of increasing resolution calculated by the Mallat algorithm. This MRA algorithm first analyzes the image at low resolution, and then adds resolution only in the regions that require more detail.

Figure 1.18 shows a separable wavelet transform of the Lena image. The arrangement of wavelet coefficients is consistent with the decomposition diagram in Figure 1.16. Areas where image intensity varies slightly generate coefficients of almost zero, which are shown in gray.

Figure 1.17.Pyramidal decomposition of the Lena image at three levels of resolution

Figure 1.18.Separable wavelet transform of the Lena image

1.3.4. Wavelet packets

Wavelet packets provide a finer analysis by decomposing, at each level, not only the approximation spaces but also the detail spaces (see Figure 1.19.) Wavelet packets, defined by Coifman et al. [COI 92], therefore represent a generalization of multiresolution decomposition.

Figure 1.9.Tree of spaces of wavelet packets

The wavelet packet transform is redundant and should only be used in cases where an extremely fine analysis is required. The choice of the best decomposition base depends on the principle of minimal entropy.

Figure 1.20 shows that the coefficients of wavelet packets defined at each node (j, p) by are calculated using a filter bank. Given a discrete input signal a0(k), it uniquely characterizes such that

[1.32]

Thus, the decomposition formula is described by

[1.33]

Consequently, the reconstruction is described by

[1.34]

NOTE 1.11.-Notations and signify that a zero is inserted between each sample of y.

Figure 1.20.Example of decomposition (at three levels) into wavelet packets by cascading filtering and decimation

1.3.5. Multiresolution analysis summarized

Axioms

Orthonormal basis of where k ∈

is known as the scaling function

Orthonormal basis of where (j, k)

is known as a wavelet.

Figure 1.21 shows the diagram of an MRA at three levels.

Figure 1.21.Schematization of a multiresolution analysis at three levels

Mallat algorithm

– The first step of this fast algorithm described in Figure 1.21 consists of separating the signal into two components: a smooth component (the overall appearance) obtained by low-pass filtering (corresponding to the scaling function) and the set of small details (alterations) obtained by high-pass filtering (corresponding to “small” wavelets that encode small details).

– The second step of this algorithm consists of repeating the procedure at half resolution. This step is therefore twice as fast as the preceding step because twice as few coefficients are calculated with the same effort.

– And so on, until the end of the process, at which point the signal is so smooth it disappears; all the information is contained in the coefficients of wavelets dj. The Mallat algorithm is therefore also known as the fast wavelet transform (FWT) (very close to the pyramidal algorithms developed in 1983 by Burt and Adelson [BUR 83])

Coefficients aj and dj are, respectively, known as the approximation coefficients and the wavelet coefficients (or details) of a signal at level j. Multilevel signal decomposition (see Figure 1.22) is achieved by a series of filter banks in quadrature mirrors h (low-pass filter obtained from ) and g (high-pass filter), where .