numerical methods - C Code Wavelet Transform and Explanation

Question

I am trying to implement a wavelet transform in C and I have never done it before. I have read some about Wavelets, and understand the 'growing subspaces' idea, and how Mallat's one sided filter bank is essentially the same idea.

However, I am stuck on how to actually implement Mallat's fast wavelet transform. This is what I understand so far:

1. The high pass filter, h(t), gives you the detail coefficients. For a given scale j, it is a reflected, dilated, and normed version of the mother wavelet W(t).

2. g(t) is then the low pass filter that makes up the difference. It is supposed to be the quadrature mirror of h(t)

3. To get the detail coefficients, or the approximation coefficients for the jth level, you need to convolve your signal block with h(t) or g(t) respectively, and downsample the signal by 2^{j} (ie take every 2^{j} value)

However these are my questions:

1. How can I find g(t) when I know h(t)?

2. How can I compute the inverse of this transform?

Do you have any C code that I can reference? (Yes I found the one on wiki but it doesn't help)

What I would like some code to say is:

A. Here is the filter

B. Here is the transform (very explicitly) C.) Here is the inverse transform (again for dummies)

Thanks for your patience, but there doesn't seem to be a Step1 - Step2 - Step3 -- etc guide out there with explicit examples (that aren't HAAR because all the coefficients are 1s and that makes things confusing).

Answer 1

the Mallat recipe for the fwt is really simple. If you look at the matlab code, eg the script by Jeffrey Kantor, all the steps are obvious.

In C it is a bit more work but that is mainly because you need to take care of your own declarations and allocations.

Firstly, about your summary:

1. usually the filter h is a lowpass filter, representing the scaling function (father)
2. likewise, g is usually the highpass filter representing the wavelet (mother)
3. you cannot perform a J-level decomposition in 1 filtering+downsampling step. At each level, you create an approximation signal c by filtering with h and downsampling, and a detail signal d by filtering with g and downsampling, and repeat this at the next level (using the current c)

About your questions:

1. for a filter h of an an orthogonal wavelet basis, [h_1 h_2 .. h_m h_n], the QMF is [h_n -h_m .. h_2 -h_1], where n is an even number and m==n-1
2. the inverse transform does the opposite of the fwt: at each level it upsamples detail d and approximation c, convolves d with g and c with h, and adds the signals together -- see the corresponding matlab script.

Using this information, and given a signal x of len points of type double, scaling h and wavelet g filters of f coefficients (also of type double), and a decomposition level lev, this piece of code implements the Mallat fwt:

double *t=calloc(len+f-1, sizeof(double));
memcpy(t, x, len*sizeof(double));        
for (int i=0; i<lev; i++) {            
    memset(y, 0, len*sizeof(double));
    int len2=len/2;
    for (int j=0; j<len2; j++)           
        for (int k=0; k<f; k++) {          
            y[j]     +=t[2*j+k]*h[k];      
            y[j+len2]+=t[2*j+k]*g[k];      
        }
    len=len2;                            
    memcpy(t, y, len*sizeof(double));    
}
free(t);

It uses one extra array: a 'workspace' t to copy the approximation c (the input signal x to start with) for the next iteration.

See this example C program, which you can compile with gcc -std=c99 -fpermissive main.cpp and run with ./a.out.

The inverse should also be something along these lines. Good luck!