FFT implementation in ImageJ

[Student1]

Hi,

I was wondering if ImageJ has standard FFT algorithm? Because I know ImageJ has a FFT window and it also FHT window, so does the FFT implementation based on the FHT algorithm? When I look into the code I basically see the FHT implementation but not a standard FFT algorithm.

Thanks.

Mariam Dost
--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Herbie-4]

Mariam,

ImageJ computes the 2D FFT via the 2D FHT.

The resulting transforms (Fourier-spectra) are essentially the same as
with a (direct) "classical" 2D FFT implementation. However the
computation is faster.

There is a plugin called FFTJ which is based on "classical 2D" FFT
implementation. The source code is available.

You may also have a look at the code in "Numerical Recipes". However,
you have to change the C code to Java, which is rather easy.

HTH

Herbie

::::::::::::::::::::::::::::::::::
On 16.06.14 18:58, Student1 wrote:

> Hi,
>
> I was wondering if ImageJ has standard FFT algorithm? Because I know
> ImageJ has a FFT window and it also FHT window, so does the FFT
> implementation based on the FHT algorithm? When I look into the code
> I basically see the FHT implementation but not a standard FFT
> algorithm.
>
> Thanks.
>
> Mariam Dost -- ImageJ mailing list:
> http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[ctrueden]

Hi Herbie & Mariam,

> You may also have a look at the code in "Numerical Recipes". However, you
> have to change the C code to Java, which is rather easy.

Note that Numerical Recipes code is released under a very restrictive
license. Specifically: redistribution is prohibited. So if you are
producing open source software, you will need to stay away from it.

Regards,
Curtis


On Mon, Jun 16, 2014 at 12:16 PM, Herbie <[hidden email]> wrote:

> Mariam,
>
> ImageJ computes the 2D FFT via the 2D FHT.
>
> The resulting transforms (Fourier-spectra) are essentially the same as
> with a (direct) "classical" 2D FFT implementation. However the computation
> is faster.
>
> There is a plugin called FFTJ which is based on "classical 2D" FFT
> implementation. The source code is available.
>
> You may also have a look at the code in "Numerical Recipes". However, you
> have to change the C code to Java, which is rather easy.
>
> HTH
>
> Herbie
>
> ::::::::::::::::::::::::::::::::::
>
> On 16.06.14 18:58, Student1 wrote:
>
>> Hi,
>>
>> I was wondering if ImageJ has standard FFT algorithm? Because I know
>> ImageJ has a FFT window and it also FHT window, so does the FFT
>> implementation based on the FHT algorithm? When I look into the code
>> I basically see the FHT implementation but not a standard FFT
>> algorithm.
>>
>> 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

[Kenneth R Sloan]

As always with _Numerical Recipes_, use the code with caution.  The code is
explicitly intended as a *starting point*.  You should also read the WORDS
in the chapter, and consider extending and hardening the sample code.

Also, if you can find it, my experience is that the C version of _NR_ is
distinctly WORSE than the original ForTran for many algorithms (I have not
checked the FFT code to see if this trend holds here).  When I use _NR_ algorithms,
I always start with the original.

And…while I appreciate the reasons, it seems (to me) wrong to claim to “compute the
FFT via the FHT”.  Truth in advertising, please. Most of the time, “close” is good enough.
But, not always.

I think ImageJ would be improved by offering both the FFT *and* the FHT, with appropriate
(and correct) documentation.

--
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 16, 2014, at 13:37 , Curtis Rueden <[hidden email]<mailto:[hidden email]>> wrote:

Hi Herbie & Mariam,

You may also have a look at the code in "Numerical Recipes". However, you
have to change the C code to Java, which is rather easy.

Note that Numerical Recipes code is released under a very restrictive
license. Specifically: redistribution is prohibited. So if you are
producing open source software, you will need to stay away from it.

Regards,
Curtis


On Mon, Jun 16, 2014 at 12:16 PM, Herbie <[hidden email]<mailto:[hidden email]>> wrote:

Mariam,

ImageJ computes the 2D FFT via the 2D FHT.

The resulting transforms (Fourier-spectra) are essentially the same as
with a (direct) "classical" 2D FFT implementation. However the computation
is faster.

There is a plugin called FFTJ which is based on "classical 2D" FFT
implementation. The source code is available.

You may also have a look at the code in "Numerical Recipes". However, you
have to change the C code to Java, which is rather easy.

