2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Most dyadic discrete wavelets transforms are already faster than FFT $\mathcal{O}(n)$ vs $\mathcal{O}(n\log(n))$ so I don't see why you would want to do that. Yes maybe it makes sense if the wavelet filters are really large but most are not. If you are looking for speed-ups maybe "lifting transform" factorizations can be of interest. $\endgroup$ Jan 3, 2016 at 20:28
  • $\begingroup$ If the filters are large then there's a question why you are using wavelets in the first place as they are supposed to capture local features and the longer the filters the less local the features captured will be. $\endgroup$ Jan 3, 2016 at 20:36
  • $\begingroup$ @mathreadler Thanks for commenting. I know that wavelets are used primarly for capturing details. But as I was implying the application I'm working on is focused on demonstrating wavelets for teaching purposes, therefore it should present wide variety of filters for different usage in image processing. As for the speed-up, I've read in the article about optimizing FWT explaining that for filters of length at least 16 it is convenient to use FFT based wavelet transform (it makes sense if you compare the complexity of the two algorithms). $\endgroup$
    – SysGen
    Jan 3, 2016 at 21:52

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, I'll accept it. I've optimized the algorithm as follows: One iteration of 1D FWT does FFT of 1D input data and then muliplies it with pre-FFT 1D filter (instead of convolving in spatial domain). Afterwards it transforms the data backwards using IFFT and finally downsamples the result. This works fine, although it doesn't really seem very much optimized (as you suggested). $\endgroup$
    – SysGen
    Jan 5, 2016 at 13:47
  • $\begingroup$ (cont.) This approach provides faster results for filters of length 64, about the same results for 32 long filters and slower for shorter filters. It might be possible to optimize the algorithm even more so that it is usable for lengths >=16 (according to literature), but it doesn't seem that worthy to me. Thanks again for your time. $\endgroup$
    – SysGen
    Jan 5, 2016 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.