[Insight-developers] FFT update

[Luis Ibanez]

Hi Kent,

The restriction of FFT algorithms for using 2^N number of samples
is pretty common, it arises directly from the implementation of
the algorithm in the form of permutations.

The typical solution is to do zero-padding or reflexions of the
image in order to reach the next 2^N number that is greater or
equal than the current number of samples.

That means that when computing the FFT of an image of size

   450 x 450, we padd it with zeroes to make it 512x512

and pay for the extra computations. This produces an spectrum
of 512x512 entries.

Since the transitions between the real image border and the
zone of zeros creates an artificial discontinuity in the image,
a number of spurious high frequencies are introduced in the
Fourier space. In order to mitigate this effect, people typically
use techniques like the Hamming windowing which multiplies the
image intensities by a sinusouidal form in order to attenuate
the transitions in the border.

All these issues are "part of the fun" of using Fourier transforms
and users that try FFT should be familiar with their implications.
Even MatLab users should be familiar with this issues.


I would consider fair to make the ITK FFT filter to test the input
image for 2^N dimension and if the dimensions do not fit a power of
two, reject the image.  We could then provide a couple of filters
for 'adapting' the image for FFT.  For example we will need a
combination of Zero-padding and Hamming windowing (there are two
or three other common windows: for example the Hanning window which
instead of a sinusouid used half of a cosinus) as a conveniently
packaged filter.

        itkZeroPaddingHammingWindowImageFilter
        itkZeroPaddingHanningWindowImageFilter

another option is to crop the image to the closest smaller 2^N size,
this could be done with a

       itkCropHammingWindowImageFilter
       itkCropHanningWindowImageFilter

of by simply using the current itkRegionOfInterestImageFilter and
only adding a generic itkHammingWindowImageFilter.

Yet another option is to do the padding on-the-fly inside the FFT
filter, each time that a row is processed. This will have the
advantage of not requiring an extra copy of the image to be held
in memory as the output of one of the previous ZeroPaddinwXXWindowing
filters




    Luis



------------------------

Kent Williams wrote:
> Three things:
> 
> 1. The problems I have been having with VNL fft arise from there being 
> constraints on the dimensions, as
> reported at: http://sourceforge . net/mailarchive/message . php?msg_id=2213052
> 
> Since vnl won't do FFT's of arbitrarily dimensioned images, I'll try a 
> few of the FFT codes I've found to see if I can find one that works for 
> any image.
> 
> 2. FFTW was dumping core on a test case on my machine. After consulting 
> with the FFTW folks it turns out that the stock version of GCC on Red 
> Hat Nine (3.2.2) compiles FFTW incorrectly. GCC 3.3.2 passes the test.  
> There is a FindFFTW.cmake, so if you have FFTW installed, you can define 
> USE_FFTW (and FFTW_LIB and FFTW_INCLUDE, if your fftw isn't installed in 
> a system directory) and use the itkFFTW classes if you need.
> 
> 3. Since the current Testing/Code/Algorithms/itkFFTTest.cxx generates a 
> 'false pass' for the VnlFFT classes, I'm removing itkFFTTest from the 
> itkAlgorithmsTest2 program until I've replaced the VNL with a working, 
> license-compatible FFT.
> 
> _______________________________________________
> Insight-developers mailing list
> Insight-developers at itk . org
> http://www . itk . org/mailman/listinfo/insight-developers
>