HTH

Herbie

::::::::::::::::::::::::::::::::::

On 16.06.14 18:58, Student1 wrote:

Hi,

I was wondering if ImageJ has standard FFT algorithm? Because I know
ImageJ has a FFT window and it also FHT window, so does the FFT
implementation based on the FHT algorithm? When I look into the code
I basically see the FHT implementation but not a standard FFT
algorithm.

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

[James Ewing]

My experience with the NR FFT is that it can be improved for speed.  Using pointers, and discarding that strange translation of Fortran that generates useless vectors starting at the index 1, I wrote a C translation of the Fortran NR FFT that improved execution time by about 30%.  I can send the C code to anyone who wants it.  I’m not promising that there aren’t faster versions, but this could be a starting point.

 - Jim Ewing.

On Jun 16, 2014, at 5:44 PM, Kenneth R Sloan <[hidden email]> wrote:

> As always with _Numerical Recipes_, use the code with caution.  The code is
> explicitly intended as a *starting point*.  You should also read the WORDS
> in the chapter, and consider extending and hardening the sample code.
>
> Also, if you can find it, my experience is that the C version of _NR_ is
> distinctly WORSE than the original ForTran for many algorithms (I have not
> checked the FFT code to see if this trend holds here).  When I use _NR_ algorithms,
> I always start with the original.
>
> And…while I appreciate the reasons, it seems (to me) wrong to claim to “compute the
> FFT via the FHT”.  Truth in advertising, please. Most of the time, “close” is good enough.
> But, not always.
>
> I think ImageJ would be improved by offering both the FFT *and* the FHT, with appropriate
> (and correct) documentation.
>
> --
> 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 16, 2014, at 13:37 , Curtis Rueden <[hidden email]<mailto:[hidden email]>> wrote:
>
> Hi Herbie & Mariam,
>
> You may also have a look at the code in "Numerical Recipes". However, you
> have to change the C code to Java, which is rather easy.
>
> Note that Numerical Recipes code is released under a very restrictive
> license. Specifically: redistribution is prohibited. So if you are
> producing open source software, you will need to stay away from it.
>
> Regards,
> Curtis
>
>
> On Mon, Jun 16, 2014 at 12:16 PM, Herbie <[hidden email]<mailto:[hidden email]>> wrote:
>
> Mariam,
>
> ImageJ computes the 2D FFT via the 2D FHT.
>
> The resulting transforms (Fourier-spectra) are essentially the same as
> with a (direct) "classical" 2D FFT implementation. However the computation
> is faster.
>
> There is a plugin called FFTJ which is based on "classical 2D" FFT
> implementation. The source code is available.
>
> You may also have a look at the code in "Numerical Recipes". However, you
> have to change the C code to Java, which is rather easy.
>
> HTH
>
> Herbie
>
> ::::::::::::::::::::::::::::::::::
>
> On 16.06.14 18:58, Student1 wrote:
>
> Hi,
>
> I was wondering if ImageJ has standard FFT algorithm? Because I know
> ImageJ has a FFT window and it also FHT window, so does the FFT
> implementation based on the FHT algorithm? When I look into the code
> I basically see the FHT implementation but not a standard FFT
> algorithm.
>
> 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

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Herbie-4]

Dear Curtis, dear Kenneth, dear Jim,

it would be really interesting to know whether such a restricted code
license still applies if it is to converted to a different programming
language (with respect to this list most probably Java)?
(Evidently, there is a coder converting parts of "Numerical
Recipes"-code to Java (IMHO of doubtable quality). I don't know whether
any restrictions apply to his code.)

AFAIK, the most recent editions of "Numerical Recipes" contain C++ code
although containing only minor object oriented lines of code, i.e. the
code examples are mainly plain C-code. I agree with Jim that the
"Numerical Recipes"-FORTRAN code for the FFT is less appealing and that
even the C++/C-versions allow for optimization. However and at least in
the latest editions, the authors mention other, more efficient approaches.

