## CFFTWWrapper: Fast Fourier Transform in Image Apprentice

April 9, 2011 Leave a comment

# ‘CFFTWWrapper’

# MIT’s FFTW based Plugin for Image Apprentice

**Download Source Code** here.

**Download Precompiled binaries** here.

Following text describes a plugin to perform Fast Fourier Transform and Inverse Fast Fourier Transform on 2D data.

This document describes how the FFTW version 3.0.1 based Plugin for Image Apprentice works. For this, I have developed an easy to use wrapper class around FFTW named CFFTWWrapper. At the time of writing, the latest version of Image Apprentice available is version 0.5.0.3.

This document assumes that you have gone through the documentation of Image Apprentice and you are comfortable working with Image Apprentice’s Plugin Development Kit.

The purpose of the class CFFTWWrapper is to build an easy to use interface around the FFTW Library. The class in no way utilizes the full potential of the FFTW Library but completely suffices the need of this plugin, namely computing FFT and Inverse FFT in 2D for a given Image Processing Algorithm. The algorithm/filter can be implemented in-between the FFT and iFFT steps using convolution and de-convolution.

There are 5 steps involved in applying Fast Fourier Transform using FFTW:

- Declare complex numbers to contain the image data allocate memory for them.
- Create a plan to implement FFT in ‘n’ dimensions; this plugin does it in 2 dimensions.
- Fill up the complex variable’s real and imaginary parts. Real part gets the image intensities and complex part will be zero.
- Excute the plan.
- Destroy the plan to free the memory used in the plan. Utilize the complex numbers as per need for filter making.

**STEP 1:**** **

In ‘processor.h’, following pointers are declared:

fftw_complex *inR, *outR, *inG, *outG, *inB, *outB;

In addition, an object of the class CFFTWWrapper has been created to get access to the functions of FFTW Library.

CFFTWWrapper m_fftw;

The pointers are of type fftw_complex, a data type defined in the FFTW to contain real and imaginary parts of a complex number as double data type.

*Here onwards, rest of the code goes in the ‘processor.cpp’ file.*

In the member function DoFFT(), these pointers are allocated memory of size same as the physical dimensions of the operand image utilizing the member function AllocateMemory of class CFFTWWrapper.

int N = width*height; // physical dimensions of image.

inB = m_fftw.AllocateMemory(inB, N);

**STEP 2:**** **

The next step is to create a plan to compute a 2D FFT, which is an object that contains all the data that FFTW needs to compute the FFT. This function creates the plan for 2D FFT:

void CFFTWWrapper::CreatePlan(fftw_plan* plan,

int width, int height,

fftw_complex* in, fftw_complex* out,

int direction)

The first argument is the reference to a plan object as defined in FFTW Library fftw_plan, The next two arguments, width and height, are the size (width, height) of the transform you are trying to compute. The arguments nx and ny can be any positive integer.

The next two arguments are pointers to the input and output arrays of the transform. These pointers can be equal, indicating an *in-place* transform. In this plugin, they are different (inB/outB etc.).

The fourth argument, direction, can be either FFT_DIRECTION_FORWARD (-1) or FFT_DIRECTION_BACKWARD (+1), and indicates the direction of the transform you are interested in; *technically, it is the sign of the exponent in the transform.*

The data in the in/out arrays is overwritten during planning, so such planning should be done before the input is initialized by the user.

**STEP 3:**** **

Fill up the real and Imaginary parts on inB, inG and inR complex arrays utilizing SetReal() and SetComplex() member functions of class CFFTWWrapper.

for (int j=0; j<height; j++) // span rows

{

offset = j*width;

for(int i=0; i<width; i++) // span columns

{

index = offset + i;

// Blue Real part

m_fftw.SetReal(inB, index, (double) buffer[count++]);

// Blue Imaginary part

m_fftw.SetImaginary(inB, index, 0.0);

// Green Real part

m_fftw.SetReal(inG, index, (double) buffer[count++]);

// Green Imaginary part

m_fftw.SetImaginary(inG, index, 0.0);

// Red Real part

m_fftw.SetReal(inR, index, (double) buffer[count++]);

// Red Imaginary part

m_fftw.SetImaginary(inR, index, 0.0);

}

}

Multiplication with pow(-1,i+j) of the buffer array performs the centering (not shown here but implemented in the source code).

**STEP 4:**** **

Once the plan has been created, you can use it as many times as you like for transforms on the specified in/out arrays, computing the actual transforms via void ExecutePlan(fftw_plan* plan):

// Execute FFTW Plans

m_fftw.ExecutePlan(&pB);

**STEP 5:**

When you are done with the plan, you deallocate any used memory in the plan by calling:

// Once executed, destroy the plans to release it’s memory

m_fftw.DestroyPlan(&pB);

This should be enough to perform FFT operation over the image date in the Plugin Development Kit for Image Apprentice.

Users should note that FFTW computes an unnormalized DFT. Thus, computing a forward followed by a backward transform (or vice versa) results in the original array scaled by n. For the definition of the DFT, see Section 4.7 [What FFTW Really computes], page 39 in the FFTW documentation.

Computing the inverse FFT is straight-forward if you have understood the above documentation. Just go through the code of member function DoIFFT() in ‘processor.cpp’ of this plugin. Just keep in mind that complex arrays allocated with AllocateMemory() while doing FFT should be deallocated by DeAllocateMemory() after doing inverse FFT.

As usual, after compilation and building the plugin, you have to copy the IAPlugin.dll file (present in Debug/Release folder as per your project configuration) and paste it in the folder that you are using as Plugin folder for Image Apprentice. As a default it is a folder next to the application (‘ia.exe’) named as “Plugins”.

Other than this, as the plugin is dependent on the FFTW library, ** along with the ‘IAPlugin.dll’ plugin, you have to paste the ‘fftw3.dll’ file present in the “fftw301” folder inside the source code directory to the Plugins folder**. This

**MUST**be kept in mind before using the FFTW based plugin.

**Regarding FFTW**: The FFTW package was developed at MIT by Matteo Frigo and Steven G. Johnson.

Further references:

- http://www.fftw.org/install/windows.html
- http://www.fftw.org/fftw3.pdf
- Image Apprentice Documentation.