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

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 3

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

Answer 4

This problem took me quite some time but if you have the right approach it is very simple.

Note this only works for a square matrix. A rectangle will require you to use the other algorithm (transpose and flip). If you want to do it in place, that may need you to temporarily resize the array.

Simplifying the problem

Consider the following matrix:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

Rotate 90 degrees, and look only at the corners (numbers 1, 4, 16 and 13). If you have problems visualizing it, help yourself with a post-it note.

Now, let's consider the following one:

1 - - 2
- - - -
- - - -
4 - - 3

Rotate it 90 degrees, and notice how the numbers get rotated in a circular manner: 2 becomes 1, 3 becomes 2, 4 becomes 3, 1 becomes 4.

Rotating corners

In order to rotate corners, it is necessary to define all corners in terms of the first corner:

• 1st corner would be (i, j)
• 2nd corner would be (SIZE - j, i)
• 3rd corner would be (SIZE - i, SIZE - j)
• 4th corner would be (j, SIZE - i)

Note that arrays are 0 based, therefore SIZE will need to be 0 based as well. (meaning, you will need to subtract 1).

Now that you understood the idea of rotating corners, we will expand the idea of "rotating corners" to "rotating quadrants". The same principle holds.

Code

You will need to make sure no number if overwritten. Meaning, you will need to rotate 4 numbers at a time simultaneously.

#include <algorithm>
#include <numeric>
#include <vector>

using std::iota;
using std::swap;
using std::vector;

// Rotates 4 numbers.
// e.g: 1, 2, 3, 4 becomes 4, 1, 2, 3
// int& means numbers are passed by reference, not copy.
void rotate4(int &a, int &b, int &c, int &d)
{
   swap(a, b);
   swap(b, c);
   swap(c, d);
}

void rotateMatrix(vector<vector<int>>& m) {
    int n = m.size();

    // NOTE: i and j from 0 to n/2 is a quadrant
    for (int i = 0; i < n/2; i++) {
    // NOTE : here + 1 is added to make it work when n is odd
    for (int j = 0; j < (n + 1)/2; j++) {
        int r_i = (n - 1) - i;
        int r_j = (n - 1) - j;

        rotate4(
             m   [i]   [j],
             m [r_j]   [i],
             m [r_i] [r_j],
             m   [j] [r_i]
        );
    }
    }
}

void fillMatrix(vector<vector<int>>& m) {
    int offset = 0;

    for (auto &i : m) {
        iota(i.begin(), i.end(), offset);
        offset += i.size();
    }
}

// Usage:
const int size = 8;
vector<vector<int>> matrix (size, vector<int>(size));
fillMatrix(matrix);
rotateMatrix(matrix);

Printing

To print the matrix you can use:

#include <algorithm>
#include <iostream>
#include <iterator>

using std::copy;
using std::cout;
using std::ostream;
using std::ostream_iterator;
using std::vector;

ostream& operator<<(ostream& os, vector<vector<int>>& m) {
    for (auto const &i : m) {
        copy(i.begin(), i.end(), ostream_iterator<int>(os, " "));
        os << "\n";
    }

    return os;
}

// Usage
cout << matrix;

Answer 5

the real answer: no, u can't without allocating some memory.

or you have to use recursion, which will fail with large images.

however there are methods that require less memory than the image itself

for example, you could take point A (x from 0 to width, y from 0 to height), calculate it's new location, B, copy B to it's new location (C) before replacing it with A, etc..

but, that method would require to keep track of what bytes have already been moved. (using a bitmap of one bit per pixel in the rotated image)

see the wikipedia article, it clearly demonstrates that this cannot be done for non square images: here is the link again: http://en.wikipedia.org/wiki/In-place_matrix_transposition

Answer 6

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 7

Here is a simple method in java,

    public static void rotateMatrix(int[][] a) {                                                                            
    int m =0;
    for(int i=0; i<a.length; ++i) {
        for(int j=m; j<a[0].length; ++j) {
            int tmp = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = tmp;
        }
        m++;
    }

    for(int i=0; i<a.length; ++i) {
        int end = a.length-1;
        for(int j=0; j<a[0].length; j++) {
            if(j>=end)
                break;
            int tmp = a[i][j];
            a[i][j] = a[i][end];
            a[i][end] = tmp;
            end--;
        }
    }
}

Answer 8

This is similar to rotation of 2D matrix. Here is my algorithm below which rotates 2D matrix by 90 degrees. It also works for M X N. Take the transpose of the given matrix and then swap 1st column with last, 2nd column with 2nd last column and so on. You can also do with rows instead of columns.

import java.io.*;
import java.util.*;

public class MatrixRotationTest
{
public static void main(String arg[])throws Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter the matrix rows:");
    int r = Integer.parseInt(br.readLine());
    System.out.println("Enter the matrix columns:");
    int c = Integer.parseInt(br.readLine());
    int[][] matrix = new int[r*c][r*c];
    for(int i=0;i<r;i++)
    {
        System.out.println("Enter row "+(i+1));
        for(int j=0;j<c;j++)
        {
            matrix[i][j] = Integer.parseInt(br.readLine());
        }
    }
    matrix = reverseMatrixColumns(transformMatrix(matrix),r,c);
    System.out.println("Rotated Matrix");
    for(int i=0;i<c;i++)
    {
        for(int j=0;j<r;j++)
        {
            System.out.print(matrix[i][j]+" ");
        }
        System.out.println();
    }
}

    //Transform the given matrix
public static int[][] transformMatrix(int[][] matrix)throws Exception
{
    for(int i=0;i<matrix.length;i++)
    {
        for(int j=i;j<matrix[0].length;j++)
        {
            int temp = matrix[i][j];
            matrix[i][j] = matrix [j][i];
            matrix[j][i] = temp;
        }
    }
}

    //Swap columns
public static int[][] reverseMatrixColumns(int[][] matrix,int r,int c)
{
    int i=0,j=r-1;
    while(i!=r/2)
    {
        for(int l=0;l<c;l++)
        {
            int temp = matrix[l][i];
            matrix[l][i] = matrix[l][j];
            matrix[l][j] = temp;
        }
        i++;
        j--;
    }
    return matrix;
}
}

Answer 9

Here is my attempt for matrix 90 deg rotation which is a 2 step solution in C.
First transpose the matrix in place and then swap the cols.

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {1, 2, 3, 4, 5}, 
                      {6, 7, 8, 9, 10},
                          {11, 12, 13, 14, 15},
                          {16, 17, 18, 19, 20},
                          {21, 22, 23, 24, 25}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}