Wavelet transform

As wavelet transform ( WT , English wavelet transform a family of linear is) time - frequency - transformations in the Mathematics and Engineering Sciences (primary: Telecommunications , computer science ), respectively. The WT is made up of the wavelet analysis, which denotes the transition from the time representation to the spectral or wavelet representation, and the wavelet synthesis, which denotes the reverse transformation of the wavelet transformed into the time representation.

The term wavelet describes the basic function used for the transformation , with which the signal or image to be analyzed - generally an N-dimensional function - is “compared”.

The roots of the wavelet school are in France, where the originally French term ondelette was coined, but its English counterpart wavelet later became the name of the game. Translated into German, wavelet means something like small wave or ripple and expresses the fact that, in contrast to the Fourier transformation, temporally localized waves or functions are used as a basis, which enables the time and frequency resolution mentioned above. Like all linear time-frequency transformations, the wavelet transform is also subject to the uncertainty relation of communications engineering , i.e. H. an event cannot be localized at the same time as precisely as required in terms of time and frequency. There is always only one compromise between good temporal resolution or good resolution in the frequency domain.

The wavelet transformation is primarily divided into two camps, namely the continuous wavelet transformation, which has its main application in mathematics and data analysis, and the discrete wavelet transformation, which is more likely to be found in engineering and its application in Area of data reduction, data compression and signal processing lies (see).

functionality

The wavelet transform can be seen as an improvement on the short-term Fourier transform (STFT).

Short-term Fourier transform weaknesses

With the STFT, a window function is applied to the signal to be examined - for example the Gaussian bell curve as in the Gabor transformation . For each point of the STFT, the window is shifted to the point in time to be considered and to the frequency to be considered (modulation in the time domain). The absolute duration and bandwidth of the window (“width” in the time and frequency domains) - and thus the resolution - do not change as a result.

The resolutions in the time and frequency domains only depend on the shape of the window. Due to the time-frequency uncertainty, the resolution in the time domain is inversely proportional to the resolution in the frequency domain. It is therefore not possible to achieve the best possible resolution in the time domain and in the frequency domain at the same time. If a signal contains frequency components at both high and low frequencies, one would like to achieve a good (absolute) frequency resolution at low frequencies , since a small absolute frequency change is very important here. With a high frequency, a good time resolution is more important, since a complete oscillation takes less time and the instantaneous frequency can therefore change more quickly.

For a signal with frequency components at 1 Hz and 1 kHz, for which the frequency should be resolved to 10 percent, a frequency resolution of 0.1 Hz is necessary at 1 Hz. At 1 kHz, this corresponds to a resolution of 0.01 percent - such a good resolution is not necessary here. On the other hand, at 1 kHz, the signal performs ten complete oscillations in 10 ms. In order to be able to resolve frequency changes in this period, a time resolution better than 10 ms is necessary. At 1 Hz, this period corresponds to only one hundredth of an oscillation. Such a good temporal resolution is therefore not necessary here. At low frequencies, a good frequency resolution is desired while accepting poor time resolution, and at high frequencies a good time resolution with poorer frequency resolution. The short-time Fourier transformation does not do this.

Summary of how it works

As with the STFT, a window function is applied to the signal under investigation. However, instead of moving and modulating the window (shift in the frequency domain) (as with the STFT), the window is shifted and scaled. As with modulation, the scaling also results in a frequency shift, but at the same time as the frequency is increased, the duration (“width” in the time domain) of the window is reduced. This results in a better temporal resolution at higher frequencies. At low frequencies the frequency resolution is better, but the time resolution is worse.

Continuous wavelet transform

Morlet wavelet , example of a wavelet function (defined similarly to a Gaussian wave packet )

{\ displaystyle \ psi (t)}

Continuous wavelet transformation of a sine signal with an abrupt frequency change

The continuous wavelet transform (CWT, engl. Continuous wavelet transform ) is given by

