.: Click here to download :.
The FFW package is an FFT-based algorithm for a fast 2D convolution using the overlap-add method.
The overlap-add method is based on the fundamental technique in DSP: decompose the signal into simple
components, process each of the components in some useful way, and recombine the processed components into
the final signal. This is possible since the convolutional operator is linear. The FFW package works
similarly to fftfilt function (Matlab Image Processing Toolbox) but in a deeper way: all possible
lengths for vectors are considered and not only lengths which are powers of two. This is highly
necessary since the FFTW package ( for more details visit
http://www.fftw.org ) includes codelets
optimized also for other fixed sizes. Codelets are produced automatically by the FFTW codelet generator:
you can add your own codelets and re-calculate the execution times for each FFT.
The execution times for:
- FFT of real 1D vectors
- FFT of complex 1D vectors
- IFFT of complex 1D vectors
The FFW package can be easily used to improve speed performances of:
- 2D convolution (Matlab function conv2)
- 2D filtering (Matlab function filter2)
- 2D cross-correlation (Matlab function xcorr2)
- Normalized cross-correlation (Matlab function normxcorr2)
How does FFW package work?
In order to find the best parameters for overlap-add method an exhaustive search on 2D matrices would not be possible. The computational cost of FFT2 operator is done decomposing it into the computational costs of two series of FFTs on monodimensional arrays. For example, if you want to calculate the FFT2 computational cost using a matrix N x M as input, you will perform the following sum: N*cost(FFT(M)) + M*cost(FFT(N)) where cost(FFT(X)) is the computational cost of FFT operator using as input a vector whose length is X. The computational cost of FFT for a real vector is, in general, different from the cost of FFT for a complex vector. For this reason more than one choice is possible: you can choose the first dimension along which you can apply the FFT operator. Analogous considerations can be made for IFFT operator.
After the minimum computational cost has been found, a finer tuning is possible: the FFW algorithm makes a quasi-exhaustive search using an optimized algorithm. The fine-tuning option requires a lot of time but it is recommended for high-performances FFT-based filtering. Of course, this option has sense only when you have to do several convolution products.
If both input images are real FFW algorithm uses 'symmetric' option when using IFFT operator. The optimized parameters for FFW algorithm depend only on sizes of input matrices and on their values (real or complex). If the same filter has to be applied to several images, its FFT2 value can be determined only one time, saving computational time. In this case (the same filter applied to several images) the determination of optimized parameter must not take into account the computational cost of such operation, since it is done only once. FFW algorithm can also work in time domain: this choice is necessary for small filter kernel, using standard conv2 built-in Matlab function.
Index Terms: Matlab, source, code, conv, conv2, fft, fft2, convolution, correlation, normalized cross-correlation, filtering, filter, filters, fast fourier transform, kernel.
 |
Figure 1. Lucky Luke |
||
|
A useful package for a fast and optimized 2D filtering. |
|||
|
|
|||
|
Release |
Date |
Major features |
|
|
3.1 |
2006.12.19 |
|
|
|
3.0 |
2006.12.18 |
|
|
|
2.0 |
2006.09.09 |
|
|
|
1.0 |
2006.09.03 |
|
|
This software is completely free.
The authors have no relationship or partnership
with The Mathworks. All the code provided is written in Matlab
language (M-files and/or M-functions), with no dll or other
protected parts of code (P-files or executables). The code was
developed with Matlab 14 SP1.
The code provided has to be considered "as is" and it is without any kind of warranty. The
authors deny any kind of warranty concerning the code as well
as any kind of responsibility for problems and damages which may
be caused by the use of the code itself including all parts of
the source code.