I fully agree with Kenneth that the essential value of "Numerical
Recipes" is the explanatory text, not the code examples. It was for this
reason that I mentioned the book with respect to the poster's original
request.
(BTW, I also like the older editions of "Numerical Recipes" better than
the latest, even though they don't cover as much topics.)

With best regards

Herbie

:::::::::::::::::::::::::::::::::::::::
On 16.06.14 22:37, Curtis Rueden wrote:

> Hi Herbie & Mariam,
>
>> You may also have a look at the code in "Numerical Recipes". However, you
>> have to change the C code to Java, which is rather easy.
>
> Note that Numerical Recipes code is released under a very restrictive
> license. Specifically: redistribution is prohibited. So if you are
> producing open source software, you will need to stay away from it.
>
> Regards,
> Curtis
>
>
> On Mon, Jun 16, 2014 at 12:16 PM, Herbie <[hidden email]> wrote:
>
>> Mariam,
>>
>> ImageJ computes the 2D FFT via the 2D FHT.
>>
>> The resulting transforms (Fourier-spectra) are essentially the same as
>> with a (direct) "classical" 2D FFT implementation. However the computation
>> is faster.
>>
>> There is a plugin called FFTJ which is based on "classical 2D" FFT
>> implementation. The source code is available.
>>
>> You may also have a look at the code in "Numerical Recipes". However, you
>> have to change the C code to Java, which is rather easy.
>>
>> HTH
>>
>> Herbie
>>
>> ::::::::::::::::::::::::::::::::::
>>
>> On 16.06.14 18:58, Student1 wrote:
>>
>>> Hi,
>>>
>>> I was wondering if ImageJ has standard FFT algorithm? Because I know
>>> ImageJ has a FFT window and it also FHT window, so does the FFT
>>> implementation based on the FHT algorithm? When I look into the code
>>> I basically see the FHT implementation but not a standard FFT
>>> algorithm.
>>>
>>> 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

[Dimiter Prodanov (imec)]

Hi,

I don't  think that by porting C code to Java one violates any license. Porting requires usually reimplementation and re-optimization.
This is in fact new development. So I wouldn't bother about licensing issues in this case.
Besides, there are some mistakes in the Numerical Recipes.

Best regards,

Dimiter



--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Herbie-4]

Dimiter,

thanks for your comments.

 > Besides, there are some mistakes in the Numerical Recipes.

The 1D FFT C++-code, i.e. realft() and four1(), from "Numerical Recipes"
3rd Ed., 2007 appears to work correctly, at least after its conversion
to Java (that didn't required much work).

In fact, across the web you will find quite some criticism concerning
these routines but as far as I could see, this is due to the incorrect
handling of the result vector (complex-valued Fourier spectral data) of
the routine realft() that must be slightly re-ordered according to the
descriptions given in the accompanying text and in the header comment.

Best

Herbie

:::::::::::::::::::::::::::::::::::::::::::::::::
On 18.06.14 11:28, Dimiter Prodanov (imec) wrote:

> Hi,
>
> I don't  think that by porting C code to Java one violates any
> license. Porting requires usually reimplementation and
> re-optimization. This is in fact new development. So I wouldn't
> bother about licensing issues in this case. Besides, there are some
> mistakes in the Numerical Recipes.
>
> Best regards,
>
> Dimiter

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[dscho]

Dear Dimiter,

On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:

> I don't  think that by porting C code to Java one violates any license.

You might not think that. But it is established by lawyers that porting
constitutes copying in the sense covered by copyright.

Sorry.
Johannes

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Kenneth Sloan-2]

Copyright is not license.

Which may be moot, because the _NR_ code is also copyrighted.

--
Kenneth Sloan
[hidden email]


On Jun 18, 2014, at 10:18 , Johannes Schindelin <[hidden email]> wrote:

> Dear Dimiter,
>
> On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:
>
>> I don't  think that by porting C code to Java one violates any license.
>
> You might not think that. But it is established by lawyers that porting
> constitutes copying in the sense covered by copyright.
>
> Sorry.
> Johannes
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Dimiter Prodanov (imec)]

Hi Johannes,

I was not aware of this. Is there an accessible reference?

On the other hand, the hypothesis there is that porting is a "derivative work".
In the case of scientific code this is difficult to defend because the code is derived from scientific paper(s) - a set of formulas.
So if your code is sufficiently different I don't think that demonstration of development from first principles is difficult.
I.e. there is only 1 algorithm calculating a power-of-2 FFT so any implementations are bound to be very similar.
For that matter Numerical Recipies cannot claim any priority over the original derivation of Cooley and Tukey.
I can agree that "derivation" is in place if you keep the signature of a method and do not change substantially the body of the method
(i.e. names of variables, constants, initial values etc.). This will be indeed "porting".

