[Insight-developers] FFTW Is being worked on.

[Hans Johnson]

John,

I just wanted to let you know that we (The University of Iowa Department 
of Psychiatry) are working on an implementation of FFT's for ITK.  We 
are currently building a facade class framework for FFT's so that other 
groups can plug in their favorite FFT algorithms without modifying the 
end application.

We currently have a prototype facade class system working in our C++ 
image library system (which almost parallels the ITK Image framework). 
The prototype currently defaults to using the SGI scsl optimized fft's 
under IRIX, compaq/HP cxml under alpha/Linux, and FFTW under all other 
platforms.  The prototype system has been used extensively in our 
software for the past 4 years under multithreaded (both hand threaded 
and OpenMP threaded) applications.  I have not verified this, but I have 
  heard that the vnl 1D fft algorithms are not thread safe.

One of the problems with FFTW is that you must decide at compile time if 
you want to do single precision or double precision FFT's.  You can not 
mix the two in a single application (but you can change between the two 
by including sfftw.h or dfftw.h and linking against libsfftw.a or 
libdfftw.a).  This is not a major show stopper for most applications, 
because the developers usually does not mix the two.

The biggest hurdle that we are running into for porting this to ITK is 
deciding what to do about memory layouts for doing inplace FFT's.  The 
problem arises in that a real valued spatial domain image needs less 
memory than it's frequency domain representation.  For example, a 
32x32x32 pixel real valued image can be stored in a 34x32x32 memory 
space if you take into account that the FFT of a real spatial domain is 
complex conjugate symetric.  Many FFT image processing algorithms 
require the user to take advantage of such properties to keep the memory 
  useage to a manageable level.

The first implementation of the ITK-FFT's will probably only work on the 
  out of place FFT's and only for FFTW and SGI scsl libraries.  In 
addition, the input spatial domain data must be real valued (i.e. the 
developer will have to explicity convert unsigned char data to floating 
point data before using the FFT facade interface).  The framework will 
also have documentation for how to implement the intel math 
libraries(both linux and windows versions) at a latter date.  Our 
current goal is to have a limited working version of the ITK-FFT facade 
class implemented by March 1st.

I would appreciate a discussion of how other groups intend to use the 
FFTW routines.  As part of that discussion, it would be useful to 
include approximate memory requirements and data types.

USE 1) Use FFT's as a Butterworth filter on floating point data where 
the  Butterworth filter is created once and several floating point 
images are processed sequentially one after the other and resuing the 
same memory locations  (temporary image variable) for the frequency 
domain representation of the images.  This can be done with out of place 
FFT's without too much wasted memory.

USE 2) Use FFT's on unsigned char data to produce frequency domain 
representation of a set of images for an interative algorithm.  At the 
start of each iteration convert all unsigned char images to frequency 
domain representation, process in frequency domain, convert result back 
to spatial domain, process some more and repeat.  (I know that this 
looks like a contrived example, but this is actually the way many of our 
programs work, and it results in speed increases of 10X and memory 
savings of 4X.)

Regards,
Hans J. Johnson

-- 
===================================================================
Hans J. Johnson                              W294 GH
hans-johnson@uiowa.edu                       Dept. of Psychiatry
http://www.psychiatry.uiowa.edu/~hjohnson    The University of Iowa
(319) 353-8587                               Iowa City, IA 52242
===================================================================

> Message: 1
> Date: Tue, 28 Jan 2003 18:40:09 -0500 (EST)
> From: "John M. Galeotti" <jgaleotti@cmu.edu>
> To: Insight-Developers <insight-developers@public.kitware.com>
> Subject: [Insight-developers] FFT
> 
> Hello, in George Stetten's ITK class today the issue arose that ITK has no
> Fourier Transform filter.  I would like to suggest looking at FFTW (see
> http://www.fftw.org/faq/section1.html ).  Basically, its very fast, very
> generic (ND, etc.), and available under a wide variety of licenses
> including GPL, commercial, etc.
> 
> ---
> John M. Galeotti   (jgaleotti@cmu.edu)  412-268-9576
> Robotics Institute, EDSH, Carnegie Mellon University
> 5000 Forbes Avenue, Pittsburgh, PA 15213