Rotating a 2D pixel array by 90 degrees

Question

I have an array of pixel data for an image. The image I am getting is already rotated to 270 degrees. So I am trying to rotate it again by 90 degrees to have the correct image. I've tried a transpose algorithm, by changing data[x][y] to data[y][x], but I don't think that's the correct way. Can anyone guide me what can I do to have it rotated?

Kappel

That's the only way. You can parallelize process to make it more quickly. – Soapwort

Answer 1

This can be done without using any extra space, so called In-place matrix transposition (not exact the same). Remember to do some mirroring after the transposition.

1. If the image is square

2. If the image is not square

   • For non-square matrices, the algorithms are more complicated. Many of the algorithms prior to 1980 could be described as "follow-the-cycles" algorithms. That is, they loop over the cycles, moving the data from one location to the next in the cycle. In pseudocode form:

Buoyage

Answer 2

You have old_data[rows][cols] and new_data[cols][rows], then:

for(int i=0; i<cols; i++) {
    for(int j=0; j<rows; j++) {
        new_data[i][j] = old_data[rows-1-j][i];
    }
}

This should rotate old_data by 90 degrees CW.

Rory

Yeah. It will. I tried this with a small matrix. :) Just make sure if input image is of the order MxN, then output image is of the order NxM. – Rory

Thanks, I am trying this now. – Kappel

Answer 3

If you want to do it in-place with O(1) space, you can follow this:

1. Transpose the matrix by swapping data[i][j] and data[j][i] :

   for (int i = 0; i < n; i += 1) {
       for (int j = i+1; j < n; j += 1) {
           swap(data[i][j], data[j][i]);
       }
   }
   

2. Reverse each row or column for +90 or -90 degrees of rotation, respectively. For example for +90 degrees of rotation:

   for (int i = 0; i < n; i += 1) {
       for (int j = 0; j < n/2; j += 1) {
           swap(data[i][j], data[i][n-1-j]);
       }
   }
   

Pallium

Answer 4

To rotate the image (2D matrix) by 90deg, you can easily do this by mapping out a pattern between the initial state and the end state after rotating it by 90deg.

---

a[i][j] => a[m][n]
a[0][0] => a[0][2]
a[0][1] => a[1][2]
a[0][2] => a[2][2]
a[1][0] => a[0][1]
a[1][1] => a[1][1]
a[1][2] => a[2][1]
a[2][0] => a[0][0]
a[2][1] => a[1][0]
a[2][2] => a[2][0]

Now the solution is obvious. All the J's turn to M and N = (Size of matrix(2) - I).

---

const rotateImage = (a) => {
  let size = a.length;
  let results = new Array(size);
  for (let i = 0; i < size; i++) {
    results[i] = new Array(size);
  }
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      results[j][(size - 1) - i] = a[i][j];
    }
  }
  return results;
}

console.log(rotateImage([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]));

Troudeloup