Here is a discussion on the matter:
http://programmers.stackexchange.com/questions/58338/when-porting-code-must-i-follow-the-original-license
"There is porting which is to taking someone's source code to create something that works on a different system or in a different language.
Then there is reverse engineering which is to make something that behaves like someone else's program, but has nothing of substance from the original work.
Porting means you have their permission. So you need to ask the original creator what your rights are regarding license and how you release it.
Reverse Engineering means you either can't or won't talk to the original creator, and you can do whatever you darn well please. (just keep on the lookout for any lawyers)."
 
http://www.uwyo.edu/buerkle/misc/wnotnr.html

All in all, the question is very interesting.


Best regards,

Dimiter

-----Original Message-----
From: Johannes Schindelin [mailto:[hidden email]]
Sent: 18 June, 2014 17:18
To: Dimiter Prodanov (imec)
Cc: [hidden email]
Subject: Re: FFT implementation in ImageJ

Dear Dimiter,

On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:

> I don't  think that by porting C code to Java one violates any license.

You might not think that. But it is established by lawyers that porting constitutes copying in the sense covered by copyright.

Sorry.
Johannes

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[James Ewing]

Perhaps the answer is to use the Gnu Scientific Library source as a starting point. It’s efficient, fast, and protected by a copy-left agreement.  There are a number of implementations of Fourier transform algorithms besides the FFT, useful for discrete transforms, real transforms, etc.
 - Jim

On Jun 18, 2014, at 11:18 AM, Johannes Schindelin <[hidden email]> wrote:

> Dear Dimiter,
>
> On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:
>
>> I don't  think that by porting C code to Java one violates any license.
>
> You might not think that. But it is established by lawyers that porting
> constitutes copying in the sense covered by copyright.
>
> Sorry.
> Johannes
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[dscho]

Hi Dimiter,

On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:

> I was not aware of this. Is there an accessible reference?

A Google search brought this up:
http://stackoverflow.com/questions/3256967/what-are-the-copyright-and-licensing-issues-of-porting-code
as well as other good resources. Please do not ask me more about this: I
am not a lawyer so what I say is not legal advice anyway.

> All in all, the question is very interesting.

Sorry, I disagree. This is not very interesting to me. I much prefer
programming over technical discussions of the law. But the point
stands: porting software is considered subject to copyright law.

And the Numerical Recipes are the worst offender of applying this law.
They should be ashamed, doubly so, it has nothing to do with science when
you try to prevent the dissemination and application of knowledge, and
every scientist should stay as far away as possible from this
incredibly science-unfriendly book.

Ciao,
Johannes

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Student1]

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


On Jun 18, 2014, at 1:09 PM, Johannes Schindelin <[hidden email]> wrote:

> Hi Dimiter,
>
> On Wed, 18 Jun 2014, Dimiter Prodanov (imec) wrote:
>
>> I was not aware of this. Is there an accessible reference?
>
> A Google search brought this up:
> http://stackoverflow.com/questions/3256967/what-are-the-copyright-and-licensing-issues-of-porting-code
> as well as other good resources. Please do not ask me more about this: I
> am not a lawyer so what I say is not legal advice anyway.
>
>> All in all, the question is very interesting.
>
> Sorry, I disagree. This is not very interesting to me. I much prefer
> programming over technical discussions of the law. But the point
> stands: porting software is considered subject to copyright law.
>
> And the Numerical Recipes are the worst offender of applying this law.
> They should be ashamed, doubly so, it has nothing to do with science when
> you try to prevent the dissemination and application of knowledge, and
> every scientist should stay as far away as possible from this
> incredibly science-unfriendly book.
>
> Ciao,
> Johannes
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[ctrueden]

Hi Dimiter,

> I don't think that by porting C code to Java one violates any
> license. Porting requires usually reimplementation and
> re-optimization. This is in fact new development. So I wouldn't bother
> about licensing issues in this case.

Incorrect.

From the Numerical Recipes website [1]:
> The Numerical Recipes programs are all copyrighted by the authors of
> the Numerical Recipes books. Under copyright law, all "derivative
> works" (modified versions, or translations into another computer
> language) also come under the same copyright.

From Digital Law Online [2]:
> Many people have reimplemented computer programs by rewriting them to
> replace the source code with code of their own writing. There is no
> reason to believe that this would not be a copyright infringement,
> particularly if the reimplementer had access to the source code of the
> original program, even if none of the original source code remains.

