[ImageJ-devel] imglib2 FFT algorithm explanation

[Brian Northan]

Hi Sara

I've worked quite a bit with these classes the last couple of years.  The
list and Stephen Priebisch (the author) has been pretty helpful, so
consider them the final authority, but here is some information that might
be helpful.

1.  The latest versions of the fft functions are in the fft2 directory.  (
https://github.com/imglib/imglib/tree/master/algorithms/core/src/main/java/net/imglib2/algorithm/fft2)
they are a bit faster then those in 'fft'.  I believe the older versions
are depreciated.

2.  The newer FFT (FFT.java
https://github.com/imglib/imglib/blob/master/algorithms/core/src/main/java/net/imglib2/algorithm/fft2/FFT.java)
calculates dimensions and subsequent padding value as the first step in
*realToComplex*.  It looks like it always does it as to get the dimensions
optimized for speed.  Mines also supports dimensions optimized for small
size and *FFTMethods* supports this.

Why, for example, if I transform a 256x256 image I get back a 281x560
> spectrum
>

I not sure why this happened...  were you trying to compute a power
spectrum??  Or just looking at the complex valued image that was returned
after the FFT calculation??

The convolution function automatically pads as to avoid circular
convolution at the edges.  So if your kernel size is also 256 by 256 the
numbers make sense.  The image would get padded to 512 by 512 and the input
to the FFT padded a bit more (560 by 560 sounds right) after transform
281X560 complex coefficients seems right.

(as a side note it seems that power of 2s are not an efficient size for
mines FFTs I guess I will have to look at the details of the PFA algorithm
to understand why... thanks for pointing out that mines uses PFA)

Brian

>
>>

On Fri, Jul 25, 2014 at 8:07 AM, SARA SCHIESARO <
sara.schiesaro at student.unife.it> wrote:

> Hi all,
> I've already worked with FourierTransform and FFTConvolution classes, I've
> also studied their codes in order to adapt them to my program, anyway I
> still have some doubts about those classes and I hope you can help me!
>
> First, dimensions of the output resulting from the FourierTransform and
> those of the fftKernel in the FFTConvolution class differ from those of the
> input images, why? Why, for example, if I transform a 256x256 image I get
> back a 281x560 spectrum?
>
> Secondly, trying to find out an answer to the first doubt I have, I find
> out that the spectrum dimensions are calculated by using the package
> edu.mines.jtk.dsp and in particular the classes FftReal/FftComplex, both
> based on the Pfacc class. Comments to the Pfacc class said that this class
> implements the PFA algorithm for the FFT computation, so my second doubt is
> this: do the FourierTransform and FFTConvolution classes implement the PFA
> algorithm?
>
> I really need to find it out in order to continue my work, so any help
> will be appreciated!
> Thanks a lot,
>
> Sara S.
>
> _______________________________________________
> ImageJ-devel mailing list
> ImageJ-devel at imagej.net
> http://imagej.net/mailman/listinfo/imagej-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imagej.net/pipermail/imagej-devel/attachments/20140730/e7fdac36/attachment.html>