{\ displaystyle {\ mathcal {W}} _ {\ psi} x (a, b) = {\ frac {1} {a}} \ int _ {- \ infty} ^ {\ infty} {\ overline {\ psi \ left ({\ frac {tb} {a}} \ right)}} x (t) \; dt.}

It is

${\ displaystyle x (t)}$ : the function to be transformed, for example an audio or image signal
${\ displaystyle \ psi (t)}$ : Wavelet function (English mother wavelet ) which can be selected differently depending on the application
${\ displaystyle b}$ : Translation parameters for scanning the data in the temporal or spatial dimension ${\ displaystyle x (t)}$
${\ displaystyle a}$ : Scaling parameter that scans the data over different frequency ranges

With the wavelet family derived from the Mother wavelet ${\ displaystyle \ psi (t)}$

{\ displaystyle \ psi _ {ab} = {\ frac {1} {a}} \ psi \ left ({\ frac {tb} {a}} \ right)}

the continuous wavelet transformation can be expressed compactly as a scalar product

{\ displaystyle {\ mathcal {W}} _ {\ psi} x (a, b) = \ langle \ psi _ {ab}, x \ rangle}

write.

Properties of wavelets

A wavelet is a square-integrable function that can be selected relatively freely. In general, there is another technical requirement for a wavelet, the admissibility condition : ${\ displaystyle \ psi (t)}$

{\ displaystyle \ int _ {- \ infty} ^ {\ infty} {\ frac {| {\ hat {\ psi}} (\ omega) | ^ {2}} {| \ omega |}} d \ omega < \ infty}

Here called the Fourier transform of . The admissibility condition is needed for the proof of some central theorems and properties, which is why it is often included in the definition of a wavelet. ${\ displaystyle {\ hat {\ psi}} (\ omega)}$ ${\ displaystyle \ psi (t)}$

A direct consequence of the admissibility is that the Fourier transform of the wavelet vanishes at the point 0:

{\ displaystyle {\ hat {\ psi}} (\ omega = 0) = 0}

It also follows that the first moment of the wavelet, i.e. its mean value, vanishes:

{\ displaystyle \ int _ {- \ infty} ^ {\ infty} \ psi (t) \; dt = 0}

Wavelet synthesis

The original function x (t) can be recovered from the wavelet transform up to an additive constant using the reconstruction formula

{\ displaystyle x (t) = {\ frac {1} {c _ {\ phi \ psi}}} \ int _ {0} ^ {\ infty} \! {\ frac {da} {a}} \ int _ {- \ infty} ^ {\ infty} \! \! \! db \; {\ mathcal {W}} _ {\ psi} x (a, b) {\ frac {1} {a}} \ phi \ left ({\ frac {tb} {a}} \ right),}

With

{\ displaystyle c _ {\ phi \ psi} = \ int _ {0} ^ {\ infty} {\ frac {d \ omega} {\ omega}} {\ overline {{\ hat {\ phi}} (\ pm \ omega)}} {\ hat {\ psi}} (\ pm \ omega) \; d \ omega.}

It is the dual wavelet function . ${\ displaystyle \ phi (t)}$ ${\ displaystyle \ psi (t)}$

Reproducing core

The wavelet transform of the wavelet itself is referred to as the reproducing kernel . Thus designated

{\ displaystyle K _ {\ psi} (a, b) = \ langle \ psi _ {ab}, \ psi \ rangle}

the core of the wavelet . ${\ displaystyle \ psi}$

The kernel carries the attribute reproducing because the wavelet transform is reproduced under the convolution with the kernel, that is, the wavelet transform is invariant under the convolution with the kernel. This folding is given by

