Wavelet transform

Last updated
An example of the 2D discrete wavelet transform that is used in JPEG2000. Jpeg2000 2-level wavelet transform-lichtenstein.png
An example of the 2D discrete wavelet transform that is used in JPEG2000.

In mathematics, a wavelet series is a representation of a square-integrable (real- or complex-valued) function by a certain orthonormal series generated by a wavelet. This article provides a formal, mathematical definition of an orthonormal wavelet and of the integral wavelet transform.

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure (algebra), space (geometry), and change. It has no generally accepted definition.

Real number Number representing a continuous quantity

In mathematics, a real number is a value of a continuous quantity that can represent a distance along a line. The adjective real in this context was introduced in the 17th century by René Descartes, who distinguished between real and imaginary roots of polynomials. The real numbers include all the rational numbers, such as the integer −5 and the fraction 4/3, and all the irrational numbers, such as 2. Included within the irrationals are the transcendental numbers, such as π (3.14159265...). In addition to measuring distance, real numbers can be used to measure quantities such as time, mass, energy, velocity, and many more.

Complex number Element of a number system in which –1 has a square root

A complex number is a number that can be expressed in the form a + bi, where a and b are real numbers, and i is a solution of the equation x2 = −1. Because no real number satisfies this equation, i is called an imaginary number. For the complex number a + bi, a is called the real part, and b is called the imaginary part. Despite the historical nomenclature "imaginary", complex numbers are regarded in the mathematical sciences as just as "real" as the real numbers, and are fundamental in many aspects of the scientific description of the natural world.

Contents

Definition

A function is called an orthonormal wavelet if it can be used to define a Hilbert basis, that is a complete orthonormal system, for the Hilbert space of square integrable functions.

In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal and unit vectors. A set of vectors form an orthonormal set if all vectors in the set are mutually orthogonal and all of unit length. An orthonormal set which forms a basis is called an orthonormal basis.

Hilbert space inner product space that is metrically complete; a Banach space whose norm induces an inner product (follows the parallelogram identity)

The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions. A Hilbert space is an abstract vector space possessing the structure of an inner product that allows length and angle to be measured. Furthermore, Hilbert spaces are complete: there are enough limits in the space to allow the techniques of calculus to be used.

In mathematics, a square-integrable function, also called a quadratically integrable function or function, is a real- or complex-valued measurable function for which the integral of the square of the absolute value is finite. Thus, square-integrability on the real line is defined as follows.

The Hilbert basis is constructed as the family of functions by means of dyadic translations and dilations of ,

Dyadic transformation the transformation of the unit interval that maps x to 2x mod 1

The dyadic transformation is the mapping

Translation (geometry) in Euclidean geometry, a function that moves every point a constant distance in a specified direction

In Euclidean geometry, a translation is a geometric transformation that moves every point of a figure or a space by the same distance in a given direction.

In operator theory, a dilation of an operator T on a Hilbert space H is an operator on a larger Hilbert space K, whose restriction to H composed with the orthogonal projection onto H is T.

for integers .

If under the standard inner product on ,

this family is orthonormal, it is an orthonormal system:

where is the Kronecker delta.

In mathematics, the Kronecker delta is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:

Completeness is satisfied if every function may be expanded in the basis as

with convergence of the series understood to be convergence in norm. Such a representation of f is known as a wavelet series. This implies that an orthonormal wavelet is self-dual.

In mathematics, a dual wavelet is the dual to a wavelet. In general, the wavelet series generated by a square integrable function will have a dual series, in the sense of the Riesz representation theorem. However, the dual series is not itself in general representable by a square integrable function.

The integral wavelet transform is the integral transform defined as

The wavelet coefficients are then given by

Here, is called the binary dilation or dyadic dilation, and is the binary or dyadic position.

Principle

The fundamental idea of wavelet transforms is that the transformation should allow only changes in time extension, but not shape. This is affected by choosing suitable basis functions that allow for this.[ how? ] Changes in the time extension are expected to conform to the corresponding analysis frequency of the basis function. Based on the uncertainty principle of signal processing,

where t represents time and ω angular frequency (ω = 2πf, where f is temporal frequency).

