Discrete Wavelet Transform (DWT)
The Discrete Wavelet Transform (DWT) is a mathematical transform used to break a signal or data into different frequency components, which can then be analyzed or processed. It is particularly useful in signal processing, image compression (like JPEG2000), and denoising.
Simple Math Behind Discrete Wavelet Transform (DWT)
Let’s break it down step by step with simple math to help understand the underlying principles.
1. Wavelet Basics
A wavelet is a small wave, and its key feature is that it has limited duration. The main idea behind wavelet transforms is to break down a signal into components that are localized in both time and frequency.
The two main components of the wavelet transform are:
- Scaling Function (Low-pass filter)
- Wavelet Function (High-pass filter)
These functions are used to analyze different parts of the signal at various resolutions.
2. Convolution with Filters
The DWT involves convolving the signal with two filters:
- A low-pass filter (scaling filter) ( h[n] )
- A high-pass filter (wavelet filter) ( g[n] )
For a discrete signal ( x[n] ), we use the convolution to compute the approximation (low-frequency component) and detail (high-frequency component) at each level.
Low-pass and High-pass Filtering:
The low-pass filter computes the approximation (smooth part of the signal):
A[n] = ∑â‚– x[k] h[n - k]The high-pass filter computes the detail (rapid changes or "edges"):
D[n] = ∑â‚– x[k] g[n - k]Where ( A[n] ) represents the approximation and ( D[n] ) represents the detail of the signal.
3. Decimation (Downsampling)
After filtering, the output is downsampled (decimated) by a factor of 2. This means we keep only every second sample of the output:
A[n] = decimate(∑â‚– x[k] h[n - k])D[n] = decimate(∑â‚– x[k] g[n - k])This step reduces the size of the data, removing redundant information. The downsampling is performed to focus on lower frequencies and details without losing key signal components.
4. Multi-level Decomposition (Multi-resolution Analysis)
For multi-level decomposition, the approximation ( A[n] ) becomes the input signal for the next level of filtering. This process is repeated for as many levels as needed.
At each level, you continue applying the low-pass and high-pass filters, followed by downsampling. This way, you create a tree of frequency components where:
- Level 1: Approximation and detail.
- Level 2: Approximation of Level 1 and its detail.
- And so on.
5. Example: 1D Discrete Wavelet Transform (DWT)
Let’s consider a simple 1D signal ( x[n] = [1, 2, 3, 4, 5, 6, 7, 8] ).
1. Low-pass filter (scaling function):
h = [1/2, 1/2]2. High-pass filter (wavelet function):
g = [1/2, -1/2]3. Convolution and Downsampling:
* **Approximation**: Convolve ( x[n] ) with ( h ) and downsample.
* **Detail**: Convolve ( x[n] ) with ( g ) and downsample.
Step 1: First Level Filtering
* **Approximation ( A[n] )** (convolution with ( h )):
A[0] = (1 * 1/2) + (2 * 1/2) = 1.5A[1] = (2 * 1/2) + (3 * 1/2) = 2.5A[2] = (3 * 1/2) + (4 * 1/2) = 3.5A[3] = (4 * 1/2) + (5 * 1/2) = 4.5* **Downsample ( A[n] )**: Take every second value to get ( A[n] = [2.5, 4.5] ).
* **Detail ( D[n] )** (convolution with ( g )):
D[0] = (1 * 1/2) - (2 * 1/2) = -0.5D[1] = (2 * 1/2) - (3 * 1/2) = -0.5D[2] = (3 * 1/2) - (4 * 1/2) = -0.5D[3] = (4 * 1/2) - (5 * 1/2) = -0.5* **Downsample ( D[n] )**: Take every second value to get ( D[n] = [-0.5, -0.5] ).
Step 2: Second Level Filtering
Now take the approximation ( A[n] = [2.5, 4.5] ) and apply the same steps (filter and downsample) to further decompose the signal into higher and lower frequencies.
Mathematical Formulation of Inverse Discrete Wavelet Transform (IDWT)
The **Inverse Discrete Wavelet Transform (IDWT)** can be mathematically expressed as follows:
x[n] = upsample(A1[n]) * h[n] + upsample(D1[n]) * g[n]Where:
- A1[n] is the approximation (low-frequency part) of the signal at level 1.
- D1[n] is the detail (high-frequency part) of the signal at level 1.
- h[n] is the low-pass filter (scaling function).
- g[n] is the high-pass filter (wavelet function).
The * symbol represents the convolution operation.
To reconstruct the original signal from the approximation and detail components, the approximation is upsampled and convolved with the low-pass filter \( h[n] \), while the detail is upsampled and convolved with the high-pass filter \( g[n] \). Finally, the results are added together to obtain the reconstructed signal.
Conclusion
The Discrete Wavelet Transform (DWT) involves two key steps: filtering with wavelet (low-pass and high-pass filters) and downsampling. By performing this repeatedly, we can analyze the signal at multiple levels of resolution, capturing both low-frequency and high-frequency information. This process is useful in tasks such as signal compression, feature extraction, and noise reduction.