Algorithm to rotate an image 90 degrees in place? (No extra memory)

Question

In an embedded C app, I have a large image that I'd like to rotate by 90 degrees. Currently I use the well-known simple algorithm to do this. However, this algorithm requires me to make another copy of the image. I'd like to avoid allocating memory for a copy, I'd rather rotate it in-place. Since the image isn't square, this is tricky. Does anyone know of a suitable algorithm?

Edited to add clarification, because people are asking:

I store an image in the usual format:

// 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];
}

I'm hoping to move the contents of the data array around, then swap over the width and height member variables. So if I start with a 9x20 pixel image, then rotate it, I'll end up with a 20x9 pixel image. This changes the stride of the image, which complicates the algorithm a lot.

Answer 1

This might help: In-place matrix transposition.

(You might also have to do some mirroring after the transposition, as rlbond mentions).

Answer 2

This might be too vague, and not be what you're looking for, but I'm gonna post anyway.

If you consider an image to be a 2d array of pixels, you only need to reverse the order of either the top-level or nested array, depending on whether you want horizontal or vertical flipping..

So you would either loop through each pixel column (0->columns/2), and swap them (so you only need temp memory for 1 pixel, not the whole picture), or loop through rows for horizontal flipping.. Does that make sense? Will elaborate / write code if not..

Answer 3

Since you specified "no extra allocation" and trying to put a rotated non-square image back into the same space seems like trying to put a square peg into a round hole (Edit: Unless you realize that images are usually stored in flat arrays, unlike me), how about something like this:

If you read the image from memory in "the wrong order", it's essentially the same as rotating it. This may or may not be suitable for whatever you're doing, but here goes:

image[y][x] /* assuming this is the original orientation */
image[x][original_width - y] /* rotated 90 degrees ccw */
image[original_height - x][y] /* 90 degrees cw */
image[original_height - y][original_width - x] /* 180 degrees */

Answer 4

Not sure what processing you will do after the rotation, but you can leave it alone and use another function to read rotated pixel from the original memory.

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

Where input parameter x and y has swapped dimension from original