Haar-Wavelet
The Haar wavelet is the first in the literature has become known wavelet and was proposed in 1909 by Alfréd hair. It is also the simplest known wavelet and can be formed from the combination of two rectangular functions.
Advantageously, the Haar wavelet is the simple implementability of the corresponding fast wavelet transform ( FWT ). The disadvantage of Haar wavelets is that it is discontinuous and therefore can not be differentiated.
- 2.1 forward transformation
- 2.2 retransformation
- 2.3 Recursive filter bank
- 2.4 interpretation
The functions of the Haar wavelet basis
Scaling function
The scaling function or " father wavelet " function of the Haar wavelet basis is the indicator function of the interval.
It satisfies the functional equation
Wavelet
The wavelet is the " collapsed " difference between two consecutive scaling functions:
Said.
The spelling with prefactor ensures that the matrix
Is an orthogonal matrix. This is part of the conditions that require the orthogonal wavelets.
Multiscale Analysis
This function generates the multi-scale analysis of step functions. This is any function with " finite energy " is assigned to each scale, the following projection:
The difference between the two scales can then be expressed by the " mother wavelet " or the actual wavelet:
With true and as functions in the Hilbert space
- All these functions have norm 1,
- Is perpendicular to at k ≠ l,
- Is perpendicular to at i ≠ j or k ≠ l,
- Which form a Hilbert basis.
Fast Haar wavelet transform
Given a discrete signal f, obtained by a finite sequence or quadratsummierbare
Is shown. He is as a continuous signal, the step function
Assigned.
Forward transformation
From the discrete signal is by pairwise " vertically, " a vektorwertiges signal, the so-called polyphase decomposition, produces:
This will be multiplied term by term with the Haar transform matrix
And is there.
Inverse transformation
We get a mean value signal s and a difference signal d from which by means of simple reversal of the steps taken, the output signal can be recovered:
If the variation from member to member in the output signal is limited by a small ε > 0, the fluctuation is in b by √ 2 ⋅ ε limited, so still small, the size of the links in but d by ε / √ 2 A smooth signal is thus decomposed into a still smooth signal sampling frequency and half in a small differential signal. This is the starting point of the wavelet compression.
Recursive filter bank
We can repeat the process by declaring s to the output signal and decompose with the above procedure, we obtain a sequence of decompositions, has a -th of the original sampling frequency and by 2k / 2 ⋅ ε bounded variation, also has a -th of the original sampling and 2k/2-1 ⋅ ε limited members.
Interpretation
As a discrete signal f is a real sequence (fn) is usually considered over Z with finite energy,
Among these, there are some very simple consequences? N, called Kronecker or Dirac delta, one for each nZ. For their followers that each nth has the value 1, and all others to 0, at k ≠ n
Now we can write each signal trivial as a series in the signal space
Or as a sum of two rows
In many practical relevant signal classes, such as continuous over-sampled bandlimited signals, values of adjacent follower members are adjacent, that is, in general, f2n and f2n 1 close together, relative to its absolute value. This is however not taken into account in the above series. In the mean and difference of f2n and f2n 1 whose similarity would strongly expressed, the average is two values similar and the difference is small. If we use the identity
To adjacent members of the first row or corresponding elements in the second decomposition summarized in ( scaled ) mean values and differences:
Now we are introducing new designations:
- The new base sequences
- With the new transformed coefficients
Thus we have the cutting of the Haar wavelet transform
And by means of the infinite Euclidean scalar product, we can write
The last three identities describe a " Conjugate Quadrature filter bank ( CQF ) ", which can be defined for more general base sequences an and bn. The base sequences at all arise by shifting to the respective 2n a0, bn by the shift from b0. More in the article Daubechies wavelets.
Now the sequence s = ( sn ) contains a smoothed version of the output signal at half the sampling rate, so you can also decompose s according to this rule and continue this procedure over a certain depth recursive. From an output signal s0: = f so successively, the tuples
If f is finite, ie almost everywhere zero, with length N, then have the consequences in the decomposition, in essence, that is, up to additive constants, the lengths
So that the total number of significant coefficients is maintained. The consequences in the decomposition usually are better suited for further processing such as compression or search for specific features than the raw output signal.
Modifications
The polyphase decomposition of the output signal can also be made to a different block size than 2 s, the corresponding hair matrix is to require that it is an orthogonal matrix and its first line consists of all entries 1 / √ s. Meet this requirement, the matrices of the discrete cosine transform, and the Walsh -Hadamard transformation.
The Haar wavelet transform corresponds to a DCT transform for block size s = 2, which is applied sequentially in horizontal and vertical direction in the image = pixel rectangle.