The higher the required resolution in time, the lower the resolution in frequency has to be. The larger the extension of the analysis windows is chosen, the larger is the value of [ how? ].

Basis function with compression factor.jpg

When Δt is large,

  1. Bad time resolution
  2. Good frequency resolution
  3. Low frequency, large scaling factor

When Δt is small

  1. Good time resolution
  2. Bad frequency resolution
  3. High frequency, small scaling factor

In other words, the basis function Ψ can be regarded as an impulse response of a system with which the function x(t) has been filtered. The transformed signal provides information about the time and the frequency. Therefore, wavelet-transformation contains information similar to the short-time-Fourier-transformation, but with additional special properties of the wavelets, which show up at the resolution in time at higher analysis frequencies of the basis function. The difference in time resolution at ascending frequencies for the Fourier transform and the wavelet transform is shown below.

STFT and WT.jpg

This shows that wavelet transformation is good in time resolution of high frequencies, while for slowly varying functions, the frequency resolution is remarkable.

Another example: The analysis of three superposed sinusoidal signals with STFT and wavelet-transformation.

Analysis of three superposed sinusoidal signals.jpg

Wavelet compression

Wavelet compression is a form of data compression well suited for image compression (sometimes also video compression and audio compression). Notable implementations are JPEG 2000, DjVu and ECW for still images, CineForm, and the BBC's Dirac. The goal is to store image data in as little space as possible in a file. Wavelet compression can be either lossless or lossy. [1]

Using a wavelet transform, the wavelet compression methods are adequate for representing transients, such as percussion sounds in audio, or high-frequency components in two-dimensional images, for example an image of stars on a night sky. This means that the transient elements of a data signal can be represented by a smaller amount of information than would be the case if some other transform, such as the more widespread discrete cosine transform, had been used.

Discrete wavelet transform has been successfully applied for the compression of electrocardiograph (ECG) signals [2] In this work, the high correlation between the corresponding wavelet coefficients of signals of successive cardiac cycles is utilized employing linear prediction.

Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic signals are better compressed by other methods, particularly traditional harmonic compression (frequency domain, as by Fourier transforms and related).

See Diary Of An x264 Developer: The problems with wavelets (2010) for discussion of practical issues of current methods using wavelets for video compression.

Method

First a wavelet transform is applied. This produces as many coefficients as there are pixels in the image (i.e., there is no compression yet since it is only a transform). These coefficients can then be compressed more easily because the information is statistically concentrated in just a few coefficients. This principle is called transform coding. After that, the coefficients are quantized and the quantized values are entropy encoded and/or run length encoded.

A few 1D and 2D applications of wavelet compression use a technique called "wavelet footprints". [3] [4]

Comparison with Fourier transform and time-frequency analysis

TransformRepresentationInput
Fourier transform ξ, frequency
Time-frequency analysis t, time; f, frequency
Wavelet transforma, scaling; b, time

Wavelets have some slight benefits over Fourier transforms in reducing computations when examining specific frequencies. However, they are rarely more sensitive, and indeed, the common Morlet wavelet is mathematically identical to a short-time Fourier transform using a Gaussian window function. [5] The exception is when searching for signals of a known, non-sinusoidal shape (e.g., heartbeats); in that case, using matched wavelets can outperform standard STFT/Morlet analyses. [6]

Other practical applications

The wavelet transform can provide us with the frequency of the signals and the time associated to those frequencies, making it very convenient for its application in numerous fields. For instance, signal processing of accelerations for gait analysis, [7] for fault detection, [8] for design of low power pacemakers and also in ultra-wideband (UWB) wireless communications. [9]

  1. Discretizing of the c-τ-axis

    Applied the following discretization of frequency and time:

    Leading to wavelets of the form, the discrete formula for the basis wavelet:

    Such discrete wavelets can be used for the transformation:

  2. Implementation via the FFT (fast Fourier transform)

    As apparent from wavelet-transformation representation (shown below)

    where c is scaling factor, τ represents time shift factor

    and as already mentioned in this context, the wavelet-transformation corresponds to a convolution of a function y(t) and a wavelet-function. A convolution can be implemented as a multiplication in the frequency domain. With this the following approach of implementation results into:

    • Fourier-transformation of signal y(k) with the FFT
    • Selection of a discrete scaling factor
    • Scaling of the wavelet-basis-function by this factor and subsequent FFT of this function
    • Multiplication with the transformed signal YFFT of the first step
    • Inverse transformation of the product into the time domain results in YW for different discrete values of τ and a discrete value of
    • Back to the second step, until all discrete scaling values for are processed
    There are many different types of wavelet transforms for specific purposes. See also a full list of wavelet-related transforms but the common ones are listed below: Mexican hat wavelet, Haar Wavelet, Daubechies wavelet, triangular wavelet.

