Fourier transform

[VanGog]

Hi,
I read your article. Just before this:
http://www.imagemagick.org/Usage/fourier/#waves_2d
there is sentence:

The wave has a number of components to it.

Image example

But missing the example.

I started to read your article because I am interested of explanation of the Fourier Transform used on images. I want to use it in my program if I will learn enough stuff. First I started to read this tutorial:
http://lodev.org/cgtutor/fourier.html
but I am stuck on the problem that I don't understand the difference between imaginary and real part displayed on those graphs (e.g. why the hell the green imaginary line is 6,6mm high on my display but the red is 3,3 mm high when I draw sinusoid).

I read that using convolution filters like gaussian blur is pretty slow (Also I have seen it in my programs) but that if I would use Fourier transform so they are much more faster. I'm curious how hard is this to learn.

[fmw42]

See if this is better http://www.fmwconcepts.com/imagemagick/ ... urier.html

[VanGog]

I wanted to try some of your examples but this

Code: Select all

ImageMagick-6.9.0-Q16>  convert lena.png -fft    +depth +adjoin lena_fft_%d.png 

does this error:
convert.exe: delegate library support not built-in `lena.png' (FFTW) @ warning/fourier.c/ForwardFourierTransformImage/982.

I did not yet make myself to install the HDRI version. But this one should work even with clipping, shouldn't? I just wanted to test how mirroring of simple B/W shapes works.

[dlemstra]

There is currently no support for the FFTW library in the Windows build of Imagemagick. The library uses the GPL license which is not compatible with our license. I recently committed a change to our configure.exe program to allow a build with incompatible licenses. I will try to see if I can add FFTW when I have some time available. But we won't publish a release that includes this, you will have to build ImageMagick yourself.

[VanGog]

No, thanks. I should be able to build my own program for this (at least now I know that the library exists - thanks!). But I was impatient and wanted to try... The FFT calculation is not so hard but the things around it takes time.

[fmw42]

If you are on Linux or Mac OSX or Windows with Cygwin, you should be able to install the FFTW delegate library and then recompile IM. Then you command should work.

For Windows users, see viewtopic.php?f=4&t=14251#p56836

[VanGog]

what is difference in sign -/+ ? Between +fft and -fft?

When you create two images by -fft: one spectrum and second phase, are they the arrays of real and imaginary numbers respectively? Or is it something different? I have seen the real and imaginary parts in spectrum of sinus function, so I am interested if it is the same, but for different input signal. I am finishing reading of the article Fourier Transforms examples so I did not yet read the second article about processing.

[fmw42]

-fft produces two image: magnitude and phase (no negative values)

+fft produces two image: real and imaginary (with negative values) and should always be used with IM compile in HDRI mode.

[VanGog]

Both articles are good but I think something is missing there or could be explained better about the basis. I have found this article which seems to me better explained:
http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

Very good sentence in the above link, answered very good question: what is product of Fourier transform? I would ask this question too, and would expect similar answer:

The Fourier Transform produces a complex number valued output image which can be displayed with two images, either with the real and imaginary part or with magnitude and phase.

Also I would very highlight the fact that all the "magnitudes" which you display are logarithmic transform in fact, not the magnitudes itself. This is good to know for programmers like me.

I expect that it is not possible to use FFT for multiple cores calculation. Hence

Question:

This is question about FFT arithmetic and FFT formulas in general, as if there would be possible such solution for programmer. If I would split one big image of dimensions 2048x2048 into 4 quarter images and sent those images to 4x 1024x1024 magnitude arrays/images, would it be possible to join the magnitude arrays and perform e.g. blur and then again split the magnitude into 4 arrays, convert them back to normal images and then join the image back? This would mean to perform blur on 2048x2048 image and I hope it could be faster then if I would perform the FFT coding and decoding with only 1 core. Would there be significant time save of time loss?

[fmw42]

Multiple cores cannot be used that way. But they may be able to spread the computations out. I do not know if the IM implementation of FFT is OpenMP enabled. The IM developer would have to comment about that.

[VanGog]

You confirmed that it is not possible to use more cores for FFT computations, but is it possible to join four different magnitudes to one image, and four different phase to one image and then join it and get the original image? I believe this would be mathematically possible even it sounds like non-sense - why the hell we should do it.

[fmw42]

I did not confirm that you could join four magnitude or phase images into the quadrants of the final magnitude or phase. I said you could not do that. The FFT process does not work that way. You might be able to spread some of the computations in parallel using OpenMP, but I do not know if the IM developers have done that. Spreading computations in one algorithm is not the same as using different cores for different quadrants.

Also if you had read my notes more carefully, you would have see the following:

"We see that the magnitude image, as mentioned earlier, appears totally black. So now, lets enhance the magnitude with a log transform to produce the 'spectrum' image."

The magnitude is always black with perhaps a small white dot in the middle at the zero frequency or DC point. To see anything reasonable in the magnitude you need to convert it with a log function, which is then called the spectrum.

I see that a number of my links at the beginning to other articles explaining the FFT have gone dead. So I will have to try finding where they have moved or find other similar references.

[VanGog]

It's truth that you have the log command everywhere so no need to mention that. The article is long so it is not simple to remember all details on reading once. If one checks the code, so it is there. But still I think best would be call it logarithmic transformation of magnitude or logarithmic scaling of magnitude or the logarithm of the magnitude just for clarity. And to talk about magnitude just in cases where you don't use the log.

I don't know what you mean by spreading out computations in parallel using OpenMP. I didn't heard about it yet.

[fmw42]

I appreciate that there is a lot to learn and it is a difficult concept.

I have updated the introductory references (links) near the beginning of my tutorial and remove the dead links.

The conventional term for log enhanced magnitude is "spectrum".

For OpenMP, you need multiple cores and IM compiled (by default) with OpenMP enabled. See
http://www.imagemagick.org/script/openmp.php
http://www.imagemagick.org/script/archi ... hp#threads
MAGICK_THREAD_LIMIT at http://www.imagemagick.org/script/resou ... nvironment
viewtopic.php?f=2&t=20756&p=83407&hilit=thread#p83407
--disable-openmp at http://www.imagemagick.org/script/advan ... #configure

[VanGog]

I have found very interesting article, this is from point of view of programming. It explains the basis. There are also algorithms in Java but this is similar to C/C++.

Basis of DSP (Digital Signal Processing)
http://www.developer.com/java/other/art ... -Works.htm

Spectrum Analysis using Java, Sampling Frequency, Folding Frequency, and the FFT Algorithm
http://www.developer.com/java/other/art ... orithm.htm

There is more articles like that but this will take time to read. I think this is really useful coz I did not see yet such complex tutorials on this topic, from the point of programmer.