FFTW: Why is DC component at ends/corners

When I get the Fourier transform of a 1D vector, with FFTW, the peak
in the Fourier spectrum (or DC component) is at one end with the
adjacent frequency component at the other end.  E.g. here is a typical
Fourier spectrum.

100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60,
70 ,80, 90

It is not clear to me why it is not

0, 10, 20, 30, 40, 50, 60, 70 ,80, 90, 100, 90, 80, 70, 60, 50, 40,
30, 20, 10, 0.

With images, the low frequency components are in the corners instead
of the middle.

Is this how I should have the FT is input if I want to get an inverse
FT?  If so, exactly where should the DC component go in the input
matrix for a 2D FT, top-left, top-right, bottom-left, bottom-right?
What low frequency components should go in the other corners?
Presumably, if you zero pad, the zeros go in the middle.  I tried
taking a 2D FT with the DC component in the middle and rotating the
quadrants by 180 degrees.  The output look like I would have expected
except that every other element in the horizontal direction was zero.

Many thanks in advance,
Peter.

PeterOut wrote:
> When I get the Fourier transform of a 1D vector, with FFTW, the peak
> in the Fourier spectrum (or DC component) is at one end with the
> adjacent frequency component at the other end. [..]

> With images, the low frequency components are in the corners instead
> of the middle.

Take a look in the (imo poor) FFTW docs about the data format.
In images, the zero frequency usually is placed in the center,
but in FFTW's data format it's at index 0.
You may rotate the output array half a round to get what you want.

> If so, exactly where should the DC component go in the input
> matrix for a 2D FT, top-left, top-right, bottom-left, bottom-right?

Index 0 in both dimensions. Top-left.

> I tried
> taking a 2D FT with the DC component in the middle and rotating the
> quadrants by 180 degrees.  The output look like I would have expected
> except that every other element in the horizontal direction was zero.

Which transform exactly? Did you mix up real and complex data points?
Did you give correct transform sizes? For FFTW, the dimension with
sequential data in memory is the last dimension (Y in 2D).


Hendrik vdH

PeterOut wrote:
> When I get the Fourier transform of a 1D vector, with FFTW, the peak
> in the Fourier spectrum (or DC component) is at one end with the
> adjacent frequency component at the other end.

Things to bear in mind...

The DFT (and the FFT/FFTW algorithms that compute the DFT) is periodic 
in the frequency domain. For an N-pt DFT, the index values [0,N-1] 
correspond to the normalised frequency range [0,2pi). We normally like 
to think about the double sided spectrum [-pi,pi), but since the DFT is 
periodic, the range [-pi,0) is the same as [pi,2pi) -- which is the same 
as the indices [N/2,N-1].

The easiest thing to do is to just shift the samples around before 
plotting them if you want to see the DC component in the centre. For 
example, MATLAB has a function just for this purpose, called fftshift.

> Is this how I should have the FT is input if I want to get an inverse
> FT?

Shift the data so that the DC component is back at index 0 before doing 
the inverse DFT.

> If so, exactly where should the DC component go in the input
> matrix for a 2D FT, top-left, top-right, bottom-left, bottom-right?

For an MxN image, the DC component will appear at coordinate (0,0), but 
to centre it you want to shift the samples so that DC is at coordinate 
(M/2,N/2). This corresponds to the "top-left" of the bottom-right 
quadrant. (Assuming (0,0) is located in the top-left of the entire DFT 
array.)

That is, the 2D DFT quadrants

[A][B]
[C][D]

should be swapped to

[D][C]
[B][A]

> Presumably, if you zero pad, the zeros go in the middle.

Zero padding is less of a hassle if you do it after shifting. That way 
you just need to centre your DFT is a larger array of zeros, rather than 
trying to figure out where in the unshifted array they should go.

Cheers,
Mark.

On Feb 7, 1:51 pm, "PeterOut" <MajorSetb...@excite.com> wrote:
> When I get the Fourier transform of a 1D vector, with FFTW, the peak
> in the Fourier spectrum (or DC component) is at one end with the
> adjacent frequency component at the other end.  E.g. here is a typical
> Fourier spectrum.
>
> 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60,
> 70 ,80, 90
>
> It is not clear to me why it is not
>
> 0, 10, 20, 30, 40, 50, 60, 70 ,80, 90, 100, 90, 80, 70, 60, 50, 40,
> 30, 20, 10, 0.

I'm assuming you are using real-valued input. In that case, the
negative frequencies are not computed because they are equal to the
conjugates of the positives. Therefore the FFT only generates the
RIGHT SIDE of the transform centered on DC. So DC *is* at the center,
it's just that the left half of the transform has been removed.

Same for images...

Scott

On Feb 7, 4:51 pm, "PeterOut" <MajorSetb...@excite.com> wrote:
> When I get the Fourier transform of a 1D vector, with FFTW, the peakin the Fourierspectrum (or DC component) is at one end with the
> adjacent frequency component at the other end.  E.g. here is a typical
> Fourier spectrum.
>
> 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 10, 20, 30, 40, 50, 60,
> 70 ,80, 90
>
> It is not clear to me why it is not
>
> 0, 10, 20, 30, 40, 50, 60, 70 ,80, 90, 100, 90, 80, 70, 60, 50, 40,
> 30, 20, 10, 0.
>
> With images, the low frequency components are in the corners instead
> of the middle.
>
> Is this how I should have the FT is input if I want to get an inverse
> FT?  If so, exactly where should the DC component go in the input
> matrix for a 2D FT, top-left, top-right, bottom-left, bottom-right?
> What low frequency components should go in the other corners?
> Presumably, if you zero pad, the zeros go in the middle.  I tried
> taking a 2D FT with the DC component in the middle and rotating the
> quadrants by 180 degrees.  The output look like I would have expected
> except that every other element in the horizontal direction was zero.
>
> Many thanks in advance,
> Peter.

Many thanks to Hendrik and Mark for their very helpful replies.  They
solved the problem I was addressing.