Posted by
Kenneth R Sloan on
Jun 20, 2014; 9:24am
URL: http://imagej.273.s1.nabble.com/FFT-implementation-in-ImageJ-tp5008239p5008346.html
At some point, it helps to use precise terminology.
FT - Fourier Transform - a mathematical function mapping complex signals to complex spectra
FFT - Fast Fourier Transform - a particular algorithm which implements the FT
Most implementations of the FT depend, more or less, on the FFT. Different choices for representation,
etc. These might still be called “implementations of the FFT”.
Others may differ enough that they deserve their own name - when they do, it’s proper to say
that they implement the FT and not the FFT!
Still others are implementation of something “similar, but not quite the same as the FT”. They should probably NOT ever be called either FT or FFT.
I am reminded of another system I use regularly which has a primitive called “cube” - which takes
three dimensions (height, width, depth). It always hurts my brain to type it.
I am also reminded of a question I once actually heard asked at an imaging conference: “has anyone
considered implementing the Fast Fourier Transform using optics?”
--
Kenneth Sloan
[hidden email]<mailto:
[hidden email]>
"La lutte elle-même vers les sommets suffit à remplir un coeur d'homme; il faut imaginer Sisyphe heureux."
On Jun 20, 2014, at 01:46 , Daniel Sage <
[hidden email]<mailto:
[hidden email]>> wrote:
FFT is the important block of many image processing algorithms. So, it is crucial to get an efficient FFT. The problem here is that the efficiency is related to the available resources of the client machine: memory, number of cores, GPU, OS, C-language.
In the Java world, we can find many FFT libraries:
- Several translation of the Numerical Recipes FFT
- FHT of ImageJ
- Colt (Parallel Colt) and JTransform
- Apache Commons Math
- Java Wrapper for the C library FFTW (Fast Fourier Transform in the West)
- Java wrapper for FFTPACK
- JCUFFT (Cuda / GPU)
The choice of the "good" FFT library is difficult because several criteria have to taken into account:
- execution time (without any specific hardware, Matlab has the fastest one!)
- multithreading
- efficient for every size of signals, not only the the power of 2
- exactness for every size (padding?)
- energy conservation
- data type: float or double and data dimension: 1D, 2D, and 3D
- data structure: a complex object for every pixel, real and imaginary arrays, or interleave format. Surprisingly, the last structure is use in many libraries.
- compactness: using the Hermitian symmetry to save memory
- providing binaries (DLL) for several OS when the library is written in C/C++
- licensing
- checking the presence of GPU to run on it
- and probably the most important for the user: the availability of complex-number methods to process the coefficients of the Fourier transform avoiding multiple copies from one data structure to a other data structure.
Piotr Wendykier has some benchmarking:
http://dl.acm.org/citation.cfm?id=1824809Best,
Daniel
Read a bit more! If RI is a real-valued image, then FT(RI) is symmetric - which means you
only have to store half of the (complex) result. So…it’s a wash (but requires knowledge about
the “scrambling” of your representation.)
You can think of this from an information theory point of view: the FT does not create any new information, so it should be obvious that you don’t need more bits to represent the result.
Perhaps trickier is the other way around - given a symmetric spectrum,
the inverseFT gives a real image. Depending on the datatype you are using, this
might require special handling (coercing tiny imaginary values to 0).
This is one of the reasons why you might prefer to use an “industrial strength” FFT implementation if you want to USE the FT (instead of wanting to implement from first principles so that you understand it).
Of course, if memory is free (or your images are small), you might not find this space-saving complication as a worthwhile tradeoff. When the FFT was invented, memory was NOT free!
Today, it might be more correct to implement FT and inverseFT as strictly complex<->complex, and
convert images real<->complex.
On the third hand, for large enough images, you should also consider memory access patterns. Memory might APPEAR to be “free” - but USING all that memory may not be.
Are we having fun, yet?
--
Kenneth Sloan
[hidden email]<mailto:
[hidden email]><mailto:
[hidden email]>
"La lutte elle-même vers les sommets suffit à remplir un coeur d'homme; il faut imaginer Sisyphe heureux."
On Jun 19, 2014, at 11:06 , Student1 <
[hidden email]<mailto:
[hidden email]><mailto:
[hidden email]>> wrote:
Hi Burger,
I kind of wanted to implement the FFT by hand instead of using a library because I really want to understand how the FFT works and make sure I got the implementation correct. I know that combining the complex and real array is doubling the size of the array and I don’t know exactly how to fix that. I don’t thinks theres a problems in the rest of the code I implemented.
Thanks.
Mariam Dost
On Jun 19, 2014, at 9:46 AM, Burger Wilhelm <
[hidden email]<mailto:
[hidden email]><mailto:
[hidden email]>> wrote:
Hello Miriam,
have you considered the FFT implementation in Apache Commons Math?:
http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/transform/FastFourierTransformer.htmlWorks "out of the box" and results are correct.
--Wilhelm Burger
________________________________________
From: ImageJ Interest Group [
[hidden email]] On Behalf Of Student1 [
[hidden email]]
Sent: Wednesday, June 18, 2014 23:58
To:
[hidden email]
Subject: Re: FFT implementation in ImageJ
Hi,
First of all thanks for everybody’s input. I implemented an FFT algorithm by basically looking it up online and I am tracing through the calculation by hand to get a better understanding of the FFT. The FFT I implemented does not produce the image that should be produced by ImageJ. I was wondering if anyone can see where I am going wrong with my calculation. My work is here:
http://stackoverflow.com/questions/24291896/fft-image-is-not-the-same-as-the-fft-image-produced-in-imagejThanks.
Mariam Dost
--
ImageJ mailing list:
http://imagej.nih.gov/ij/list.html--
ImageJ mailing list:
http://imagej.nih.gov/ij/list.html--
ImageJ mailing list:
http://imagej.nih.gov/ij/list.html--
ImageJ mailing list:
http://imagej.nih.gov/ij/list.html