Optimized 2D wavelet transform using FFT

Question

I'm currenty aiming to optimize my fast wavelet transform (FWT) algorithm for 2D signals (images). It works as follows:

• one iteration of 1D FWT does convolution of 1D input data with a selected 1D filter (lengths from 2 to approx. 60) and downsamples the result
• algorithm for 2D transform does 1D FWT across all rows and then all columns of the input image
• it iterates if more levels are desired

The transform is a part of interactive application that demonstrates wavelets and their use. It works fairly fast and usually responds in real time to user's interactions. But if the filter is very long some performance issues occur. I've read that using Fast Fourier Transorm (FFT) instead of convolution is effective for long enough filters.

I've already implemented the 1D FFT, but the question is how to use it for maximum efficiency? Should I transform the input data before single 1D FWT, then perform convolution (which corresponds to multiplication in frequency domain), and then transform the data back using inverse FFT? Also, how is the multiplication done exactly? For example, the input data of length 256 and filter of length 4 are both transformed using FFT and then only the first 4 values of input data are multiplied before transforming the data back? I'm struggling a little bit on the details and would very much appreciate any insight into this.

EDIT: I've figured out that in my case I'm after circular convolution, therefore the filter should be zero padded so that its length is the same as length of the input data. But my question about efficiency still holds. How should I use FFT for FWT computation in order to be beneficial?

Answer 1

I'm still not convinced you are spending your time optimally. Probably you would get better gains doing other optimizations. Already 10-15 taps are considered very long wavelet filters for most applications that I have seen. But nevermind that I will try and answer your question.

---

You can do two different approaches

1. You could do it one level at a time.
2. Everything at once.

There are drawbacks and gains from either of them. I will start with the first one.

If you go for one level at a time:

• You zero pad filters to be equal lenght as the rows and columns. Also make sure you pad so the filter gets in the middle.
• FFT the padded filters and corresponding image dimension. If width $\neq$ height you would need to do 2 FFTs per filter one of each dimension length.
• Pointwise multiplication of the FFTs of filter and image.
• Inverse FFT of the product image.
• Downsample product image in the dimension you transformed.
• Repeat for the next dimension.
• Repeat for all levels.

Notice that this approach will involve a set of iFFTs and FFTs at each level. That would be double-bad.

The everything-at-once approach:

• Same as above but instead of iFFT and decimating each level to just FFT back again on the decimated signal you just multiply several times with the filter and do iFFT and decimate 2,4,8 times et-cetera. Then you only need to do one set of FFTs (at the start) but still a full set of iFFTs for each level.

Also the multiplications while in the Fourier domain will be more computationally expensive than ordinary multiplications as the fourier components will be $\in \mathbb{C}$ but filter and image coefficients $\in \mathbb{R}$ ( I guess ) and you would also likely need higher numerical precision to get the same error.