[DIP] Discrete Wavelet Transform: Wavelet Decomposition

다음은 DWT의 수식이다.

$$ W_\Psi (f)(j,k) = \sum_n f[n] \Psi^*_{j,k} [n] \\ \Psi_{j,k} [n] = \frac{1}{\sqrt{2^j}}\Psi \left( \frac{ n-k2^j }{2^j} \right)$$

 

간단하게는 CWT의 discrete version으로 이해하면 되고, 사실 이를 바탕으로 유도되는 것이긴 하지만...

Multi Resolution Analysis (MRA)에 사용되는 Discrete Wavlet Transform (DWT)는 Wavelet 함수만으로 충분한 CWT와 조금 차이가 있다.

 

Scaling Function 과 Wavelet Function이 두 개 존재하는 DWT 

실제로 DWT에서는 Wavelet 함수 하나만을 사용하기 보다는 Scaling 함수를 추가해서 사용한다.

• 이 Scaling 함수는 signal에 대한 low pass filter 에서 사용되고,
• Wavelet 함수는 high pass filter로 사용되면서
• Wavelet Decomposition이 이루어진다.

dyadic scale 로 Scaling function은 다음과 같음:
$$ \Phi_{j,k} [n] = \frac{1}{\sqrt{2^j}}\Phi \left( \frac{ n-k2^j }{2^j} \right)$$

이는 MRA에서 approximation $V_j$에 대한 basis function을 생성하는데 사용된다.

 

반면, Wavelet 함수는 detail $W_j$에 대한 basis function을 생성하는데 사용된다.

 

Scaling function과 Wavelet function의 관계는 다음과 같다.

이전에 Wavelet을 설명할 때 scale을 $s$로 표현했는데,
사실 문헌에서는 CWT에선 $a$를 DWT에선 $j$가 더 많이 사용한다.
때문에 이 문서에서는 $j$를 사용한다.

2024.09.02 - [.../Signals and Systems] - [SS] Wavelet Transform

[SS] Wavelet Transform

---

Scaling function과 Wavelet function의 관계 (w/ 2-scale relation)

Scaling Function 의 모함수 $\Phi(t)$는 다음의 2-scale equation을 만족해야 함:

$$\Phi(t)= \sqrt{2} \sum_l h_l \Phi(2t-l) \ \Phi_{j,k}[n] = \sum_l h_l \Phi_{j-1,2k+l}[n]$$

• 이는 2배로 scaling한 모함수의 linear combination으로 모함수 자체를 표현할 수 있음을 식으로 나타낸 것임.
• $h_l$은 low pass filter의 $l$-th element 값임.

Wavelet Function 의 모함수 $\Psi(t)$는 다음을 만족해야 함:

$$\Psi(t) = \sqrt{2} \sum_l g_l \Phi(2t-l) \ \Psi_{j,k}[n] = \sum_l g_l \Phi_{j-1, 2k+l} [n]$$

• 이는 Wavelet Function의 모함수가, Scaling function의 2배 scaling한 것을 basis로 하여 high-pass filter의 coefficient인 $g_l$과 결합해 정의됨을 의미함.
• $g_l$은 high pass filter의 $l$-th element 값임.

이들 관계에 의해 filter의 coefficient(계수) 가 결정됨.

 

다음은 Haar filter의 경우를 보여줌.

값이 정확하진 않지만, 2-scale relation 을 Haar 기준으로 정성적으로 보여준다. https://www.slideserve.com/brantj/multiresolution-analysis-and-wavelet-bases-powerpoint-ppt-presentation

 

Haar wavelet에서

• scaling(저주파) 필터 계수 : $\boxed{h_0 = \frac{1}{\sqrt{2}}, \quad h_1 = \frac{1}{\sqrt{2}}}$
• wavelet(고주파) 필터 계수 : $\boxed{g_0 = \frac{1}{\sqrt{2}}, \quad g_1 = -\frac{1}{\sqrt{2}}}$

Scaling function 모함수

• Haar scaling function $\Phi(t)$는 [0,1) 구간에서 1인 step 함수로 정의됨
• two-scale relation:
  • $\boxed{\Phi(t) = \sqrt{2} \left( h_0 \Phi(2t) + h_1 \Phi(2t-1) \right)}$
  • 즉, $\Phi(t) = \sqrt{2}\left( \frac{1}{\sqrt{2}} \Phi(2t) + \frac{1}{\sqrt{2}} \Phi(2t-1) \right) = \Phi(2t) + \Phi(2t-1)$

Wavelet function 모함수

• Haar wavelet function $\Psi(t)$는 [0,0.5) 구간은 +1, [0.5,1) 구간은 -1로 정의됨
• two-scale relation:
  • $\boxed{\Psi(t) = \sqrt{2} \left( g_0 \Phi(2t) + g_1 \Phi(2t-1) \right)}$
  • 즉, $\Psi(t) = \sqrt{2} \left( \frac{1}{\sqrt{2}} \Phi(2t) + \left(-\frac{1}{\sqrt{2}}\right) \Phi(2t-1) \right) = \Phi(2t) - \Phi(2t-1)$

이 Haar filter로부터 MRA basis는 다음이 성립
$$
\boxed{\Phi_{j,k}[n] = \sum_{l=0}^1 h_l \Phi_{j-1,2k+l}[n]}, \quad \boxed{\Psi_{j,k}[n] = \sum_{l=0}^1 g_l \Phi_{j-1,2k+l}[n]}
$$

 

