Code covered by the BSD License

Highlights from FFW Fastest Filtering in the West

5.0
5.0 | 3 ratings Rate this file 16 Downloads (last 30 days) File Size: 98.1 KB File ID: #12171

FFW Fastest Filtering in the West

Luigi Rosa (view profile)

05 Sep 2006 (Updated )

Fast 2D convolution - filtering

File Information
Description

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
have been calculated with the script provatempo2.m from length N = 3 up to length N = 2048. A finer determination of such times can be done using PAPI for Matlab ( available here or at http://icl.cs.utk.edu/papi ). A 2D FFT (see Matlab command fft2) is decomposed into several 1D FFTs: the FFT operator for an N-dimensional array can in fact be splitted into several 1-dimensional FFTs of monodimensional arrays. The FFW algorithm automatically selects which is the best choice (first dimension, second dimension and best lengths for overlap-add method) and calculates the 2D convolution.

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)

Index Terms: Matlab, source, code, conv, conv2, fft, fft2, convolution, correlation, normalized cross-correlation, filtering, filter, filters, fast fourier transform, kernel.

For more details please visit
http://www.advancedsourcecode.com/ffw.asp

Luigi Rosa
Via Centrale 35
67042 Civita Di Bagno
L'Aquila ITALY
mobile +39 3207214179
web site http://www.advancedsourcecode.com

MATLAB release MATLAB 7.0.1 (R14SP1)
Tags for This File   Please login to tag files.
 Please login to add a comment or rating.
Comments and Ratings (5)
06 Mar 2011 Felipe G. Nievinski

Felipe G. Nievinski (view profile)

The FFTw now comes with Matlab.

Comment only
27 Jul 2010 Dung Chu

Dung Chu (view profile)

Great! I got 100% speedup compared to conv2 with image of 720x480 and gabor filter of 20x20

Comment only
29 Oct 2007 Xiao-Tao Xie

aha, so quickly!
good

15 Sep 2007 David Kolin

Big speed improvement over Matlab's builtin conv2 function. Highly recommended.

14 Jun 2007 Nick Clark

Why has nobody reviewed this yet!?!?! A little slow on the small arrays but destroys matlab's built in conv2 on very large 2D arrays. Well done. Useful indeed

Contact us