将图像旋转 90 度的算法？ （没有额外的内存）

在嵌入式 C 应用程序中，我有一个大图像，我想将其旋转 90 度。目前我使用众所周知的简单算法 http://www.cs.nott.ac.uk/~smx/IVIPracticals/exercise1.html去做这个。然而，这个算法要求我制作图像的另一个副本。我想避免为副本分配内存，我宁愿就地旋转它。由于图像不是正方形，这很棘手。有谁知道合适的算法？

编辑以添加澄清，因为人们在问：

我以通常的格式存储图像：

// Images are 16 bpp
struct Image {
    int width;
    int height;
    uint16_t * data;
};

uint16_t getPixel(Image *img, int x, int y)
{
    return img->data[y * img->width + x];
}

我希望能够移动内容data周围排列，然后交换width and height成员变量。因此，如果我从 9x20 像素图像开始，然后旋转它，我最终会得到 20x9 像素图像。这改变了图像的步幅，使算法变得更加复杂。

这可能有帮助：原地矩阵转置 http://en.wikipedia.org/wiki/In-place_matrix_transposition.

（正如 rlbond 提到的，你可能还需要在转置后进行一些镜像）。