Skip to content
Search

Wavelet Transform

lastmod 2021-07-05created 2014-09-0148 edits

(Stationary wavelet transform (SWT) and Discrete wavelet transform (DWT) both redirect here.)

Image recon- struction Scheme of decomposition up to the second level High-level data flow

In mathematics, a wavelet series is a representation of a square-integrable function by an orthonormal series generated by a wavelet.

Wavelet transforms can compose models of signals, systems, and processes from a set of special signals. These special signals are called wavelets; taking a single small, locally existing wave (wavelet) as a pattern, it represents an arbitrary waveform by shifting it or by scaling it up and down.

The mathematical theory preceding wavelet transform theory goes back much further. In 1807, Joseph Fourier devised Fourier analysis, which can represent a signal as a superposition of sine and cosine waves. Wavelets were first mentioned as a mathematical subject in the appendix of Harr's 1909 dissertation. The Harr wavelet had the property of vanishing completely outside a finite interval. Because the Harr wavelet was not a continuously differentiable function, its applications were limited. Afterward, mathematicians' interest shifted from the concept of frequency analysis to scale analysis, for building mathematical structures in which the scale varies. Such scale analysis measures the average perturbation of a signal at different scales, so it is less sensitive to noise. Wavelets have an extremely wide range of applications: they can examine the frequency of a specific part of a signal, smooth a signal containing noise, or find the boundary between signal and noise. They can also be applied to time series analysis, signal compression, fault analysis of control systems, and more.

Overview of the wavelet transform

Wavelet transforms can compose models of signals, systems, and processes from a set of special signals. These special signals are called wavelets; taking a single small, locally existing wave (wavelet) as a pattern, it represents an arbitrary waveform by shifting it or by scaling it up and down. The mathematical theory preceding wavelet transform theory goes back much further. In 1807, Joseph Fourier devised Fourier analysis, which can represent a signal as a superposition of sine and cosine waves. Wavelets were first mentioned as a mathematical subject in the appendix of Harr's 1909 dissertation. The Harr wavelet had the property of vanishing completely outside a finite interval. Because the Harr wavelet was not a continuously differentiable function, its applications were limited. Afterward, mathematicians' interest shifted from the concept of frequency analysis to scale analysis, for building mathematical structures in which the scale varies. Such scale analysis measures the average perturbation of a signal at different scales, so it is less sensitive to noise. Wavelets have an extremely wide range of applications: they can examine the frequency of a specific part of a signal, smooth a signal containing noise, or find the boundary between signal and noise. They can also be applied to time series analysis, signal compression, fault analysis of control systems, and more. The practicality of the wavelet transform was recognized in 1982, when Morlet, a French oil exploration engineer, actually applied it. Through joint research with the theoretical physicist Alex Grossmann, he broadly defined the wavelet transform from the viewpoint of quantum mechanics at the time. The wavelet transform uses a variable mother wavelet function. Long time intervals are used for analyzing more precise low-frequency information, and short intervals are used for high-frequency information. The greatest characteristic of wavelets is that, in addition to the characteristic of Fourier analysis of representing signals in the frequency domain, they enable time-frequency analysis that can also handle temporal or spatial transitions variably at the same time.

Because the Fourier transform contains no time information, it cannot be used for time-frequency analysis. So, by introducing the concept of a time window into the Fourier transform, the STFT, which can reveal time information, can be used. However, the biggest problem of the STFT in time-frequency analysis is that its bases lack similarity. Because the bases of the original Fourier transform are similar, it reacts sensitively to singularities and is used for things such as anomaly detection. In the STFT, however, applying a time window breaks this similarity, which lowers its sensitivity to singularities. So a method was devised for time-frequency analysis without breaking the similarity of the bases, and this is the wavelet transform.

A characteristic of time-frequency analysis using the wavelet transform is that time resolution is high in the high-frequency range, and frequency resolution is high in the low-frequency range. This makes the wavelet transform more effective than the STFT for time-frequency analysis. This is because for a rapidly changing signal, the point (position) of change is important, while for a slowly changing signal, the period or frequency of the change is important.

Stationary wavelet transform

The Stationary wavelet transform (SWT) is a wavelet transform algorithm designed to overcome the lack of translation-invariance of the discrete wavelet transform (DWT).

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 (location in time).

Daubechies wavelet