{\ displaystyle (K _ {\ psi} * {\ mathcal {W}} _ {\ psi} x) (a, b) = \ int _ {0} ^ {\ infty} \! {\ frac {da '} {a '}} \ int _ {- \ infty} ^ {\ infty} \! \! \! db' \; {\ frac {1} {a '}} K _ {\ psi} \ left ({\ frac {a} {a '}}, {\ frac {b-b'} {a '}} \ right) ({\ mathcal {W}} _ {\ psi} x) (a, b).}

This is not an ordinary convolution as it is not commutative; however, it is associative.

The reproducing kernel has a further important meaning because it indicates the minimal correlation between two points (a, b) and (a ', b') in the wavelet space. This can be shown by considering the autocorrelation of white noise in the wavelet space. If we denote a Gaussian white noise with variance 1, then its autocorrelation is given by . The correlation in the wavelet dream is then (without performing the calculation) ${\ displaystyle \ xi (t)}$ ${\ displaystyle \ langle \ xi (t) \ xi (t ') \ rangle = \ delta (t, t')}$

{\ displaystyle \ langle ({\ overline {{\ mathcal {W}} _ {\ psi} \ xi (a ', b')}} {\ mathcal {W}} _ {\ psi} \ xi (a, b) \ rangle = {\ frac {1} {a '}} K _ {\ psi} \ left ({\ frac {1} {a'}}, {\ frac {b-b '} {a'}} \ right),}

so just given by the reproducing core.

Discrete wavelet transform

The Discrete Wavelet Transformation or DWT is a wavelet transformation that is carried out in a time and frequency discrete manner.
It has been shown that the information despite reduction to a discrete subset in remain intact. ${\ displaystyle \ {(a, b) = (\ alpha ^ {k}, l \, \ beta \, \ alpha ^ {- k}): \; k, l \ in \ mathbb {Z} \} \ subset \ mathbb {R} _ {+} \ times \ mathbb {R}}$ ${\ displaystyle \ alpha> 1, \ beta> 0}$
A DWT can be implemented very efficiently as a series of time-discrete filters ; the continuous wavelet transform is practically calculated in this way.

Fast wavelet transform

The fast wavelet transform (Engl. Almost wavelet transform , FWT ) is an algorithm that using the theory of multi-scale analysis implements the discrete wavelet transform. The formation of the inner product of the signal with each wavelet is replaced by the successive division of the signal into frequency bands . This reduces the complexity of the wavelet transformation from (cf. fast Fourier transformation ) to . ${\ displaystyle O (N \ log N)}$ ${\ displaystyle O (N)}$

Wavelet Packet Transformation and Best Basis Algorithms

The wavelet packet transformation is an extension of the fast wavelet transformation (FWT) in that not only the low-pass channel but also the band-pass channel are further split by means of the wavelet filter bank. This can be used to convert a standard 2-channel DWT such as B. the Daubechies wavelets to obtain an M-channel DWT, where M is a power of 2; the exponent is called the depth of the packet tree. This method is used in broadband data transmission as an alternative to the fast Fourier transformation .

If white noise is transformed as an input signal in a recursion step of the FWT , the result is again white noise due to the orthogonal nature of the DWT, with the energy (= square sum of the samples) being evenly distributed between the low-pass and band-pass channels. If one takes the greatest possible deviation from this behavior, i. H. the most complete possible concentration of the signal energy on one of the two channels, as a decision criterion as to whether the input channel should be split, and if this method is continued for the split channels, a variant of a best-base method is created.

Important applications

Image compression and video compression : wavelet compression
Solution of differential equations
Signal processing

history

First wavelet ( Haar wavelet ) by Alfréd Haar (1909)
Since the 1950s: Jean Morlet and Alex Grossmann
Since the 1980s: Yves Meyer , Stéphane Mallat , Ingrid Daubechies , Ronald Coifman , Victor Wickerhauser

Web links

Wavelets for Kids - Introduction (English; PDF; 2.77 MB)
The engineer's ultimate guide to wavelet analysis by Robi Polikar (English) - Explanation of the wavelet transform with motivation, which is easy to understand for people with knowledge of the Fourier transform
Collection of links to wavelets
Wavelet Digest Home Page

Individual evidence

↑ Strutz: Image data compression. SpringerVieweg, 2009

[Strutz-1] Strutz: Image data compression. SpringerVieweg, 2009