Jump to content
  • Advertisement
Sign in to follow this  
docyoung83

fourier transform question

This topic is 5406 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working on a program that needs to be able to compute the fast Fourier transform of an image. However, one thing that I notice is that most FFT code libraries only support input sizes that are 2n. Unfortunately, some of the images I work with may not have these dimensions. Therefore, I was wondering how exactly these images should (or could) be padded with extra "blank" space so that the FFT will still work. For example, should the image be padded as in Example 1 or 2: EXAMPLE 1 In this case, the extra blank values are simply added to the end of the original image array, which is pretty trivial. EXAMPLE 2 In this case, the extra blanks are added so that the image remains square. I am trying in vain to get FFTW to work, since it can work on arbitrary size input images, but so far I've had no success. EDIT: And lastly, if I do pad the image, what value (i.e. color) should be used so that the transform is not affected.

Share this post


Link to post
Share on other sites
Advertisement
any image padding will mess with (edit: change) the FFT. And the typical FFT requires powers of 2 because its optimizations are based on that. you can still do a regular FT on an arbitrarilysized image. Do you really need to implement _the_ FFT, or is it enough to implement a FT that performs well?

[Edited by - lonesock on September 25, 2004 4:42:37 PM]

Share this post


Link to post
Share on other sites
http://www.fftw.org/ looks like it supports doing non power-of-two DFTs... it'll likely be slower than a power-of-two version, but it's not called the Fastest Fourier Transform in the West for nothing!

Share this post


Link to post
Share on other sites
There is several FFT algorithms out there. FFTW implements many of these and combines these to form near optimal transform for given size of transform. FFTW also comes with compiler of sort for creating codelets it uses to do the transforms. This compiler created the fastest transform for one N-point FFT (don't recall the exact size :) sorry). FFTW is the way to go!

Secondly, padding does not mess the FFT in anyway that would be harmful. By padding with zeros you get better frequency resolution (- resolution might not be the best word -), but the information content remains still the same. Only negative side is that you have to use larger transform that would be necessary.

2D-DFT:
F(k,l)=sum(N-1,n=0)sum(M-1,m=0)( I(n,m)*exp(-j*pi*(kn/N+lm/M)) )
It is obvious from this that if image I has components that are zero it does not alter the frequency information in anyway. That is, if you treat the image as one finite image and not as a infinite plane containing copies of the image. The calculation does not change but the interpretation. In the latter case padding would be bad.

Hope this helps.. probably only messes up your thoughts.. sorry about that :)

Share this post


Link to post
Share on other sites
Quote:

Do you really need to implement _the_ FFT, or is it enough to implement a FT that performs well?


To be perfectly honest, I have absolutely no clue what the Fourier transform even is. The most accurate description I can give you is "it takes a signal in the time domain and transforms it into the frequency domain" but I don't really even understand what that is telling me. So in answer to your question, I'm afraid I'm not even knowledgable enough to answer that. The only thing required is that it's relatively fast for 4096x4096 images.

Thanks also to Winograd and nohbdy for the info. In the end I think I will have to go with FFTW because of the arbitrary input size. Would it be all that hard to code a FFT algorithm myself? I have searched and reviewed dozens of sites about this, but they are all just a bit over my head when it comes to explanation. I'm thinking I'll just have to buy a differential equations textbook and flip to the chapter on the transforms.

Share this post


