## Ee

i Un

That is, the raw (fc-space) data can be simply phase-shifted by an amount corresponding to the location shift of the image and result subjected to an inverse Fourier transform to get the translated image. This computation can be performed with the FFT algorithm by simply regarding Eq. (1) as the DFT of the quantity in square brackets.

The implementation of a rotation is a little more subtle. If we let x = (x, y) and k = (kx, ky) and write

,F—1(i) = I(x) = Y^ I(k) exp{i2n(xTk)}, the image I rotated by an angle 6 given by the rotation matrix / cos 6 — sin 6

sin 6 cos 6

can be expressed as

^2i(k) exp{i2nxTR—1k}, which can be rewritten as (letting k* = R—1k)

A rotation of an image can be implemented by the rotation of the k-space data.

Being more explicit about the details, we have

n m (i2% ^^ i(kx, ky) exp I -((x cos 6 — y sin 6) mkx kx ky \nm + (x sin 6 + y cos 6) nky)

3.2 Implementation by Chirp-z

The calculation can be performed by a chirp-z transform [16]. Simply put, the chirp-z reexpresses the exponent in Eq. (2)

This is easily seen to be a convolution of the two functions in square brackets, multiplied by the constant exp{mxTRTx}. The convolution can be implemented with the FFT algorithm. The actual calculation would require an FFT of each quantity in square brackets, a multiplication of the two transforms, an inverse FFT of the product and a final multiplication by the constant in front of the summation. The result is a calculation that requires 0(nmlog nm) operations.

This method is considerably more efficient than the DFT given in Eq. (3), but when written out in detail it is seen to require that the image being rotated be square. See [17].

### 3.3 Implementation by Shearing

An alternative method for performing k-space or image rotations is to approximate the rotation by successive use of shearing transformations. According to [18], shearing was discovered independently by [10], [15], and [6].

A shear, parallel to the x-axis, is given by the shearing matrix product

Equation (3) can be implemented directly. Unfortunately, written in this way, the implied Fourier transform cannot be computed by the fast Fourier transform algorithm because of the cos and sin factors; the exponents no longer contain integral multiples of — and —. It can be computed as written (a discrete Fourier transform), but the calculations are prohibitively slow.

Precisely, we know that the number of computations required to compute Eq. (3) directly is 0(n2 x m2) (see, e.g., [2]) because it has to be computed for each value of kx and ky. There are at least two alternative computational approaches, which we discuss in the next two subsections.

The pixels in each row are translated by an amount proportional to the y-index of that row.

A shear, parallel to the y-axis, is given by the shearing matrix product

0 0