I'm not sure how practical this might be but is it possible to use Fast Fourier Transform to rotate a raster image?
To be honest, I never really understood FFT, but I saw it being used for JPEG, for example. What I try to say is let's pretend I can grab some FFT library, what do I do next?
Also, I read that there is this Gibbs phenomenon which causes ringing artifacts. Would it be a problem here as well?
Fourier transforms wouldn't help you with a rotation. You'd just end up having to rotate the matrix of Fourier coefficients, instead of rotating the original image.
Consider for example an image made of a perfect sine wave along the x-axis with wave-vector $(k, 0)$. (The wave-vector is the spacial frequencies along the $x$ and $y$ axes). The Fourier transform of this would be all black, with a single white pixel at position $(k, 0)$.
When you rotate the image by an angle $\theta$, you'll get a perfect sine wave along an oblique axis. If you draw a diagram and do a little trigonometry, you can see that the new wave-vector will be $(k \cos \theta, k \sin \theta)$. (It helps for this part to know that the frequency $k$ is one over the period.)
Therefore, the Fourier transform of the rotated result would be all black, with a single white pixel at position $(k \cos \theta, k \sin \theta)$. But that's just what you'd get if you rotated the Fourier transform of the original wave by $\theta$.
As for the Gibbs phenomenon, it's an issue when downsampling an image, or compressing it by frequency quantization (as in JPEG). But simply taking the Fourier transform of an image doesn't introduce any Gibbs ringing. The Fourier transform is lossless and perfectly reversible if done properly: it represents all the information in the original image.
Yes, it is possible. Remember that a shift in space is equivalent to a linear-phase multiplication in frequency. A rotation can be accomplished by a shearing operation in one direction followed by a shearing operation in the perpendicular direction followed by a final shear in the original direction (Alan Paeth, ``A Fast Algorithm for General Raster Rotation,'' Proceedings of Graphics Interface 1986. Larkin et al. have shown how to take this concept and turn it into 1D FFTs multiplied by linear-phase terms, another set of perpendicular 1D FFTs followed by linear-phase multiplication, followed by a final set of 1D FFTs, etc., in the original direction ("Fast Fourier method for the accurate rotation of sampled images", Optic Communications, 1997).
Alternately, you can definitely rotate the Fourier matrix to accomplish rotation. But you have to keep in mind that the rotation must be around the origin in DFT space. Since the DFT is periodic, you have to circularly shift the array to the center, rotate around that, and then shift back. Even then it induces a rotation of the image around the origin (upper left corner), accounting for the fact that the image itself is now treated by the DFT as if it is periodic.