See also

Related Research Articles

Fourier analysis Branch of mathematics regarding periodic and continuous signals

In mathematics, Fourier analysis is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fourier, who showed that representing a function as a sum of trigonometric functions greatly simplifies the study of heat transfer.

Wavelet function for integral Fourier-like transform

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one recorded by a seismograph or heart monitor. Generally, wavelets are intentionally crafted to have specific properties that make them useful for signal processing. Using a "reverse, shift, multiply and integrate" technique called convolution, wavelets can be combined with known portions of a damaged signal to extract information from the unknown portions.

Haar wavelet

In mathematics, the Haar wavelet is a sequence of rescaled "square-shaped" functions which together form a wavelet family or basis. Wavelet analysis is similar to Fourier analysis in that it allows a target function over an interval to be represented in terms of an orthonormal basis. The Haar sequence is now recognised as the first known wavelet basis and extensively used as a teaching example.

Fourier transform mathematical transform that expresses a mathematical function of time as a function of frequency

The Fourier transform (FT) decomposes a function of time into its constituent frequencies. This is similar to the way a musical chord can be expressed in terms of the volumes and frequencies of its constituent notes. The term Fourier transform refers to both the frequency domain representation and the mathematical operation that associates the frequency domain representation to a function of time. The Fourier transform of a function of time is itself a complex-valued function of frequency, whose magnitude (modulus) represents the amount of that frequency present in the original function, and whose argument is the phase offset of the basic sinusoid in that frequency. The Fourier transform is not limited to functions of time, but the domain of the original function is commonly referred to as the time domain. There is also an inverse Fourier transform that mathematically synthesizes the original function from its frequency domain representation.

Short-time Fourier transform

The short-time Fourier transform (STFT), is a Fourier-related transform used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time. In practice, the procedure for computing STFTs is to divide a longer time signal into shorter segments of equal length and then compute the Fourier transform separately on each shorter segment. This reveals the Fourier spectrum on each shorter segment. One then usually plots the changing spectra as a function of time.

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

Continuous wavelet transform

In mathematics, the continuous wavelet transform (CWT) is a formal tool that provides an overcomplete representation of a signal by letting the translation and scale parameter of the wavelets vary continuously.

Discrete wavelet transform

In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. As with other wavelet transforms, a key advantage it has over Fourier transforms is temporal resolution: it captures both frequency and location information.

In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of values.

In digital signal processing, upsampling, expansion, and interpolation are terms associated with the process of resampling in a multi-rate digital signal processing system. Upsampling can be synonymous with expansion, or it can describe an entire process of expansion and filtering (interpolation). When upsampling is performed on a sequence of samples of a signal or other continuous function, it produces an approximation of the sequence that would have been obtained by sampling the signal at a higher rate. For example, if compact disc audio at 44,100 samples/second is upsampled by a factor of 5/4, the resulting sample-rate is 55,125.

Gabor transform

The Gabor transform, named after Dennis Gabor, is a special case of the short-time Fourier transform. It is used to determine the sinusoidal frequency and phase content of local sections of a signal as it changes over time. The function to be transformed is first multiplied by a Gaussian function, which can be regarded as a window function, and the resulting function is then transformed with a Fourier transform to derive the time-frequency analysis. The window function means that the signal near the time being analyzed will have higher weight. The Gabor transform of a signal x(t) is defined by this formula:

Continuous wavelets of compact support can be built [1], which are related to the beta distribution. The process is derived from probability distributions using blur derivative. These new wavelets have just one cycle, so they are termed unicycle wavelets. They can be viewed as a soft variety of Haar wavelets whose shape is fine-tuned by two parameters and . Closed-form expressions for beta wavelets and scale functions as well as their spectra are derived. Their importance is due to the Central Limit Theorem by Gnedenko and Kolmogorov applied for compactly supported signals [2].

