http://imagej.273.s1.nabble.com/FFT-implementation-in-ImageJ-tp5008239p5008349.html
limited support (most often even equal support) in _both_ domains.
According to the FT this is impossible, i.e. such signal representations
I fully agree that, e.g. DFT algorithms that are not limited to a power
of two support should not be called FFT. Their results, while being
("true") FFT implementations. That said, and with regard to ImageJ-n, it
> 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=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]><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.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>
>
> -- ImageJ mailing list:
http://imagej.nih.gov/ij/list.html>