The Daubechies wavelets, based on the work of Ingrid Daubechies, are a family of orthogonal wavelets defining a discrete wavelet transform and characterized by a maximal number of vanishing moments for some given support. With each wavelet type of this class, there is a scaling function (called the father wavelet) which generates an orthogonal multiresolution analysis.

Wavelet Daubechies 1 (db1) Coefficients

The coefficients of db1 are the same as those of the Haar wavelet.

Haar wavelet

The first DWT was invented by Hungarian mathematician Alfréd Haar.

Haar Coefficients

  • Decomposition low-pass filter
    • h0 = 0.7071067811865476
    • h1 = 0.7071067811865476
  • Decomposition high-pass filter
    • g0 = -0.7071067811865476
    • g1 = 0.7071067811865476
  • Reconstruction low-pass filter
    • h'0 = 0.7071067811865476
    • h'1 = 0.7071067811865476
  • Reconstruction high-pass filter
    • g'0 = 0.7071067811865476
    • g'1 = -0.7071067811865476

Note that 0.7071067811865476 is an approximation of sqrt(1/2)

2D-Haar-Transform

OpenCV must be installed beforehand. Compilation and usage are as follows. 

## Compile: 
nvcc main.cu -lopencv_highgui

## Run:
./a.out [이미지경로] [WAVELET LEVEL] [GPU THREAD COUNT] [PREVIEW FLAG (0 or 1)]

C Code 

/** Equals (sqrt(2) / 2) */
#define MATH_SQRT2_2  (0.7071067811865475244)

#define HAAR_COEFFICIENTS  MATH_SQRT2_2
#define HAAR_LOW0   (HAAR_COEFFICIENTS)
#define HAAR_LOW1   (HAAR_COEFFICIENTS)
#define HAAR_HIGH0  (HAAR_COEFFICIENTS)
#define HAAR_HIGH1  (HAAR_COEFFICIENTS * (-1))

template <typename T>
bool haar_1d(T const * data, std::size_t size, T * result)
{
    assert(data   != nullptr);
    assert(result != nullptr);
    assert(size > 0);

    static std::vector<T> temp;
    static std::size_t    half;
    static std::size_t    step;
    static std::size_t    cursor;

    if (size > temp.size()) {
        temp.resize(size);
    }
    half   = (size >> 1);
    cursor = 0;
    step   = 0;

    for (cursor = 0; cursor < half; ++cursor) {
        step = (cursor << 1);
        // temp[cursor       ] = (data[twice] *  HAAR_LOW0) + (data[twice + 1] *  HAAR_LOW1); // LOW
        // temp[cursor + half] = (data[twice] * HAAR_HIGH0) + (data[twice + 1] * HAAR_HIGH1); // HIGH
        temp[cursor       ] = (data[step] + data[step + 1]) * HAAR_COEFFICIENTS; // LOW
        temp[cursor + half] = (data[step] - data[step + 1]) * HAAR_COEFFICIENTS; // HIGH
    }

    if (result != nullptr) {
        for (cursor = 0; cursor < size; ++cursor) {
            result[cursor] = temp[cursor];
        }
    }

    return true;
}

Documentation

Super-resolution_Algorithm_using_Discrete_Wavelet_Transform_for-17-2-12.pdf
Image super-resolution technique using the discrete wavelet transform
Wavelet_Transform-re19.pdf
Edge detection algorithm using the band characteristics of wavelets
Multimedia_signal_processing_theory_and_practice_-_Wavelet_Transform.zip
Multimedia Signal Processing Theory and Practice - Lecture notes, Chapter 5: Wavelet Transform.
Wavelet_Transform_Module_for_IBM_AIX_Visualization_Data_Explorer.pdf
Wavelet Transform Module for IBM AIX Visualization Data Explorer. (Link)

Project

Project relative site

See also

Favorite site

Sample code

References

  1. Discrete_Wavelet_Transform(DWT)_Filter_Design.pdf ↩

  2. Lecture.2013s.10-The_Discrete_Wavelet_Transform.pdf ↩

  3. Discrete_Haar_Wavelet_Transformation_-_CodeProject.pdf ↩

  4. 2D-Haar-Transform-master.zip ↩

  5. Fwt2d_src.zip ↩

  6. The_Daubechies_D4_Wavelet_Transform.pdf ↩

  7. A_Linear_Algebra_View_of_the_Wavelet_Transform.pdf ↩

author Zer0 sitemap