As I said, it is best to completely avoid the Numerical Recipes code, since
it is only available under a very restrictive license not conducive to open
source development or distribution.

-Curtis

[1] http://www.nr.com/com/info-copyright.html
[2] http://digital-law-online.info/lpdi1.0/treatise27.html


On Wed, Jun 18, 2014 at 4:28 AM, Dimiter Prodanov (imec) <
[hidden email]> wrote:

> Hi,
>
> I don't  think that by porting C code to Java one violates any license.
> Porting requires usually reimplementation and re-optimization.
> This is in fact new development. So I wouldn't bother about licensing
> issues in this case.
> Besides, there are some mistakes in the Numerical Recipes.
>
> Best regards,
>
> Dimiter
>
>
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Herbie-4]

On 18.06.14 21:09, Johannes Schindelin wrote:

 > [...] every scientist should stay as far away as possible from this
 > incredibly science-unfriendly book.

:::::::::::::::::::::::::::::::::::::::::::::

Good day Johannes Schindelin,

as always I'm quite thankful for your comments and opinions.

As a reader who likes the very book--as I've written, less for its code,
but for the accompanying text--I realize from your judgement, that I
must doubt being a scientist anymore. Perhaps I should burn the book
("stay as far away as possible"), but also due to historic reasons this
may be more than problematic.

Looking forward to hearing more profound opinions of this kind

Herbie

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Unruh, Jay-2]

While I agree with the general interpretation of copyright law here, I don't really understand how the numerical recipes restrictive license stands given that much of their code is copied/derived from other papers.  I do use numerical recipes to learn about algorithms, but I typically find the primary literature reference and use it for the code if I decide not to recode things.

Anyway, if you want a "written from scratch" fft, feel free to use mine: http://research.stowers.org/imagejplugins/Jay_Plugins_HTML_source/jalgs/jfft/po4fft.java.html

It is surprisingly fast though I won't make any claims of its speed relative to popular platforms like fftw.  It is GPL licensed.  This is basically to keep people like numerical recipes from copying without shame (and yes, shame is probably the only preventative factor).  I'm happy to relicense for specific applications.

Jay

-----Original Message-----
From: ImageJ Interest Group [mailto:[hidden email]] On Behalf Of Curtis Rueden
Sent: Wednesday, June 18, 2014 10:42 PM
To: [hidden email]
Subject: Re: FFT implementation in ImageJ

Hi Dimiter,

> I don't think that by porting C code to Java one violates any license.
> Porting requires usually reimplementation and re-optimization. This is
> in fact new development. So I wouldn't bother about licensing issues
> in this case.

Incorrect.

From the Numerical Recipes website [1]:
> The Numerical Recipes programs are all copyrighted by the authors of
> the Numerical Recipes books. Under copyright law, all "derivative
> works" (modified versions, or translations into another computer
> language) also come under the same copyright.

From Digital Law Online [2]:
> Many people have reimplemented computer programs by rewriting them to
> replace the source code with code of their own writing. There is no
> reason to believe that this would not be a copyright infringement,
> particularly if the reimplementer had access to the source code of the
> original program, even if none of the original source code remains.

As I said, it is best to completely avoid the Numerical Recipes code, since it is only available under a very restrictive license not conducive to open source development or distribution.

-Curtis

[1] http://www.nr.com/com/info-copyright.html
[2] http://digital-law-online.info/lpdi1.0/treatise27.html


On Wed, Jun 18, 2014 at 4:28 AM, Dimiter Prodanov (imec) < [hidden email]> wrote:

> Hi,
>
> I don't  think that by porting C code to Java one violates any license.
> Porting requires usually reimplementation and re-optimization.
> This is in fact new development. So I wouldn't bother about licensing
> issues in this case.
> Besides, there are some mistakes in the Numerical Recipes.
>
> Best regards,
>
> Dimiter
>
>
>
> --
> 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

[Burger Wilhelm]

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

[bnorthan]

There is also a multi-dimensional implementation in imglib2 that seems to
work well.  It uses mines jtk which was originally licensed under GPL, but
there was talk they got permission to release it with a less restrictive
license (https://github.com/imglib/imglib/issues/38).


On Thu, Jun 19, 2014 at 11:46 AM, Burger Wilhelm <
[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

[Student1]

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]> 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