Link to post
Share on other sites
I'll try to give a better explanation of what the fourier transform is, though no promises :) Imagine your picture as a heightmap or sorts... each pixel in the image represents a height or amplitude (intensity of the light/color)... if you take a row of pixels, those heights will vary up and down. If you draw a smooth line to connect all the points, you'll end up with what looks like any other kind of signal/wave (radio, telephone, internet, TV... they're all just signals). You can also imagine a very simplified sine wave with a given amplitude, frequency, and phase but your image is going to be much more complicated than a simple sin wave. However, the signal of the image can be represented by a sum of a whole bunch of sin waves with different parameters.

The fourier transform essentially takes your signal and breaks it down into it's component parts in the frequency domain (this is a complex number). This is handy for a lot of things... for example, performing a blur on an image in the time domain requires you to build a filter kernel (say, a 3x3 grid with each value 1/9) and pixel-by-pixel use that kernel to perform the blur. If you transform the image into the frequency domain, convolution (the pixel-by-pixel use of the filter/convolution kernel) becomes simple multiplication/masking of the lower frequencies (AKA a low pass filter). For large filter kernels or large images, this can be a huge performance gain. That's just one example from the field of image processing... there's several other fields that use the fourier transform.

There's a fourier transform for continuous signals and one for discrete data like images called a DFT (main difference being the use of a Summation rather than actual integration). The FFT is just a special version of the DFT designed to be fast in hardware or software, and isn't technically limited to 2n sizes.

As for whether or not you should implement your own DFT... I would personally rather understand it and use a library like FFTW than implement it myself and not really know what it is, why it works, and what it's good for. (Not saying you can't do both, just a question of priorities and I know some people have a knack for implementing things without really understanding them)

Maybe if we had a better understanding of what you were doing other than finding the frequencies of count chocula (heh) we could help more ;) How'd you know to use a DFT in the first place?

-nohbdy

Share this post


Link to post
Share on other sites
First of all, a bump in rating for you. I really appreciate (and actually understand) a vast part of your explanation. To be honest, even the reason I need to implement this function is a bit complicated. The software I'm working on is designed to load and display micrograph images. Micrographs are nothing more than digital pictures of specimens inside an electron microscope. So, for example, you place some virus particles on a microscope slide, put the slide in the microscope, adjust the focus settings accordingly, and then use a digital camera built into the microscope to take a snapshot of what is currently on the slide. Then you can take these captured images and perform all kinds of scientific analyses on them (3D reconstruction, etc). However, due to the nature of this kind of work, there are a lot of built-in "impurities" in the resulting micrograph that can lead to incorrect 3D reconstruction. In other words, the microscope has a natural "noise" that will distort the images of the viruses as taken from the camera. (Ok, I'm pretty sure of everything I've said so far, but this next section may be slightly confusing/incorrect, so bear with me.) To compensate for this, the contrast transform function (CTF) of the microscope needs to be calculated. The way you do this is by taking the FTs of all the micrographs and combining them into a single averaged FT. Then, by performing further analysis on this averaged FT, the CTF of the microscope can be calculated and this value can be used to determined the purity of the sample, and can affect the way the virus is reconstucted in 3D.

Whew. If you can get all that, you're doing better than me!

Share this post


Link to post
Share on other sites
Taking averages of several FT's is equal to taking averages of the images and applying FT to the averaged image. This is because FT is a linear transfrom. That means that if F{} denotes FT then a*F{I1} + b*F(I2} = F{a*I1 + b*I2}, where I1/I2 is the image.

Share this post


Link to post
Share on other sites
Quote:
Original post by Winograd
...padding does not mess the FFT in anyway that would be harmful. By padding with zeros you get better frequency resolution...

I'm not the most knowledgable on this (although I should be given that I made a lot of use of Fourier Transforms during my degree - I've just forgotten most of it along with almost everything else) but wouldn't your best bet be to clamp the texture to pad it out? By setting the padding to a constant colour you'll add unwanted noise along the image borders due the irregular jump in values.

Share this post


Link to post
Share on other sites
Quote:
Original post by Winograd
if you treat the image as one finite image and not as a infinite plane containing copies of the image. The calculation does not change but the interpretation. In the latter case padding would be bad.


As I said if you treat the image as one finite image.. that is infinite plane containing zeros around the image.. you will always get the "noise" from the jump. In the case of infinite plane containing copies of the image you will suffer from the "noise" what Motorherp was talking about.

Finite image:
.
.
000000
. .00AB00. .
00CD00
000000
.
.

Infinite image:

.
.
CDCDCD
. .ABABAB. .
CDCDCD
ABABAB
.
.

When the DFT is size of one cycle MxN (in example 2x2) there will be no difference in the result.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!