Posted by
Kenneth R Sloan on
URL: http://imagej.273.s1.nabble.com/FFT-implementation-in-ImageJ-tp5008239p5008327.html
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.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