Skip to content

Wavelet Transform

(Stationary wavelet transform (SWT), Discrete wavelet transform (DWT) 모두 이 곳으로 리다이렉트 된다.)

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

수학에서 웨이블릿 수열은 웨이블릿이 생성한 직교정규화 수열에 의해서 제곱해서 적분가능한 함수의 표현이다.

웨이블릿 변환(wavelet transforms)은 신호, 시스템, 프로세스의 모델을 특수한 신호의 집합으로 구성할 수 있다. 이 특수한 신호를 웨이블릿이라고 부르고, 국부적으로 존재하는 어떤 하나의 작은 파(wavelet)를 패턴으로 하여 이것을 천이시키거나 확대, 축소의 스케일(scale)을 통하여 임의의 파형으로 표현한 것이다.

웨이블릿 변환 이론에 앞선 수학적 이론은 훨씬 이전으로 거슬러 올라간다. 즉, 1807년 Joseph Fourier는 하나의 신호를 정현파와 여현파로 중첩시켜 표현할 수 있는 Fourier 해석을 창안하였다. 1909년의 Harr의 학위논문 부록에 제시된 웨이블릿이 처음으로 수학적 과제로 언급되었다. Harr 웨이블릿은 유한한 구간 밖에서는 완전히 소멸되는 특성을 갖고 있었다. Harr 웨이블릿은 연속 미분 가능한 함수가 아니었으므로 응용에 제한이 있었다. 이후 수학자들의 관심은 주파수 해석의 개념으로부터 스케일이 변화하는 수학적 구조를 생성하기 위한 스케일 해석으로 이행해 갔다. 이러한 스케일 해석은 서로 다른 스케일에서의 신호의 평균 섭동을 측정하므로 노이즈에 덜 민감하다. 웨이블릿의 응용 범위는 지극히 넓어서 신호의 특정 부분의 주파수를 조사할 수 있으며, 노이즈를 포함한 신호를 평활하거나, 신호와 노이즈의 경계를 구할 수 있다. 시계열의 해석, 신호의 압축, 제어 시스템의 고장 해석 등에도 응용할 수 있다.

웨이블릿 변환의 개요

웨이블릿 변환(wavelet transforms)은 신호, 시스템, 프로세스의 모델을 특수한 신호의 집합으로 구성할 수 있다. 이 특수한 신호를 웨이블릿이라고 부르고, 국부적으로 존재하는 어떤 하나의 작은 파(wavelet)를 패턴으로 하여 이것을 천이시키거나 확대, 축소의 스케일(scale)을 통하여 임의의 파형으로 표현한 것이다. 웨이블릿 변환 이론에 앞선 수학적 이론은 훨씬 이전으로 거슬러 올라간다. 즉, 1807년 Joseph Fourier는 하나의 신호를 정현파와 여현파로 중첩시켜 표현할 수 있는 Fourier 해석을 창안하였다. 1909년의 Harr의 학위논문 부록에 제시된 웨이블릿이 처음으로 수학적 과제로 언급되었다. Harr 웨이블릿은 유한한 구간 밖에서는 완전히 소멸되는 특성을 갖고 있었다. Harr 웨이블릿은 연속 미분 가능한 함수가 아니었으므로 응용에 제한이 있었다. 이후 수학자들의 관심은 주파수 해석의 개념으로부터 스케일이 변화하는 수학적 구조를 생성하기 위한 스케일 해석으로 이행해 갔다. 이러한 스케일 해석은 서로 다른 스케일에서의 신호의 평균 섭동을 측정하므로 노이즈에 덜 민감하다. 웨이블릿의 응용 범위는 지극히 넓어서 신호의 특정 부분의 주파수를 조사할 수 있으며, 노이즈를 포함한 신호를 평활하거나, 신호와 노이즈의 경계를 구할 수 있다. 시계열의 해석, 신호의 압축, 제어 시스템의 고장 해석 등에도 응용할 수 있다. 웨이블릿 변환은 1982년 프랑스의 석유 탐사 기사 Morlet이 실제로 응용하면서부터 그 실용성이 인정되었다. 이론물리학자인 Alex Grossmann과 협동 연구를 수행함으로써 당시 양자역학의 관점에서 웨이블릿 변환을 폭넓게 정의하였다. 웨이블릿 변환은 가변의 웨이블릿 모함수를 사용한다. 좀더 높은 정도의 저주파수 정보의 분석을 위해서는 장시간의 간격을 이용하며, 고주파수 정보를 위해서는 짧은 간격이 이용된다. 이러한 웨이블릿의 가장 큰 특징은 주파수 영역에서 신호를 표현하는 Fourier 해석의 특징을 비롯하여, 시간적 또는 공간적 추이도 동시에 가변적으로 다룰 수 있는 시간-주파수 해석이 가능하다는 것이다.

Fourier 변환은 시간 정보를 가지고 있지 않기 때문에, 시간-주파수 해석에 이용할 수 없다. 그래서 Fourier 변환에 시간 윈도우의 개념을 도입함으로써, 시간 정보를 알 수 있는 STFT를 이용할 수 있다. 그러나 STFT의 시간-주파수 해석에 있어서의 가장 큰 문제는 기저의 상사성이 없는 것이다. 원래의 Fourier 변환은 기저가 상사이기 때문에 특이점에 민감하게 반응하여 이상 검출 등에 이용되고 있다. 그러나, STFT에서는 시간 윈도우를 부여함에 따라 상사성이 무너져, 특이점에 대하여 감도가 떨어진다. 그래서 기저의 상사성을 무너뜨리지 않고 시간-주파수 분석을 하는 방법이 고안되었는데 이것이 웨이블릿 변환이다.

웨이블릿 변환에 의한 시간-주파수 해석의 특징은 고주파수 영역에서는 시간 분해능이 높고, 저주파 영역에서는 주파수 분해능이 높다는 것이다. 이를 통하여 웨이블릿 변환은 STFT보다 시간-주파수 해석에서 효과적이다. 급격하게 변화하는 신호는 그 변화 시점(위치)가 중요하며, 완만하게 변화하는 신호는 그 변화의 주기 또는 주파수가 중요하기 때문이다.

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

db1의 계수는 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

참고로 0.7071067811865476는 sqrt(1/2)의 근사 값이다

2D-Haar-Transform

OpenCV를 미리 설치해야 하며, 컴파일 및 사용방법은 아래와 같다. 

## 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
이산 웨이블릿 변환을 이용한 영상의 초고해상도 기법
Wavelet_Transform-re19.pdf
웨이블릿의 대역 특성을 이용한 윤곽선 검출 알고리즘
Multimedia_signal_processing_theory_and_practice_-_Wavelet_Transform.zip
멀티미디어 신호처리 이론 및 실습 - 강의자료 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 ↩