In the mathematics of signal processing, the harmonic wavelet transform, introduced by David Edward Newland in 1993, is a wavelet-based linear transformation of a given function into a time-frequency representation. It combines advantages of the short-time Fourier transform and the continuous wavelet transform. It can be expressed in terms of repeated Fourier transforms, and its discrete analogue can be computed efficiently using a fast Fourier transform algorithm.

In functional analysis, a Shannon wavelet may be either of real or complex type. Signal analysis by ideal bandpass filters defines a decomposition known as Shannon wavelets. The Haar and sinc systems are Fourier duals of each other.

Overcompleteness is a concept from linear algebra that is widely used in mathematics, computer science, engineering, and statistics. It was introduced by R. J. Duffin and A. C. Schaeffer in 1952.

The wavelet transform modulus maxima (WTMM) is a method for detecting the fractal dimension of a signal.

Fractional wavelet transform (FRWT) is a generalization of the classical wavelet transform (WT). This transform is proposed in order to rectify the limitations of the WT and the fractional Fourier transform (FRFT). The FRWT inherits the advantages of multiresolution analysis of the WT and has the capability of signal representations in the fractional domain which is similar to the FRFT.

In mathematics, in functional analysis, several different wavelets are known by the name Poisson wavelet. In one context, the term "Poisson wavelet" is used to denote a family of wavelets labeled by the set of positive integers, the members of which are associated with the Poisson probability distribution. These wavelets were first defined and studied by Karlene A. Kosanovich, Allan R. Moser and Michael J. Piovoso in 1995–96. In another context, the term refers to a certain wavelet which involves a form of the Poisson integral kernel. In a still another context, the terminology is used to describe a family of complex wavelets indexed by positive integers which are connected with the derivatives of the Poisson integral kernel.

Wavelet packet bases are designed by dividing the frequency axis in intervals of varying sizes. These bases are particularly well adapted to decomposing signals that have different behavior in different frequency intervals. If has properties that vary in time, it is then more appropriate to decompose in a block basis that segments the time axis in intervals with sizes that are adapted to the signal structures.

References

  1. JPEG 2000, for example, may use a 5/3 wavelet for lossless (reversible) transform and a 9/7 wavelet for lossy (irreversible) transform.
  2. A. G. Ramakrishnan and S. Saha, "ECG coding by wavelet-based linear prediction," IEEE Trans. Biomed. Eng., Vol. 44, No. 12, pp. 1253-1261, 1977.
  3. N. Malmurugan, A. Shanmugam, S. Jayaraman and V. V. Dinesh Chander. "A New and Novel Image Compression Algorithm Using Wavelet Footprints"
  4. Ho Tatt Wei and Jeoti, V. "A wavelet footprints-based compression scheme for ECG signals". Ho Tatt Wei; Jeoti, V. (2004). "A wavelet footprints-based compression scheme for ECG signals". 2004 IEEE Region 10 Conference TENCON 2004. A. p. 283. doi:10.1109/TENCON.2004.1414412. ISBN   0-7803-8560-8.
  5. Bruns, Andreas (2004). "Fourier-, Hilbert- and wavelet-based signal analysis: are they really different approaches?". Journal of Neuroscience Methods. 137 (2): 321–332. doi:10.1016/j.jneumeth.2004.03.002. PMID   15262077.
  6. Krantz, Steven G. (1999). A Panorama of Harmonic Analysis. Mathematical Association of America. ISBN   0-88385-031-1.
  7. "Novel method for stride length estimation with body area network accelerometers", IEEE BioWireless 2011, pp. 79-82
  8. Liu, Jie (2012). "Shannon wavelet spectrum analysis on truncated vibration signals for machine incipient fault detection". Measurement Science and Technology. 23 (5): 1–11. doi:10.1088/0957-0233/23/5/055604.
  9. Akansu, A. N.; Serdijn, W. A.; Selesnick, I. W. (2010). "Emerging applications of wavelets: A review" (PDF). Physical Communication. 3: 1. doi:10.1016/j.phycom.2009.07.001.