## Info

and where c = cos 6, s = sin 6, t = — tan and d is the angle of rotation. So an image can be rotated using three successive shear transformations utilizing only one-dimensional FFTs.

The amount of computation required, if the shears are implemented as one dimensional FFTs, is 0(nm log n) for the shears parallel to the x-axis and 0(mnlog m) for the shears parallel to the y-axis. The entire computation thus requires 0(nm log nm) operations.

Figure 2 shows the images corresponding to the successive steps in a shear-based calculation of a rotation; the intermediate images would not normally be output in the actual use of the rotation but are simply provided to help the reader understand the method.

Because of the Fourier duality between image space and k-space, note that the the shift theorem can be implemented on k-space data instead of the image data. That is, the k-space data can be rotated by using the analogous formulas prior to actual reconstruction into an image.

The shearing approach can be extended directly to three dimensional images since a 3D rotation matrix, R3D, can be written as the product of three extended 2D rotation matrices:

0 0