http://imagej.273.s1.nabble.com/FFT-implementation-in-ImageJ-tp5008239p5008614.html
> 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=1824809>
> Best,
>
> 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]>
>> "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]>> 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]>> 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.html>>
>> Works "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-imagej>>
>> Thanks.
>>
>> 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