## Resampling by Full Fourier Transform Methods

The preceding empirical demonstration suggests that image reconstruction by a full Fourier method is information conserving, depending on the implementation. Hence, in this section we will compare different approaches to implementation and then return to the issue of information conservation. Image translations can easily be performed in fc-space without interpolation; however, rotations may require interpolation, whether performed in fc-space or on images. Interpolation in fc-space, while well-studied [9,14], can introduce new errors [11,19], particularly for uniform-in-space sampling schemes.

When performing translations and rotations using Fourier methods, there are at least three possible ways it can be implemented:

(1) The discrete Fourier transform (DFT)

(2) The chirp-z transform (CZT)

(3) The fast Fourier transform (FFT)

There are important practical issues influencing the choice among these three. The DFT is least efficient computationally but requires no special thought. The FFT is more efficient when the data lie on a regular grid, particularly when the image dimensions are a power of two. However, rotation of the image off the original grid introduces a variable transformation that prevents direct use of the FFT. The CZT is equally efficient to the FFT but without special "tricks" can only operate on square (or cubic) arrays.

### 3.1 Implementation by Discrete Fourier Transform

In two dimensions the implementation of a translation can be easily handled by phase shifts in Fourier space. For an nxm image I (letting be the Fourier transform and be the inverse Fourier transform) we have

nm and

Consequently, the image translated by a vector S = (a, b) can be expressed as

" m fi2n \ = E E ^' ) exP — (m(x + a)fex + "(y + ) tt V"m J

0 0