[Insight-developers] [Fwd: FFTW Is being worked on.]
Vincent A. Magnotta
vincent-magnotta@uiowa.edu
29 Jan 2003 15:57:08 -0600
--=-1ngGfGUzRQATN9EnRtI2
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
--
Vincent A. Magnotta
Iowa MH-CRC
W280 GH
Phone: 319-353-8537
Fax: 319-384-5532
Email: vincent-magnotta@uiowa.edu
Web: http://www.psychiatry.uiowa.edu
--=-1ngGfGUzRQATN9EnRtI2
Content-Disposition: inline
Content-Description: Forwarded message - FFTW Is being worked on.
Content-Type: message/rfc822
Return-Path: <hjohnson@mail.psychiatry.uiowa.edu>
Received: from benton.psychiatry.uiowa.edu (benton.psychiatry.uiowa.edu
[129.255.141.93]) by tesla.psychiatry.uiowa.edu (8.12.5/8.12.5) with ESMTP
id h0TKK476007479 for <vince@tesla.psychiatry.uiowa.edu>; Wed, 29 Jan 2003
14:20:04 -0600
Received: from sun.its.uiowa.edu (sun.its.uiowa.edu [128.255.56.61]) by
benton.psychiatry.uiowa.edu (SGI-8.9.3/8.9.3) with ESMTP id OAA28046 for
<vince@benton.psychiatry.uiowa.edu>; Wed, 29 Jan 2003 14:20:04 -0600 (CST)
Received: from mail.psychiatry.uiowa.edu (mail.psychiatry.uiowa.edu
[129.255.141.114]) by sun.its.uiowa.edu (8.11.6/8.11.6/uiowa-2.9) with
ESMTP id h0TKJsu242082 for <vincent-magnotta@uiowa.edu>; Wed, 29 Jan 2003
14:19:57 -0600
Received: from mail.psychiatry.uiowa.edu (robin.psychiatry.uiowa.edu
[129.255.141.118]) by mail.psychiatry.uiowa.edu (8.11.6/8.11.6) with ESMTP
id h0TKJoh05855; Wed, 29 Jan 2003 14:19:50 -0600
Message-ID: <3E383766.1090009@mail.psychiatry.uiowa.edu>
Date: Wed, 29 Jan 2003 14:19:50 -0600
From: Hans Johnson <hjohnson@mail.psychiatry.uiowa.edu>
Reply-To: hans-johnson@uiowa.edu
Organization: The Unversity of Iowa
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.1) Gecko/20021003
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: insight-developers@public.kitware.com
CC: Kent Williams <kent@mail.psychiatry.uiowa.edu>, Hans Johnson <hjohnson@mail.psychiatry.uiowa.edu>, "Vincent A. Magnotta" <vincent-magnotta@uiowa.edu>
Subject: FFTW Is being worked on.
References: <20030129114951.24946.99687.Mailman@public.kitware.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
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
--=-1ngGfGUzRQATN9EnRtI2--