| Re: Fourier Transform when intervals are not uniform [message #45855] |
Tue, 11 October 2005 01:48 |
Timm Weitkamp
Messages: 66
Registered: August 2002
|
Member |
|
|
Sid,
Your problem is the same encountered in X-ray computerized tomography.
The most common technique used to solve it is known as "filtered
backprojection" (FBP). In tomography, it is the Fourier-space data that
are sampled on a radial grid and need to be transformed back into real
space. The fundamental idea behind FBP is to perform the interpolation
from the radial grid to a Cartesian grid in real space rather than in
Fourier space. This avoids artifacts, albeit at the expense of more
computing time.
FBP works as follows: take your 2D radially-sampled data and
1) for each line of points that intersects the origin (i.e., each set
of points with equal theta or theta+pi),
a) apply a weight factor to each point that is essentially
the distance of the point from the origin. (This is done to
compensate for
the non-uniform sampling density, which is highest near the
origin.).
This is the "filtering" part.
b) Then, take the 1D Fourier transform of the line.
c) Then, smear the result out in two dimensions.
This is the "backprojection" part.
2) Finally, add up the smeared 2D images of all lines, obtained in step
1c, and you will get the 2D FT.
The problem is also known as an inverse Radon transform. IDL provides a
routine named RADON, which carries out steps 1c and 2 for you in a more
convenient and faster way than you would be able to do if you
programmed these steps in IDL yourself.
Also, be aware that the above is only a gross description of FBP.
Implementing the steps above will work, but there are details to know
and respect in order to avoid artifacts, which I don't go into. There
is a fabulous book on tomography that explains all of this in an
extremely practical way: "Principles of Computerized Tomographic
Imaging" by A. Kak and M. Slaney. You can download the whole book from
www.slaney.org/pct/. The part that deals with your problem is in
Chapter 3, pages 56-74.
Good luck
Timm
Timm Weitkamp
ESRF, Grenoble, France
Sid wrote:
> Hello
>
> I am trying to (2-d) fourier transform when the data is sampled at
> non-uniform values of x and y (it is uniform in r and theta). I don't
> know if I should try to :
>
> 1. Write my own brute-force FT algorithm (I wrote one, using
> int_tabulate, gives me "sidelobes" in the 1-d FT of a gaussian)
>
> 2. Try and look at the algorithm of FFT in IDL to see if I can just
> take the FFT in radial co-ordinates.
>
> I looked up the Cooley-Tukey algorithm in Numerical Recipes, but
> doesn't seem like IDL uses that, since it works for any number of
> points.
>
> Does anyone know what algorithm the IDL FFT uses / how to get around
> this?
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
