Algorithm to rotate the image 90 degrees? (No extra memory)

Question

In the embedded C application, I have a large image that I would like to rotate 90 degrees. I am currently using the well-known simple algorithm for this. However, this algorithm requires me to make another copy of the image. I would like to avoid allocating memory for the copy, I would rather put it in place. Since the image is not square, it is difficult. Does anyone know a suitable algorithm?

Edited to add clarification because people ask:

I save the 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 hope to move the contents of the data array, and then change the member variables width and height . Therefore, if I start with a 9x20 pixel image, and then rotate it, I get an image of 20x9 pixels. This changes the image pitch, which complicates the algorithm.

Answer 1

This may help: Transaction in place .

(You may need to do some mirroring after transposition, as rlbond mentions).

Answer 2

If you read an image from memory in the “wrong order”, it is essentially equivalent to rotating it. This may or may not be suitable for what you are 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 rotation, but you can leave it alone and use another function to read the rotated pixel from the original memory.

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

If the input parameter x and y has the swap size from the original

Answer 4

It may be too vague and not be what you are looking for, but I will post it anyway.

If you think the image is a 2-dimensional array of pixels, you only need to reverse the order of the upper or lower array, depending on whether you want horizontal or vertical switching.

Thus, you either scroll through each column of pixels (0-> columns / 2), or swap them (so that you only need temporary memory for 1 pixel, not the whole image) or a loop through rows for horizontal paging. Does this make sense? Will develop / write code if not ..

Answer 5

real answer: no, u cannot but allocate some memory.

or you should use recursion that fails with large images.

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

For example, you can take point A (x from 0 to width, y from 0 to height), calculate a new location, B, copy B to a new location (C) before replacing it with A, etc.

but for this method you will need to keep track of which bytes have already been moved. (using a bitmap of one bit per pixel in a rotating image)

see the wikipedia article, it 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

Here is an easy way 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 7

This problem took me quite a while, but if you have the right approach, it is very simple.

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

Simplification of the problem

Consider the following matrix:

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

Turn 90 degrees and look only at the corners (numbers 1, 4, 16 and 13). If you have problems with visualization, help yourself with the recording after that.

Now consider the following:

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

Turn it 90 degrees and pay attention to how the numbers rotate in a circular manner: 2 becomes 1, 3 becomes 2, 4 becomes 3, 1 becomes 4.

Rotating corners

To rotate the corners, you need to define all the angles in terms of the first corner:

• 1st angle will be (i, j)
• The second corner will be (SIZE - j, i)
• The third corner will be (SIZE - i, SIZE - j)
• The fourth corner will be (j, SIZE - i)

Note that arrays are based on 0, so SIZE should also be based on 0. (this means you will need to subtract 1).

Now that you understand the idea of ​​rotating angles, we will expand the idea of ​​"rotating angles" to "rotating quadrants." The same principle holds.

The code

You will need to make sure that the number is not overwritten. So you will need to rotate 4 numbers at the same time.

 #include <algorithm> #include <numeric> #include <vector> using std::iota; using std::swap; using std::vector; // Rotates 4 numbers. // eg: 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); 

Print

To print a matrix that 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 8

This is similar to rotating a 2D matrix. Here is my algorithm below which the 2D matrix rotates 90 degrees. It also works for MX N. Take the transpose of this matrix, and then replace the 1st column with the last, 2nd column with the second last column, and so on. You can also do 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 to rotate the matrix 90 degrees, which is a 2-step solution in C.
First transfer the matrix into place and then swap 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; }