직관적으로 Haar Wavelet에서

• scaling function: 두 구간의 합 (평균 성분)에 해당함
• wavelet function: 두 구간의 차 (변화 성분)에 해당함

사실 수식적인 전개는 ...
대학원 시험이면 모를까,
실제 사용에선 거의 구현된 function을 이용하는게
대부분이고 API를 이해하고 입출력을 잘 사용하면 끝이다.
filter bank 와 어떻게 wavelet decomposition이 되는지만 파악해도된다.

---

Filter bank

Filter bank는
wavelet decomposition이나 wavelet reconstruction, MRA에서
signal를 여러 주파수 대역으로 나누거나 합성하기 위해 설계된 필터 집합을 가리킴.

 

Filter bank와 관련하여 앞서 다룬 Scaling 함수와 Wavelet 함수의 내용 중 반드시 기억해야할 것은 다음과 같음:

• Scaling Function $\Phi_{j,k}[n]$은 approximation coefficients (low freq. 성분)를 계산하는데 사용됨.
• Wavelet Function $\Psi_{j,k}[n]$은 detail coefficients (hihg freq. 성분)를 계산하는데 사용됨.

Haar, Daubechies, Symlets, Coiflets 등 다양한 wavelet 이 사용가능하며,
이들 각각은 2-scale relation에 의해 고유한 $h_l$과 $g_l$의 필터계수를 가짐.

pywt.Wavelet('haar').filter_bank 나
pywt.Wavelet('db2').filter_bank 등으로
  Filter bank의 실제 필터 계수값들을 확인 가능.
(dec_lo, dec_hi, rec_lo, rec_hi)

---

Wavelet Decomposition

Scale $j$가 커질수록 low freq. 에 해당하는 wavelet이 되기 때문에,
MRA의 경우

• 초반에는 high freq.를 낮은 주파수 해상도로 분석 (주파수축에 대해서 coarse하게, 시간축에서는 fine)하고
• 점점 분해를 많이 할수록 low freq.성분을 높은 주파수 해상도로 분석(주파수축에 대해서 fine, 시간축에서는 coarse)하게 된다.

orthogonal basis와 inner product로 wavelet transform의 계수를 구하는 대신,

실제 구현에서는 high pass filter( wavelet 함수로 결정)와 low pass filter (scaling 함수로 결정)의 kernel $g$와 $h$를 reflect시킨 후 convolution을 하는 것으로 되어있는 경우 많음:

(영상처리나 ML에선 사실상 convolution이 아닌 cross-correlation이 더 많은데 DWT 라이브러리들은 반대임)

Mallat 알고리즘 (1988/89)

$*$(convolution)으로 Wavelet Decomposition은 다음과 같이 진행됨:

1. $A_0 = x[n], j=0$ 

2. $A_{j+1}[k] = (A_j * h_{reflected})[2k], D_{j+1}[k] = (A_j * g_{reflected})[2k]$

3. $j=j+1$

4. 정해진 Level 과 j가 같아질 때까지 2번을 recursive하게 반복.

 

즉, 다음이 성립
$$A_j = A_{j+1} \oplus D_{j+1} \\ A_{j} \supset A_{j+1} $$

(filter bank 관점에서,  decomposition의 level이 올라갈수록 low freq.부분이 점점 더 세밀하게 분해됨을 의미함)

 

1D에서의 Wavelet Decomposition이 진행은 다음과 같음.

factor-2 의 down sampling이 왼쪽에서 명확히 들어나진 않지만, 오른쪽에서 보면 길이가 1/2로 줄어드는 것을 확인할 수 있음: https://ataspinar.com/posts/a-guide-for-using-the-wavelet-transform-in-machine-learning/

 

2d signal (e.g. Image) 에서는 다음과 같음:

https://www.researchgate.net/figure/D-DWT-with-3-Level-decomposition_fig1_251938085

 

 

decomposition할 때 filter kernel과 reconstruction할 때의 filter kernel은 다름:

• orthogonal wavelet의 경우,
  • reconstruction low-pass 필터는 decomposition low-pass의 reverse-conjugate 형태,
  • reconstruction high-pass 필터는 decomposition high-pass의 reverse-conjugate 형태

PyWavelet으로 다음을 통해 확인해 볼 것:

import pywt
w = pywt.Wavelet('db2')
filters = w.filter_bank
for name, coeffs in zip(['dec_lo', 'dec_hi', 'rec_lo', 'rec_hi'], filters):
    print(f"{name}: {coeffs}")

---

MRA

다음은 time-frequency analysis에서 resolution과 uncertainty를 보여주는 그림임:

c는 Short Time Fourier Transform이고, d가 바로 wavelet을 통한 MRA임

 

다음은 앞서의 Wavelet Decompostion과 MRA의 time-freq. 의 해상도 그림과의 관계를 보여준다.

https://www.researchgate.net/figure/Wavelet-decomposition-of-time-domain-signal_fig2_3839556

 

---

같이 보면 좋은 자료들

https://ataspinar.com/posts/a-guide-for-using-the-wavelet-transform-in-machine-learning/

A guide for using the Wavelet Transform in Machine Learning

https://velog.io/@partyover/DSP-Wavelet-Transform

[DSP] Wavelet Transform (CWT, DWT)

2025.06.29 - [Programming/DIP] - [DIP] Wavelet Transform: PyWavelet

[DIP] Wavelet Transform: PyWavelet

https://youtu.be/y7KLbd7n75g?si=aZNFuPPRyXoQRIfY

 

---