[Numpy-discussion] real_fft2d

[Warren Focke]

On Tue, 17 Feb 2004, Scott Rifkin wrote:

> I'd like to take the 2d fourier transform of an image, remove some of the
> lower frequency signal, take the inverse 2d fourier transform, and then
> reconstruct the image.  I'm trying to use the python imaging library to do
> the image part and FFT for the fourier transform part.
>
> When I take the real_fft2d of a matrix (integer valued in this
> case-UInt16), I get a new matrix of the same size with complex entries.

That's surprising.  Input of shape (n, m) to real_fft2d should produce
output of shape (n, m/2+1).  fft2d should produce output of the same shape
as the input.

> In this implementation of the fourier transform, how is this resulting
> matrix arranged?  There seem to be a few different conventions out there
> for what, say, entry [0,0] represents.  Which one does FFT use?

Entry [0,0] of the output contains the DC term.

If your input is 4x4, your output should be 4x3, with frequencies arrnged
thus:

[[[ 0,0], [ 0,1], [ 0,2],
  [ 1,0], [ 1,1], [ 1,2],
  [ 2,0], [ 2,1], [ 2,2],
  [-1,0], [-1,1], [-1,2]]]

so if you want to zero out frequencies 0 and 1, multiply  the transform by
a mask like:

[[0, 0, 1],
 [0, 0, 1],
 [1, 1, 1],
 [0, 0, 1]]

> If I want to remove signal from wavelengths longer than a certain interval
> (say anything over 200 pixels), do I need to process the result from
> real_fft2d more or can I do the removal directly on that matrix and then
> take the inverse directly?

That should work.

> Is there a good reference for the FFT package or the FFTPACK library out
> there?

The doc strings may be on the terse side, and you have to read them for
several functions to find the answers to all of the questions you ask
here, but they are in there.

Docs for FFTPACK are at http://www.netlib.org/fftpack/doc

Warren Focke