🚀 go-pugleaf

In article <dak.717841519@kaa> dak@kaa.informatik.rwth-aachen.de (David Kastrup) writes:

> What's wrong with the left upper corner? Index (0,0) is where it belongs.

How about the following:

1.  When a 2-D Fourier transform happens in the real world, one
    normally find the zero frequency in the middle of the pattern.
    For example, look at Airy's disc in any decent optics textbook.

2.  When progrmming up a Fourier filter (e.g., a low-pass filter) it
    is much easier (and shorter, faster) to calculate the distance
    from the middle of the image than it is from all the corners.
    With the zero frequency at the upper left of an image, the
    distance from it increases along the rows/columns and then
    decreases; and evaluating the radial distance is not a one-liner
    (in Fortran or Pascal, at least).

3.  I'm not aware of any image processing package that chooses to
    calculate Fourier spectra with the origin anywhere else than at
    the centre (someone will now post the name of one that does; sigh).

> If you want to somehow have a "logical" order with 0 in the middle, remember
> that a frequency component of -1/N Hz is ABSOLUTELY indestinguishable
> from (N-1)/N Hz due to sampling aliasing. The transform is based on
> that fact (at least the fast algorithms), and why mangle up the indexing?

Shifting the origin of the spectra cannot introduce aliasing!  It is
present irrespective of where one chooses to put the origin.

The way in which most people shift the origin to the middle of an
image is by pre- and post-gridding (i.e., multiplying alternate
elements by -1).  This applies to both 1D and 2D transforms,
incidentally.  Hence, there is no need to fiddle with the indexing:
one can simply put a wrapper around an upper-left-origin 2D FFT.

> DISPLAY it shifted by whatever you want, but do not mangle the data
> structure, because that tends to COMPLICATE things instead of making
> them easier, especially since all the theorems of DFT are usually
> formulated for indexes 0..N-1.

It's equally easy to define the DFT in terms of a centred origin all
the theorems then follow, since the two representations are of course
equivalent.  However, for physicists and most flavours of engineer at
least, having a software FT produce results similar to the real world
is more important than mathematical purity.

--
 Dr Adrian F. Clark                                   JANET: alien@uk.ac.essex
 INTERNET: alien%uk.ac.essex@nsfnet-relay.ac.uk          FAX: (+44) 206-872900
 BITNET: alien%uk.ac.essex@ac.uk              PHONE: (+44) 206-872432 (direct)
 Dept ESE, University of Essex, Wivenhoe Park, Colchester, Essex, C04 3SQ, UK.